Лекции по Теории передачи сигналов   

7. Корректирующие коды

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

К этому типу кодов обычно относят систематические коды с расстоянием d=3, которые позволяют исправить все одиночные ошибки (7.3).

Рассмотрим построение семизначного кода Хэмминга, каждая комбинация которого содержит четыре  информационных и триконтрольных символа. Такой код, условно обозначаемый (7.4), удовлетворяет неравенству (7.11)    и   имеет   избыточность

Если информационные символы с занимают в комбинация первые четыре места, то последующие три контрольных символа образуются по общему правилу (7.9) как суммы:

                                                                              (7.14)

Декодирование осуществляется путем трех проверок на четность (7.10):

                                                                                  (7.15)

Так как х равно 0 или 1, то всего может быть восемь контрольных чисел Х=х1х2х3: 000, 100, 010, 001, 011, 101, 110 и 111. Первое из них имеет место в случае правильного приема, а остальные семь появляются при наличии искажений и должны использоваться для определения местоположения одиночной ошибки в семизначной комбинации. Выясним, каким образом устанавливается взаимосвязь между контрольными числами я искаженными символами. Если искажен один из контрольных символов:  или , то, как следует из (7.15), контрольное число примет соответственно одно из трех значений: 100, 010 или 001. Остальные четыре контрольных числа используются для выявления ошибок в информационных символах.

Таблица 7.1

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

Таблица 7.2

Если подставить коэффициенты  в выражение (7.15), то получим:

                                                                                  (7.16)

При искажении одного из информационных символов становятся равными единице те суммы х, в которые входит этот символ. Легко проверить, что получающееся в этом случае контрольное число согласуется с табл. 7.1.Нетрудно заметить, что первые четыре контрольные числа табл. 7.1 совпадают со столбцами табл. 7.2. Это свойство дает возможность при выбранном распределении контрольных чисел составить таблицу коэффициентов . Таким образом, при одиночной ошибке можно вычислить контрольное число, позволяющее по табл. 7.1 определить тот символ кодовой комбинации, который претерпел искажения. Исправление искаженного символа двоичной системы состоит в простой замене 0 на 1 или 1 на 0. B качестве примера рассмотрим передачу комбинации, в которой информационными символами являются , Используя ф-лу (7.14) и табл. 7.2, вычислим контрольные символы:

Передаваемая комбинация при этом будет . Предположим, что принята комбинация — 1001, 010 (искажен символ ). Подставляя соответствующие значения в (7.16), получим:

Вычисленное таким образом контрольное число  110 позволяет согласно табл. 7.1 исправить ошибку в символе.

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

                                                                                         (7.17)

Так, если произошла ошибка в информационном символе с'5 то контрольное  число , что соответствует  числу 5 в двоичной системе.

В заключение отметим, что в коде (7.4) при появлении многократных ошибок контрольное число также может отличаться от нуля. Однако декодирование в этом случае будет проведено неправильно, так как оно рассчитано на исправление лишь одиночных ошибок.



*****
Новосибирск © 2009-2017 Банк лекций siblec.ru
Лекции для преподавателей и студентов. Формальные, технические, естественные, общественные, гуманитарные, и другие науки.