Код Хэмминга

Семейство линейных кодов с исправлением ошибок

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

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

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

История

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

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

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

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

Паритет

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

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

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

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

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

1. Пронумеруйте биты, начиная с 1: бит 1, 2, 3, 4, 5, 6, 7 и т. д.
2. Запишите номера битов в двоичном формате: 1, 10, 11, 100, 101, 110, 111 и т. д.
3. Все позиции битов, которые являются степенями двойки (имеют один бит 1 в двоичной форме своей позиции), являются битами четности: 1, 2, 4, 8 и т. д. (1, 10, 100, 1000).
4. Все остальные позиции битов с двумя или более битами 1 в двоичной форме являются битами данных.
5. Каждый бит данных включен в уникальный набор из 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 мы получаем все возможные коды Хэмминга: ${\displaystyle 2^{m}-1}$ ${\displaystyle 2^{m}-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

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

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

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

${\displaystyle \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 ) -единичная матрица .

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

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

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

и

${\displaystyle \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. ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {a}}=[a_{1},a_{2},a_{3},a_{4}],\quad a_{i}\in \{0,1\}}$ ${\displaystyle {\vec {x}}}$ ${\displaystyle {\vec {a}}}$ ${\displaystyle {\vec {x}}={\vec {a}}G}$

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

${\displaystyle {\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) ). Это можно резюмировать с помощью пересмотренных матриц:

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

и

${\displaystyle \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 в систематической форме:

${\displaystyle \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 записывается как

${\displaystyle \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]) укажет место ошибки, а «нет ошибки» указывает на бит четности. Если бит четности правильный, то однократная коррекция ошибок будет указывать (побитовое) исключающее или двух местоположений ошибок. Если позиции равны («нет ошибок»), то двойная битовая ошибка либо не произошла, либо исчезла сама собой. В противном случае произошла двойная битовая ошибка.

Смотрите также

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

Примечания

1. См. лемму 12 из
2. Хэмминг (1950), стр. 153–154.
3. Томпсон, Томас М. (1983), От кодов, исправляющих ошибки, через сферические упаковки к простым группам, Математические монографии Каруса (№ 21), Математическая ассоциация Америки, стр. 16–17, ISBN 0-88385-023-0
4. Kythe & Kythe 2017, с. 115.
5. Кайт и Кит 2017, с. 95.
6. Мун Т. Кодирование с коррекцией ошибок: математические методы и алгоритмы. Джон Уайли и сыновья, 2005. (Глава 3) ISBN 978-0-471-64800-0 

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

• Хэмминг, Ричард Уэсли (1950). «Коды обнаружения и исправления ошибок» (PDF) . Технический журнал Bell System . 29 (2): 147–160. doi :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.

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

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