Код Хэмминга

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Код Хемминга»)
Перейти к: навигация, поиск

Ко́ды Хэ́мминга — вероятно, наиболее известный из первых самоконтролирующихся и самокорректирующихся кодов. Построен применительно к двоичной системе счисления. Позволяет исправлять одиночную ошибку (ошибка в одном бите) и находить двойную[1].

Названы в честь американского математика Ричарда Хэмминга, предложившего их.

История[править | править вики-текст]

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

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

Систематические коды[править | править вики-текст]

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

Самоконтролирующиеся коды[править | править вики-текст]

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

При этом невозможно узнать, в каком именно разряде произошла ошибка, и, следовательно, нет возможности исправить её. Остаются незамеченными также ошибки, возникающие одновременно в двух, четырёх, и т. д. — в четном количестве разрядов. Впрочем, двойные, а тем более четырёхкратные ошибки полагаются маловероятными.

Самокорректирующиеся коды[править | править вики-текст]

Коды, в которых возможно автоматическое исправление ошибок, называются самокорректирующимися. Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, одного контрольного разряда недостаточно. Как видно из дальнейшего, количество контрольных разрядов k должно быть выбрано так, чтобы удовлетворялось неравенство или , где m — количество основных двоичных разрядов кодового слова.

Минимальные значения k при заданных значениях m, найденные в соответствии с этим неравенством, приведены в таблице.

Диапазон m kmin
1 2
2-4 3
5-11 4
12-26 5
27-57 6

В настоящее время наибольший интерес представляют двоичные блочные корректирующие коды. При использовании таких кодов информация передаётся в виде блоков одинаковой длины и каждый блок кодируется и декодируется независимо друг от друга. Почти во всех блочных кодах символы можно разделить на информационные и проверочные. Таким образом, все комбинации кодов разделяются на разрешенные (для которых соотношение информационных и проверочных символов возможно) и запрещенные.

Основными характеристиками самокорректирующихся кодов являются:

  1. Число разрешенных и запрещенных комбинаций. Если n — число символов в блоке, r — число проверочных символов в блоке, k — число информационных символов, то  — число возможных кодовых комбинаций,  — число разрешенных кодовых комбинаций,  — число запрещенных комбинаций.
  2. Избыточность кода. Величину называют избыточностью корректирующего кода.
  3. Минимальное кодовое расстояние. Минимальным кодовым расстоянием d называется минимальное число искаженных символов, необходимое для перехода одной разрешенной комбинации в другую.
  4. Число обнаруживаемых и исправляемых ошибок. Если g — количество ошибок, которое код способен исправить, то необходимо и достаточно, чтобы
  5. Корректирующие возможности кодов.

Граница Плоткина даёт верхнюю границу кодового расстояния

или

при

Граница Хемминга устанавливает максимально возможное число разрешенных кодовых комбинаций

где  — число сочетаний из n элементов по i элементам. Отсюда можно получить выражение для оценки числа проверочных символов: :

Для значений разница между границей Хемминга и границей Плоткина невелика.

Граница Варшамова — Гильберта для больших n определяет нижнюю границу числа проверочных символов

Все вышеперечисленные оценки дают представление о верхней границе d при фиксированных n и k или оценку снизу числа проверочных символов

Код Хэмминга[править | править вики-текст]

Построение кодов Хэмминга основано на принципе проверки на четность числа единичных символов: к последовательности добавляется такой элемент, чтобы число единичных символов в получившейся последовательности было четным.

знак здесь означает сложение по модулю 2

.

 — ошибки нет, однократная ошибка.

Такой код называется или . Первое число — количество элементов последовательности, второе — количество информационных символов.

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

Для примера рассмотрим классический код Хемминга . Сгруппируем проверочные символы следующим образом:

Получение кодового слова выглядит следующим образом:

=

На вход декодера поступает кодовое слово где штрихом помечены символы, которые могут исказиться в результате помехи. В декодере в режиме исправления ошибок строится последовательность синдромов:

называется синдромом последовательности.

Получение синдрома выглядит следующим образом:

=

Кодовые слова кода Хэмминга

0 0 0 0 0 0 0
0 0 0 1 0 1 1
0 0 1 0 1 1 0
0 0 1 1 1 0 1
0 1 0 0 1 1 1
0 1 0 1 1 0 0
0 1 1 0 0 0 1
0 1 1 1 0 1 0
1 0 0 0 1 0 1
1 0 0 1 1 1 0
1 0 1 0 0 1 1
1 0 1 1 0 0 0
1 1 0 0 0 1 0
1 1 0 1 0 0 1
1 1 1 0 1 0 0
1 1 1 1 1 1 1

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

Для кода в таблице указаны ненулевые синдромы и соответствующие им конфигурации ошибок (для вида: ).

Синдром 001 010 011 100 101 110 111
Конфигурация ошибок 0000001 0000010 0001000 0000100 1000000 0010000 0100000
Ошибка в символе

My hemcode.png HemDecode.PNG

Алгоритм кодирования[править | править вики-текст]

