Хэмминга (7,4) - Hamming(7,4)

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

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

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

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

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

Цель

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

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

Эта таблица описывает, какие биты четности покрывают переданные биты в закодированном слове. Например, п₂ обеспечивает четность для битов 2, 3, 6 и 7. Он также детализирует, какой переданный бит покрывается каким битом четности при чтении столбца. Например, d₁ покрывается п₁ и п₂ но нет п₃ Эта таблица будет иметь поразительное сходство с матрицей проверки на четность (ЧАС) в следующем разделе.

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

	${\displaystyle d_{1}}$	${\displaystyle d_{2}}$	${\displaystyle d_{3}}$	${\displaystyle d_{4}}$
${\displaystyle p_{1}}$	да	да	Нет	да
${\displaystyle p_{2}}$	да	Нет	да	да
${\displaystyle p_{3}}$	Нет	да	да	да

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

Таким образом, при правильном выборе покрытия битов четности все ошибки с расстоянием Хэмминга, равным 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&1\\\end{pmatrix}}.}$

Битовая позиция битов данных и четности

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

• п₁ охватывает d₁, d₂, d₄
• п₂ охватывает d₁, d₃, d₄
• п₃ охватывает d₂, d₃, d₄

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

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

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

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

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

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

Отображение в примере Икс. Четность красных, зеленых и синих кругов одинакова.

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

${\displaystyle \mathbf {x} =\mathbf {G} \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.

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

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

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

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

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

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

${\displaystyle \mathbf {r} =\mathbf {x} }$

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

${\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&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 это нулевой вектор, получатель может сделать вывод, что ошибки не было. Этот вывод основан на наблюдении, что когда вектор данных умножается на грамм, смена базиса происходит в векторное подпространство, которое является ядро из ЧАС. Если во время передачи ничего не происходит, р останется в ядре ЧАС и умножение даст нулевой вектор.

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

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

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

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

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

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

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

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

С Икс - это переданные данные, они безошибочны, и в результате продукт ЧАС и Икс равно нулю. Таким образом

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

Теперь продукт ЧАС с ${\displaystyle i^{th}}$ стандартный базисный вектор выбирает этот столбец ЧАС, мы знаем, что ошибка возникает в том месте, где этот столбец ЧАС происходит.

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

${\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 вызывает плохую четность в красных и зеленых кругах.

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

Сейчас же,

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

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

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

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

Расшифровка

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

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

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

Затем полученное значение, п_р, равно Rr. Используя рабочий пример сверху

${\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 (показаны синим текстом) с плохой четностью только в зеленом кружке (показаны красным текстом)

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

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

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

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

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

Данные ${\displaystyle ({\color {blue}d_{1}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})}$	Хэмминга (7,4)		Хэмминга (7,4) с дополнительным битом четности (Хэмминга (8,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}})}$	Диаграмма	Передано ${\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}})}$	Диаграмма
0000	0000000		00000000
1000	1110000		11100001
0100	1001100		10011001
1100	0111100		01111000
0010	0101010		01010101
1010	1011010		10110100
0110	1100110		11001100
1110	0010110		00101101
0001	1101001		11010010
1001	0011001		00110011
0101	0100101		01001011
1101	1010101		10101010
0011	1000011		10000111
1011	0110011		01100110
0111	0001111		00011110
1111	1111111		11111111

E₇ решетка

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

${\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₈ решетка. ^[2]

Рекомендации

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

внешняя ссылка

• Проблема программирования о коде Хэмминга (7,4)