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

Ответ 1

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

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

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

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

Если мы используем два бита для данных и третий для проверки на четность (скажем, например, четность). Мы теряем 4 данных. Но это имеет то преимущество, что мы можем обнаружить однократный сбой (который преобразует четное число 1 в нечетное число единиц). Нечетные числа отмечены символом *. И мы видим, что каждое нечетное (ошибочно переданное) слово заглушено четными (законно переданными) словами. Поэтому, если мы получим 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 бит.

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

Ответ 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 и увидите, что есть шесть 1s, вы знаете, что там ошибка, но не знаете где. Предположим, мы добавляем больше бит четности, каждый из которых зависит только от части сообщения, как показано ниже, путем копирования рассмотренных бит и использования '-' для игнорируемых бит:

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

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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