Коды Хэмминга

Коды с обнаружением и исправлением ошибок

Лекция № 6

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

Корректирующие коды делятся на систематические и несистематические.

Систематически или линейным, кодом называется код, имеющий постоянную длину и четкое деление всех кодовых элементов на информационные k и контрольные m элементы, занимающие определенные места в комбинациях.

Составление корректирующих кодов производится примерно по следующему правилу. Сначала определяется количество контрольных символов m, которое следует добавить к данной кодовой комбинации, состоящей из k информационных символов. Далее устанавливается место, где эти контрольные символы должны быть расставлены в комбинации, и их состав, то есть является ли данный контрольный символ 1 или 0. На приеме обычно применяется проверка на четность определенной части разрядов.

Эти коды позволяют обнаруживать и исправлять все одиночные ошибки (при d =3), а также исправлять все одиночные ошибки и обнаруживать все двойные ошибки (при d =4), но не исправлять их.

Рассмотрим Код Хэмминга, исправляющий все одиночные ошибки.

В качестве исходного кода берется двоичный код на все сочетания с числом информационных символов k, к которому добавляется m контрольных символов. Таким образом, общая длина закодированной комбинации n=k+m.

Рассмотрим последовательность кодирования и декодирования по методу Хэмминга.

Кодирование. Определение числа контрольных символов. Для этого можно воспользоваться следующими рассуждениями. При передаче по каналу с шумами может быть или искажен любой из n символов кода, или слово может быть передано без искажений. Таким образом, может быть n +1 вариантов искажения (включая передачу без искажений).Используя контрольные символы, мы должны различать все n +1 случаев.

С помощью m контрольных символов можно описать 2^m событий. Значит, должно быть выполнено условие

2^m ≥ n +1= k+m +1 (3-11)

Информ. k	1 2 3 4 5 6 7 8 9 10 11 12 13 26
Контр. m	2 3 3 3 4 4 4 4 4 4 4 5 5 5

Задаем m, определим k: 2^m ≥ k+m +1

2² ≥ k +2+1, k =1

2^m ≥ k +3+1, k =2, 3, 4

Размещение контрольных символов. В принципе месторождение этих символов значения не имеет: их можно приписывать и перед информационными словами, и после них, и чередуя информационные символы с контрольными. Однако произвольное месторасположение контрольных символов будет затруднять проверку принятого кода. Поэтому для удобства обнаружения искаженного символа целесообразно размещать их на местах кратных степени 2, то есть в позициях 1, 2, 4, 8 и т.д. Информационные символы располагаются на оставшихся местах. Поэтому, для 7-элементой закодированной комбинации можно записать:

2³, k =4 }

m =3} m _1, m _2, k _н, m ₃, k ₃, k ₂, k ₁ (3-12)

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

Определение состава контрольных символов. Выявление того, какой символ должен стоять на контрольной позиции (1 или 0), производится по коэффициентам при помощи проверки на четность. Рассмотрим определение коэффициентов на примере комбинации (3-12).

Таблица 3-11

Разряды двоичных чисел	Символы кода (для 3-12)
4(k н)	3 (k 3)	2 (k 2)	1(k 1)
				m 1
				m 2
				k 4
				m 3
				k 3
				k 2
				k 1

В таблицу вписаны все кодовые комбинации (исключая нулевую) для 4-разрядного двоичного кода на все сочетания.

Таблица 3-12

Проверочная таблица

m 1	k 4	k 3	k 1
m 2	k 4	k 2	k 1
m 3	k 3	k 2	k 1

Из таблицы 3-11 составляется таблица 3-12, в которой вписаны символы в 3- х строках в следующей закономерности. В первую строку таблицы 3-12 записываются символы m _1,. k _4,. k _3,. k ₁ против которых проставлены единицы в младшем (первом) разряде комбинации двоичного кода в таблице 3-11. Так в комбинациях 0001, 011, 0101, 0111 единицы находятся в младших разрядах. Во вторую строку проверочных коэффициентов записываются символы, против которых стоит 1 во втором разряде двоичного кода. Это комбинации 0010, 0011, 0110 и 0111-записали m ₂, k _4, k _2, k ₁. В третью строку записываются символы, против которых стоят единицы в третьем разряде двоичных комбинаций (m ₃, k ₃, k ₂, k ₁)

В случае кодирования более длинных кодовых комбинаций таблицы 3-11 и 3-12 должны быть расширены, так как должны быть записаны четвертая, пятая и т.д. строки проверочных коэффициентов. Так для комбинации m ₁, m ₂, k ₁₁, m ₃, k ₁₀, k ₉, k ₈, m ₄, k ₇, k ₆, k ₅, k ₄, k ₃, k ₂, k ₁. таблицы 3-12 будет состоять из 4-х строк.

