Коды Хэмминга: линейные коды исправления ошибок

Введение

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

В информатике и телекоммуникациях коды Хамминга — это семейство кодов коррекции линейных ошибок. Коды Хамминга могут обнаруживать однобитовые и двухбитовые ошибки или исправлять однобитовые ошибки без обнаружения неисправленных ошибок. В отличие от простого паритетного кода, который не может исправлять ошибки и может обнаруживать только нечётное количество ошибочных бит, коды Хамминга являются совершенными кодами, то есть они достигают максимально возможной скорости для кодов с заданной длиной блока и минимальным расстоянием, равным трём. Ричард У. Хамминг изобрел коды Хамминга в 1950 году как способ автоматической коррекции ошибок, вносимых считывателями перфокарт. В своей оригинальной статье Хамминг изложил свою общую идею, но особенно сосредоточился на коде Хамминга (7,4), который добавляет три бита чётности к четырем битам данных. С математической точки зрения, коды Хамминга представляют собой класс двоичных линейных кодов. Для каждого целого числа r ≥ 2 существует кодовое слово с длиной блока и длиной сообщения. Следовательно, скорость кодов Хамминга равна , что является максимально возможной для кодов с минимальным расстоянием в три (то есть минимальное количество изменений бит, необходимых для перехода от любого кодового слова к любому другому кодовому слову, равно трём) и длиной блока 2^(r) − 1. Матрица проверки чётности кода Хамминга строится путём перечисления всех столбцов длины r, отличных от нуля, что означает, что двойственный код кода Хамминга является укороченным кодом Адамара, также известным как код Симплекса. Матрица проверки чётности обладает свойством, что любые два столбца линейно независимы попарно. Из-за ограниченной избыточности, добавляемой кодами Хамминга к данным, они могут обнаруживать и исправлять ошибки только при низком уровне ошибок. Это справедливо для компьютерной памяти (обычно оперативной памяти), где битовые ошибки крайне редки, и коды Хамминга широко используются. Оперативная память с такой системой коррекции называется ECC RAM (ECC memory). В этом контексте часто используется расширенный код Хамминга с одним дополнительным битом чётности. Расширенные коды Хамминга достигают расстояния Хамминга, равного четырём, что позволяет декодеру различать случаи, когда происходит не более одной однобитовой ошибки, и случаи, когда возникают любые двухбитовые ошибки. В этом смысле расширенные коды Хамминга обеспечивают однократную коррекцию ошибок и обнаружение двойных ошибок, что обозначается как SECDED.

In computer science and telecommunication, Hamming codes are a family of linear error correcting codes. Hamming codes can detect one bit and two bit errors, or correct one bit errors without detection of uncorrected errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of bits in error. Hamming codes are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance of three. Richard W. Hamming invented Hamming codes in 1950 as a way of automatically correcting errors introduced by punched card readers. In his original paper, Hamming elaborated his general idea, but specifically focused on the Hamming(7,4) code which adds three parity bits to four bits of data. In mathematical terms, Hamming codes are a class of binary linear code. For each integer r ≥ 2 there is a code word with block length and message length Hence the rate of Hamming codes is , which is the highest possible for codes with minimum distance of three (i. e., the minimal number of bit changes needed to go from any code word to any other code word is three) and block length 2^(r) − 1. The parity check matrix of a Hamming code is constructed by listing all columns of length r that are non zero, which means that the dual code of the Hamming code is the shortened Hadamard code, also known as a Simplex code. The parity check matrix has the property that any two columns are pairwise linearly independent. Due to the limited redundancy that Hamming codes add to the data, they can only detect and correct errors when the error rate is low. This is the case in computer memory (usually RAM), where bit errors are extremely rare and Hamming codes are widely used, and a RAM with this correction system is an ECC RAM (ECC memory). In this context, an extended Hamming code having one extra parity bit is often used. Extended Hamming codes achieve a Hamming distance of four, which allows the decoder to distinguish between when at most one one bit error occurs and when any two bit errors occur. In this sense, extended Hamming codes are single error correcting and double error detecting, abbreviated as SECDED.

