Примеры кодов с исправлением одиночных ошибок различных типов.

1. Код с исправлением одного замещения.

Зафиксируем число n и найдем число l такое ,что .

Легко видеть , что . Для произвольного слова положим .

H(X) представляет собой вектор длины l, полученный в результате сложения векторов (mod2), являющихся двоичными записями (c помощью l цифр) номеров единичных символов слова Х.

Рассмотрим код , состоящий из всех слов таких, что

H(X)=( 0,0,…,0 ).

Пример. Пусть n = 6, Х = 010101, Y = 110100.

Тогда l = 3, Н(Х) = (0,1,0) (1,0,0) (1,1,0) = (0,0,0) и

H (Y) = (0,0,1) (0,1,0) (1,0,0) = (1,1,1). Следовательно, .

Покажем, что является кодом с исправлением одного замещения.

Рассмотрим однозначное отображение ( декодирование ), при котором каждому слову ставится в соответствие слово Y , если , или слово, полученное из Y замещением символа с номером N(H(Y)) на противоположный, если .

Убедимся, что при таком декодировании в каждом кодовом слове будет исправлена любая одиночная ошибка типа замещения, если она произойдет. Действительно, пусть в некотором слове произошло замещение j – го символа , в результате чего получилось слово Y.

Так как и ,

то .

Производя в слове Y замещение символа с номером N(H(Y))= , получим исходное слово Х .

Пример. Пусть в слове Х = 010101 произошло замещение пятого символа , в результате чего получилось слово Y = 010111.

Так как , то числовое значение слова H(Y) равняется 5 и определяет номер замещенного символа.

Описанные выше коды были предложены Хеммингом .

Заметим , что . Это следует из того , что при произвольном задании значений n – l компонент, номера которых отличны от (информационные позиции), значения компонент с номерами (проверочные позиции) однозначно определяются из условия H(X)=( 0,0,…,0 ).

В частности , . Код представим следующей таблицей (*).

000000 111000 110011 001011 101101 010101 011110 100110	000000 100001 010010 001100 110100 001011 110011 101101 011110 111111	000000 100011 010101 001110 111001 110110	000000 001101 011010 101111 110100

2. Код с исправлением одной ошибки типа .

Для произвольного двоичного слова положим .

Очевидно , что число w(X) равно сумме номеров единичных символов слова х.

При любых n и k определим код как множество слов таких, что W(X)=0(mod k) , и положим .

Пример. Пусть n = 6, Х = 110100 и Y = 010101.Тогда W(X) = 1+2+4 = 7, W(Y) = =2+4+6=12 и , следовательно, .

Покажем , что каждый код при является кодом с исправлением ошибки типа 0 .

Предположим , что в слове Х произошло не более одной ошибки типа

0 , в результате чего получилось слово Y . Ясно, что , если ошибки не произошло , и , если ошибка произошло в ом символе. Так как , то при W(Y)(mod k)=0 , если ошибки не произошло, или номеру замещенного символа в противном случае . Это позволяет построить декодирование , при котором в каждом слове кода ( при будет исправлена одиночная ошибка типа 0 , если она произойдет .

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

Пусть . Выберем в качестве проверочных позиций компоненты с номерами 1,2,…, и убедимся в том, что при любом заполнении остальных (информационных) позиций существует (вообще говоря , уже не однозначное ) заполнение проверочных позиций, при котором выполняется условие H(X)=( 0,0,…,0 ) для

Действительно, пусть информационные позиции вносят в сумму некоторую величину , наименьший положительный вычет которой по mod(n+1) равен i ( . Очевидно, что проверочные позиции всегда можно заполнить так, чтобы они вносили в эту сумму величину n+1-i , что обеспечивает выполнение условия W(X)=0(mod k). Другое заполнение проверочных позиций , при котором также получается кодовое слово , возможно лишь тогда , когда 2(n+1)-i , так как . Отюда следует , что полученное множество содержит не менее половины слов кода , а в случае совпадает с .

3. Код с исправлением одного выпадения или вставки.

Покажем , что каждый код при является также кодом с исправлением одного выпадения (и , следовательно , кодом с исправлением одного исправления или вставки ) .

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

Пусть обозначает число единиц (соответственно нулей), расположенных правее выпавшего символа, и . Тогда, если выпал символ 0,то ,а если символ 1,то . Поэтому , обозначая наименьший неотрицательный вычет числа - W(Y) по mod k через и замечая , что , имеем Поскольку , то на основании сравнения чисел и можно определить , какой из символов (0 или 1 ) выпал.

Таким образом, для восстановления слова Х по слову Y достаточно в случае вставить в слово Y символ 0 так , чтобы правее него было единиц , а в случае вставить в слово Y символ 1 так , чтобы правее него было нулей .

Пример. Пусть в слове Х = 110100 выпал первый символ, в результате чего получилось слово Y = 10100. Находим , что и , следовательно, . В силу условия отсчитаем справа нулевых символов и вставляем перед ними символ 1, получим исходное слово Х.

4. Код с исправлением одного выпадения , вставки или замещения .

Покажем , что каждый код при является кодом с исправлением одного выпадения, вставки или замещения .

Убедимся в том , что этот код является кодом с исправлением одного замещения. Пусть в j- ом символе некоторого слова Х произошло замещение, в результате чего получилось слово У . Ясно , что , где знак + соответствует замещению типа 0 , а знак - соответствует замещению типа 1 . Обозначим через наименьший по абсолютной величине вычет числа по mod k ( в случае , когда таких вычетов два , для определенности через обозначим положительный вычет ). Из соотношений (mod k ) , и следует, что , что обеспечивает возможность исправления в каждом слове кода (при любого замещения , если оно произойдет .

Пример. Отметим, что Х = 010101 , так как W(X)= 2+4+6=12 и W(X) (mod 12).

Предположим , что в четвертом символе слова Х произошло замещение, в результате чего получилось слово Y = 010001. Так как W(Y) = 2 + 6 = 8 и W(Y) = 8 = -4 (mod 12) , то , что указывает на номер замещенного символа. Код приведен в таблице (*).

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

Пусть . В качестве проверочных позиций выберем компоненты с номерами 1,2,…, и n. Ясно , что в виде суммы некоторых из этих чисел можно представить любое число от 0 до 2n-1. Поэтому точно так же , как это было сделано выше , можно показать , что при произвольном заполнении остальных (информационных) позиций и таком последующем заполнении проверочных позиций , при котором выполняется условие (mod k), для k=2n , получается множество, содержащее не менее половины слов кода и совпадающие с при .