Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
otvety_TELEMEKhANIKA.doc
Скачиваний:
357
Добавлен:
07.06.2015
Размер:
6.7 Mб
Скачать

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

m1

k4

k3

k1

                1. m2

                  1. k4

k2

k1

m3

k3

k2

k1

Число строк в проверочной табл. 4.15 равно числу контрольных символов т.

В случае кодирования более длинных информационных кодовых комбинаций табл. 4.14 и 4.15 должны быть расширены, так как должны быть записаны четвертая, пятая и т.д. строки проверочных коэффициентов. Для этого нужно лишь увеличить число разрядов двоичного кода в табл. 4.14. Например, для комбинации т1, m2, k11, m3, k10, k9, k8, m4, k7, k6, k5, k4, k3, k2, k1, имеющей одиннадцать информационных символов и четыре контрольных символа, табл. 4.14 будет содержать 15 строк, а табл. 4.15 будет состоять из четырёх строк.

Состав контрольных символов с помощью проверок определяют следующим образом. Суммируют информационные символы, входящие в каждую строку табл. 4.15; если сумма единиц в данной строке четная, то значение символа т, входящего в эту строку, равно 0, если нечетная, то 1. По первой строке табл. 4.15 определяют значение символа т1, по второй – т2, по третьей – m3.

Полученные по табл. 4.15 контрольные символы подставляют в полную кодовую комбинацию (4.6) кода Хэмминга, которая теперь полностью определена.

Пример 4.1

Закодировать кодом Хэмминга, исправляющим одну ошибку, информационную комбинацию двоичного кода 1101.

В информационной комбинации содержится четыре информационных разряда, т.е. k=4.

Согласно табл. 4.13 число контрольных символов m=3, и в соответствии с (4.6) размещаются они на позициях 1, 2 и 4, а информационные символы – на позициях 3, 5, 6 и 7 полной кодовой комбинации, в которой всего семь разрядов, так как n=k+m. Символы информационной части известны, а контрольные символы необходимо определить.

Полную кодовую комбинацию можно записать в виде:

т1 m2 k4 m3 k3 k2 k1

? ? 1 ? 1 0 1

Для определения контрольных символов заполняем табл. 4.15 значениями информационных символов и в полученной таким образом табл. 4.16 суммируем по модулю 2 информационные символы каждой строки.

Таблица 4.16

Проверочная таблица кода Хэмминга, заполненная информационными символами

Очевидно, что суммирование информационных символов первой строки даёт 1, суммирование этих символов второй и третьей строк даёт 0. Следовательно, имеем следующий состав контрольных символов: т1 =1, m2 =0, m3=0.

Подставляя контрольные символы на их позиции в (4.6), получим полную кодовую комбинацию кода Хэмминга: 1 0 1 0 1 0 1.

Декодирование кода Хэмминга. Для обнаружения и исправления ошибки выполняются следующие действия.

1. Заполнение проверочной таблицы символами полной кодовой комбинации

Проверочная таблица кода Хэмминга (см. табл. 4.15) заполняется символами полной кодовой комбинации с использованием структуры (4.6) этой комбинации.

2. Суммирование по модулю 2 строк проверочной таблицы

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

3. Определение места искажения

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

4. Исправление искажения

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

Контрольные символы в соответствии с (4.6) отбрасываются, неискажённая информационная часть обрабатывается.

Пример 4.2

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

Принятая кодовая комбинация имеет 7 разрядов, поэтому согласно табл. 4.11 в ней имеется 4 информационных символа и 3 контрольных. Структура такой комбинации имеет вид (4.6):

т1

m2

k4

m3

k3

k2

k1

1

0

1

0

1

1

1

Проверочная таблица семиразрядного кода Хэмминга имеет вид табл. 4.15. Подстановка в неё символов принятой комбинации даёт табл. 4.17.

Таблица 4.17

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]