История

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

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

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

Паритет

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

Код "два из пяти"

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

Повторение

Другой код, использовавшийся в то время, повторял каждый бит данных несколько раз, чтобы обеспечить его правильную передачу. Например, если бит данных, который нужно отправить, равен 1, то код с повторением n=3 отправит 111. Если три полученных бита не идентичны, значит, во время передачи произошла ошибка. Если канал достаточно чист, то в большинстве случаев в каждой тройке меняется только один бит. Таким образом, 001, 010 и 100 соответствуют биту 0, а 110, 101 и 011 – биту 1, при этом большее количество одинаковых цифр ("0" или "1") указывает на значение исходного бита данных. Код, обладающий способностью восстанавливать исходное сообщение при наличии ошибок, называется кодом, исправляющим ошибки. Этот код тройного повторения является кодом Хэмминга с m=2 (1=m=2), поскольку в нем два бита четности и 1=2<sup>2</sup> − 2 − 1 = 1 бит данных. Однако такие коды не могут правильно исправлять все ошибки. В нашем примере, если канал инвертирует два бита и приемник получает 001, система обнаружит ошибку, но сделает вывод, что исходный бит равен 0, что неверно. Если увеличить длину битовой строки до четырех, мы сможем обнаружить все двухбитные ошибки, но не исправить их (количество битов четности четное); при пяти битах мы сможем обнаруживать и исправлять все двухбитные ошибки, но не все трехбитные ошибки. Более того, увеличение количества битов четности неэффективно, поскольку в нашем исходном случае пропускная способность снижается в три раза, а эффективность резко падает по мере увеличения количества повторений каждого бита для обнаружения и исправления большего числа ошибок.

Описание

Если в сообщение включено больше битов для коррекции ошибок, и если эти биты можно расположить таким образом, чтобы различные ошибочные биты приводили к разным результатам обнаружения ошибок, то можно было бы идентифицировать поврежденные биты. В семибитном сообщении существует семь возможных ошибок в одном бите, поэтому три бита контроля ошибок потенциально могут указать не только на наличие ошибки, но и на бит, вызвавший ее. Хамминг изучил существующие схемы кодирования, включая кодирование «два из пяти», и обобщил их концепции. Для начала он разработал номенклатуру для описания системы, включая количество битов данных и битов коррекции ошибок в блоке. Например, контроль четности включает один бит для любого слова данных, поэтому, предполагая слова ASCII с семью битами, Хамминг описал это как код (8,7), с восемью битами в общей сложности, из которых семь – данные. Пример повторения будет (3,1), следуя той же логике. Коэффициент кодирования – это второе число, деленное на первое, для нашего примера повторения – 1/3. Хамминг также заметил проблемы, связанные с изменением двух и более битов, и описал это как «расстояние» (сейчас его называют расстоянием Хэмминга). Контроль четности имеет расстояние 2, поэтому изменение одного бита может быть обнаружено, но не исправлено, а изменение любых двух битов останется незамеченным. Повторение (3,1) имеет расстояние 3, поскольку для получения другого кодового слова без видимых ошибок необходимо изменить три бита в одной тройке. Оно может исправить ошибки в одном бите или обнаружить, но не исправить, ошибки в двух битах. Повторение (4,1) (каждый бит повторяется четыре раза) имеет расстояние 4, поэтому изменение трех битов может быть обнаружено, но не исправлено. Когда три бита изменяются в одной группе, могут возникнуть ситуации, когда попытка исправления приведет к неправильному кодовому слову. В общем, код с расстоянием k может обнаруживать, но не исправлять k – 1 ошибок. Хамминга интересовали одновременно две задачи: увеличение расстояния настолько, насколько это возможно, и одновременное увеличение коэффициента кодирования настолько, насколько это возможно. В 1940-х годах он разработал несколько схем кодирования, которые значительно превосходили существующие коды. Ключом ко всем его системам было перекрытие битов контроля четности, благодаря чему они могли проверять как друг друга, так и данные.

