Код Хэмминга

Код Хэмминга1Код ХэммингаКоды Хэмминга — вероятно, наиболее известный из первых самоконтролирующихсясамокорректирующихся кодов. Построены они применительно к двоичной системе счисления.иИсторияВ середине 1940-х годов Ричард Хэмминг работал в знаменитых лабораториях фирмы Белл (Bell Labs) насчётной машине Bell Model V. Это была электромеханическая машина, использующая релейные блоки,скорость которых была очень низка: один оборот за несколько секунд.

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

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

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

Одиночная ошибка в каком-либо разрядепередаваемого слова (в том числе, может быть, и в контрольном разряде) изменит четность общего количестваединиц. Счетчики по модулю 2, подсчитывающие количество единиц, которые содержатся среди двоичныхцифр числа, могут давать сигнал о наличии ошибок.При этом невозможно узнать, в каком именно разряде произошла ошибка, и, следовательно, нет возможностиисправить её. Остаются незамеченными также ошибки, возникающие одновременно в двух, четырёх, и т.д. — вчетном количестве разрядов.

Впрочем, двойные, а тем более четырёхкратные ошибки полагаютсямаловероятными.Самокорректирующиеся кодыКоды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Дляпостроения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одногоконтрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов k должнобыть выбрано так, чтобы удовлетворялось неравенствоили, где m— количество основных двоичных разрядов кодового слова. Минимальные значения k при заданныхКод Хэмминга2значениях m, найденные в соответствии с этим неравенством, приведены в таблице.Диапазон m kmin122-435-11412-26527-576В настоящее время наибольший интерес представляют двоичные блочные корректирующие коды.

Прииспользовании таких кодов информация передаётся в виде блоков одинаковой длины и каждый блоккодируется и декодируется независимо друг от друга. Почти во всех блочных кодах символы можно разделитьна информационные и проверочные. Таким образом, все комбинации кодов разделяются на разрешенные (длякоторых соотношение информационных и проверочных символов возможно) и запрещенные.Основными характеристиками самокорректирующихся кодов являются:1. Число разрешенных и запрещенных комбинаций. Если n - число символов в блоке, r - число проверочныхсимволов в блоке, k - число информационных символов, то- число возможных кодовых комбинаций,- число разрешенных кодовых комбинаций,- число запрещенных комбинаций.2.

Избыточность кода. Величину называют избыточностью корректирующего кода.3. Минимальное кодовое расстояние. Минимальным кодовым расстоянием d называется минимальное числоискаженных символов, необходимое для перехода одной разрешенной комбинации в другую.4. Число обнаруживаемых и исправляемых ошибок. Если g - количество ошибок, которое код способенисправить, то необходимо и достаточно, чтобы5. Корректирующие возможности кодов.Граница Плоткина даёт верхнюю границу кодового расстоянияилиприГраница Хемминга устанавливает максимально возможное число разрешенных кодовых комбинацийгде- число сочетаний из n элементов по i элементам. Отсюда можно получитьвыражение для оценки числа проверочных символов:Для значенийразница между границей Хемминга и границей Плоткина невелика.Граница Варшамова-Гильберта для больших n определяет нижнюю границу числа проверочных символовВсе вышеперечисленные оценки дают представление о верхней границе d прификсированных n и k или оценку снизу числа проверочных символовКод Хэмминга3Код ХеммингаПостроение кодов Хемминга основано на принципе проверки на четность числа единичных символов: кпоследовательности добавляется такой элемент, чтобы число единичных символов в получившейсяпоследовательности было четным.знакздесь означает сложение по модулю 2.илиинформационных- ошибки нет,однократная ошибка.

Такой код называется. Первое число - количество элементов последовательности, второе - количествосимволов.Длякаждогочислапроверочныхклассический код Хемминга с маркировкойсимволовсуществуетт.е. -. При иных значениях k получается так называемый усеченных код, например международный телеграфныйкод МТК-2, у которого. Для него необходим код Хемминга, который является усеченным отклассического.

