что такое избыточность кода

Кодирование информации и избыточность кода

Любое сообщение, может быть представлено в различной форме, то есть закодировано различными способами. Разные способы кодирования неравноценны по занимаемому ими количеству информации. Оптимальным кодом будет тот, при использовании которого среднее значение энтропии, приходящееся на один символ, равно энтропии источника информации.

Чем выше избыточность кода, тем больше вероятность безошибочной передачи информации, но тем больший объём требуется для её хранения и большая пропускная способность канала передачи. Естественные человеческие языки характеризуются очень высокой степенью избыточности, также велика избыточность генома высших организмов, хранящегося в молекулах ДНК.

Величина \(H /Q\) называется экономичностью кода. Для оптимального кода \(H /Q=1\) а избыточность отсутствует, то есть \(E = 0\).

Процесс уменьшения избыточности кодирования называется сжатием информации и применяется для понижения объёма памяти, требуемой для хранения информации. Для сжатия информации, хранящейся в памяти, используются– архиваторы и упаковщики.

Пример: определить энтропию информации, содержащейся в сообщении «ученье − свет, а не ученье – тьма» и избыточность кода. Каждый символ в сообщении кодируется 1 байтом (8 бит).
Решение: Подсчитаем количество символов в сообщении, для простоты игнорируя пробелы: N=26. Найдём частоту повторения каждого символа (вероятность в сообщении), составив следующую таблицу, приведенную на скрине слева.

Удельная энтропия (энтропия одного символа в сообщении) в битах на символ, равна \[\tilde H = 5 \cdot \frac<1><<13>><\log _2>13 + \frac<3><<13>><\log _2>\frac<<13>> <3>+ 2 \cdot \frac<3><<26>><\log _2>\frac<<26>> <3>+ 4 \cdot \frac<1><<26>><\log _2>26 \approx \] \[ \approx \frac<5><<13>> \cdot 3.7004 + \frac<3><<13>> \cdot 2.1155 + \frac<6><<26>> \cdot 3.1155 + \frac<4><<26>> \cdot 4.7004 \approx 3.3535\] Полная энтропия сообщения \(H = 3.3535 \cdot 26 = 87.19\) бит. Количество бит, необходимое для кодирования каждого символа одним байтом, составляет \(Q = 208\;\) бит.
Избыточность кода \(E=1-87.19/208=0.58=58%\).

Источник

Электронные средства сбора, обработки и отображения информации

Оглавление

Помехоустойчивое кодирование

Понятие корректирующего кода

Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Клодом Шенноном. Он сформулировал теорему для дискретного канала с шумом: при любой скорости передачи двоичных символов, меньшей, чем пропускная способность канала, существует такой код, при котором вероятность ошибочного декодирования будет сколь угодно мала.

Построение такого кода достигается ценой введения избыточности. То есть, применяя для передачи информации код, у которого используются не все возможные комбинации, а только некоторые из них, можно повысить помехоустойчивость приема. Такие коды называют избыточными или корректирующими. Корректирующие свойства избыточных кодов зависят от правил построения этих кодов и параметров кода (длительности символов, числа разрядов, избыточности и др.).

В настоящее время наибольшее внимание уделяется двоичным равномерным корректирующим кодам. Они обладают хорошими корректирующими свойствами и их реализация сравнительно проста.

Наиболее часто применяются блоковые коды. При использовании блоковых кодов цифровая информация передается в виде отдельных кодовых комбинаций (блоков) равной длины. Кодирование и декодирование каждого блока осуществляется независимо друг от друга, то есть каждой букве сообщения соответствует блок из п символов.

Блоковый код называется равномерным, если п (значность) остается одинаковой для всех букв сообщения.

Различают разделимые и неразделимые блоковые коды.

При кодировании разделимыми кодами кодовые операции состоят из двух разделяющихся частей: информационной и проверочной. Информационные и проверочные разряды во всех кодовых комбинациях разделимого кода занимают одни и те же позиции.

При кодировании неразделимыми кодами разделить символы выходной последовательности на информационные и проверочные невозможно.

