Увеличивая дальше количество контрольных разрядов, можно было бы построить коды, рассчитанные на исправление двойных ошибок и обнаружение тройных и т.д. Однако методы построения этих кодов не вполне разработаны.
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с.