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

Question

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

Как это работает и каковы его ограничения, если таковые имеются?

Существуют ли лучшие решения для исправления ошибок (в отличие от повторной передачи)? Существуют ли обстоятельства, когда ретрансляция лучше?

Answer 1

Давайте попробуем объяснить это немного:

У нас есть 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-битный код исправления ошибок.

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

Answer 2

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

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 с, дополнительный 1 не требуется), а сообщение 10010110 становится 100101101 (четыре 1, дополнительный 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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

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

Answer 5

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

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

Answer 6

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

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

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