Код Хэмминга

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

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

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

С математической точки зрения коды Хэмминга - это класс двоичных линейных кодов. Для каждого целого числа $r \geq 2$ существует код с длиной блока $n = 2 r - 1$ и длиной сообщения $k = 2 r - r - 1$ . Следовательно, скорость кодов Хэмминга равна $R = k / n = 1 - r / (2 r - 1)$ , что является наивысшим возможным для кодов с минимальным расстоянием, равным трем (т. Е. Минимальное количество смен битов, необходимых для перехода от любого кодовое слово для любого другого кодового слова - три) и длина блока $2 г - 1$ .Проверочная матрицакода Хэмминга строится путем перечисления всех столбцов длины $г$ , которые отличны от нуля, что означаетчтодвойственный кодкода Хэмминга являетсясокращенный код Адамара. Матрица проверки на четность обладает тем свойством, что любые два столбца попарнолинейно независимы.

Из-за ограниченной избыточности, которую коды Хэмминга добавляют к данным, они могут обнаруживать и исправлять ошибки только при низком уровне ошибок. Это случай компьютерной памяти (обычно ОЗУ), где битовые ошибки чрезвычайно редки и широко используются коды Хэмминга, а ОЗУ с этой системой исправления представляет собой ОЗУ с ECC ( память ECC ). В этом контексте часто используется расширенный код Хэмминга, имеющий один дополнительный бит четности. Расширенные коды Хэмминга достигают расстояния Хэмминга, равного четырем, что позволяет декодеру различать, когда возникает не более одной однобитовой ошибки, и когда возникают любые двухбитовые ошибки. В этом смысле расширенные коды Хэмминга предназначены для исправления одиночной ошибки и обнаружения двойной ошибки, сокращенно SECDED .

История [ править ]

Ричард Хэмминг , изобретатель кодов Хэмминга, работал в Bell Labs в конце 1940-х годов над компьютером Bell Model V , машиной на основе электромеханического реле с временем цикла в секундах. Вход подавался на перфорированную бумажную ленту шириной семь восьмых дюйма, в которой было до шести отверстий в ряду. В будние дни при обнаружении ошибок в реле машина останавливалась и мигала, чтобы операторы могли исправить проблему. В нерабочее время и в выходные дни, когда не было операторов, машина просто переходила к следующему заданию.

Хэмминг работал по выходным и все больше разочаровывался в необходимости перезапускать свои программы с нуля из-за обнаруженных ошибок. В записанном на пленку интервью Хэмминг сказал: «И поэтому я сказал:« Черт побери, если машина может обнаружить ошибку, почему она не может определить местоположение ошибки и исправить ее? »». ^[3] В течение следующих нескольких лет он работал над проблемой исправления ошибок, разрабатывая все более мощный набор алгоритмов. В 1950 году он опубликовал то, что теперь известно как код Хэмминга, который до сих пор используется в таких приложениях, как память ECC .

Коды, предшествующие Хэммингу [ править ]

До кодов Хэмминга использовался ряд простых кодов обнаружения ошибок, но ни один из них не был так эффективен, как коды Хэмминга, в том же объеме.

Четность [ править ]

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

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

Код два из пяти [ править ]

Код два из пяти - это схема кодирования, которая использует пять битов, состоящих ровно из трех нулей и двух единиц. Это дает десять возможных комбинаций, достаточных для представления цифр 0–9. Эта схема может обнаруживать все одиночные битовые ошибки, все битовые ошибки с нечетными номерами и некоторые битовые ошибки с четными номерами (например, переворачивание обоих 1-битов). Однако он по-прежнему не может исправить ни одну из этих ошибок.

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