Непрерывными называются такие коды, в которых введение избыточных символов в кодируемую последовательность информационных символов осуществляется непрерывно, без разделения ее на независимые блоки. Непрерывные коды также могут быть разделимыми и неразделимыми.

Общие принципы использования избыточности

Способность кода обнаруживать и исправлять ошибки обусловлена наличием избыточных символов. На ввод кодирующего устройства поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из п двоичных символов, причем n>k. Всего может быть различных входных последовательностей и различных выходных последовательностей. Из общего числа выходных последовательностей только последовательностей соответствуют входным. Будем называть их разрешенными кодовыми комбинациями. Остальные ( — ) возможных выходных последовательностей для передачи не используются. Их будем называть запрещенными кодовыми комбинациями.

— случаев безошибочной передачи;

— ·(-1) случаев перевода в другие разрешенные комбинации, что соответствует необнаруживаемым ошибкам;

— ·( — ) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены.

Часть обнаруживаемых ошибочных кодовых комбинаций от общего числа возможных случаев передачи соответствует:

К_обн .

Рассмотрим, например, обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (п=k+1). Общее число выходных последовательностей составит , то есть вдвое больше общего числа кодируемых входных последовательностей. За подмножество разрешенных кодовых комбинаций можно принять, например, подмножество комбинаций, содержащих четное число единиц (или нулей). При кодировании к каждой последовательности из k информационных символов добавляется один символ (0 или 1), такой, чтобы число единиц в кодовой комбинации было четным. Искажение любого четного числа символов переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Часть обнаруженных ошибок составляет:

К_обн .

Пример кодирующего устройства с проверкой на четность показан на рис.

Основные параметры корректирующих кодов

Основными параметрами, характеризующими корректирующие свойства кодов являются избыточность кода, кодовое расстояние, число обнаруживаемых или исправленных ошибок.

Рассмотрим суть этих параметров.

Избыточность корректирующего кода может быть абсолютной и относительной. Под абсолютной избыточностью понимают число вводимых дополнительных разрядов

Относительной избыточностью корректирующего кода называют величину

_отн

_отн.

Эта величина показывает, какую часть общего числа символов кодовой комбинации составляют информационные символы. Ее еще называют относительной скоростью передачи информации.

Если производительность источника равна Н символов в секунду, то скорость передачи после кодирования этой информации будет равна

поскольку в последовательности из п символов только k информационных.

Если число ошибок, которое нужно обнаружить или исправить, значительно, необходимо иметь код с большим числом проверочных символов. Скорость передачи информации при этом будет уменьшена, так как появляется временная задержка информации. Она тем больше, чем сложнее кодирование.

Кодовое расстояние характеризует cтепень различия любых двух кодовых комбинаций. Оно выражается числом символов, которыми комбинации отличаются одна от другой.

Чтобы получить кодовое расстояние между двумя комбинациями двоичного кода, достаточно подсчитать число единиц в сумме этих комбинаций по модулю 2.

Кодовое расстояние может быть различным. Так, в первичном натуральном безызбыточном коде это расстояние для различных комбинаций может различаться от единицы до п, равной значности кода.

Число обнаруживаемых ошибок определяется минимальным расстоянием между кодовыми комбинациями. Это расстояние называется хэмминговым.

В безызбыточном коде все комбинации являются разрешенными, =1. Достаточно только исказиться одному символу, и будет ошибка в сообщении.

Теорема. Чтобы код обладал свойствами обнаруживать одиночные ошибки, необходимо ввести избыточность, которая обеспечивала бы минимальное расстояние между любыми двумя разрешенными комбинациями не менее двух.

Доказательство. Возьмем значность кода п=3. Возможные комбинации натурального кода образуют следующее множество: 000, 001, 010, 011, 100, 101, 110, 111. Любая одиночная ошибка трансформирует данную комбинацию в другую разрешенную комбинацию. Ошибки здесь не обнаруживаются и не исправляются, так как =1. Если =2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию.

Пусть подмножество разрешенных комбинаций образовано по принципу четности числа единиц. Тогда подмножества разрешенных и запрещенных комбинаций будут такие:

Очевидно, что искажение помехой одного разряда (одиночная ошибка) приводит к переходу комбинации в подмножество запрещенных комбинаций. То есть этот код обнаруживает все одиночные ошибки.

