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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален.
Найти источники: "Hamming (7,4)" - новости · газеты · книги · ученый · JSTOR ( июнь 2019 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

Хэмминга (7,4) -Код

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

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

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

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

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

Цель [ править ]

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

Кусочек #	1	2	3	4	5	6	7
Переданный бит	${\ displaystyle p_ {1}}$	${\ displaystyle p_ {2}}$	${\ displaystyle d_ {1}}$	${\ displaystyle p_ {3}}$	${\ displaystyle 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 должны выглядеть знакомо, поскольку они отображают биты данных в свои биты четности:

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

Остальные строки (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}}

Кодирование канала [ править ]

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

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

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

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

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

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

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

Проверка четности [ править ]

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

Исправление ошибок [ править ]

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

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

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

\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 на стандартный базисный вектор выбирает этот столбец H , мы знаем, что ошибка возникает в том месте, где встречается этот столбец H. $i^{th}$

Например, предположим, что мы ввели битовую ошибку в бит # 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}}

Ошибка в бите 5 вызывает плохую четность в красных и зеленых кругах.

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

Сейчас же,

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

Множественные битовые ошибки [ править ]

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

Нетрудно показать, что с помощью этой схемы можно исправить только однобитовые ошибки. В качестве альтернативы, коды Хэмминга могут использоваться для обнаружения одиночных и двойных битовых ошибок, просто отмечая, что произведение 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

Решетка E ₇[ править ]

Код Хэмминга (7,4) тесно связан с решеткой E 7 и, фактически, может быть использован для ее построения, или, точнее, ее двойственной решетки 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\}.

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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

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

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

[1]