Код Хэмминга

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

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

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

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

История

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

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

Кодексы до Хэмминга

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

Паритет

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

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

Код «два из пяти»

Код «два из пяти» — это схема кодирования, в которой используются пять битов, состоящих ровно из трех нулей и двух единиц. Это обеспечивает ${\binom {5}{3}}=10$ возможных комбинаций, достаточных для обозначения цифр 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 ( исключающее ИЛИ всех битовых позиций, содержащих 1) был равен 0. Мы используем позиции 1, 10, 100 и т. д. (в двоичном формате) в качестве ошибки. - биты исправления, что гарантирует возможность установки битов исправления ошибок так, чтобы индекс XOR всего сообщения был равен 0. Если получатель получает строку с индексом XOR 0, он может заключить, что повреждений не было, и в противном случае индекс-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.

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

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

Биты закодированных данных		п1	п2	d1	п4	d2	д3	d4	стр.8	d5	d6	d7	d8	d9	d10	д11	стр. 16	д12	д13	д14	d15
Битовая позиция		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	...
Паритет кусочек покрытие	п1
	п2
	п4
	стр.8
	стр. 16

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

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

Биты четности	Всего бит	Биты данных	Имя	Ставка
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
9	511	502	Хэмминг(511502)	502/511 ≈ 0.982
...
$м$	$n=2^{m}-1$	$k=2^{m}-m-1$	Хэмминг $(2^{m}-1,2^{m}-m-1)$	$(2^{m}-m-1)/(2^{m}-1)$

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

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

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

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

Этот расширенный код Хэмминга был популярен в компьютерных системах памяти, начиная с IBM 7030 Stretch в 1961 году. ^[4] где он известен как SECDED (или SEC-DED, сокращенно от одиночной коррекции ошибок, обнаружения двойной ошибки ). ^[5] Серверные компьютеры 21 века, обычно сохраняя уровень защиты SECDED, больше не используют метод Хэмминга, вместо этого полагаясь на конструкции с более длинными кодовыми словами (от 128 до 256 бит данных) и модифицированными сбалансированными деревьями проверки четности. ^[4] Код Хэмминга (72,64) по-прежнему популярен в некоторых аппаратных средствах, включая Xilinx семейства ПЛИС . ^[4]

[7,4] Код Хэмминга

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

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

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

Строительство G и H

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

и $\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}$ , матрица, состоящая из всех нулей. ^[6]

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

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

Таким образом, можно получить из H путем транспонирования левой части H с единичной k - тождественной матрицей в левой части G. 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}.$

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

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

Кодирование

Пример

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

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

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

[8,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 из
^ Хэмминг (1950) , стр. 153–154.
^ Томпсон, Томас М. (1983), От кодов с исправлением ошибок через сферические упаковки к простым группам , Математические монографии Каруса (№ 21), Математическая ассоциация Америки, стр. 16–17, ISBN 0-88385-023-0
^ Перейти обратно: ^а ^б ^с Кайт и Кит 2017 , с. 115.
^ Кайт и Кит 2017 , с. 95.
^ Перейти обратно: ^а ^б Мун Т. Кодирование с коррекцией ошибок: Математические методы иАлгоритмы. Джон Уайли и сыновья, 2005 г. (Гл. 3). ISBN 978-0-471-64800-0

Ссылки

Хэмминг, Ричард Уэсли (1950). «Коды обнаружения и исправления ошибок» (PDF) . Технический журнал Bell System . 29 (2): 147–160. дои : 10.1002/j.1538-7305.1950.tb00463.x . S2CID 61141773 . Архивировано (PDF) из оригинала 9 октября 2022 г.
Мун, Тодд К. (2005). Кодирование с исправлением ошибок . Нью-Джерси : Джон Уайли и сыновья . ISBN 978-0-471-64800-0 .
Маккей, Дэвид Дж. К. (сентябрь 2003 г.). Теория информации, логический вывод и алгоритмы обучения . Кембридж : Издательство Кембриджского университета . ISBN 0-521-64298-1 .
Д.К. Бхаттачаррия, С. Нанди. «Эффективный класс кодов SEC-DED-AUED». 1997 Международный симпозиум по параллельным архитектурам, алгоритмам и сетям (ISPAN '97) . стр. 410–415. дои : 10.1109/ИСПАН.1997.645128 .
«Математическая задача, апрель 2013 г. Коды, исправляющие ошибки» (PDF) . Руководитель группы SwissQuant . Апрель 2013 г. Архивировано (PDF) из оригинала 12 сентября 2017 г.
Кит, Дэйв К.; Кит, Прем К. (28 июля 2017 г.). «Расширенные коды Хэмминга» . Алгебраическая и стохастическая теория кодирования . ЦРК Пресс. стр. 95–116. ISBN 978-1-351-83245-8 .

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

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

[FOOTNOTEHamming1950153–154-2] Хэмминг (1950) , стр. 153–154.

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

[FOOTNOTEKytheKythe2017115-4] Перейти обратно: ^а ^б ^с Кайт и Кит 2017 , с. 115.

[FOOTNOTEKytheKythe201795-5] Кайт и Кит 2017 , с. 95.

[Moon-6] Перейти обратно: ^а ^б Мун Т. Кодирование с коррекцией ошибок: Математические методы иАлгоритмы. Джон Уайли и сыновья, 2005 г. (Гл. 3). ISBN 978-0-471-64800-0

[1]

[2]

[3]

[4]

[5]

[6]