В общем случае при необходимости обнаруживать ошибки кратности — минимальное хэммингово расстояние должно быть, по крайней мере, на единицу больше , то есть

+1.

В этом случае никакая ошибка кратности не в состоянии перевести одну разрешенную комбинацию в другую.

Ошибки можно не только обнаруживать, но и исправлять.

Теорема. Для исправления одиночной ошибки каждой разрешенной кодовой комбинации необходимо сопоставить подмножество запрещенных кодовых комбинаций. Чтобы эти подмножества не пересекались, хэммингово расстояние должно быть не менее трех.

Доказательство. Пусть, как и в предыдущем примере, п=3. Примем разрешенные комбинации 000 и 111 (кодовое расстояние между ними равно 3). Разрешенной комбинации 000 поставим в соответствие подмножество запрещенных комбинаций 001, 010, 100. Эти запрещенные комбинации образуются в результате возникновения единичной ошибки в комбинации 000.

Аналогично разрешенной комбинации 111 необходимо поставить в соответствие подмножество запрещенных комбинаций 110, 011, 101. Если сопоставить эти подмножества запрещенных комбинаций, то очевидно, что они не пересекаются:

В общем случае исправляемые ошибки кратности связаны с кодовым расстоянием соотношением

=2+1. (2.1)

где — сочетание из п элементов по t (число возможных ошибок кратности t на длине п-разрядной комбинации).

Если, например, п=7, =1, то из (2.1)

Нужно отметить, что каждый конкретный корректирующий код не гарантирует исправления любой комбинации ошибок. Коды предназначены для исправления комбинаций ошибок, наиболее вероятных для заданного канала связи.

Групповой код с проверкой на четность

Недостатком кода с четным числом единиц является необнаружение четных групповых ошибок. Этого недостатка лишены коды с проверкой на четность, где комбинации разбиваются на части, из них формируется матрица, состоящая из некоторого числа строк и столбцов:

Строки образуются последовательно по мере поступления символов исходного кода. Затем после формирования т строк матрицы производится проверка на четность ее столбцов и образуются контрольные символы . Контрольные символы образуются путем суммирования по модулю 2 информационных символов, расположенных в столбце:

.

При таком кодировании четные групповые ошибки обнаруживаются. Не обнаруживаются лишь такие ошибки, при которых искажено четное число символов в столбце.

Можно повысить обнаруживающую способность кода путем одновременной проверки на четность по столбцам и строкам или столбцам и диагоналям (поперечная и диагональная проверка).

Если проверка проводится по строкам и столбцам, то код называется матричным.

Проверочные символы располагаются следующим образом:

;

.

В этом случае не обнаруживаются только ошибки четной кратности с кратностью 4, 8, 16 и т.д., при которых происходит искажение символов с попарно одинаковыми индексами строк столбцов. Наименьшая избыточность кода получается в том случае, когда образуемая матрица является квадратной.

Недостатком такого кода является необходимость внесения задержки в передачу информации на время, необходимое для формирования матрицы.

Матричный код позволяет исправлять одиночные ошибки. Ошибочный элемент находится на пересечении строки и столбца, в которых имеется нарушение четности.

Коды с постоянным весом

Весом называется число единиц, содержащихся в кодовых комбинациях.

В коде «3 из 7» возможных комбинаций сто двадцать восемь (=128), а разрешенных кода только тридцать пять. Относительная избыточность _отн = 0,28.

Схема устройства определения веса комбинаций кода «3 из 7» приведена на рис. 2.6.

Циклические коды

Циклические коды характеризуются тем, что при циклической перестановке всех символов кодовой комбинации данного кода образуется другая кодовая комбинация этого же кода.

— комбинация циклического кода;

— также комбинация циклического кода.

Например, комбинация 1001111 (п=7) будет представлена многочленом

При таком представлении действия над кодовыми комбинациями сводятся к действиям над многочленами. Эти действия производятся в соответствии с обычной алгебры, за исключением того, что приведение подобных членов осуществляется по модулю 2.

