Как вычисляется интервал Хэмминга?

Question

[hello_world42]

В книге Эндрю Таненбаума "Архитектура компьютера" у меня возникли трудности в разделе - код исправления ошибок (ECC) в следующем отрывке:

В качестве простого примера кода с обнаружением ошибок рассмотрим код, в котором к данным присоединяется один бит четности. Бит четности выбирается таким образом, чтобы число битов со значением 1 в кодовом слове было четным (или нечетным). Интервал Хэмминга для этого кода равен 2, поскольку любая одноразрядная ошибка приводит к кодовому слову с неправильной четностью. Другими словами, достаточно двух одноразрядных ошибок для перехода от одного допустимого кодового слова к другому допустимому слову. Такой код может использоваться для обнаружения одиночных ошибок. Если из памяти считывается слово с неверной четностью, поступает сигнал об ошибке. Программа выполняться не сможет, но зато не выдаст неверных результатов. В качестве простого примера кода исправления ошибок рассмотрим код с четырьмя допустимыми кодовыми словами: 0000000000, 0000011111, 1111100000 и 1111111111. Интервал Хэмминга для этого кода равен 5. Это значит, что он может исправлять двойные ошибки. Если появляется кодовое слово 0000000111, компьютер знает, что изначально это слово выглядело как 0000011111 (если произошло не более двух ошибок). При появлении трех ошибок (например, слово 0000000000 меняется на 0000000111) этот метод не подходит.

Не понимаю почему интервал Хэмминга для этого кода (0000000000, 0000011111, 1111100000 и 1111111111) равен 5, относительно какого слова он равен 5, если относительно каждого слова из списка, то 0000000000 и 1111111111 различаются на 10 бит, следовательно их интервал Хэмминга равен 10. И что вообще подразумевается под словом код или это синоним к кодовому слову (единицу из n бит, содержащую m бит данных и r контрольных разрядов, часто называют кодовым словом.)
Разъясните, пожалуйста, эту тему.

Answer 1

[Rsa97]

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

Comments

[hello_world42]

Спасибо за ответ! Не могли бы вы еще разъяснить как расстояние Хэммита влияет на возможность исправления ошибок? В той же книге рассказывалось, что для обнаружения d одноразрядных ошибок необходим код с расстоянием d + 1, а для исправления d одноразрядных ошибок необходим код с расстоянием 2d + 1. Но почему именно так до меня не дошло. И код, как я понял, - это набор допустимых кодовых слов, только тогда не понятно как для него может вычисляться расстояние Хэммита, разве что, если для каждого слова это расстояние всегда одинаковое - тогда понятно.

[Rsa97]

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

По исправлению ситуацию можно представить графически. Есть две точки на расстоянии 2d+1, соответствующие ближайшим корректным словам и ошибочное слово, лежащее между этими точками. Мы можем отнести ошибочное слово к одному из корректных, если расстояние до него меньше, чем до другого корректного слова. Такое выполняется только если это расстояние меньше или равно d, то есть исправляется не более d ошибок.

Пример:
(000, 111).
Интервал Хэмминга равен 3.
2d+1 <= 3, d = 1.
Если мы изменяем только один бит слова (d = 1), то можем гарантированно определить, какое корректное слово было искажено. 001, 010, 100 дадут 000. 110, 101, 011 дадут 111.
Если мы изменяем до двух бит (d = 2), то уже не можем восстановить слово. 001 может соответствовать 000 с одной ошибкой или 111 с двумя ошибками. Однако мы по прежнему обнаруживаем сам факт ошибки.
Если же мы изменяем до трёх бит (d = 3), то даже не можем гарантировать обнаружение ошибки. 000 это либо корректное слово, либо 111 с тремя ошибками.