Коды Хемминга

Код Хемминга – это блочный код, позволяющий исправлять одиночные и фиксировать двойные ошибки, разработанный Ричардом Хеммингом в сороковых годах прошлого столетия.

В то время он работал в лаборатории Белла на электромеханической счетной машине Bell Model V. Ввод данных в эту машину осуществлялся с помощью перфокарт. Это была самая ненадежная часть вычислительной машины. Перфокарты часто считывались неправильно. Исправление и обнаружение ошибок ввода данных отнимало огромное количество времени, а пропущенные ошибки могли привести к неверным результатам работы.

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

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

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

Если длина информационного блока, который требуется закодировать - m бит. Количество контрольных бит, используемых для его кодирования, – k, то закодированный блок будет иметь длину: n = m+k бит. Для каждого блока такой длины возможны n различных комбинаций, содержащих ошибку.

Таким образом, для каждого передаваемого информационного блока может существовать n–блоков, содержащих однократную ошибку, и один блок - без ошибок. Следовательно, максимальное количество различных закодированных блоков, содержащих не больше одной ошибки, будет: 2^m(n+1), где n = m+k.

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

Следовательно, минимальное количество контрольных бит, необходимых для исправления однократной ошибки, определяется из равенства:

2^m * (n+1)=2ⁿ

Учитывая, что n = m + k, получаем:

k=2^k – m – 1

Так как количество бит должно быть целым числом, то k, вычисленное с помощью этого уравнения, необходимо округлить до ближайшего большего целого числа.

Например, для информационных данных длиной 7 необходимо 4 контрольных бита, чтобы обеспечить исправление однократных ошибок, а для данных длинной 128 бит необходимо 8 контрольных бит.

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

Все биты, порядковые номера которых являются степенью двойки, – это контрольные разряды. То есть если порядковый номер бита обозначить символом ‘n’, то для контрольных бит должно быть справедливо равенство: n=2^k , где к – любое положительное целое число.

Например, для закодированной последовательности длиной 13 бит проверочными будут: 1, 2, 4 и 8 биты, так как 2⁰ = 1, 2¹ = 2, 2² = 4, 2³ = 8.

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

Для того, чтобы определить какими контрольными битами контролируют бит, необходимо разложить его порядковый номер по степени 2. Таким образом, девятый бит будет контролироваться битами 1 и 8, так как 9 = 2⁰ + 2³ = 1 + 8.

Рассмотрим пример кодирования бинарной последовательности данных, состоящей из семи элементов: 1001101.

1. Определим необходимое количество контрольных разрядов. Расчет будем вести по формуле: k = 2^k – m – 1, где k – количество контрольных разрядов, m – количество информационных разрядов. Так как количество бит должно быть целым числом, то k, вычисленное с помощью этого уравнения, необходимо округлить до ближайшего большего целого числа.

Результат расчета приведен ниже:

Таким образом, число контрольных бит - 4.

2. Определим расположение проверочных бит в результирующей закодированной последовательности. Обозначим информационные биты символом И, а контрольные биты символом П. Индекс около этих символов будет означать их порядковый номер в закодированной последовательности.

Контрольные биты будут занимать четыре позиции с порядковыми номерами, равными степени двойки: 2⁰, 2¹, 2², 2³ => 1,2,4,8.

Размещение информационных и контрольных бит в результирующей последовательности будет следующим:

Осталось определить значения проверочных бит.

3. Определим, какие группы контролируют проверочные биты. Для этого разложим порядковые номера информационных бит по степени двойки:

И₃: 3 = 2⁰ + 2¹ = 1 + 2 => Информационный бит И₃ проверяется контрольными битами П₁ и П₂.

И₅: 5 = 2⁰ + 2² = 1 + 4 => Информационный бит И₅ проверяется контрольными битами П₁ и П₄.

И₆: 6 = 2¹ + 2² = 2 + 4 => Информационный бит И₆ проверяется контрольными битами П₂ и П₄.