Обнаружение ошибок при помощи циклического кода обеспечивается тем, что в качестве разрешенных комбинаций выбираются такие, которые делятся без остатка на некоторый заранее выбранный полином G(x). Если принятая комбинация содержит искаженные символы, то деление на полином G(x) осуществляется с остатком. При этом формируется сигнал, свидетельствующий об ошибке. Полином G(x) называется образующим.

Построение комбинаций циклического кода возможно путем умножения исходной комбинации А(х) на образующий полином G(x) с приведением подобных членов по модулю 2:

Таким образом, все полиномы, отображающие комбинации циклического кода, будут иметь степень ниже п.

Часто в качестве полинома, на который осуществляется деление, берется полином G(x)=+1. При таком формировании кодовых комбинаций позиции информационных и контрольных символов заранее определить нельзя.

Большим преимуществом циклических кодов является простота построения кодирующих и декодирующих устройств, которые по своей структуре представляют регистры сдвига с обратными связями.

Число разрядов регистра выбирается равным степени образующего полинома.

Обратная связь осуществляется с выхода регистра на некоторые разряды через сумматоры, число которых выбирается на единицу меньше количества ненулевых членов образующего полинома. Сумматоры устанавливаются на входах тех разрядов регистра, которым соответствуют ненулевые члены образующего полинома.

На рис. 2.7 приведена схема кодирующего регистра для преобразования четырехразрядной комбинации в семиразрядную.

В табл. 2.3 показано, как путем сдвигов исходной комбинации 0101 получается комбинация циклического кода 1010011. п=7, k=4. Комбинация 0101, ключ в положении 1. В течение первых четырех тактов регистр будет заполнен, затем ключ переводится в положение 2. Обратная связь замыкается. Под действием семи сдвигающих тактов проходит формирование семиразрядного циклического кода.

Свойства циклического кода:

1) циклический код обнаруживает все одиночные ошибки, если образующий полином содержит более одного члена. Если G(x)=x+1, то код обнаруживает одиночные ошибки и все нечетные;

2) циклический код с G(x)=(x+1)G(x) обнаруживает все одиночные, двойные и тройные ошибки;

Источник

Что такое избыточность кода

3. Избыточность

Максимальная энтропия алфавита достигается при равенстве вероятностей всех символов, что представляет собой наиболее экономичный оптимальный код, который, однако, при реальной передаче трудно использовать. Так называемая относительная энтропия задана формулой

Поскольку энтропия является одновременно и количеством информации, то можно выразить избыточность сообщения и следующим способом:

Если уж приводить для иллюстрации какой-то популярный пример избыточности сообщения, то лучше всего указать на разговорный и письменный язык. Избыточность в языке состоит в растянутости и повторимости, обеспечивающих помехоустойчивость речи, возможность легкого понимания друг друга. Так, например, при разговоре в шумном зале или при обсуждении сложного вопроса речь требует большей избыточности. При малой избыточности, наоборот, концентрированность информации велика, велика и экономичность речи, то есть каждая фраза такой речи содержит что-то новое, что-то неожиданное, большую степень информации; однако при этом даже небольшая помеха приводит к большой потере информации. Простейшим видом избыточности является повторение. Более сложным видом ее является, например, применение так называемых контрольных кодов в передаче сообщений, о которых мы уже упоминали выше. Препятствием для концентрации информации как раз и является повышенный результат действия помех при пониженной избыточности. Кроме того, проблема избыточности сообщения связана также с проблемой времени. Степень отличительности в передаваемом сообщении зависит от времени. Можно понизить помехи и повысить отличительность при передаче сообщения тем, что мы растянем передачу на больший интервал времени, так что, собственно говоря, понизится пропускная способность передающего канала. Речь может идти о замедлении передачи или об использовании повторений, но и то и другое связано с избыточностью. Оба эти процесса облегчают понимание сообщения, прием его адресатом, что известно из процесса обучения; учебный материал лучше усваивается тогда, когда изложение ведется либо достаточно медленно, либо если трудные места изучаемого повторяются в различном виде.