If more error correcting bits are included with a message, and if those bits can be arranged such that different incorrect bits produce different error results, then bad bits could be identified. In a seven bit message, there are seven possible single bit errors, so three error control bits could potentially specify not only that an error occurred but also which bit caused the error. Hamming studied the existing coding schemes, including two of five, and generalized their concepts. To start with, he developed a nomenclature to describe the system, including the number of data bits and error correction bits in a block. For instance, parity includes a single bit for any data word, so assuming ASCII words with seven bits, Hamming described this as an (8,7) code, with eight bits in total, of which seven are data. The repetition example would be (3,1), following the same logic. The code rate is the second number divided by the first, for our repetition example, 1/3. Hamming also noticed the problems with flipping two or more bits, and described this as the "distance" (it is now called the Hamming distance, after him). Parity has a distance of 2, so one bit flip can be detected but not corrected, and any two bit flips will be invisible. The (3,1) repetition has a distance of 3, as three bits need to be flipped in the same triple to obtain another code word with no visible errors. It can correct one bit errors or it can detect but not correct two bit errors. A (4,1) repetition (each bit is repeated four times) has a distance of 4, so flipping three bits can be detected, but not corrected. When three bits flip in the same group there can be situations where attempting to correct will produce the wrong code word. In general, a code with distance k can detect but not correct k − 1 errors. Hamming was interested in two problems at once: increasing the distance as much as possible, while at the same time increasing the code rate as much as possible. During the 1940s he developed several encoding schemes that were dramatic improvements on existing codes. The key to all of his systems was to have the parity bits overlap, such that they managed to check each other as well as the data.

Коды Хамминга с дополнительным паритетом (SECDED)

Коды Хэмминга имеют минимальное расстояние 3, что означает, что декодер может обнаружить и исправить одиночную ошибку, но не способен отличить двойную битовую ошибку одного кодового слова от одиночной битовой ошибки другого кодового слова. Таким образом, некоторые двойные битовые ошибки будут ошибочно декодированы как одиночные и останутся необнаруженными, если не предпринимать попыток исправления. Для устранения этого недостатка коды Хэмминга можно расширить, добавив дополнительный бит четности. Это позволяет увеличить минимальное расстояние кода Хэмминга до 4, что дает декодеру возможность различать одиночные и двойные битовые ошибки. Таким образом, декодер может обнаружить и исправить одиночную ошибку, одновременно обнаруживая (но не исправляя) двойную ошибку. Если декодер не пытается исправлять ошибки, он может надежно обнаруживать тройные битовые ошибки. Если декодер исправляет ошибки, некоторые тройные ошибки могут быть ошибочно приняты за одиночные и "исправлены" до неверного значения. Следовательно, исправление ошибок представляет собой компромисс между надежностью (способностью достоверно обнаруживать тройные битовые ошибки) и устойчивостью (способностью продолжать функционировать при наличии одиночных битовых ошибок). Этот расширенный код Хэмминга был популярен в компьютерных системах памяти, начиная с IBM 7030 Stretch в 1961 году, где он известен как SECDED (или SEC DED, сокращение от single error correction, double error detection – коррекция одиночной ошибки, обнаружение двойной). Серверные компьютеры в 21 веке, хотя обычно поддерживают уровень защиты SECDED, больше не используют метод Хэмминга, предпочитая конструкции с более длинными кодовыми словами (от 128 до 256 бит данных) и модифицированными деревьями проверки сбалансированной четности. Код (72,64) Хэмминга по-прежнему популярен в некоторых аппаратных разработках, включая семейства FPGA Xilinx.

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

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