Другой используемый в то время код повторял каждый бит данных несколько раз, чтобы гарантировать, что он был отправлен правильно. Например, если бит данных, который должен быть отправлен, равен 1, код повторения n = 3 отправит 111. Если три полученных бита не идентичны, во время передачи произошла ошибка. Если канал достаточно чистый, большую часть времени в каждой тройке будет изменяться только один бит. Следовательно, 001, 010 и 100 соответствуют 0 биту, а 110, 101 и 011 соответствуют 1 биту, причем большее количество одинаковых цифр ('0' или '1') указывает, что бит данных должен быть. Код с этой способностью восстанавливать исходное сообщение при наличии ошибок известен как исправляющий ошибки.код. Этот код с тройным повторением представляет собой код Хэмминга с m = 2, поскольку имеется два бита четности, а 2 ² - 2 - 1 = 1 бит данных.

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

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

Коды Хэмминга [ править ]

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

Хэмминг изучил существующие схемы кодирования, в том числе две из пяти, и обобщил их концепции. Для начала он разработал номенклатуру для описания системы, включая количество битов данных и битов исправления ошибок в блоке. Например, четность включает в себя один бит для любого слова данных, поэтому, принимая слова ASCII с семью битами, Хэмминг описал это как код (8,7) с восемью битами всего, из которых семь являются данными. Пример повторения будет (3,1) , следуя той же логике. Скорость кода является второе число делится на первый, для нашего примера повторения, 1/3.

Хэмминг также заметил проблемы с переворачиванием двух или более битов и описал это как «расстояние» (теперь оно называется расстоянием Хэмминга , после него). Четность имеет расстояние 2, поэтому одно изменение битов может быть обнаружено, но не исправлено, и любые два изменения битов будут невидимы. Повторение (3,1) имеет расстояние 3, так как три бита необходимо перевернуть в одной и той же тройке, чтобы получить другое кодовое слово без видимых ошибок. Он может исправлять однобитовые ошибки или обнаруживать, но не исправлять, двухбитовые ошибки. Повторение (4,1) (каждый бит повторяется четыре раза) имеет расстояние 4, поэтому переворот трех битов можно обнаружить, но не исправить. Когда три бита в одной группе меняются местами, могут возникнуть ситуации, когда попытка исправить приведет к неправильному кодовому слову. В общем случае код с расстоянием kможет обнаруживать, но не исправлять k - 1 ошибок.

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

Общий алгоритм [ править ]

Следующий общий алгоритм генерирует код исправления одиночных ошибок (SEC) для любого количества битов. Основная идея состоит в том, чтобы выбрать исправляющие ошибки биты так, чтобы индекс-XOR ( XOR всех битовых позиций, содержащих 1) был равен 0. Мы используем позиции 1, 10, 100 и т. Д. (В двоичном формате) в качестве ошибки. -исправляющие биты, что гарантирует, что можно установить исправляющие ошибки биты так, чтобы индекс-XOR всего сообщения был 0. Если получатель получает строку с индексом-XOR 0, они могут сделать вывод, что повреждений не было, и в противном случае index-XOR указывает индекс поврежденного бита.

Алгоритм можно вывести из следующего описания:

Пронумеруйте биты, начиная с 1: биты 1, 2, 3, 4, 5, 6, 7 и т. Д.
Запишите битовые числа в двоичном формате: 1, 10, 11, 100, 101, 110, 111 и т. Д.
Все битовые позиции, которые являются степенями двойки (имеют один бит 1 в двоичной форме их позиции), являются битами четности: 1, 2, 4, 8 и т. Д. (1, 10, 100, 1000)
Все остальные битовые позиции с двумя или более 1 битами в двоичной форме их позиции являются битами данных.
Каждый бит данных включен в уникальный набор из 2 или более битов четности, что определяется двоичной формой его битовой позиции.
1. Бит четности 1 охватывает все битовые позиции, для которых установлен младший значащий бит: бит 1 (сам бит четности), 3, 5, 7, 9 и т. Д.
2. Бит четности 2 охватывает все битовые позиции, в которых установлен второй младший бит: биты 2-3, 6-7, 10-11 и т. Д.
3. Бит четности 4 охватывает все битовые позиции, для которых установлен третий младший бит: биты 4–7, 12–15, 20–23 и т. Д.
4. Бит четности 8 охватывает все битовые позиции, для которых установлен четвертый младший бит: биты 8–15, 24–31, 40–47 и т. Д.
5. В общем, каждый бит четности охватывает все биты, в которых поразрядное И позиции четности и позиция бита не равны нулю.

