15. Особенности и принцип построения кода Хэмминга. Обнаружение и исправление ошибок кодом Хэмминга. Синдром линейного кода.

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

К кодам Хэмминга обычно относятся коды с =3, исправляющие все одиночные ошибки и коды с=4, исправляющие все одиночные и обнаруживающие все двойные ошибки. Для исправления всех одиночных ошибок число синдромов должно бытьn+1 ( n – число разрядов ). Из них n синдромов используются для указания местоположения ошибки, а один – нулевой, соответствует их отсутствию. Следовательно, .n=m+k, где m –информационные разряды, к –проверочные.

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

Сгруппируем в первую сумму все элементы, номера которых имеют значение «1» в 1-м младшем разряде двоичного числа. Во вторую сумму сгруппируем элементы, номера которых имеют значение «1» во втором разряде двоичного числа и т.д. для третьей и четвертой сумм.

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

Полная кодовая комбинация передаваемая в линию будет иметь вид:

Порядок кодирования кодом Хэмминга в устройстве защиты от ошибок передатчика:

1. от источника принимается 5-ти элементная кодовая комбинация и ее разряды записываются в отведенных для них местах 3,5,6,7 и 9.

2. Суммированием по модулю 2 определяются проверочные разряды. Их значения должны быть такими, чтобы сумма, в которую входит данный проверочный разряд, равнялась «0». Другими словами, каждый проверочный разряд должен дополнить свою сумму до четного количества единиц.

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

4. Сформированная таким образом кодовая комбинация передается в канал.

Рассмотрим пример: Источник выдает информационные элементы

Тогда полная кодовая комбинация, которая будет передаваться в канал, имеет вид:

Порядок декодирования на приеме в устройстве защиты от ошибок.

1. Подсчитываем 4 суммы в каждую из которых входят информационные разряды и по одному проверочному.

2. Производится анализ полученных сумм, при этом возможны три случая:

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

б) проверочное число отличается от значения 0000, причем по его значению можно определить номер ошибочного разряда.

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

3. В зависимости от результатов анализа:

а) информация выдается потребителю;

б) ошибки исправляются и информация выдается потребителю;

в) принятая комбинация стирается и в устройстве защиты от ошибок вырабатывается сигнал «ошибка».

Принята комбинация:

Все «0», значит комбинация принята верно.

Допустим что произошло искажение в третьем элементе и вместо 1 принят 0. Тогда принятая комбинация имеет вид:

В данном случае синдром равен 0011, что соответствует ошибке в 3 элементе кодовой комбинации. Для устранения данной ошибки необходимо изменить находящийся в этом элементе символ на обратный.

Схема кодера.

Схема декодера.

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

Код Хэмминга имеет существенный  недостаток:  при  обнаружении любого числа ошибок он исправляет лишь одиночные  ошибки. Избыточность  семиэлементного кода Хэмминга равна 0,43. При увеличении значности кодовых комбинаций увеличивается число проверок,  но уменьшается избыточность кода. К тому же код Хэмминга не  позволяет обнаружить групповые ошибки, сконцентрированные в пакетах.  Длина пакета ошибок представляет собой увеличенную на единицу разность между именами старшего и младшего ошибочных элементов.