Для Примера рассмотрим классический код Хемминга. Сгруппируемпроверочные символы следующим образом:знакздесь означает сложение по модулю 2.Получение кодового слова выглядит следующим образом:=На вход декодера поступает кодовое словогде штрихом помечены символы,которые могут исказиться в результате помехи. В декодере в режиме исправления ошибок строитсяпоследовательность синдромов:называется синдромом последовательности.Получение синдрома выглядит следующим образом:=Кодовые словакода ХеммингаКод Хэмминга4Синдром0000000000101100101100011101010011101011000110001011101010001011001110101001110110001100010110100111101001111111указывает на то, что в последовательности нет искажений.

Каждому ненулевому синдромусоответствует определенная конфигурация ошибок, которая исправляется на этапе декодирования. Для кодав таблице указаны ненулевые синдромы и соответствующие им конфигурации ошибок (для вида:).Синдром001010011100101110111Конфигурация ошибок 0000001 0000010 0001000 0000100 1000000 0010000 0100000Ошибка в символеКод Хэмминга5Код Хэмминга6Алгоритм кодированияПредположим, что нужно сгенерировать код Хемминга для некоторого информационного кодового слова. Вкачестве примера возьмём 15-битовое кодовое слово x1...x15, хотя алгоритм пригоден для кодовых слов любойдлины. В приведённой ниже таблице в первой строке даны номера позиций в кодовом слове, во второй —условное обозначение битов, в третьей — значения битов.123456789101112131415x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15100100101110001Вставим в информационное слово контрольные биты r0...r4 таким образом, чтобы номера их позицийпредставляли собой целые степени двойки: 1, 2, 4, 8, 16...

Получим 20-разрядное слово с 15информационными и 5 контрольными битами. Первоначально контрольные биты устанавливаем равныминулю. На рисунке контрольные биты выделены розовым цветом.123456789 10 11 12 13 1415 16 17181920r0 r1 x1 r2 x2 x3 x4 r3 x5 x6 x7 x8 x9 x10 x11 r4 x12 x13 x14 x1500100010001011100001В общем случае количество контрольных бит в кодовом слове равно двоичному логарифму числа бит кодовогослова (включая контрольные биты), округлённому в большую сторону до ближайшего целого. Например,информационное слово длиной 1 или 2 бита требует двух контрольных разрядов, 3- или 4-битовоеинформационное слово — трёх, 5...11-битовое — четырёх, 12...26-битовое — пяти и т.д.Добавим к таблице 5 строк (по количеству контрольных битов), в которые поместим матрицу преобразования.Каждая строка будет соответствовать одному контрольному биту (нулевой контрольный бит — верхняястрока, четвёртый — нижняя), каждый столбец — одному биту кодируемого слова.

В каждом столбце матрицыпреобразования поместим двоичный номер этого столбца, причём порядок следования битов будет обратный— младший бит расположим в верхней строке, старший — в нижней. Например, в третьем столбце матрицыбудут стоять числа 11000, что соответствует двоичной записи числа три: 00011.123456789 10 11 12 13 1415 16 17181920r0 r1 x1 r2 x2 x3 x4 r3 x5 x6 x7 x8 x9 x10 x11 r4 x12 x13 x14 x150010001000101110000110101010101010101010r001100110011001100110r100011110000111100001r200000001111111100000r300000000000000011111r4В правой части таблицы мы оставили пустым один столбец, в который поместим результаты вычисленийконтрольных битов. Вычисление контрольных битов производим следующим образом.

Берём одну из строкматрицы преобразования (например, r0) и находим её скалярное произведение с кодовым словом, то естьперемножаем соответствующие биты обеих строк и находим сумму произведений. Если произведениеполучилось больше единицы, находим остаток от его деления на 2. Иными словами, мы подсчитываем сколькораз в кодовом слове и соответствующей строке матрицы в одинаковых позициях стоят единицы и берём эточисло по модулю 2.Код Хэмминга7Если описывать этот процесс в терминах матричной алгебры, то операция представляет собой перемножениематрицы преобразования на матрицу-столбец кодового слова, в результате чего получается матрица-столбецконтрольных разрядов, которые нужно взять по модулю 2.Например, для строки r0:r0 = (1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·0+0·0+1·1+0·0+1·1+0·1+1·1+0·0+1·0+0·0+1·0+0·1) mod 2 = 5 mod 2 =1.Полученные контрольные биты вставляем в кодовое слово вместо стоявших там ранее нулей.