Код Хемминга

 
 
 
 
 
 

Раз получившаяся сумма не равна нулю, а контрольный бит указывает на ошибку передачи, то обнаруживаем двойную ошибку. Исправление двойных ошибок здесь, конечно, невозможно.

Увеличивая дальше количество контрольных разрядов, можно было бы построить коды, рассчитанные на исправление двойных ошибок и обнаружение тройных и т.д. Однако методы построения этих кодов не вполне разработаны. 
 
 
 

         
 
 
 
 
 
 
 

3. Принцип построения кодов Хемминга.

       Построение кодов Хемминга базируется на принципе проверки на

четность веса W (числа единичных символов) в информационной груп-

пе кодового блока.

   Поясним идею проверки на четность на примере простейшего кор-

ректирующего кода, который так и называется кодом с проверкой на

четность или кодом с проверкой по паритету (равенству).

   В таком коде к кодовым комбинациям безызбыточного первичного

двоичного k-разрядного кода добавляется один дополнительный разряд

(символ проверки на четность, называемый проверочным, или конт-

рольным). Если число символов 1 исходной кодовой комбинации чет-

ное, то в дополнительном разряде формируют контрольный символ 0, а

если число символов 1 нечетное, то в дополнительном разряде форми-

руют символ 1. В результате общее число символов 1 в любой переда-

ваемой кодовой комбинации всегда будет четным.

   Таким образом, правило формирования проверочного символа сво-

дится к следующему:

                        r1 = i1 ⊕ i2 ⊕ ... ⊕ ik ,

где i - соответствующий информационный символ (0 или 1); k - общее

их число а под операцией "⊕" здесь и далее понимается сложение по

mod 2. Очевидно, что добавление дополнительного разряда увеличива-

ет общее число возможных комбинаций вдвое по сравнению с числом

комбинаций исходного первичного кода, а условие четности разделяет

все комбинации на разрешенные и неразрешенные. Код с проверкой на

четность позволяет обнаруживать одиночную ошибку при приеме кодо-

вой комбинации, так как такая ошибка нарушает условие четности, пе-

реводя разрешенную комбинацию в запрещенную.

   Критерием правильности принятой комбинации является равенство

нулю результата S суммирования по mod 2 всех n символов кода, вклю-

чая проверочный символ r1. При наличии одиночной ошибки S прини-

мает значение 1: 

            S = r1 ⊕ i1 ⊕ i2 ⊕ ... ⊕ ik = ò 0 - ошибки нет,

                                           = ò1 - однократная ошибка.

                          n

    Этот код является (k +1, k)-кодом, или (n, n-1)-кодом. Минимальное

расстояние кода равно двум (dmin = 2), и, следовательно, никакие ошиб-

ки не могут быть исправлены. Простой код с проверкой на четность

может использоваться только для обнаружения (но не исправления) од-

нократных ошибок.

    Увеличивая число дополнительных проверочных разрядов и форми-

руя по определенным правилам проверочные символы r, равные 0 или

1, можно усилить корректирующие свойства кода так, чтобы он позво-

лял не только обнаруживать, но и исправлять ошибки. На этом и осно-

вано построение кодов Хемминга.

    Коды Хемминга позволяют исправлять одиночную ошибку, с помощью

непосредственного описания. Для каждого числа проверочных символов

r = 3, 4, 5… существует классический код Хемминга с маркировкой

                          (n, k) = (2r-1, 2r-1 - r) ,            (3.20)

т. е. (7,4), (15,11), (31,26) …

    При других значениях числа информационных символов k полу-

чаются так называемые усеченные (укороченные) коды Хемминга.

Так, для Международного телеграфного кода МТК-2 , имеющего

5 информационных символов, потребуется использование коррек-

тирующего кода (9,5), являющегося усеченным от классического кода

Хемминга (15,11), так как число символов в этом коде уменьшается

(укорачивается) на 6.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4.Применение.

   Код Хэмминга используется в некоторых прикладных программах в области хранения данных, особенно в RAID 2; кроме того, метод Хемминга давно применяется в памяти типа ECC и позволяет "на лету" исправлять однократные и обнаруживать двукратные ошибки. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Литература:

1. Лидовский В.И. Теория информации. - М., «Высшая школа», 2002г. - 120с.
2. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И.Халкин, Е.В.Федоров и др. - М.: Высшая школа, 2001 г. - 383с.
3. Цапенко М.П. Измерительные информационные системы. - . - М.: Энергоатом издат, 2005. - 440с.