Предположим, что нужно сгенерировать код Хемминга для некоторого информационного кодового слова. В качестве примера возьмём 15-битовое кодовое слово x1x15, хотя алгоритм пригоден для кодовых слов любой длины. В приведённой ниже таблице в первой строке даны номера позиций в кодовом слове, во второй — условное обозначение битов, в третьей — значения битов.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 x15
1 0 0 1 0 0 1 0 1 1 1 0 0 0 1

Вставим в информационное слово контрольные биты r0r4 таким образом, чтобы номера их позиций представляли собой целые степени двойки: 1, 2, 4, 8, 16… Получим 20-разрядное слово с 15 информационными и 5 контрольными битами. Первоначально контрольные биты устанавливаем равными нулю. На рисунке контрольные биты выделены розовым цветом.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
r0 r1 x1 r2 x2 x3 x4 r3 x5 x6 x7 x8 x9 x10 x11 r4 x12 x13 x14 x15
0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1

В общем случае количество контрольных бит в кодовом слове равно двоичному логарифму числа, на единицу большего, чем количество бит кодового слова (включая контрольные биты); логарифм округляется в большую сторону. Например, информационное слово длиной 1 бит требует двух контрольных разрядов, 2-, 3- или 4-битовое информационное слово — трёх, 5…11-битовое — четырёх, 12…26-битовое — пяти и т. д.

Добавим к таблице 5 строк (по количеству контрольных битов), в которые поместим матрицу преобразования. Каждая строка будет соответствовать одному контрольному биту (нулевой контрольный бит — верхняя строка, четвёртый — нижняя), каждый столбец — одному биту кодируемого слова. В каждом столбце матрицы преобразования поместим двоичный номер этого столбца, причём порядок следования битов будет обратный — младший бит расположим в верхней строке, старший — в нижней. Например, в третьем столбце матрицы будут стоять числа 11000, что соответствует двоичной записи числа три: 00011.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
r0 r1 x1 r2 x2 x3 x4 r3 x5 x6 x7 x8 x9 x10 x11 r4 x12 x13 x14 x15
0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 r0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 r1
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 r2
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 r3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 r4

В правой части таблицы мы оставили пустым один столбец, в который поместим результаты вычислений контрольных битов. Вычисление контрольных битов производим следующим образом. Берём одну из строк матрицы преобразования (например, r0) и находим её скалярное произведение с кодовым словом, то есть перемножаем соответствующие биты обеих строк и находим сумму произведений. Если произведение получилось больше единицы, находим остаток от его деления на 2. Иными словами, мы подсчитываем сколько раз в кодовом слове и соответствующей строке матрицы в одинаковых позициях стоят единицы и берём это число по модулю 2.

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

Полученные контрольные биты вставляем в кодовое слово вместо стоявших там ранее нулей. По аналогии находим проверочные биты в остальных строках. Кодирование по Хэммингу завершено. Полученное кодовое слово — 11110010001011110001.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
r0 r1 x1 r2 x2 x3 x4 r3 x5 x6 x7 x8 x9 x10 x11 r4 x12 x13 x14 x15
0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 r0 1
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 r1 1
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 r2 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 r3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 r4 1

Алгоритм декодирования[править | править вики-текст]

Алгоритм декодирования по Хэммингу абсолютно идентичен алгоритму кодирования. Матрица преобразования соответствующей размерности умножается на матрицу-столбец кодового слова и каждый элемент полученной матрицы-столбца берётся по модулю 2. Полученная матрица-столбец получила название «матрица синдромов». Легко проверить, что кодовое слово, сформированное в соответствии с алгоритмом, описанным в предыдущем разделе, всегда даёт нулевую матрицу синдромов.

Матрица синдромов становится ненулевой, если в результате ошибки (например, при передаче слова по линии связи с шумами) один из битов исходного слова изменил своё значение. Предположим для примера, что в кодовом слове, полученном в предыдущем разделе, шестой бит изменил своё значение с нуля на единицу (на рисунке обозначено красным цветом). Тогда получим следующую матрицу синдромов.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
r0 r1 x1 r2 x2 x3 x4 r3 x5 x6 x7 x8 x9 x10 x11 r4 x12 x13 x14 x15
1 1 1 1 0 1 1 0 0 0 1 0 1 1 1 1 0 0 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 s0 0
0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 s1 1
0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 s2 1
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 s3 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 s4 0

Заметим, что при однократной ошибке матрица синдромов всегда представляет собой двоичную запись (младший разряд в верхней строке) номера позиции, в которой произошла ошибка. В приведённом примере матрица синдромов (01100) соответствует двоичному числу 00110 или десятичному 6, откуда следует, что ошибка произошла в шестом бите.

Применение[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Коды Хемминга — "Все о Hi-Tech". all-ht.ru. Проверено 20 января 2016.

Литература[править | править вики-текст]

  • Питерсон У., Уэлдон Э. Коды, исправляющие ошибки: Пер. с англ. М.: Мир, 1976, 600 c.
  • Пенин П. Е., Филиппов Л. Н. Радиотехнические системы передачи информации. М.: Радио и Связь, 1984, 256 с.
  • Блейхут Р. Теория и практика кодов, контролирующих ошибки. Пер. с англ. М.: Мир, 1986, 576 с.