И₇: 7 = 2⁰ + 2¹ + 2² = 1 + 2 + 4 => Информационный бит И₇ проверяется контрольными битами П₁, П₂ и П₄.

И₉: 9 = 2⁰ + 2³ = 1 + 8 => Информационный бит И₉ проверяется контрольными битами П₁ и П₈.

И₁₀: 10 = 2¹ + 2³ = 2 + 8 => Информационный бит И₁₀ проверяется контрольными битами П₂ и П₈.

И₁₁: 11 = 2⁰ + 2¹ + 2³ = 1 + 2 + 8 => Информационный бит И₁₁ проверяется контрольными битами П₁, П₂ и П₈.

4. Рассчитаем значения контрольных бит. Для этого определим группы для всех контрольных бит, просуммируем их по модулю два, а результат запишем в соответствующие контрольные биты (дополним группы до четности единиц):

П₁ = И₃ + И₅ + И₇ + И₉ + И₁₁ = 1 + 0 + 1 + 1 + 1 = 0

П₂ = И₃ + И₆ + И₇ + И₁₀ + И₁₁= 1 + 0 + 1 + 0 + 1 = 1

П₄ = И₅ + И₆ + И₇ = 0 + 0 + 1 = 1

П₈ = И₉ + И₁₀ + И₁₁ = 1 + 0 + 1 = 0

Таким образом, закодированная последовательность будет иметь следующий вид:

1. Проверим на четность единиц все группы, контролируемые проверочными разрядами:

П₁: П₁ + И₃ + И₅ + И₇ + И₉ + И₁₁ = 0 + 1 + 0 + 1 + 1 + 1 = 0 0

П₂: П₂ + И₃ + И₆ + И₇ + И₁₀ + И₁₁ = 1 + 1 + 1 + 1 + 0 + 1 = 1 0

П₄: П₄ + И₅ + И₆ + И₇ = 1 + 0 + 1 + 1 = 1 0

П₈: П₈ + И₉ + И₁₀ + И₁₁ = 0 + 1 + 0 + 1 = 0 0

Так как проверка четности единиц не прошла для групп контрольных битов П₂ и П₄, то ошибка содержится в битах, принадлежащих этим группам. Алгоритм Хемминга позволяет исправлять только одну ошибку, поэтому будем искать неисправность, исходя из предположения, что могла произойти только одна ошибка. Если это предположение - неверно, то все попытки исправить данные только привнесут дополнительные искажения информации.

Итак, если ошибка была только одна, то она должна быть в одном из битов, принадлежащих обеим группам. Это биты И₆ и И₇.

Для того, чтобы уточнить, в каком именно бите произошла ошибка, обратимся к группам, в которых проверка на четность прошла успешно, а, следовательно, в этих группах все биты - корректны. Как видите, к одной из исправных групп принадлежит бит И₇, а, следовательно, он верен.

Таким образом, очевидно, что ошибка произошла в бите И₆, и, инвертировав его значение, мы восстановим принятые данные.

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

Если предположить, что количество ошибок - не более двух, то:

- Данные верны, если во всех контрольных группах количество единиц - четное, и общее количество единиц - тоже четное.

- Произошла однократная ошибка, если в некоторых контрольных группах количество единиц - нечетное, и общее количество единиц - нечетное.

- Ошибка в дополнительном контрольном разряде, если во всех контрольных группах количество единиц - четное, а общее количество единиц - нечетное.

- Двойная ошибка, если в некоторых контрольных группах количество единиц - нечетное, а общее количество единиц - четное.

Как видите, алгоритм коррекции ошибок Хемминга - достаточно прост и надежен. При этом эффективность кода растет при увеличении информационных блоков. Так, для кодирования 7 бит данных избыточность составляет чуть больше 57%, для кодирования 256 бит избыточность будет 3.5%, а для 1024 – 1%.

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