§ Для чего нужен код Хэмминга
Иногда случается, что Алиса, передавая Бобу сообщение, совершает фатальную, роковую ошибку и случайно ошибается в одной букве. Боб же, принимая от Алисы послание, читает его и даже не догадывается, что где-то появилась ошибка. Как же тогда быть в этом случае?Для этого и придуманы коды проверок сообщений, одним из которых является код Хэмминга. Что он умеет?
- Обнаруживать ошибку в переданном сообщении
- Исправлять ошибку, если она была совершена один раз на все сообщение
§ Бит четности
Продолжая тему Алисы и Боба, (которые являются большими специалистами и экспериментаторами в области связи), допустим, что Алиса, передавая сообщение Бобу, сказала, что количество единиц в этом сообщении, а она передает его в двоичном коде, либо четно, либо не четно.Например, Алиса хочет передать Бобу сообщение
001101
. Подсчитав количество единиц, Алиса приходит к выводу, что это количество — нечетно, и потому добавляет к сообщению также контрольный бит, равный 1. Если бы количество единиц было бы четным, то контрольный бит равнялся бы 0.Итоговое сообщение получилось
001101
и 1
— бит четности, контрольный бит, контрольная сумма, разные названия есть у него. В один момент, передавая по зашумленному каналу связи, приемник Боба получил следующее сообщение: 101101
и 1
. Боб не знает о содержании исходного сообщения, но начинает считать количество единиц и приходит к выводу, что количество единиц — четно, и контрольный бит, вообще-то, должен равняться 0, а он равняется 1.Исходя из этого, Боб делает вывод, что в сообщении где-то допущена ошибка, но он не знает, где именно. Несмотря на это, этого может даже быть вполне достаточно, чтобы сообщить Алисе, чтобы она выслала сообщение заново.
Проверка бита четности является самым простым, но не всегда надежным способом установить, что где-то есть ошибка. Дело в том, что если изменились 2 бита, то количество нечетных или четных останется тем же, а само сообщение уже не будет правильным. Потому контрольную сумму обычно считают другим методом, например, используя CRC32, где изменение любого количества бит будет менять контрольную сумму на совершенно другое число.
§ Определение четности
Подсчет бита четности ведут через так называемый XOR-элементов, или элемент "Исключающее ИЛИ". Этот элемент находится в основе сумматоров. Его таблица истинности такова, что еслиA == B
, то он выдает 0, иначе 1.Как известно, нам нужно подсчитать именно четность. Как определяется четность? Для этого обычно делят на 2 и смотрят остаток. Если остаток 1, то число не является четным, и наоборот, если 0, то число — четное. С точки зрения бинарной логики, тут все гораздо проще, четность находится в младшем бите итоговой суммы.
Например, сложим число 1+1 в двоичном коде, получаем 10. Младший бит результата - 0, результат четный. На самом деле, мы можем вообще избавиться от всех битов результата, кроме младшего, оставив только его, и тогда все получается элементарно. Чтобы вычислить результат суммы, необходимо применить A xor B = C, где C будет битом четности.
Сосчитаем четность у числа 10111.
- Берем первые биты, складываем 1+0=10, отбрасываем старшие биты, остается 0
- Складываем полученный результат с третьим битом: 0+1=1
- Опять, результат с четвертым: 1+1=10 (старший бит удаляем)
- И наконец, с пятым: 0+1=1
§ Определение позиции ошибки
С битом четности мы разобрались, и как находить наличие ошибки в сообщении — тоже, но теперь остался вопрос, а как же теперь найти место, где ошибка произошла? В действительности, это оказалось настолько элементарно, что я удивился, почему раньше это не мог понять (сегодня 2023г, а в родился в 1987).Для того, чтобы объяснить, я выберу сообщение длиной ровно 8 бит — 1 байт, только сразу оговорюсь, что количество бит в сообщении может быть как угодно большим, этот код работает с любым количеством бит.
Чтобы указать номер бита, в котором находится ошибка, нам потребуется ровно 3 бита. То есть, например, если ошибка в бите 5, то в двоичном коде этот номер был бы записан как
101
. Если ошибка в бите 7, то тогда номер бита будет равен 111
. То что я говорю сейчас об этом, имеет смысл. Если мы ищем номер бита, в котором произошла ошибка, то нам же и потребуется число, которое может эти номера вместить.Сделаем одну хитрость. В отличии от контрольного бита, сосчитаем не все подряд биты, а через один бит. Сейчас приведу пример:
1234567 -- номера битов исходного сообщения x x x x -- биты, для которых считаем четностьКазалось бы, нелогично. Зачем считать не всё? А вот как раз в этом и кроется смысл.
Представим, что при передаче сообщения был изменен бит 2. Контрольная сумма останется той же, ничего не изменится в ней, поскольку мы ее просто не считали. Здесь ничего пока что сделать нельзя, сообщение проверить не можем.
Но, что если бит был изменен в 1 или 3, или 5? Тогда контрольная сумма меняется и мы это увидим потому, что контрольная сумма будет уже другой. Что это значит? А то, что мы уже твердо знаем, что да, где-то либо в 1, 3, 5 или 7 бите была допущена ошибка. Иными словами, таким образом, сужается круг поиска с 8 битов до 4.
Как видно, одного бита недостаточно для того, чтобы установить, где произошла ошибка. Для этого введем в игру еще один контрольный бит, который будет считать не через 1 бит, а через 2 бита:
1234567 -- номера битов x x x x -- контрольная сумма r0 xx xx -- контрольная сумма r1Появляется вспомогательный бит контрольной суммы, который будет уточнять положение ошибочного бита. Сейчас я поясню, как это происходит.
Допустим, что ошибка произошла в бите 1. Видно, что контрольная сумма r1 уже будет не совпадать, и следовательно, у нас ошибка либо в бите 1, либо в бите 5 — всего лишь 2 варианта. Это произошло потому, что был введен уточняющий бит контрольной суммы, которая сужает круг поиска уже с 4 до 2 возможных вариантов.
Получается, что код Хэмминга это своего рода бинарный поиск! Да, теперь у нас 2 варианта, но этого недостаточно, чтобы четко установить, где именно произошла ошибка. И значит, придется добавить еще 1 контрольный бит для этого.
1234567 -- номера битов x x x x -- контрольная сумма r0 xx xx -- контрольная сумма r1 xxxx -- контрольная сумма r2Вот теперь можно точно и с уверенностью сказать, где именно будет допущена ошибка, основываясь на контрольных битах r0,r1,r2. Давайте проверим.
- Ошибка совершена в бите 5. Это значит, что бит r0 и r2 будут не совпадать, поскольку бит r0 контролирует биты 1,3,5,7, а бит r2 - биты 4,5,6,7. Единственный вариант, где не совпадает r0 и r2, это будет бит 5 и никакой другой
- Допускается ошибка в бите 3. Не совпадет контрольная сумма у r0 и r1 - они изменятся из-за этого.
Это выглядит как какая-то магия, но на самом деле, никакой магии тут нет. Ведь допуская ошибку в 1,3,5 или 7 бите, меняется r0 — младший бит номера ошибки, или допуская ошибку в 2,3,6,7 - меняется второй бит результата, а биты номер 4,5,6,7 содержат третий бит номера ошибки.
§ Код Хэмминга
Пожалуй, сейчас мы подобрались к самой сложной части, это непосредственно к тому, как записываются коды Хэмминга. Дело в том, что в коде, помимо самих битов сообщения, передаются и контрольные биты, при этом, эти же контрольные биты тоже могут быть ошибочные, так что их самих тоже можно восстанавливать. Но как это сделать?Итак, для 8 битного сообщения ранее определили, что необходимо 3 контрольных бита, чтобы указать номер ошибки. Но, помимо самого сообщения, также надо еще и 3 бита передать. Это значит, что будут переданы как минимум 8+3 бита.
Контрольные биты располагаются, согласно коду Хэмминга в позициях, равных степеней двойки, а именно, бит r0 будет находиться в 1-й позиции, бит r1 — во 2-й, бит r2 — в 4, r3 — в 8 и так далее.
Сообщение | r0 | r1 | 0 | r2 | 1 | 2 | 3 | r3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
Бит № | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
Бит #0 | x | x | x | x | x | x | ||||||
Бит #1 | x | x | x | x | x | x | ||||||
Бит #2 | x | x | x | x | x | |||||||
Бит #3 | x | x | x | x | x |
Рис 1. Код для 8 бит
По этой таблице очень легко понять, что, к примеру, совершенная ошибка в 3-м и 2-м бите дают число
1100
, что в десятичном виде даст 12. Как видим, для того чтобы закодировать 8 бит, потребуется 4 бита контроля. Для 16 бит уже потребуется дополнительные 5 бит:Сообщение | r0 | r1 | 0 | r2 | 1 | 2 | 3 | r3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | r4 | 11 | 12 | 13 | 14 | 15 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Бит № | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
Бит #0 | x | x | x | x | x | x | x | x | x | x | x | ||||||||||
Бит #1 | x | x | x | x | x | x | x | x | x | x | |||||||||||
Бит #2 | x | x | x | x | x | x | x | x | x | x | |||||||||||
Бит #3 | x | x | x | x | x | x | x | x | |||||||||||||
Бит #4 | x | x | x | x | x | x |
Рис 2. Код для 16 бит
Почему был выбран такой порядок установки контрольных бит? Не знаю, на самом деле, они могут быть расположены в любом порядке, это не повлияет ни на что, но видимо это сделано из-за определенного удобства. Если взглянуть на иллюстрации кода Хэмминга, то видно, что каждый контрольный бит открывает собственный новый бит так называемого "синдрома" номер 0,1,2 и т.д. Так что порядок расположения контрольных битов в сообщении был выбран по причине его наглядности.
§ Кодирование, декодирование
А теперь, с учетом того, что в сообщении появились новые биты, как теперь кодировать их? Элементарно. Их просто не надо учитывать при кодировании, то есть, они просто будут 0. Все остальные биты, конечно же, будут учитываться. Возьмем, к примеру, сообщение10010110
и попробуем закодировать его через код Хэмминга.Сообщение | r0 | r1 | 0 | r2 | 1 | 2 | 3 | r3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
Бит № | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
Данные | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
Бит #0 | 0 | 0 | 1 | 0 | 1 | 0 | ||||||
Бит #1 | 0 | 0 | 1 | 0 | 0 | 0 | ||||||
Бит #2 | 0 | 1 | 1 | 0 | 1 | |||||||
Бит #3 | 0 | 1 | 0 | 0 | 1 |
Рис 3. Код сообщения
Сначала впишем в позиции, где должны быть биты сообщения, нужные биты.
- Это значит, что в позицию номер 3 (там где написано "Бит №") пойдет бит 0, потом в позицию 5 пойдет бит 1, далее в 6 — бит 1, в 7 — бит 0. В позициях 9,10,11 и 12 будут оставшиеся 4 бита
1001
. - В позициях 1,2,4,8 будут нули
Теперь, считаем четность для всех контрольных битов.
-
r0 = 0 xor 0 xor 1 xor 0 xor 1 xor 0 = 0
-
r1 = 0 xor 0 xor 1 xor 0 xor 0 xor 0 = 1
-
r2 = 0 xor 1 xor 1 xor 0 xor 1 = 1
-
r3 = 0 xor 1 xor 0 xor 0 xor 1 = 0
0 1 0 1 1 1 0 0 1 0 0 1
.Почему так важно не считать биты r0,r1 и т.д. при кодировании? Все просто, это потому что нам необходимо знать изменения именно в исходном сообщений, а также для того, чтобы проверить, не изменился ли сам контрольный бит.
Представим, что при передаче сообщения от Алисы к Бобу изменился контрольный бит r1, который находится в позиции 2. Боб, принимая сообщения, высчитывает контрольные биты заново, сверяя их с теми, которые пришли от Алисы. У Алисы контрольный бит r1 был равен 1, а у Боба он стал равным 0. Боб видит эту ошибку и, поскольку все остальные контрольные биты в порядке, видит, что номер полученного бита по итогу указывает на то, что изменился r1. Но Боб, конечно, и сам догадался.
Еще одна причина, по которой контрольные биты располагаются в сообщении подобным образом в том, что когда регистрируется одиночный бит ошибки, то он всегда указывает на то, что изменился именно контрольный бит, а не бит в самом сообщении. Это, опять-таки, очень удобно получается и наглядно.
Делая вывод, могу сказать следующее. Код Хэмминга быстрый и достаточно хороший, но и он обладает некоторыми недостатками. Для того, чтобы код работал, необходимо передавать избыточные данные. Для 8 битного числа количество избыточных данных составляет аж 4 бита, что в 1.5 раза самого сообщения, так что короткие сообщения передавать накладно. Для 16 бит количество избыточных бит составляет только 5 бит, но и это 30%.
Второй недостаток в том, что при двойной ошибке исправить бит будет уже нельзя, лишь только зафиксировать факт самой ошибки. Также факт того, что это именно двойная ошибка, остается неизвестен.
Код Хэмминга удобно применять там, где количество ошибок единично и они появляются редко, например, в ECC-памяти или еще где-нибудь, к примеру, для регистрации и исправления битов, которые могут измениться в результате космических лучей.