Корреляционный код (Код с удвоением)

Элементы данного кода заменяются двумя символами, единица ‘1’ преобразуется в 10, а ноль ‘0’ в 01.

Вместо комбинации 1010011 передается 10 01 10 01 01 10 10. Ошибка обнаруживается в том случае, если в парных элементах будут одинаковые символы 00 или 11 (вместо 01 и 10).

Например, при k=5, n=10 и вероятности ошибки , . Но при этом избыточность будет составлять 50%.

Инверсный код

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

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

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

Покажем суммирование для принятых комбинаций без ошибок (1,3) и с ошибками (2,4).

Обнаруживающие способности данного кода достаточно велики. Данный код обнаруживает практически любые ошибки, кроме редких ошибок смещения, которые одновременно происходят как среди информационных символов, так и среди соответствующих контрольных. Например, при k=5, n=10 и . Коэффициент обнаружения будет составлять .

Расстоянием Хемминга d(x₁, x₂) (метрикой Хемминга) между двумя битовыми блоками одинаковой длины x₁ ={b₁, b₂, …b_n} и x₂ ={с₁, с₂, …с_n} называется количество отличающихся бит на соответствующих позициях блока. Расстояние между абсолютно одинаковыми битовыми блоками равно нулю. Изменение одного бита в любом блоке увеличивает это расстояние на 1.

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

Очевидно, что приемник не может сравнить полученный и отправленный блок. Если это возможно — значит приемнику известно точное значение отправленного блока. Если так — проблема искажений отсутствует.

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

Если передатчик использует ВСЕ возможные значения двоичного блока длиной m, то приемник не может обнаружить ошибку, ведь все значения блока допустимы. Однако закодированный двоичный блок длиной m может принимать 2^m различных значений, а исходный блок длиной n < m имеет 2ⁿ различных значений. Т.е. 2^m - 2ⁿ значений являются недопустимыми или лишними. Дополнительные m - n бит являются избыточной информацией.

Только получив недопустимое значение блока, приемник может обнаружить ошибку.

Избыточные биты желательно использовать так, чтобы обнаруживать и исправлять максимальное число ошибок. Здесь надо понимать — невозможно создать абсолютно помехозащищенный код. Всегда существует возможность такого искажения блока, что будет получено другое допустимое значение блока. Однако, желательно обеспечить максимальный эффект от «дополнительных» бит.

«Эффект» дополнительных бит проще всего определить как минимальное количество ошибок в блоке, которые код гарантированно может обнаружить и исправить. Чем больше это число – тем лучше используются дополнительные биты.

Эффективность блочного кода называется «корректирующей способностью кода ». Корректирующая способность блочного кода определяется минимальным расстоянием Хемминга d_min между двумя допустимыми значениями блока кода.

Корректирующая способность t = [(d_min - 1)/2] определяет минимальное количество ошибок t в блоке кода, которое можно обнаружить и исправить, здесь […] обозначает взятие целой части.

Идеальным случаем является d_min = d_mах, т.е. когда минимальное и максимальное расстояние между допустимыми значениями блоков равно. Тогда корректирующая способность максимальна, а избыточность данных минимальна. Такие коды называют «совершенными»

Очевидно, что при d = 1 все кодовые комбинации являются разрешенными.

Например, при n = 3 разрешенные комбинации образуют следующее множество: 000, 001, 010, 011, 100, 101, 110, 111.

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

Если d = 2, то ни одна из разрешенных кодовых комбинаций при одиночной ошибке не переходит в другую разрешенную комбинацию. Например, подмножество разрешенных кодовых комбинаций может быть образовано по принципу четности в них числа единиц, как это приведено ниже для n = 3:

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

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

Расстоянием Хемминга (или кодовым расстоянием) между словами A и B называется вес третьей кодовой комбинации, полученной при сложении исходных по модулю 2. Тогда расстояние Хемминга равно d(A,B)= A Å B. Заметим, что расстояние Хемминга равно числу несовпадающих позиций (разрядов) при сравнении их двоичной записи. Для произвольного кода X =(x ₀, x ₁,…, x_n-1)Í Bⁿ расстояние Хемминга равно

d(X)=min d(xi, xj)

Код позволяет обнаружить не более k ошибок тогда и только тогда, когда минимальное расстояние Хемминга между кодовыми словами превосходит k, т.е.когда d(b_i,b_j)³ k +1.

Код позволяет исправить не более k ошибок тогда, и только тогда, когда минимальное расстояние Хемминга между кодовыми словами превосходит 2 k, т.е.когда d(b_i,b_j)³ 2 k +1.

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

Механизм действия помех на кодовые слова из 0 и 1 математически описывается операцией "сумма по модулю 2". Обозначим наличие ошибки в данной позиции через "1", а ее отсутствие "0". Замена символа за счет помех ("0" на "1" или "1" на "0") определяется с помощью математического действия сумма по модулю два:

0 0=0 - передавали 0, ошибки нет, получили 0;

0 1=1 - передавали 0, ошибка есть, получили 1;

1 0=1 - передавали 1, ошибки нет, получили 1;

1 1=0 - передавали 1, ошибка есть, получили 0.

Пусть передавали двоичное слово 101001 - а получили 110001, т.е. ошибка произошла на втором и третьем разряде.

Если такая ошибка произойдет повторно, то восстановится исходное сообщение.

Действительно,

в первый раз: во второй раз:

передавали 101001 передавали 110001

ошибка 011000ошибка 011000

получили 110001 получили 101001

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