Хэмминг(7,4)
Линейный код с исправлением ошибок
Код Хэмминга(7,4)
Назван в честьРичард В. Хэмминг
Классификация
ТипЛинейный блочный код
Длина блока7
Длина сообщения4
Ставка4/7 ~ 0,571
Расстояние3
Размер алфавита2
Обозначение[7,4,3] 2 -код
Характеристики
идеальный код
Графическое изображение 4 бит данных d 1 - d 4 и 3 бит четности p 1 - p 3 , а также какие биты четности применяются к каким битам данных

В теории кодирования Хэмминг (7,4) — это линейный код с исправлением ошибок , который кодирует четыре бита данных в семь бит путем добавления трех битов четности . Он является членом большего семейства кодов Хэмминга , но термин «код Хэмминга» часто относится к этому конкретному коду, который Ричард В. Хэмминг представил в 1950 году. В то время Хэмминг работал в Bell Telephone Laboratories и был разочарован подверженным ошибкам считывателем перфокарт , поэтому он начал работать над кодами с исправлением ошибок. [1]

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

В квантовой информации код Хэмминга (7,4) используется в качестве основы для кода Стина , типа CSS-кода, используемого для квантовой коррекции ошибок .

Цель

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

Кусочек #1234567
Передаваемый бит п 1 {\displaystyle p_{1}} п 2 {\displaystyle p_{2}} г 1 {\displaystyle d_{1}} п 3 {\displaystyle p_{3}} г 2 {\displaystyle d_{2}} г 3 {\displaystyle d_{3}} г 4 {\displaystyle d_{4}}
п 1 {\displaystyle p_{1}} ДаНетДаНетДаНетДа
п 2 {\displaystyle p_{2}} НетДаДаНетНетДаДа
п 3 {\displaystyle p_{3}} НетНетНетДаДаДаДа

В этой таблице описывается, какие биты четности покрывают какие переданные биты в закодированном слове. Например, p 2 обеспечивает четную четность для битов 2, 3, 6 и 7. Она также детализирует, какой переданный бит покрыт каким битом четности, путем чтения столбца. Например, d 1 покрывается p 1 и p 2, но не p 3. Эта таблица будет иметь поразительное сходство с матрицей проверки четности ( H ) в следующем разделе.

Более того, если бы столбцы четности в приведенной выше таблице были удалены

г 1 {\displaystyle d_{1}} г 2 {\displaystyle d_{2}} г 3 {\displaystyle d_{3}} г 4 {\displaystyle d_{4}}
п 1 {\displaystyle p_{1}} ДаДаНетДа
п 2 {\displaystyle p_{2}} ДаНетДаДа
п 3 {\displaystyle p_{3}} НетДаДаДа

то сходство со строками 1, 2 и 4 матрицы генератора кода ( G ) ниже также будет очевидным.

Таким образом, правильно выбрав покрытие битами четности, можно обнаружить и исправить все ошибки с расстоянием Хэмминга, равным 1, что и является смыслом использования кода Хэмминга.

Матрицы Хэмминга

Коды Хэмминга можно вычислить в терминах линейной алгебры через матрицы , поскольку коды Хэмминга являются линейными кодами . Для кодов Хэмминга можно определить две матрицы Хэмминга : матрицу генератора кода G и матрицу проверки на четность H :

Г Т := ( 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 ) , ЧАС := ( 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 ) . {\displaystyle \mathbf {G^{T}} :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}},\qquad \mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1\\\end{pmatrix}}.}
Положение битов данных и битов четности

Как упоминалось выше, строки 1, 2 и 4 G должны выглядеть знакомо, поскольку они сопоставляют биты данных с их битами четности:

  • p 1 охватывает d 1 , d 2 , d 4
  • p 2 охватывает d 1 , d 3 , d 4
  • p 3 охватывает d 2 , d 3 , d 4

Оставшиеся строки (3, 5, 6, 7) отображают данные в их положение в закодированной форме, и в этой строке есть только 1, поэтому это идентичная копия. Фактически, эти четыре строки линейно независимы и образуют матрицу идентичности (по замыслу, а не по совпадению).

Также, как упоминалось выше, три строки H должны быть знакомы. Эти строки используются для вычисления вектора синдрома на принимающей стороне, и если вектор синдрома является нулевым вектором (все нули), то полученное слово не содержит ошибок; если не ноль, то значение указывает, какой бит был инвертирован.

