Хэмминг(7,4)

Код Хэмминга(7,4)
Код Хэмминга(7,4)
Назван в честь	Ричард В. Хэмминг
Классификация
Тип	Линейный блочный код
Длина блока	7
Длина сообщения	4
Ставка	4/7 ~ 0.571
Расстояние	3
Размер алфавита	2
Обозначения	[7,4,3] 2 -код
Характеристики
	идеальный код
	v ; т ; и ;

Графическое изображение 4 битов данных *от d* ₁ до d ₄ и 3 битов четности *от p* ₁ до p ₃ и того, какие биты четности применяются к каким битам данных.

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

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

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

Цель

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

Кусочек #	1	2	3	4	5	6	7
Передаваемый бит	$p_{1}$	$p_{2}$	$d_{1}$	$p_{3}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Да	Нет	Да	Нет	Да	Нет	Да
$p_{2}$	Нет	Да	Да	Нет	Нет	Да	Да
$p_{3}$	Нет	Нет	Нет	Да	Да	Да	Да

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

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

	$d_{1}$	$d_{2}$	$d_{3}$	$d_{4}$
$p_{1}$	Да	Да	Нет	Да
$p_{2}$	Да	Нет	Да	Да
$p_{3}$	Нет	Да	Да	Да

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

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

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

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

\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&1\\\end{pmatrix}}.

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

п ₁ покрывает д ₁ , д ₂ , д ₄
п ₂ покрывает д ₁ , д ₃ , д ₄
п ₃ покрывает д ₂ , д ₃ , д ₄

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

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

Четыре бита данных, собранные в вектор p , предварительно умножаются на G (т. е. Gp ) и берутся по модулю 2, чтобы получить передаваемое закодированное значение. Исходные 4 бита данных преобразуются в семь битов (отсюда и название «Хемминга (7,4)») с добавлением трех битов четности, чтобы обеспечить четность с использованием вышеуказанных покрытий битов данных. В первой таблице выше показано сопоставление каждого бита данных и бита четности с его конечной битовой позицией (от 1 до 7), но это также можно представить на диаграмме Венна . На первой диаграмме в этой статье показаны три кружка (по одному для каждого бита четности) и биты данных, которые охватывает каждый бит четности. Вторая диаграмма (показанная справа) идентична, но вместо этого отмечены позиции битов.

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

\mathbf {p} ={\begin{pmatrix}d_{1}\\d_{2}\\d_{3}\\d_{4}\\\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}

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

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

\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 :

\mathbf {r} =\mathbf {x}

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

\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&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 представляет собой нулевой вектор , получатель может заключить, что ошибки не произошло. Этот вывод основан на наблюдении, что когда вектор данных умножается на , изменение базиса в векторное подпространство, которое является ядром H. происходит G Пока во время передачи ничего не происходит, r останется в ядре H , и умножение даст нулевой вектор.

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

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

\mathbf {r} =\mathbf {x} +\mathbf {e} _{i}

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

\mathbf {e} _{2}={\begin{pmatrix}0\\1\\0\\0\\0\\0\\0\end{pmatrix}}

Таким образом, приведенное выше выражение означает ошибку в один бит в $i^{th}$ место.

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

\mathbf {Hr} =\mathbf {H} \left(\mathbf {x} +\mathbf {e} _{i}\right)=\mathbf {Hx} +\mathbf {He} _{i}

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

\mathbf {Hx} +\mathbf {He} _{i}=\mathbf {0} +\mathbf {He} _{i}=\mathbf {He} _{i}

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

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

\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}}

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

Сейчас,

\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 обнаружена ошибка, и ее можно исправить (просто перевернуть или инвертировать ее значение):

\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 :

\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 . Используя приведенный выше пример работы

\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}}

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

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

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

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

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

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

Данные $({\color {blue}d_{1}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})$	Хэмминг(7,4)		Хэмминга(7,4) с дополнительным битом четности (Хемминга(8,4))
	Передано $({\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 {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}})$	Диаграмма
0000	00 0 0 000		00 0 0 000 0
1000	11 1 0 000		11 1 0 000 1
0100	10 0 1 100		10 0 1 100 1
1100	01 1 1 100		01 1 1 100 0
0010	01 0 1 010		01 0 1 010 1
1010	10 1 1 010		10 1 1 010 0
0110	11 0 0 110		11 0 0 110 0
1110	00 1 0 110		00 1 0 110 1
0001	11 0 1 001		11 0 1 001 0
1001	00 1 1 001		00 1 1 001 1
0101	01 0 0 101		01 0 0 101 1
1101	10 1 0 101		10 1 0 101 0
0011	10 0 0 011		10 0 0 011 1
1011	01 1 0 011		01 1 0 011 0
0111	00 0 1 111		00 0 1 111 0
1111	11 1 1 111		11 1 1 111 1

Е ₇Решетка

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

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

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

Ссылки

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

Внешние ссылки

Задача программирования о коде Хэмминга (7,4)

[1] «История кодов Хэмминга» . Архивировано из оригинала 25 октября 2007 г. Проверено 3 апреля 2008 г.

[Conway-2] Конвей, Джон Х .; Слоан, Нил Дж. А. (1998). Сферические упаковки, решетки и группы (3-е изд.). Нью-Йорк: Springer-Verlag. ISBN 0-387-98585-9 .

[1]

[2]