Как работает код Хэмминга?
При передаче данных код Хемминга, по-видимому, позволяет воссоздать данные, которые были повреждены по проводам (код с исправлением ошибок).
Как это работает и каковы его ограничения, если таковые имеются?
Есть ли лучшие решения для исправления ошибок (в отличие от повторной передачи)? Существуют ли обстоятельства, когда ретрансляция лучше?
6 ответов
Давайте попробуем объяснить это немного:
У нас есть 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 контрольных битов, у вас есть код для обнаружения ошибок. Если у вас есть 2n контрольных битов, у вас есть бит, исправляющий ошибку.
Конечно, вы должны заказать "действительные" коды, чтобы они не граничили друг с другом.
Вот действительно обзор высокого уровня.
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, дополнительная 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
и контрольные биты, которые не совпадают, являются именно теми, на которые влияет третий бит данных. Это не настоящая, надежная схема исправления ошибок; это всего лишь набросок, иллюстрирующий, как создание избыточности может помочь в определении точного характера ошибки.
Информация о коде Хемминга доступна здесь и здесь.
Что касается пригодности, это объясняет, почему:
Коды с исправлением ошибок, такие как Хемминга, подходят для симплексных каналов, где не может быть запрошена повторная передача.
Обнаружение ошибок плюс повторная передача часто предпочтительнее, потому что это более эффективно.
Для сравнения рассмотрим канал с частотой ошибок на бит. Пусть размер блока будет 1000 бит.
Для исправления одной ошибки (по коду Хэмминга) требуется 10 контрольных битов на блок. Для передачи 1000 блоков требуется 10000 контрольных битов (служебных данных). Для обнаружения одной ошибки достаточно одного бита четности на блок. Для передачи 1000 блоков, только один внешний блок (из-за частоты ошибок на бит) должен быть передан повторно, что дает служебную информацию только в 2001 (= 1000 + 1001) битах.
Код Хэмминга - это математический прием для исправления до 4 потерянных бит в последовательной передаче. Он также используется в пользу "бита четности" в современных чипах памяти.
Ограничения заключаются в количестве восстанавливаемых битов, которое не превышает 4. Если потеряно более 4 бит, требуется повторная передача.
Различные ситуации требуют разных методов исправления ошибок. Некоторые из этих методов перечислены в других постах здесь.
@GameCat и как насчет 2-битного кода обнаружения ошибок.
В этом случае, скажем, 111 изменился на 100. Тогда мы можем быть уверены, что есть 2 неправильных бита, и мы знаем это, потому что расстояние между 111 и 100 составляет 2 бита, а расстояние от 000 до 100 составляет 1 бит. Поэтому, если мы знаем, что есть 2-битная ошибка, мы можем быть уверены, что это правильное значение.