Код хэмминга содержание а также история [ править ]

Программная генерация ECC

В спецификации приведён пример программного вычисления проверочных бит ЕСС для кода Хэмминга (72, 64). Как уже было отмечено ранее, в данном коде не используется бит чётности, поэтому алгоритм вычисления ECC для кода (7,4) с битом чётности будет отличаться от алгоритма для кода (72,64). В связи с этим мы разберём здесь программную реализацию вычисления ECC для кода (7,4) c битом чётности на примере вычисления бит CFGx в режимах запуска EXTBUS_CFG+JB и EXTBUS_CFG+JA.

Процесс вычисления проверочных бит заключается в перемножении исходного слова А на матрицу генерации ECC, которой является правая часть проверочной матрицы H.

Полный код функции представлен ниже:

Gen_ECC.c

uint8_t Gen_ECC(uint8_t data)
{
	uint8_t G[] = {0, 0xB,0xD,0xE}; // матрица генерации
	uint8_t i = 0, j = 0, res = 0, inputw = 0;
	
	data = data & 0xF;
	
	for (i=1; i<4; i++) // Формируем r3-r1
        {
          inputw = data & G;  // Выбрали необходимые информационные биты для формирования контрольного бита
          res=0;
          for (j=0; j<4; j++)
	      res = res ^ ((inputw >> j) & 0x01);   // Суммируем выбранные информационные биты по модулю 2, получаем один контрольный бит		
	  data |= res<<(i+4); // Дописываем контрольные биты к исходному слову
        }
		
	res=0; //Формируем бит чётности p
	for (j=0; j<8; j++)
	   res = res ^ ((data >> j) & 0x01);   // Суммируем все биты получившегося слова для нахождения бита чётности (S0)
	
	return data |= res<<4;	
}

Разберём основные части.

Для начала составим из правой части проверочной матрицы H массив генерации ECC G[], при этом каждый элемент данного массива будет представлять строку правой части матрицы H. Далее в цикле формируем проверочные биты, путем выборки необходимые информационные биты, а именно, накладывая маску из массива генерации, после чего суммируем их по модулю два. Делаем это для трёх проверочных бит. Дописываем их к информационным битам.
После вычисляем бит чётности p суммированием по модулю два всех проверочных и информационных бит, и дописываем его в кодируемое слово. Исходное слово закодировано.

Получившаяся таблица для всех значений бит CFGx:

Закодированное слово	Проверочные биты ECC	Информационные биты CFGx
0x00	0000	0000
0x71	0111	0001
0xB2	1011	0010
0xC3	1100	0011
0xD4	1101	0100
0xA5	1010	0101
0x66	0110	0110
0x17	0001	0111
0xE8	1110	1000
0x99	1001	1001
0x5A	0101	1010
0x2B	0010	1011
0x3C	0011	1100
0x4D	0100	1101
0x8E	1000	1110
0xFF	1111	1111

Контекст

Код коррекции

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

Напомним основные элементы формализации. Существует множество E, состоящее из последовательностей значений в алфавите и длины k , то есть, начиная с ранга k , все значения последовательности равны нулю. Эти элементы представляют собой пространство сообщений, которые мы хотим передать. Чтобы обеспечить сообщение желаемой избыточностью, существует инъективная карта φ для E со значениями в F , пространство последовательностей длины n и со значениями в алфавите. Функция φ называется кодирующей , φ ( E ) также отмечается, что C называется кодом , элементом слова φ ( E ) кода , k — длиной кода и n — размерностью кода. Эти обозначения используются на протяжении всей статьи.

Линейный код

Линейный код имеет более богатую алгебраическую структуру, чем общая структура корректирующих кодов.

Алфавиты A и A ‘ идентифицированы и снабжены конечной структурой поля . Самый частый случай состоит в выборе поля F ₂ или одного из его конечных расширений , тогда мы говорим о двоичном алфавите .

Множества E и F естественным образом наделены структурой векторного пространства соответствующих размерностей k и n . Если F _d обозначает конечное поле (ср. Конечное поле артикля ) кардинала d, где d — степень простого числа p , то конечное векторное пространство F обычно отождествляется с F _dn .

F имеет расстояние, которое зависит от веса Хэмминга . Расстояние между двумя точками F соответствует количеству ненулевых координат разницы между двумя точками в каноническом базисе . Код описывается тремя параметрами: [ n , k , δ], n — длина кода, k — размер кода, а δ — минимальное расстояние между двумя словами кода. Наконец, карта кодирования φ выбирается линейной , поэтому код является векторным подпространством .

Код Хэмминга — это линейный код, минимальное расстояние δ которого равно трем . Эти обозначения используются в остальной части статьи.

