Порядок составления кода хэмминга

ОСНОВНЫЕ СВЕДЕНИЯ

· Позволяет исправлять любые одиночные ошибки (s=1 и d=3). Имеется вариант кода, исправляющий любую одиночную или обнаруживающий, но не исправляющий двойные ошибки (s=r=1 и d=4). Длина кодовых слов n=m + k.

Опознаватель ошибки – двоичное проверочное число Q, указывающее номер искажённого разряда кодового слова. Формируется в результате k определённых проверок принятого кода на чётность (допускается проверка и на нечётность).

В общем случае k- разрядное число Q должно принимать столько значений, чтобы отобразить не только возможные ошибки на m информационных и k контрольных позициях, но и случай отсутствия ошибок, т.е. из соотношения

Q =2^k = 2^n-m ≥ n+1, откуда ≥ 2^m = N.

Полученное неравенство позволяет по заданному N подобрать требуемое число контрольных позиций k идругие числовые показатели кода Хэмминга (см. в табл.). Но для практических расчётов и составления кода используют более простые эмпирические формулы.

ПОРЯДОК СОСТАВЛЕНИЯ кода ХЭММИНГА

Исходные данные – исправление одиночной ошибки, число кодовых слов N £ 2^m.

1. Количество информационных символов – m = Ý log₂N..

(Ý – символ округления до ближайшего большего целого)

2. Число контрольных символов – k= Ý log₂[(m+1) + Ý log₂(m+1)].

3. Общая длина кода – n = m + k.

4. Выбор позиций размещения информационных символов m и контрольных k связан со структурой двоичного проверочного числа Q=...q₃q₂q₁ и порядком его формирования на основе проверок групп позиций (при отсутствии ошибки соответствующий разряд q_i =0, при ошибке – 1).

Обнаружение ошибки при первой проверке сформирует «1» в первом разряде q₁ числа, что соответствует значениям двоичного числа Q ® Следовательно, первая проверка должна охватывать позиции 1, 3, 5, 7,..

Единица во втором разряде q₂ формируется, если обнаружена ошибка при второй проверке, соответствующие значения Q ® определяют позиции второй проверки – 2, 3, 6, 7,...

Разряд q₃=1, если обнаруживается ошибка при третьей проверка.

Соответствующие значения проверочного числа Q указывают охватываемые этой проверкой позиции – 4, 5, 6, 7, 12, 13, 14, 15, 20,...

---

Дата добавления: 2015-07-08