Четыре бита данных — собранные как вектор p — предварительно умножаются на G (т. е. ) и берутся по модулю 2 для получения закодированного значения, которое передается. Исходные 4 бита данных преобразуются в семь бит (отсюда и название «Хэмминг (7,4)») с тремя битами четности, добавленными для обеспечения четности с использованием указанных выше покрытий битов данных. Первая таблица выше показывает отображение между каждым битом данных и четностью в его конечную позицию бита (от 1 до 7), но это также можно представить в виде диаграммы Венна . Первая диаграмма в этой статье показывает три круга (по одному для каждого бита четности) и охватывает биты данных, которые покрывает каждый бит четности. Вторая диаграмма (показанная справа) идентична, но вместо этого отмечены позиции битов. Г Т п {\displaystyle G^{T}p}

В оставшейся части этого раздела в качестве рабочего примера будут использоваться следующие 4 бита (показанные как вектор-столбец):

п = ( г 1 г 2 г 3 г 4 ) = ( 1 0 1 1 ) {\displaystyle \mathbf {p} ={\begin{pmatrix}d_{1}\\d_{2}\\d_{3}\\d_{4}\\\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}}

Канальное кодирование

Отображение в примере x . Четность красного, зеленого и синего кругов четная.

Предположим, что мы хотим передать эти данные ( 1011) по шумному каналу связи . В частности, двоичный симметричный канал означает, что искажение ошибок не благоприятствует ни нулю, ни единице (он симметричен в возникновении ошибок). Кроме того, все исходные векторы предполагаются равновероятными. Мы берем произведение G и p , с элементами по модулю 2, чтобы определить переданное кодовое слово x :

х = Г Т п = ( 1 1 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 1 ) ( 1 0 1 1 ) = ( 2 3 1 2 0 1 1 ) = ( 0 1 1 0 0 1 1 ) {\displaystyle \mathbf {x} =\mathbf {G^{T}} \mathbf {p} ={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}2\\3\\1\\2\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}}

Это означает, что 0110011вместо передачи будет передаваться 1011.

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

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

  • красный круг имеет две единицы
  • в зеленом круге две единицы
  • в синем круге четыре единицы

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

Проверка четности

Если во время передачи не произошло ошибок, то полученное кодовое слово r идентично переданному кодовому слову x :

г = х {\displaystyle \mathbf {r} =\mathbf {x} }

Приемник умножает H и r, чтобы получить вектор синдрома z , который указывает, произошла ли ошибка, и если да, то для какого бита кодового слова. Выполнение этого умножения (снова, записи по модулю 2):

з = ЧАС г = ( 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 ) ( 0 1 1 0 0 1 1 ) = ( 2 4 2 ) = ( 0 0 0 ) {\displaystyle \mathbf {z} =\mathbf {H} \mathbf {r} ={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}2\\4\\2\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}}

Поскольку синдром z является нулевым вектором , получатель может сделать вывод, что ошибки не произошло. Этот вывод основан на наблюдении, что при умножении вектора данных на G происходит изменение базиса в векторное подпространство, которое является ядром H. Пока ничего не происходит во время передачи, r останется в ядре H , а умножение даст нулевой вектор.

Исправление ошибок

В противном случае, предположим, мы можем написать

г = х + е я {\displaystyle \mathbf {r} =\mathbf {x} +\mathbf {e} _ {i}}

по модулю 2, где e i — единичный вектор , то есть нулевой вектор с 1 в , считая от 1. я т час {\displaystyle i_{й}} я т час {\displaystyle я^{й}}

е 2 = ( 0 1 0 0 0 0 0 ) {\displaystyle \mathbf {e} _{2}={\begin{pmatrix}0\\1\\0\\0\\0\\0\\0\end{pmatrix}}}

Таким образом, приведенное выше выражение означает ошибку в одном бите . я т час {\displaystyle я^{й}}

Теперь, если мы умножим этот вектор на H :

ЧАС г = ЧАС ( х + е я ) = ЧАС х + ЧАС е я {\displaystyle \mathbf {Hr} =\mathbf {H} \left(\mathbf {x} +\mathbf {e} _{i}\right)=\mathbf {Hx} +\mathbf {He} _{i}}

Поскольку x — это переданные данные, то они не содержат ошибок, и, как следствие, произведение H и x равно нулю. Таким образом