Избыточность сообщения можно сводить к нулю при пользовании оптимальным кодом. При неравномерном распределении вероятностей символов и при наличии их внутренней вероятностной связи (корреляции) уменьшается относительная энтропия и возрастает избыточность сообщения. При создании текста мы делаем меньше выборов, чем число букв в тексте, так как мы действуем в рамках грамматических правил образования слов и предложений. Только примерно от 1 /₄ и до 1 /₃ числа букв мы можем выбирать произвольно: мы можем выбрать данные буквы или не выбрать их. Следовательно, при оптимальном коде мы могли бы выражаться втрое или вчетверо короче. Любая комбинация букв здесь создавала бы слово, полное смысла, так как все буквы и комбинации их встречались бы одинаково часто и каждая таблица букв могла бы годиться для кроссворда. Однако при обычном общении людей избыточность всегда имеет место, она имеется в каждом разговоре, в газетном языке и в научной литературе. Каждый национальный язык имеет значительную степень избыточности. Как уже было сказано, избыточность имеет не только отрицательные, но и положительные, полезные стороны. Она обеспечивает возможность понять друг друга, возможность исправить ошибки, получившиеся при передаче, тогда как при нулевой избыточности ошибки при передаче сильно искажали бы конечное сообщение.

Избыточность можно снизить путем перекодирования, путем изменения статистической структуры сигнала. Так, например, Нейдхардт 1 указывает, что в телевидении можно снизить избыточность путем уменьшения скорости развертывания передаваемого образа в тех местах, где сконцентрировано наибольшее информационное содержание, и путем ускорения развертывания в тех частях, где имеются свободные места и где можно эти промежутки интегрировать во времени. Если переходные вероятности между элементами одинаковы, нет взаимозависимости символов, то корреляция между ними нулевая. Если же, наоборот, они различны, то это дает экономию передачи и уменьшает избыточность. При передаче информацию несет только часть сигналов, остальные сигналы избыточны; в полезной части сообщения одна и та же информация может содержаться несколько раз, что дает возможность дальнейшего сжатия сообщения. Нейдхардт различает холостую (бесполезную) и полезную избыточность. Из неизбыточного сообщения нельзя изъять ни один знак, не изменяя этим его смысл. Если мы хотим установить избыточность сообщения, то мы убираем из этого сообщения знаки до тех пор, пока это не лишает сообщение понятности, то есть пока оно не теряет своего смысла. В противоположность холостой избыточности полезная избыточность обеспечивает или же и повышает верность передачи сообщения, и, наоборот, появление холостой избыточности не повышает ясности сообщения.

1 ( См. Р. Neidehardt, Einf?hrung in die Informationstheorie, Berlin, 1958.)

1 ( W. Meyer-Eppler, Informationstheorie, «Naturwiss.», № 15, 1952, S. 341.)

В этом тексте можно заменить чаще всего встречающиеся в немецком языке пары букв, то есть диграммы, отдельными реже встречающимися в этом языке буквами, а вместо этих букв текста ввести необычные пары букв. Так, например, пары

можно заменить буквами

а вместо буквы V будем писать НС, так что путем такого перекодирования мы получим новый текст, состоящий уже только из 18 букв.

Другой пример с более высокой и более низкой избыточностью в коде приводит Черри 1 :

1 ( C. Cherry, On Human Communication, New York, 1957, p. 186.)

Если бы мы закодировали буквы А, В, С и D только с помощью двух бинарных знаков, например, как

то этот код получился бы очень экономичным, имеющим малую степень избыточности. Однако в этом случае даже небольшая помеха привела бы к тому, что сообщение стало бы слишком неразборчивым. Если же мы закодируем эти буквы с помощью четырех бинарных знаков, например, так

то код станет более избыточным, но он будет иметь большую помехоустойчивость. Если, например, помеха коснется одного знака (он исказится), то эту помеху можно обнаружить (но, конечно, не сразу же исправить ее). Так, например, при одной помехе код для A может измениться в 1110, 1101, 1011 (вместо 1111) или же 0111, то есть во всех этих случаях код А нельзя будет спутать с группой кодовых символов для В, С или D, как это может иметь место в случае двухзначного кода при одной помехе (когда получится 0 вместо 1 или 1 вместо 0). Конечно, например, группа 1110 может при одной ошибке получиться при искажении не только кода буквы A, но и кодовых букв В, С или D. Еще большая помехоустойчивость может быть получена при еще большем усложнении кода, при придании ему еще большей избыточности.

