Код Хэмминга

В информатике и телекоммуникациях коды Хэмминга представляют собой семейство линейных кодов исправления ошибок . Коды Хэмминга могут обнаруживать однобитовые и двухбитовые ошибки или исправлять однобитовые ошибки без обнаружения неисправленных ошибок. Напротив, простой код четности не может исправлять ошибки и может обнаруживать только нечетное количество ошибочных битов. Коды Хэмминга являются идеальными кодами , то есть они достигают максимально возможной скорости для кодов с длиной блока и минимальным расстоянием три. ^[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 r - 1$ . Матрица проверки четности кода Хэмминга строится путем перечисления всех столбцов длины $r$ , которые не равны нулю, что означает, что дуальный код кода Хэмминга является укороченным кодом Адамара , также известным как симплексный код. Матрица проверки четности обладает тем свойством, что любые два столбца попарно линейно независимы .

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

История

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

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

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

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

Паритет

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

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

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

Код «два из пяти» — это схема кодирования, которая использует пять бит, состоящих ровно из трех нулей и двух единиц. Это обеспечивает возможные комбинации, достаточные для представления цифр от 0 до 9. Эта схема может обнаружить все одиночные битовые ошибки, все нечетные битовые ошибки и некоторые четные битовые ошибки (например, переворот обоих единичных битов). Однако она все еще не может исправить ни одну из этих ошибок. ${\binom {5}{3}}=10$

Повторение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Конструкция G и H

Матрица называется (канонической) порождающей матрицей линейного ( n , k ) кода, $\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_{nk}\\\end{array}}\end{pmatrix}}$

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

$\mathbf {H} \,\mathbf {G} ^{\text{T}}=\mathbf {0}$ , матрица, состоящая из одних нулей. ^[6]

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

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

Таким образом, G можно получить из H, транспонировав левую часть 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&1\\0&0&0&1&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 ^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&1\\0&0&0&1&0&1&1\\0&0&0&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\\0&0&1&0&1&1&0&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
^ abc Kythe & Kythe 2017, стр. 115.
^ Кайт и Кайт 2017, стр. 95.
^ ab Moon T. Кодирование с исправлением ошибок: математические методы и алгоритмы. John Wiley and Sons, 2005. (Глава 3) ISBN 978-0-471-64800-0

Ссылки

Хэмминг, Ричард Уэсли (1950). «Коды обнаружения и исправления ошибок» (PDF) . Bell System Technical Journal . 29 (2): 147–160. doi :10.1002/j.1538-7305.1950.tb00463.x. hdl :10945/46756. S2CID 61141773. Архивировано (PDF) из оригинала 2022-10-09.
Мун, Тодд К. (2005). Кодирование с исправлением ошибок. Нью-Джерси : John Wiley & Sons . ISBN 978-0-471-64800-0.
MacKay, David JC (сентябрь 2003 г.). Теория информации, вывод и алгоритмы обучения. Кембридж : Cambridge University Press . ISBN 0-521-64298-1.
DK Bhattacharryya, S. Nandi. «Эффективный класс кодов SEC-DED-AUED». Международный симпозиум по параллельным архитектурам, алгоритмам и сетям (ISPAN '97) 1997 г. С. 410–415. doi :10.1109/ISPAN.1997.645128.
«Математическая задача, апрель 2013 г. Коды исправления ошибок» (PDF) . Группа руководителей swissQuant. Апрель 2013 г. Архивировано (PDF) из оригинала 12.09.2017.
Кайт, Дэйв К.; Кайт, Прем К. (28 июля 2017 г.). «Расширенные коды Хэмминга». Алгебраическая и стохастическая теория кодирования . CRC Press. стр. 95–116. ISBN 978-1-351-83245-8.

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

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

Реализации

С++