Как работает код Хэмминга?

Вы найдете подробную информацию о том, как это работает здесь

Более общая информация о кодах исправления ошибок доступна здесь

Информация о коде Хэмминга доступна здесь и здесь.

Что касается пригодности, это объясняет, почему:

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

2. Обнаружение ошибок плюс повторная передача часто предпочтительнее, потому что это более эффективно.

Для сравнения рассмотрим канал с частотой ошибок на бит. Пусть размер блока составляет 1000 бит.

Чтобы исправить одну ошибку (кодом Хэмминга), необходимо 10 проверочных битов на блок. Для передачи 1000 блоков требуется 10 000 контрольных битов (служебные данные). Чтобы обнаружить единственную ошибку, достаточно одного бита четности на блок. Чтобы передать 1000 блоков, только один внешний блок (из-за частоты ошибок на бит) должен быть повторно передан, что дает накладные расходы только 2001 (= 1000 + 1001) бит.

Код Хэмминга - это математический прием для исправления до 4 потерянных битов при последовательной передаче. Он также используется в пользу «бита четности» в современных микросхемах памяти.

Ограничения заключаются в количестве восстанавливаемых битов, которое не превышает 4. Если потеряно более 4 битов, требуется повторная передача.

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

Попробуем немного это объяснить:

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

000 --------001
 | \         | \
 | 100---------101
 |  |        |  |
 |  |        |  |
010-|-------011 |
   \|          \|
   110---------111

Каждый дефект (например, 101 читается как 100) приводит к сдвигу линии на кубе.

Если мы используем два бита для данных и третий для проверки четности (скажем, например, четность). Мы теряем 4 точки данных. Но у него есть то преимущество, что мы можем обнаружить сбой одного бита (который преобразует четное количество единиц в нечетное количество единиц). Нечетные числа отмечены *. И мы видим, что каждое нечетное (неправильно переданное) слово загоняется в угол четными (правильно переданными) словами. Так что, если мы получим 100, мы можем быть уверены, что это неверно.

Но (при сбое одного бита) правильным представлением могло быть 000, 101 или 110. Таким образом, мы можем обнаружить, что что-то пошло не так, но не можем определить, что было неправильно:

 000 -------*001
  | \         | \
  |*100---------101
  |  |        |  |
  |  |        |  |
*010-|-------011 |
    \|          \|
    110--------*111

Это называется кодом обнаружения однобитовой ошибки.

Если мы используем другой бит для проверки и, таким образом, удалим один для данных. Остается 1 бит данных и 2 контрольных бита. В этом случае предположим, что 000 и 111 являются действительными представлениями данных, а остальные шесть - нет. Теперь у нас есть интересная ситуация, если при транспортировке один бит поврежден. Если мы отправим 000 и получим 010, мы увидим, что 010 имеет одного допустимого соседа (000) и двух недопустимых (110 и 011). Итак, теперь мы знаем, что намеревались отправить 000, и можем это исправить:

 000 -------*001
  | \         | \
  |*100--------*101
  |  |        |  |
  |  |        |  |
*010-|------*011 |
    \|          \|
   *110---------111

Это называется однобитовым кодом исправления ошибок.

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

И в более общем плане.

Если у вас n контрольных битов, у вас есть n-битный код обнаружения ошибок. Если у вас есть 2n контрольных бит, у вас есть n-битный код исправления ошибок.

Конечно, вы должны заказывать «действующие» коды так, чтобы они не граничили друг с другом.

Вот действительно общий обзор.

Suppose that every time I send a message, I send thrie copies of the text.
Suppose that every time I send z message, I send three copies of the teyt.
Suppose that every tyme I send a message, I send three copies if the tezt.

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

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

Для иллюстрации давайте начнем с простой проверки на нечетность, добавив один бит, чтобы гарантировать, что общее количество битов в сообщении нечетное. Таким образом, сообщение 10110110 становится 101101100 (пять единиц, дополнительная 1 не требуется), а сообщение 10010110 становится 100101101 (четыре единицы, требуется дополнительная 1). Если вы получаете сообщение 101101101 и видите шесть единиц, вы знаете, что произошла ошибка, но не знаете, где именно. Предположим, мы добавляем больше битов четности, каждый из которых зависит только от часть сообщения, как показано ниже, путем копирования рассматриваемых битов и использования '-' для игнорируемых битов:

10110110
1-1-0-1- => 0
-0-1-1-0 =>  1
10--01-- =>   1
--11--10 =>    0
1011---- =>     0
----0110 =>      1

так что полное сообщение - 10110110011001. Теперь предположим, что ошибка передачи изменяет третий бит сообщения, так что он читается как 10010110011001. Когда получатель повторно запускает вычисление с проверкой ошибок, оно не соответствует:

10010110
1-0-0-1- => 1*
-0-1-1-0 =>  1
10--01-- =>   1
--01--10 =>    1*
1001---- =>     1*
----0110 =>      1

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

@GameCat, а как насчет 2-битного кода обнаружения ошибок.

В этом случае допустим, что 111 изменилось на 100. Тогда мы можем быть уверены, что есть 2 неправильных бита, и мы знаем это, потому что расстояние между 111 и 100 составляет 2 бита, а расстояние между 000 и 100 составляет 1 бит. Итак, если мы знаем, что есть 2-битная ошибка, мы можем быть уверены, что это правильное значение.