ЧАС х + ЧАС е я = 0 + ЧАС е я = ЧАС е я {\displaystyle \mathbf {Hx} +\mathbf {He} _{i}=\mathbf {0} +\mathbf {He} _{i}=\mathbf {He} _{i}}

Теперь, когда произведение H со стандартным базисным вектором выбирает этот столбец H , мы знаем, что ошибка возникает в том месте, где находится этот столбец H. i t h {\displaystyle i^{th}}

Например, предположим, что мы внесли битовую ошибку в бит №5.

r = x + e 5 = ( 0 1 1 0 0 1 1 ) + ( 0 0 0 0 1 0 0 ) = ( 0 1 1 0 1 1 1 ) {\displaystyle \mathbf {r} =\mathbf {x} +\mathbf {e} _{5}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}+{\begin{pmatrix}0\\0\\0\\0\\1\\0\\0\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}}
Ошибка в бите 5 приводит к плохой четности в красном и зеленом кругах.

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

Сейчас,

z = H r = ( 1 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 ) ( 0 1 1 0 1 1 1 ) = ( 3 4 3 ) = ( 1 0 1 ) {\displaystyle \mathbf {z} =\mathbf {Hr} ={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}3\\4\\3\end{pmatrix}}={\begin{pmatrix}1\\0\\1\end{pmatrix}}}

что соответствует пятому столбцу H. Кроме того, используемый общий алгоритм ( см. Код Хэмминга#Общий алгоритм ) был намеренно построен таким образом, что синдром 101 соответствует двоичному значению 5, что указывает на то, что пятый бит был поврежден. Таким образом, ошибка была обнаружена в бите 5 и может быть исправлена ​​(просто переверните или отмените его значение):

r corrected = ( 0 1 1 0 1 ¯ 1 1 ) = ( 0 1 1 0 0 1 1 ) {\displaystyle \mathbf {r} _{\text{corrected}}={\begin{pmatrix}0\\1\\1\\0\\{\overline {1}}\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}}

Это исправленное полученное значение действительно теперь соответствует переданному значению x сверху.

Расшифровка

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

Сначала определим матрицу R :

R = ( 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 ) {\displaystyle \mathbf {R} ={\begin{pmatrix}0&0&1&0&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{pmatrix}}}

Тогда полученное значение p r равно Rr . Используя приведенный выше пример выполнения

p r = ( 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 ) ( 0 1 1 0 0 1 1 ) = ( 1 0 1 1 ) {\displaystyle \mathbf {p_{r}} ={\begin{pmatrix}0&0&1&0&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}}

Множественные ошибки битов

Введены битовые ошибки в битах 4 и 5 (показаны синим текстом) с плохой четностью только в зеленом круге (показаны красным текстом)

Нетрудно показать, что с помощью этой схемы можно исправить только ошибки в одиночных битах. В качестве альтернативы коды Хэмминга можно использовать для обнаружения ошибок в одиночных и двойных битах, просто отметив, что произведение H не равно нулю всякий раз, когда происходят ошибки. На соседней диаграмме биты 4 и 5 были перевернуты. Это дает только один круг (зеленый) с недействительной четностью, но ошибки не подлежат восстановлению.

Однако код Хэмминга (7,4) и подобные коды Хэмминга не могут различать однобитовые и двухбитовые ошибки. То есть двухбитовые ошибки выглядят так же, как однобитовые ошибки. Если исправление ошибок выполняется для двухбитовой ошибки, результат будет неверным.

Аналогично, коды Хэмминга не могут обнаружить или восстановиться после произвольной трехбитовой ошибки. Рассмотрим схему: если бы бит в зеленом круге (окрашенный в красный цвет) был равен 1, проверка четности вернула бы нулевой вектор, что указывает на отсутствие ошибки в кодовом слове.

Все кодовые слова

Поскольку источник содержит только 4 бита, то возможно передать только 16 слов. Включено восьмибитное значение, если используется дополнительный бит четности ( см. код Хэмминга (7,4) с дополнительным битом четности ). (Биты данных показаны синим цветом; биты четности показаны красным; а дополнительный бит четности показан зеленым.)

Данные
( d 1 , d 2 , d 3 , d 4 ) {\displaystyle ({\color {blue}d_{1}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})} 		Хэмминг(7,4)Хэмминг(7,4) с дополнительным битом четности (Хэмминг(8,4))
Передано
( p 1 , p 2 , d 1 , p 3 , d 2 , d 3 , d 4 ) {\displaystyle ({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})} 		ДиаграммаПередано
( p 1 , p 2 , d 1 , p 3 , d 2 , d 3 , d 4 , p 4 ) {\displaystyle ({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}},{\color {green}p_{4}})} 		Диаграмма
000000 0 0 000Код Хэмминга для 0000 становится 000000000 0 0 000 0Код Хэмминга для 0000 становится 0000000 с дополнительным битом четности 0
100011 1 0 000Код Хэмминга для 1000 становится 111000011 1 0 000 1Код Хэмминга для 1000 становится 1110000 с дополнительным битом четности 1
010010 0 1 100Код Хэмминга для 0100 становится 100110010 0 1 100 1Код Хэмминга для 0100 становится 1001100 с дополнительным битом четности 1
110001 1 1 100Код Хэмминга для 1100 становится 011110001 1 1 100 0Код Хэмминга для 1100 становится 0111100 с дополнительным битом четности 0
001001 0 1 010Код Хэмминга для 0010 становится 010101001 0 1 010 1Код Хэмминга для 0010 становится 0101010 с дополнительным битом четности 1
101010 1 1 010Код Хэмминга для 1010 становится 101101010 1 1 010 0Код Хэмминга для 1010 становится 1011010 с дополнительным битом четности 0
011011 0 0 110Код Хэмминга для 0110 становится 110011011 0 0 110 0Код Хэмминга для 0110 становится 1100110 с дополнительным битом четности 0
111000 1 0 110Код Хэмминга для 1110 становится 001011000 1 0 110 1Код Хэмминга для 1110 становится 0010110 с дополнительным битом четности 1
000111 0 1 001Код Хэмминга для 0001 становится 110100111 0 1 001 0Код Хэмминга для 0001 становится 1101001 с дополнительным битом четности 0
100100 1 1 001Код Хэмминга для 1001 становится 001100100 1 1 001 1Код Хэмминга для 1001 становится 0011001 с дополнительным битом четности 1
010101 0 0 101Код Хэмминга для 0101 становится 010010101 0 0 101 1Код Хэмминга для 0101 становится 0100101 с дополнительным битом четности 1
110110 1 0 101Код Хэмминга для 1101 становится 101010110 1 0 101 0Код Хэмминга для 1101 становится 1010101 с дополнительным битом четности 0
001110 0 0 011Код Хэмминга для 0011 становится 100001110 0 0 011 1Код Хэмминга для 0011 становится 1000011 с дополнительным битом четности 1
101101 1 0 011Код Хэмминга для 1011 становится 011001101 1 0 011 0Код Хэмминга для 1011 становится 0110011 с дополнительным битом четности 0
011100 0 1 111Код Хэмминга для 0111 становится 000111100 0 1 111 0Код Хэмминга для 0111 становится 0001111 с дополнительным битом четности 0
111111 1 1 111Код Хэмминга для 1111 становится 111111111 1 1 111 1Код Хэмминга для 1111 становится 1111111 с дополнительным битом четности 1