Число проверок, а, значит, и число строк таблицы 3-12 равно числу контрольных символов m.

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

Если сумма единиц в данной строке четная, то значение символа m, входящее в эту строку, равно 0, если нечетная, то 1.

При помощи первой строки табл.3-12 определяется значение символа m ₁, при помощи второй строки- значение m ₂, третьей- m ₃.

Декодирование. Для проверки правильности комбинации снова используется метод проверки на четность по коэффициентам табл.3-12. Если комбинация принята без искажения, то сумма единиц по модулю 2 даст 0.

При искажении какого-либо символа суммирование при проверке даст единицу. По результату суммирования каждой из проверок составляется двоичное число, указывающее на место искажения. Например, первая и вторая проверки показали наличие искажения, суммирование при третьей проверке дало 0.Записываем число 011=3, которое означает, что в 3-ем символе кодовой комбинации, включающей и контрольные символы (счет производится слева направо),возникло искажение, поэтому этот символ нужно исправить на обратный ему, то есть 1 переправить на 0 или 0 на 1.После этого контрольные символы, стоящие на заранее известных местах отбрасываются.

Пример кодирования и декодирования. Предполагаем, нужно передать комбинацию 1101, то есть k =4.

Согласно таблице 3-10 число контрольных символов m =3, и размещаются они на позициях 3, 5, 6, 7. Можно записать:

m ₁ m ₂ k ₄ m ₃ k ₃ k ₂ k ₁ (3-13)

?? 1? 1 0 1

Для определения значения контрольных символов заполним табл. 3-12 значениями из последовательности (3-13). По полученной таблице 3-13 произведем проверки на четность.

Для того, чтобы вся первая строка после проставления в нее значения символа m ₁ дала в сумме четное число, необходимо, чтобы m ₁=1 (m ₁+ k ₄+ k ₃+ k ₁=1+1+1+1=0).

Вторая строка в сумме дает четное число, если m ₂=0 (m ₂+ k ₄+ k ₂+ k ₁=0+1+++1=0)

Третья строка дает четное число, если m ₃=0 (m ₃+ k ₃+ k ₂+ k ₁=0+1+0+1=0)

Таким образом, в линию послан код 1010101.

Предположим, что при передаче помеха исказила один из символов, и был принят код 1010111. Для нахождения номера ошибки принятого символа используют метод проверки на четность по табл.3-12.Для этого запишем:

m ₁ m ₂ k ₄ m ₃ k ₃ k ₂ k ₁

1 0 1 0 1 1 1

По полученной последовательности символов и по таблице 3-12 составим таблицу 3-14.

Таблица 3-13 Таблица 3-14

«Пример составления

таблицы для кода Хэмминга» «Пример декодирования кода Хэмминга»

m 1+1 +1 +1 =3 m 1=1 k 4 k 3 k 1	1 +1 +1 +1=0 m 1 k 4 k 3 k 1
m 2+1 + 0 +1 =2 m 2=0 k 4 k 2 k 1	0 +1 +1 +1=1 m 2 k 4 k 2 k 1
m 3+1 +0 +1 =2 m 3=0 k 3 k 2 k 1	0 +1 +1 +1=1 m 3 k 3 k 2 k 1

После заполнения этой таблицы сумма символов первой строки оказалась четной (1+1+1+1=0), поэтому для четности справа в первой строке табл. 3-14 приписываем 0. Сумма символов второй строки равна 3, поэтому справа для четности добавляется 1. Также для получения четности необходимо приписать 1 и к третьей строке.

Все три приписанных символа дали двоичное число 110 (но не 011), так первая проверка производилась по коэффициентам, составленным по младшим разрядам двоичного кода.

Двоичное число 110 означает десятичное число 6. Это значит, что искажение произошло в шестом символе, считая слева направо, и символ 1 нужно исправлять на 0. Так как места расположения контрольных символов заранее известны, что после коррекции контрольные символы выбрасывают и получают переданную кодовую комбинацию, состоящую из одних информационных символов 1101.

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

Так, семиразрядный код принципиально обеспечивает передачу 2⁷=128 кодовых комбинаций, однако количество информационных символов в 7-разрядном коде Хэмминга к =4, то есть полезных информационных

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

Для 7-разрядного кода Хэмминга, причем с увеличением разрядности кода избыточность уменьшается

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

Дата добавления: 2014-01-07