Если кодируемый байт данных равен 10011010, то слово данных (с использованием _ для представления битов четности) будет __1_001_1010, а кодовое слово - 011100101010.

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

Это общее правило можно показать наглядно:

Биты закодированных данных		p1	p2	d1	p4	d2	d3	d4	p8	d5	d6	d7	d8	d9	d10	d11	p16	d12	d13	d14	d15
Битовая позиция		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	…
Покрытие битов четности	p1
	p2
	p4
	p8
	p16

Показаны только 20 закодированных битов (5 битов по четности, 15 данных), но шаблон продолжается бесконечно. Ключевой особенностью кодов Хэмминга, которую можно увидеть при визуальном осмотре, является то, что любой заданный бит включен в уникальный набор битов четности. Чтобы проверить наличие ошибок, проверьте все биты четности. Шаблон ошибок, называемый синдромом ошибки , определяет бит с ошибкой. Если все биты четности верны, ошибки нет. В противном случае сумма позиций ошибочных битов четности идентифицирует ошибочный бит. Например, если биты четности в позициях 1, 2 и 8 указывают на ошибку, то бит 1 + 2 + 8 = 11 является ошибочным. Если только один бит четности указывает на ошибку, сам бит четности ошибочен.

Как видите, если у вас есть $m$ битов четности, они могут охватывать биты от 1 до . Если мы вычтем биты четности, у нас останутся биты, которые мы можем использовать для данных. При изменении $m$ мы получаем все возможные коды Хэмминга: ${\ displaystyle 2 ^ {m} -1}$ ${\ displaystyle 2 ^ {m} -m-1}$

Биты четности	Всего бит	Биты данных	Имя	Ставка
2	3	1	Хэмминга (3,1) ( код тройного повторения )	1/3 ≈ 0,333
3	7	4	Хэмминга (7,4)	4/7 ≈ 0,571
4	15	11	Хэмминга (15,11)	11/15 ≈ 0,733
5	31 год	26	Хэмминга (31,26)	26/31 ≈ 0,839
6	63	57	Хэмминга (63,57)	57/63 ≈ 0,905
7	127	120	Хэмминг (127,120)	120/127 ≈ 0,945
8	255	247	Хэмминг (255 247)	247/255 ≈ 0,969
…
$м$	${\ displaystyle n = 2 ^ {m} -1}$	${\ Displaystyle к = 2 ^ {м} -м-1}$	Hamming ${\ displaystyle (2 ^ {m} -1,2 ^ {m} -m-1)}$	${\ displaystyle (2 ^ {m} -m-1) / (2 ^ {m} -1)}$

Коды Хэмминга с дополнительной четностью (SECDED) [ править ]

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

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

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

Этот расширенный код Хэмминга популярен в системах компьютерной памяти ^{[ необходима цитата ]} , где он известен как SECDED (сокращенно от исправления одиночных ошибок, обнаружения двойных ошибок ) ^{[ необходима цитата ]} . Особенно популярен код (72,64), усеченный (127,120) код Хэмминга плюс дополнительный бит четности ^{[ необходима цитата ]} , который имеет такие же накладные расходы на пространство, как и код четности (9,8).

[7,4] Код Хэмминга [ править ]

Графическое изображение четырех битов данных и трех битов четности и того, какие биты четности применяются к каким битам данных

В 1950 году Хэмминг ввел код Хэмминга [7,4]. Он кодирует четыре бита данных в семь битов, добавляя три бита четности. Он может обнаруживать и исправлять однобитовые ошибки. С добавлением общего бита четности он также может обнаруживать (но не исправлять) двухбитовые ошибки.

Построение G и H [ править ]

Матрица называется (канонической) образующей матрицей линейного ( n , k ) кода, ${\ displaystyle \ mathbf {G}: = {\ begin {pmatrix} {\ begin {array} {c | c} I_ {k} & - A ^ {\ text {T}} \\\ end {array}} \ end {pmatrix}}}$