Э7решетка

Код Хэмминга(7,4) тесно связан с решеткой E 7 и, по сути, может быть использован для ее построения или, точнее, ее дуальной решетки E 7 ∗ (аналогичная конструкция для E 7 использует дуальный код [7,3,4] 2 ). В частности, взятие множества всех векторов x в Z 7 с x , конгруэнтным (по модулю 2), кодовому слову Хэмминга(7,4) и масштабирование на 1/ √ 2 дает решетку E 7 ∗

E 7 ∗ = 1 2 { x ∈ Z 7 : x mod 2 ∈ [ 7 , 4 , 3 ] 2 } . {\displaystyle E_{7}^{*}={\tfrac {1}{\sqrt {2}}}\left\{x\in \mathbb {Z} ^{7}:x{\bmod {2}}\in [7,4,3]_{2}\right\}.}

Это частный случай более общей связи между решетками и кодами. Например, расширенный (8,4)-код Хэмминга, который возникает из добавления бита четности, также связан с решеткой E 8 . [2]

Ссылки

  1. ^ "История кодов Хэмминга". Архивировано из оригинала 2007-10-25 . Получено 2008-04-03 .
  2. ^ Конвей, Джон Х .; Слоан, Нил JA (1998). Упаковки сфер, решетки и группы (3-е изд.). Нью-Йорк: Springer-Verlag. ISBN 0-387-98585-9.


  • Задача программирования о коде Хэмминга(7,4)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Hamming(7,4)&oldid=1269897791"