Коды Хемминга
Наиболее известные из самоконтролирующихся и самокорректирующихся кодов – коды Хемминга. Построены они применительно к двоичной системе счисления.
Для построения самокорректирующегося кода достаточно иметь один контрольный разряд (код с проверкой на четность). Но при этом мы не получаем никаких указаний о том, в каком именно разряде произошла ошибка, и, следовательно, не имеем возможности исправить ее. Остаются незамеченными ошибки, возникшие в четном числе разрядов.
Коды Хемминга имеют бóльшую относительную избыточность, чем коды с проверкой на четность, и предназначены либо для исправления одиночных ошибок (при d = 3), либо для исправления одиночных и обнаружения без исправления двойных ошибок (d = 4). В таком коде n-значное число имеет m информационных и k контрольных разрядов. Каждый из контрольных разрядов является знаком четности для определенной группы информационных знаков слова. При декодировании производится k групповых проверок на четность. В результате каждой проверки в соответствующий разряд регистра ошибки записывается 0, если проверка была успешной, или 1, если была обнаружена нечетность.
Группы для проверки образуются таким образом, что в регистре ошибки после окончания проверки получается K-разрядное двоичное число, показывающее номер позиции ошибочного двоичного разряда. Изменение этого разряда – исправление ошибки.
Первоначально эти коды предложены Хеммингом в таком виде, при котором контрольные знаки занимают особые позиции: позиция i-го знака имеет номер 2i–1. При этом каждый контрольный знак входит лишь в одну проверку на четность.
Рассмотрим код Хемминга, предназначенный для исправления одиночных ошибок, т. е. код с минимальным кодовым расстоянием d = 3.
Ошибка возможна и в одной из n позиций. Следовательно, число контрольных знаков, а значит, и число разрядов регистра ошибок должно удовлетворять условию
| k ³ log2(n + 1). | (1) |
Отсюда
| m £ n – log2(n + 1). | (2) |
Значения m и k для некоторых коротких кодов, вычисленные по формулам (1) и (2) даны в табл. 11.1.
Таблица 11.1. Значения m и n
n |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
m |
1 |
1 |
2 |
3 |
4 |
4 |
5 |
6 |
7 |
8 |
k |
2 |
3 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
I гр.: |
все нечетные позиции, включая и позиции контрольного разряда, т. е. позиции, в первом младшем разряде которых стоит 1. |
|
II гр.: |
все позиции, номера которых в двоичном представлении имеют 1 во втором разряде справа (например, 2, 3, 6, 7, 10) и т. д. |
|
III гр. |
: |
разряды, имеющие "1" в третьем разряде справа, и т. д. |
Пример 1. Пусть k = 5 (табл. 11.2).
Таблица 11.2. Формирование контрольных групп
Номер проверки |
Позиция контрольного знака |
Проверяемые позиции |
1 |
1 |
1, 3, 5, 7, 9, 11, 13, ... |
2 |
2 |
2, 3, 6, 7, 10, 11, ... |
3 |
4 |
4, 5, 6, 7, 12, 13, ... |
4 |
8 |
8, 9, 10, 11, 12, 13, ... |
5 |
16 |
16, 17, 18, 19, 20, 21 |