и называется матрицей проверки на четность . $\mathbf {H} :={\begin{pmatrix}{\begin{array}{c|c}A&I_{n-k}\\\end{array}}\end{pmatrix}}$

Это построение G и H в стандартной (или систематической) форме. Независимо от формы G и H для линейных блочных кодов должны удовлетворять

$\mathbf {H} \,\mathbf {G} ^{\text{T}}=\mathbf {0}$ , матрица из нулей. ^[4]

Так как [7, 4, 3] = [ п , к , д ] = [2 ^м - 1, 2 ^м -1- м , 3]. Проверочная матрица H кода Хэмминга строится путем перечисления всех столбцов длины т , которые попарно независимы.

Таким образом, H - это матрица, левая часть которой состоит из всех ненулевых наборов из n, причем порядок наборов из n в столбцах матрицы не имеет значения. Правая часть - это просто ( n - k ) - единичная матрица .

Таким образом , G может быть получен из Н , взяв транспонирование левой части H с идентичностью K- единичную матрицу на левой стороне G .

Матрица генератора кода и матрица проверки на четность : $\mathbf {G}$ $\mathbf {H}$

$\mathbf {G} :={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}_{4,7}$

и

$\mathbf {H} :={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\\\end{pmatrix}}_{3,7}.$

Наконец, эти матрицы можно преобразовать в эквивалентные несистематические коды с помощью следующих операций: ^[4]

Перестановки столбцов (замена столбцов)
Элементарные операции со строками (замена строки линейной комбинацией строк)

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

Пример

Из вышеприведенной матрицы имеем 2 ^k = 2 ⁴ = 16 кодовых слов. Пусть будет вектор - строки двоичных бит данных, . Кодовое слово для любого из 16 возможных векторов данных задается стандартным матричным произведением, в котором операция суммирования выполняется по модулю 2. ${\vec {a}}$ ${\vec {a}}=[a_{1},a_{2},a_{3},a_{4}],\quad a_{i}\in \{0,1\}$ ${\vec {x}}$ ${\vec {a}}$ ${\vec {x}}={\vec {a}}G$

Например, пусть . Используя порождающую матрицу, приведенную выше, мы имеем (после применения по модулю 2 к сумме), ${\vec {a}}=[1,0,1,1]$ $G$

${\vec {x}}={\vec {a}}G={\begin{pmatrix}1&0&1&1\end{pmatrix}}{\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}={\begin{pmatrix}1&0&1&1&2&3&2\end{pmatrix}}={\begin{pmatrix}1&0&1&1&0&1&0\end{pmatrix}}$

[7,4] Код Хэмминга с дополнительным битом четности [ править ]

Тот же пример [7,4] сверху с дополнительным битом четности. Эта диаграмма не предназначена для соответствия матрице H для этого примера.

Код [7,4] Хэмминга можно легко расширить до кода [8,4], добавив дополнительный бит четности поверх (7,4) закодированного слова (см. Хэмминга (7,4) ). Это можно резюмировать с помощью пересмотренных матриц:

\mathbf {G} :={\begin{pmatrix}1&1&1&0&0&0&0&1\\1&0&0&1&1&0&0&1\\0&1&0&1&0&1&0&1\\1&1&0&1&0&0&1&0\end{pmatrix}}_{4,8}

и

