Как исправить сообщение с помощью кода Хэмминга

Question

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

Спасибо.

Answer 1

Это все о Расстояние Хэмминга.

Расстояние Хэмминга между двумя значениями по основанию 2 — это количество битов, на которые они отличаются.Итак, если вы передаете A, а я получаю B, то количество битов, которые должны были быть переключены при передаче, равно расстоянию Хэмминга между A и B.

Коды Хэмминга полезны, когда биты в каждом кодовом слове передаются каким-то образом отдельно.Нас не волнует, являются ли они последовательными или параллельными, но они, например, не объединяются в аналоговое значение, представляющее несколько битов, или не сжимаются/шифруются после кодирования.

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

Итак, код Хэмминга обычно направлен на исправление 1-битных ошибок и/или обнаружение 2-битных ошибок (подробную информацию о двух основных типах см. в статье в Википедии).Могут быть созданы коды, которые исправляют/обнаруживают более серьезные ошибки, но AFAIK используется не так часто.

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

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

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

Очевидно, что 3-битные ошибки не исправляются кодом Хэмминга SECDED.Полученное значение находится дальше от значения, которое вы фактически отправили, чем до какой-либо другой кодовой точки, и я ошибочно «исправляю» его на неправильное значение.Таким образом, вам либо нужна достаточно надежная передача, чтобы вы не заботились о ней, либо вам также необходимо обнаружение ошибок более высокого уровня (например, CRC для всего сообщения).

Answer 2

Конкретно из Википедия, алгоритм следующий:

1. Пронумеруйте биты, начиная с 1:бит 1, 2, 3, 4, 5 и т. д.
2. Запишите номера битов в двоичном формате.1, 10, 11, 100, 101 и т. д.
3. Все позиции битов, которые являются степенями двойки (имеют только один бит 1 в двоичной форме своей позиции), являются битами четности.
4. Все остальные позиции битов с двумя или более битами 1 в двоичной форме являются битами данных.
5. Каждый бит данных включен в уникальный набор из 2 или более битов четности, что определяется двоичной формой его битовой позиции.
   1. Бит четности 1 охватывает все позиции битов, в которых установлен младший значащий бит:бит 1 (сам бит четности), 3, 5, 7, 9 и т. д.
   2. Бит четности 2 охватывает все позиции битов, для которых установлен второй наименее значимый бит:бит 2 (сам бит четности), 3, 6, 7, 10, 11 и т. д.
   3. Бит четности 4 охватывает все позиции битов, для которых установлен третий наименее значимый бит:биты 4–7, 12–15, 20–23 и т. д.
   4. Бит четности 8 охватывает все позиции битов, у которых установлен четвертый наименее значимый бит:биты 8–15, 24–31, 40–47 и т. д.
   5. В общем, каждый бит четности охватывает все биты, в которых двоичное И позиции четности и позиции бита не равно нулю.

Answer 3

А статья в Википедии объясняет это довольно хорошо.

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