Идеальный код

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

Геометрическая интерпретация дает элемент ответа. эти шарики замкнутого радиуса т центрированных на кодовые словах должны быть не пересекаются. Корректирующая способность кода соответствует наибольшему целому числу t, удовлетворяющему этому свойству, а также наибольшему целому числу, строго меньшему, чем δ / 2, что дает значение, равное единице в случае кода Хэмминга. Это позволяет определить первое увеличение, называемое границей Хэмминга :

1+нет.(d-1)≤dнет-k{\ Displaystyle 1 + п. (d-1) \ leq d ^ {nk}}

Существует конфигурация идеально подходит, что соответствует случаю , когда замкнутые шары радиуса а и центра кодовых слов образуют разбиение пространства F . Если передача никогда не вызывает более одного повреждения, то ошибку можно исправить. Нет лишней избыточности, код максимально компактен, чтобы гарантировать определенное исправление ошибки. Для таких кодов верхняя граница границы Хэмминга является равенством. Говорят, что они идеальны . Отсюда возникает следующее определение:

Код Хемминга является идеальным линейным кодом минимального расстояния , равным трем .

Контроль чётности

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

Если нечетное количество единиц, добавляем 0.

1 0 1 0 0 1 0 0 |

Если четное количество единиц, добавляем 1.

1 1 0 1 0 1 0 0 | 1

Если принятый бит чётности не совпадает с рассчитанным битом чётности, то считается, что произошла ошибка.

1 1 0 0 1 0 0 | 1

Под кратностью понимается, всевозможные ошибки, которые можно обнаружить. В этом случае, кратность исправляемых ошибок 0, так как мы не можем исправить ошибки, а кратность обнаруживаемых 1.

Есть последовательность 0 и 1, и из этой последовательности составим прямоугольную матрицу размера 4 на 4. Затем для каждой строки и столбца посчитаем бит четности.

Прямоугольный код – код с контролем четности, позволяющий исправить одну ошибку:

И если в процессе передачи информации допустим ошибку (ошибка нолик вместо единицы, желтым цветом), начинаем делать проверку. Нашли ошибку во втором столбце, третьей строке по координатам. Чтобы исправить ошибку, просто инвертируем 1 в 0, тем самым ошибка исправляется.

Этот прямоугольный код исправляет все одно-битные ошибки, но не все двух-битные и трех-битные.

Рассчитаем скорость кода для:

1 1 0 0 0 1 0 0 | 1

Здесь R=8/9=0,88

И для прямоугольного кода:

Здесь R=16/24=0,66 (картинка выше, двадцать пятую единичку (бит четности) не учитываем)

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

Тривиальные систематические коды. Код Хэмминга.

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

Тривиальные систематические коды могут строиться, как и групповые, на основе производящей матрицы. Обычно производящая матрица строится при помощи матриц единичной, ранг которой определяется числом информационных разрядов, и добавочной, число столбцов которой определяется числом контрольных разрядов кода. Каждая строка добавочной матрицы должна содержать не менее единиц, а сумма по модулю для любых строк не менее единиц (где минимальное кодовое расстояние). Производящая матрица позволяет находить все остальные кодовые комбинации суммированием по модулю для строк производящей матрицы во всех возможных сочетаниях (см. например, задачу 6.74).

Код Хэмминга является типичным примером систематического кода. Однако при его построении к матрицам обычно не прибегают. Для вычисления основных параметров кода задается либо количество информационных символов, либо количество информационных символов, либо количество информационных комбинаций . При помощи (59) и (60) вычисляются и . Соотношения между n, , и для Хэмминга предоставлены в табл. 1 приложения 8. Зная основные параметры корректирующего кода, определяют, какие позиции сигналов будут рабочими, а какие контрольными. Как показала практика, номера контрольных символов удобно выбирать по закону , где 0, 1, 2 и т. д. — натуральный ряд чисел. Номера контрольных символов в этом случае будут соответственно: 1, 2, 4, 8, 16, 32 и т.д.

Затем определяется значения контрольных коэффициентов (0 или 1), руководствуясь следующим правилом: сумма единиц на контрольных позициях должна быть четной. Если эта сумма четна, то значение контрольного коэффициента — 0, в противно случае — 1.

Проверочные позиции выбираются следующим образом: составляется таблица для ряда натуральных чисел в двоичном коде. Число строк таблицы:

Первой строке соответствует проверочный коэффициент , второй и т. д., как показано в табл. 2 приложения 8. Затем выявляют проверочные позиции, выписывая коэффициенты по следующему принципу: в первую проверку входят коэффициенты, которые содержат в младшем разряде 1, т. е. , , , , , и т. д.; во вторую — коэффициенты, содержащие 1 во втором разряде, т. е. , , , , , и т. д.; в третью проверку — коэффициенты, которые содержат 1 в третьем разряде, и т. д. Номера проверочных коэффициентов соответствует номерам проверочных позиций, что позволяет составить общую таблицу проверок (табл. 3, приложение 8). Старшинство разрядов считается слева направо, а при проверке сверху вниз. Порядок проверок показывает также и порядок следования разрядов в получения разрядов в полученном двоичном коде.

Если в принятом коде есть ошибка, то результат проверок по контрольным позициям образует двоичное число, указывающее номер ошибочной позиции. Исправляют ошибку, изменяя символ ошибочной позиции а обратный (см. задачу 6.78).

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

Параметры помехоустойчивого кодирования

Первый параметр, скорость кода R характеризует долю информационных («полезных») данных в сообщении и определяется выражением: R=k/n=k/m+k

где n – количество символов закодированного сообщения (результата кодирования);
m – количество проверочных символов, добавляемых при кодировании;
k – количество информационных символов.

Параметры n и k часто приводят вместе с наименованием кода для его однозначной идентификации. Например, код Хэмминга (7,4) значит, что на вход кодера приходит 4 символа, на выходе 7 символов, Рида-Соломона (15, 11) и т.д.

Второй параметр, кратность обнаруживаемых ошибок – количество ошибочных символов, которые код может обнаружить.

Третий параметр, кратность исправляемых ошибок – количество ошибочных символов, которые код может исправить (обозначается буквой t).

Помехоустойчивые коды

Современные коды более эффективны по сравнению с рассматриваемыми примерами. В таблице ниже приведены Коды Боуза-Чоудхури-Хоквингема (БЧХ)

Из таблицы видим, что там один класс кода БЧХ, но разные параметры n и k.

n — количество символов на входе.
k — количество символов на выходе.
t — кратность исправляемых ошибок.
Отношение k/n — скорость кода.
G (энергетический выигрыш) — величина, показывающая на сколько можно уменьшить отношение сигнал/шум (Eb/No) для обеспечения заданной вероятности ошибки.

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

Пример: помехоустойчивые коды и двоичная фазовая манипуляция (2-ФМн). На графике зависимость отношения сигнал шум (Eb/No) от вероятности ошибки. За счет применения помехоустойчивых кодов улучшается помехоустойчивость.

Из графика видим, код Хэмминга (7,4) на сколько увеличилась помехоустойчивость? Всего на пол Дб это мало, если применить код БЧХ (127, 64) выиграем порядка 4 дБ, это хороший показатель.

Компромиссы при использовании помехоустойчивых кодов

Чем расплачиваемся за помехоустойчивые коды? Добавили избыточность, соответственно эту избыточность тоже нужно передавать. Нужно: увеличивать пропускную способность канала связи, либо увеличивать длительность передачи.

Компромисс:

Достоверность vs полоса пропускания.
Мощность vs полоса пропускания.
Скорость передачи данных vs полоса пропускания

Необходимость чередования (перемежения)

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

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

Пример блочного перемежения:

На картинке, всего 5 блоков (с 1 по 25). Код работает исправляя ошибки в рамках одного блока (если в одном блоке 1 ошибка, код его исправит, а если две то нет). В канал связи отдается информация не последовательно, а в перемешку. На выходе кодера сформировались 5 блоков и эти 5 блоков будем отдавать не по очереди а в перемешку. Записали всё по строкам, но считывать будем, чтобы отправлять в канал связи, по столбцам. Информация в блоках перемешалась. В канале связи возникла ошибка и мы потеряли большой кусок. В процессе приема, мы опять составляем таблицу, записываем по столбцам, но считываем по строкам. За счет того, что мы перемешали большое количество блоков между собой, групповая ошибка равномерно распределится по блокам.

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

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

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

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

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

Общий алгоритм генерации ECC и коррекции ошибок на основе кода Хэмминга

Общий алгоритм коррекции ошибок (ECC), основанный на коде Хэмминга, на примере операции записи/чтения в МК 1986ВЕ8Т/1923ВК014:

1. Запись слова А:

Кодирование исходного слова А. На основании записываемых данных (для слов (72,64) также используется адрес) вычисляется проверочные (контрольные) биты ECC, которые передаются на запись совместно с исходным словом А.
Запись слова А вместе с контрольными битами ECC.

2. Чтение слова А:

Чтение слова А совместно с контрольными битами ECC.
На основании данных (для (72,64) данных и адреса) слова А производится повторный расчёт контрольных бит ECC.
Сравнение считанных проверочных бит ECC с заново рассчитанными. Если проверочные биты совпадают, значит ошибок нет, ECC биты отбрасываются и исходное слово А передаётся дальше на чтение.
Если проверочные биты не совпадают и имеет место одиночная ошибка, то происходит её исправление, операция чтения при этом также успешно выполняется. Если обнаружена двойная ошибка, то данные не восстанавливаются, и происходит ошибка чтения.

Помехоустойчивое кодирование. Коды Хэмминга

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

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

Рассмотрим пример CD диска. Там информация хранится прямо на поверхности диска, в углублениях, из-за того, что все дорожки на поверхности, часто диск хватаем пальцами, елозим по столу и из-за этого без помехоустойчивого кодирования, информацию извлечь не получится.

Использование кодирования позволяет извлекать информацию без потерь даже с поврежденного CD/DVD диска, когда какая либо область становится недоступной для считывания.

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

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

Коэффициент ошибок пакета

Коэффициент ошибок пакетов (PER) — это количество неправильно принятых пакетов данных, деленное на общее количество принятых пакетов. Пакет объявляется некорректным, если хотя бы один бит ошибочен. Ожидаемое значение PER обозначается вероятностью ошибки пакета p _p , которая для длины пакета данных N бит может быть выражена как

ппзнак равно1-(1-пе)Nзнак равно1-еNпер⁡(1-пе){\ displaystyle p_ {p} = 1- (1-p_ {e}) ^ {N} = 1-e ^ {N \ ln (1-p_ {e})}},

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

пп≈пеN.{\ displaystyle p_ {p} \ приблизительно p_ {e} N.}

Подобные измерения могут быть выполнены для передачи кадров , блоков или символов .

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

Ричард Хэмминг , изобретатель кодов Хэмминга, работал в Bell Labs в конце 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, поскольку имеется два бита четности, а 2 2 — 2 — 1 = 1 бит данных.

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

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

Исправление ошибок [ править ]

В противном случае предположим, что произошла ошибка одного бита. Математически мы можем написать

r=x+ei{\displaystyle \mathbf {r} =\mathbf {x} +\mathbf {e} _{i}}

по модулю 2, где e _i — единичный вектор , то есть нулевой вектор с 1 в , считая от 1.ith{\displaystyle i_{th}} ith{\displaystyle i^{th}}

e2=(1){\displaystyle \mathbf {e} _{2}={\begin{pmatrix}0\\1\\0\\0\\0\\0\\0\end{pmatrix}}}

Таким образом, приведенное выше выражение означает единственную битовую ошибку на месте.ith{\displaystyle i^{th}}

Теперь, если мы умножим этот вектор на H :

Hr=H(x+ei)=Hx+Hei{\displaystyle \mathbf {Hr} =\mathbf {H} \left(\mathbf {x} +\mathbf {e} _{i}\right)=\mathbf {Hx} +\mathbf {He} _{i}}

Поскольку x — это переданные данные, они не содержат ошибок, и в результате произведение H и x равно нулю. Таким образом

Hx+Hei=+Hei=Hei{\displaystyle \mathbf {Hx} +\mathbf {He} _{i}=\mathbf {0} +\mathbf {He} _{i}=\mathbf {He} _{i}}

Теперь произведение H на стандартный базисный вектор выбирает этот столбец H , мы знаем, что ошибка возникает в том месте, где встречается этот столбец H.ith{\displaystyle i^{th}}

Например, предположим, что мы ввели битовую ошибку в бит # 5.

r=x+e5=(1111)+(1)=(11111){\displaystyle \mathbf {r} =\mathbf {x} +\mathbf {e} _{5}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}+{\begin{pmatrix}0\\0\\0\\0\\1\\0\\0\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}}

Ошибка в бите 5 вызывает плохую четность в красных и зеленых кругах.

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

Сейчас же,

z=Hr=(111111111111)(11111)=(343)=(11){\displaystyle \mathbf {z} =\mathbf {Hr} ={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}3\\4\\3\end{pmatrix}}={\begin{pmatrix}1\\0\\1\end{pmatrix}}}

что соответствует пятой колонке H . Кроме того, использованный общий алгоритм ( см. Код Хэмминга # Общий алгоритм ) был преднамеренным в своей конструкции, так что синдром 101 соответствует двоичному значению 5, что указывает на повреждение пятого бита. Таким образом, в бите 5 обнаружена ошибка, которую можно исправить (просто переверните или отмените ее значение):

rcorrected=(111¯11)=(1111){\displaystyle \mathbf {r} _{\text{corrected}}={\begin{pmatrix}0\\1\\1\\0\\{\overline {1}}\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}}

Это скорректированное полученное значение теперь действительно совпадает с переданным значением x сверху.