Код Хэмминга

Коды Хемминга — простейшие линейные коды с минимальным расстоянием 3, то есть способные исправить одну ошибку. В коде Хемминга вводится понятие кодового расстояния $d(\cdot ,\cdot )$ (расстояния между двумя кодами), равного числу разрядов с неодинаковыми значениями. Возможности исправления ошибок связаны с минимальным кодовым расстоянием $d_{min}$. Исправляются ошибки кратности $r={\frac {ent(d_{min}-1)}{2}}$ и обнаруживаются ошибки кратности $d_{min}-1$ (здесь ent означает «целая часть»). Так, при контроле на нечетность $d_{min}=2$ и обнаруживаются одиночные ошибки. В коде Хемминга $d_{min}=3$. Дополнительно к информационным разрядам вводится $L=\log {2K}$ избыточных контролирующих разрядов, где $K$ — число информационных разрядов, $L$ округляется до ближайшего большего целого значения. $L$ - разрядный контролирующий код есть инвертированный результат поразрядного сложения (то есть сложения по модулю 2) номеров тех информационных разрядов, значения которых равны 1.

П р и м е р 1. Пусть имеем основной код 100110, то есть К = 6. Следовательно, L = 3 и дополнительный код равен

010 # 011 # 110 = 111,

где # — символ операции поразрядного сложения, и после инвертирования имеем 000. Теперь вместе с основным кодом будет передан и дополнительный. На приемном конце вновь рассчитывается дополнительный код и сравнивается с переданным. Фиксируется код сравнения (поразрядная операция отрицания равнозначности), и если он отличен от нуля, то его значение есть номер ошибочно принятого разряда основного кода. Так, если принят код 100010, то рассчитанный в приемнике дополнительный код равен инверсии от 010 # 110 = 100, то есть 011, что означает ошибку в 3-м разряде.

П р и м е р 2. Основной код 1100000, дополнительный код 110 (результат инверсии кода 110 # 111 = 001). Пусть принятый код 1101000, его дополнительный код 010, код сравнения 100, то есть ошибка в четвертом разряде.