Эти пять вопросов можно составить следующим образом:

2. Червовая ли это карта (или бубновая)?

3. Фигура ли это? (При ответе «нет» это значит, что карта цифровая.)

4. Это карта из высшей половины (фигур или цифровых карт)?

5. Это четная карта из данной половины?

После пяти ответов на эти вопросы мы получим ответ, какая именно карта вытянута.

1 ( H. Zemanek, Ungewohnte Zahlen aus der Informations-theory, «Radiotechnik», № 6, 1954, S. 188.)

Рост человеческого познания и накопление информации памятью также делается возможным именно благодаря бессознательному использованию избыточности. Наша память производит сжатие информационного содержания зафиксированных ею сообщений, и она снижает их избыточность, сохраняя только самое существенное из сообщений. (К этому вопросу мы еще возвратимся в конце настоящей книги.) По-видимому, следует считать память системой обусловленных вероятностей. Чем теснее связь запомнившихся содержаний, тем больше упорядоченность в памяти и тем меньше ее избыточность.

В настоящее время, например, проблемой, имеющей значение для дальнейшего непрерывного развития научного познания, становится чрезмерное возрастание числа научных книг, что связано с большой степенью избыточности в научных книгах, то есть с тем, что в различных книгах идеи повторяются и читатель теряет много времени, так как он вынужден читать в изучаемых книгах такое, что он и без того знает и что не дает ему новой информации. Причем потеря времени на чтение уже знакомого текста непропорциональна выигрышу от закрепления в памяти информации, полученной уже ранее. Поэтому было бы желательно провести какую-то унификацию, централизацию, концентрацию и контроль книжного фонда, чтобы можно было обеспечить лучший учет, обзор научной литературы и снизить избыточность. Как остроумно указывает польский писатель Станислав Лем в своей книге «Магелланово облако», при нынешнем росте книжной продукции дело может дойти до того, что через какое-то время каждому второму человеку в мире придется стать библиотекарем и земной шар превратится в гигантскую библиотеку. Поэтому необходимо найти способы улучшения хранения и переработки научной информации путем внедрения в библиотечное дело электронных вычислительных машин. Введение информации в эти машины было бы значительно более экономичным, чем в книги, и это дало бы значительное снижение избыточности в научных книгах. С помощью этих машин можно было бы также экономично обрабатывать информацию таким образом, что будет выявляться гомоморфизм в научных сообщениях, а это приведет к снижению избыточности, ибо приведет к исключению того, что во многих научных работах является одинаковым и повторяющимся. Одновременно это объединяло бы то подобное, что имеется в работах различных дисциплин.

На первый взгляд существует некоторая ограниченность в повышении информации и в снижении избыточности в нашем познании. Нулевая избыточность могла бы быть достигнута тогда, когда эффективное содержание сообщения было таким же, как содержание, которое может быть нами получено при оптимальном использовании канала, что возможно было бы, например, при полном отсутствии помех. Помехи в передаче сообщений можно уменьшить применением избыточности, путем использования более длительного времени для передачи наряду с некоторыми другими способами борьбы с помехами. Между скоростью передачи и помехами должна, следовательно, существовать определенная зависимость. Нельзя, например, полностью устранить разрыв во времени между входом и выходом при передаче сообщения. Самый быстрый процесс передачи информации может ведь происходить только со скоростью света (если иметь в виду только физическую скорость передачи сообщения; в теории информации скорость передачи сообщения измеряется числом переданных двоичных единиц информации в секунду).

Однако развитие познания является доказательством того, что нет никакого абсолютного предела нашего познания, имеются только пределы относительные, исторические. Человек приобретает все более совершенные знания об объективной реальности, и его информация возрастает, а избыточность в его мышлении и познании убывает. Производится конденсация информации, причем это не связано с повышением помех и аварийности, а обеспечивается способностью к обучению и памятью. По мере развития общества, от поколения к поколению человек все лучше осваивает более экономичные коды для передачи сообщений, фиксации и хранения их в мозгу.

Источник