\mathbf {H} :={\begin{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}_{4,8}.

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

\mathbf {H} =\left({\begin{array}{cccc|cccc}0&1&1&1&1&0&0&0\\1&0&1&1&0&1&0&0\\1&1&0&1&0&0&1&0\\1&1&1&0&0&0&0&1\end{array}}\right)_{4,8}.

Например, первая строка в этой матрице представляет собой сумму второй и третьей строк H в несистематической форме. Используя систематическую конструкцию для кодов Хэмминга, приведенную выше, матрица A очевидна, а систематическая форма G записывается как

\mathbf {G} =\left({\begin{array}{cccc|cccc}1&0&0&0&0&1&1&1\\0&1&0&0&1&0&1&1\\0&0&1&0&1&1&0&1\\0&0&0&1&1&1&1&0\end{array}}\right)_{4,8}.

Несистематическая форма G может быть сокращена по строкам (с использованием элементарных операций со строками), чтобы соответствовать этой матрице.

Добавление четвертой строки эффективно вычисляет сумму всех битов кодового слова (данных и четности) как четвертый бит четности.

Например, 1011 кодируется (с использованием несистематической формы G в начале этого раздела) в 01 1 0 011 0, где синие цифры - данные; красные цифры - это биты четности из кода Хэмминга [7,4]; а зеленая цифра - это бит четности, добавленный кодом [8,4]. Зеленая цифра делает четность кодовых слов [7,4] четной.

Наконец, можно показать, что минимальное расстояние увеличилось с 3 в коде [7,4] до 4 в коде [8,4]. Следовательно, код можно определить как [8,4] код Хэмминга.

Чтобы декодировать код Хэмминга [8,4], сначала проверьте бит четности. Если бит четности указывает на ошибку, исправление одиночной ошибки (код Хэмминга [7,4]) укажет местоположение ошибки, а «нет ошибки» указывает бит четности. Если бит четности правильный, то исправление одиночной ошибки укажет (побитовое) исключающее ИЛИ из двух местоположений ошибок. Если местоположения равны («нет ошибки»), то двойная битовая ошибка либо не произошла, либо исчезла сама собой. В противном случае произошла двойная битовая ошибка.

См. Также [ править ]

Теория кодирования
Код Голея
Код Рида – Мюллера
Исправление ошибок Рида – Соломона
Турбо код
Код проверки на четность с низкой плотностью
Граница Хэмминга
Расстояние Хэмминга

Примечания [ править ]

^ См. Лемму 12 из
Перейти ↑ Hamming (1950) , pp. 153–154.
^ Томпсон, Томас М. (1983), От кодов с исправлением ошибок через упаковку сфер до простых групп , Математические монографии Каруса (# 21), Математическая ассоциация Америки, стр. 16–17, ISBN 0-88385-023-0
^ а б Мун Т. Кодирование с исправлением ошибок: математические методы и алгоритмы. Джон Вили и сыновья, 2005. (Cap. 3) ISBN 978-0-471-64800-0

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

Хэмминг, Ричард Уэсли (1950). «Коды обнаружения и исправления ошибок» (PDF) . Технический журнал Bell System . 29 (2): 147–160. DOI : 10.1002 / j.1538-7305.1950.tb00463.x .
Луна, Тодд К. (2005). Кодирование с исправлением ошибок . Нью-Джерси : John Wiley & Sons . ISBN 978-0-471-64800-0.
Маккей, Дэвид JC (сентябрь 2003 г.). Теория информации, логические выводы и алгоритмы обучения . Кембридж : Издательство Кембриджского университета . ISBN 0-521-64298-1.
Д. К. Бхаттачаррия, С. Нанди. «Эффективный класс кодов SEC-DED-AUED». 1997 Международный симпозиум по параллельным архитектурам, алгоритмам и сетям (ISPAN '97) . С. 410–415. DOI : 10.1109 / ISPAN.1997.645128 .
«Математическая задача, апрель 2013 г. Коды с исправлением ошибок» (PDF) . Группа лидеров swissQuant Group . Апрель 2013.

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

Визуальное объяснение кодов Хэмминга
CGI-скрипт для расчета расстояний Хэмминга (от Р. Терво, UNB, Канада)
Инструмент для вычисления кода Хэмминга

[1] См. Лемму 12 из

[FOOTNOTEHamming1950153&ndash;154-2] Перейти ↑ Hamming (1950) , pp. 153–154.

[3] Томпсон, Томас М. (1983), От кодов с исправлением ошибок через упаковку сфер до простых групп , Математические монографии Каруса (# 21), Математическая ассоциация Америки, стр. 16–17, ISBN 0-88385-023-0

[Moon-4] а б Мун Т. Кодирование с исправлением ошибок: математические методы и алгоритмы. Джон Вили и сыновья, 2005. (Cap. 3) ISBN 978-0-471-64800-0

[1]