Сергей Холодилов (fat_crocodile) wrote,
Сергей Холодилов
fat_crocodile

Categories:

Код Хэмминга

Есть 10 типов людей: те, кто понимают двоичную систему счисления и те, кто нет.


Я несколько раз про него читал и вроде бы даже один раз делал. Но каждый раз это было как-то непросто. То есть воспринималось как некоторая (хотя и не слишком сложная) магия, которую надо в правильном порядке сделать и тогда -- крэкс-пэкс-фэкс -- получаем в синдроме номер ошибочного бита. Откуда он там? Ну как же, мы же вместе вычисляли, по формулам. Вот формулы, вот матрица преобразования -- там всё получается, можете проверить. Доктор, а откуда у вас такие формулы? А их придумал великий Хэмминг.

Richard Wesley Hamming, кстати, если и не великий, то выдающийся без дураков. Мало того, что он сам получил премию Тьюринга и проч., так ещё и имени его учреждена медаль. Вручается с 1988 за достижения в теории информации.

В общем, поскольку там всё действительно несложно, то продраться и на некоторое время усилием удержать в голове это было можно, но потом оно каждый раз ускользало. И только сегодня я случайно понял, что формулы и матрицы не просто так, а там есть мысль, простая как полено (но от этого не менее, а более красивая), отчего-то не осознанная мною ранее. Оказывается, достаточно правильно поставить задачу, пять минут подумать, как её решать, и сразу всё становится очевидно.

А обычно почему-то сразу кидаются рассказывать про матрицы, и в целом даже получается вроде бы ясно -- вот только не понятно.

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

Это правда просто, совсем просто, и даже формул почти не будет. Но вот двоичная система счисления понадобится, не без этого.

О чем это вообще
Допустим мы передаем данные по сети, нолики и единички. Сеть не очень надежна. Космические лучи, фазы луны -- в общем, иногда что-нибудь сбойнет и нолик станет единичкой или единичка ноликом. Ну и для простоты мы предполагаем, что это случается редко и по одному биту (т.е. с ситуацией, когда разряд молнии обнулил весь пакет данных мы не боремся, такие вопросы должны как-то иначе решаться).

Важно! Мы боремся именно с ошибками вида "нолик станет единичкой или единичка ноликом". Других ошибок у нас не бывает, т.е. разряды не могут пропадать или появляться.

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

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

Т.е.

0101100 -- исходные данные
01011001 -- с добавленным контрольным битом.

Приёмник получив пакет считает в нем единички и смотрит, четное в результате получилось, или нет.

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

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

c = d0 + d1 + .. + dn

нули, конечно, не вносят вклада в сумму, так что в общем это то же самое, что "считает единички".

Сколько может стоить исправление одной ошибки
Сузим пространство возможных вариантов. Общая программа действий такова: у нас есть исходный пакет данных и мы добавляем к нему сколько-то дополнительных контрольных бит, которые будем вычислять по формулам. Принимающая сторона может повторить вычисления, получить свои значения для контрольных бит и сравнить их с теми, которые ей пришли. И по результатам этих сравнений должно быть возможно исправить ошибку в одном бите. Как-то так.

Безотносительно конкретных формул, сколько для этого нужно контрольных бит, минимально?

На каждый контрольный бит у нас на приемнике будет одно сравнение, результат может быть "совпало" или "не совпало", т.е. один бит информации.
Чтобы исправить одну ошибку нам надо уметь различать следующие состояния: ошибок нет, ошибка в первом бите, .. в i-м бите, .. в последнем бите.

Т.е. 2количество контрольных бит >= общее количество бит + 1

+ 1 тут от состояния "ошибок нет"
"общее количество бит" включает в себя как информационные, так и контрольные биты (конечно, в них тоже могут быть ошибки)

Т.е., если подставить несколько значений:

1 контрольный бит, 21 = 2 состояния, 1 бит всего, из них 0 информационных
2 контрольных бита, 22 = 4 состояния, 3 бита всего, из них 1 информационный
3 контрольных бита, 23 = 8 состояния, 7 бит всего, из них 4 информационных
4 контрольных бита, 24 = 16 состояний, 15 бит всего, из них 11 информационных
5 контрольных бита, 25 = 32 состояния, 31 бит всего, из них 26 информационных
6 контрольных бит, 26 = 64 состояния, 63 бита всего, из них 57 информационных

И т.п.

Соотношение контрольных/информационных улучшается, но происходит это, конечно, за счет того, что в последнем случае мы можем исправить одну ошибку на каждые 63 бита, а во втором одну на каждые три.

Просто для понимания: это теоретические соотношения, полученные из соображений "меньше бит нам точно не хватит". Пока не понятно, можно ли сделать код, который реализует их на практике. Но на самом деле можно, и код Хэмминга как раз подходит.

Код Хэмминга: постановка задачи и куча подсказок
Итак, приёмник получает пакет, вычисляет свою версию контрольных бит, сравнивает их с теми, которые получил. По результатам сравнения вычисляет синдром. Синдром это число, у которого i-й бит равен 1, если i-е контрольные биты не совпали. Если совпали, то соответствующий бит синдрома равен 0.

Ну и результат:

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

Крэкс-пэкс-фэкс!

Это постановка задачи.
Теперь некоторые детали о том, как выглядит решение -- собственно всё, кроме формул.

  • уже по постановке задачи понятно, что важно, под какими номерами в пакете идут контрольные биты. Контрольные биты находятся внутри пакета и идут по номерам степеней двойки. То есть как-то так:

    10010110100 -- исходные данные
    cc1c001c0110100 -- с добавленными контрольными битами
    c1c213c4050617c809110111012113014015 -- с нумерацией битов (от 1, как обещали)

  • не менее важно, в каком порядке контрольные биты входят в синдром. i-й контрольный бит стоит на месте 2i, т.е. с0 (самый младший) на месте 1, с1 на 2, с2 на 4, и т.п.

    c0c11c2001c30110100

  • все формулы имеют такой же вид, как в контроле четности. То есть ci = dk + dr + ... + dp, где dj это какие-то информационные биты. Сложение, конечно, по модулю 2.



Тут можно пять минут подумать.

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

Давайте посмотрим на пример:

c0c11c2001c30110100

приемник это получил и вычислил свои контрольные биты

c'0c'1c'2c'3

Теперь, если в синдроме должен быть номер ошибочного бита, а сравнение c3 и c'3 отвечает за третий (считаем от 0) бит синдрома, то это сравнение должно сообщать о наличие/отсутствие ошибки в битах с номерами 8, 9, 10, .. 15. Просто потому, что если значение синдрома от 8 до 15, то в двоичной системе это от 10002 до 11112 и его третий (старший в данном случае) бит установлен в 1. Отсюда получаем:

c3 = d9 + d10 + d11 + d12 + d13 + d14 + d15

Если при передаче изменится значение бита 8 (это как раз сам c3), 9, 10 .. 15 (а эти участвуют в вычислении c3), то вычисленное на приёмнике таким же образом c'3 не совпадет и -- ура -- третий бит синдрома равен 1.

Аналогично можно выделить область ответственности остальных контрольных битов.

c2 = d5 + d6 + d7 + d12 + d13 + d14 + d15

Потому что это синдромы из диапазонов 01002 -- 01112 и 11002 -- 11112 -- и второй бит у них установлен в 1.

c1 = d3 + d6 + d7 + d10 + d11 + d14 + d15

Это синдромы 00102, 00112, 01102, 01112, 10102, 10112, 11102, 11112.

И наконец

c0 = d3 + d5 + d7 + d9 + d11 + d13 + d15

А это просто младший бит, т.е. все нечетные синдромы.
Обобщить этот пример и получить классический код Хэмминга довольно несложно.

Если по честному, то к ci относятся номера из диапазона [2i, 2i+1) и далее от такого же диапазона, смещенного на 2i+1, потом ещё на 2i+1 и т.п.
Если по хардкору, то можно даже как-то так: c[i] = sum(d[j] for j in range(i+1, n) if j & (1 << i)) % 2

Вот собственно и всё.


Теперь вы знаете, как работает код Хэмминга. Если же ещё хочется понять, какого черта о нём написано в википедии, читайте дальше.

[приложения: то же, но без сравнений; пример; матрицы; обобщение; несколько ошибок]
Appendix A: Отказываемся от сравнений
Мне кажется, со сравнениями понятнее, но в других местах это описывают без них, и определенный смысл в этом есть, так что надо как-то объяснить...

Выше была предложена следующая модель вычисления синдрома:
- по полученным данным приемник вычисляет свои контрольные биты c'0..c'k
- сравнивает их с полученными контрольными битами c0..ck
- если c'i != ci, то i-й бит синдрома si устанавливается в 1.

Первое, что тут можно упростить это собственно сравнение. Так как сложение по модулю 2 одинаковых значений дает 0, а разных -- 1, вместо сравнения можно написать

si = c'i + ci

Дальше, поскольку c'i вычисляется на приёмнике по формуле вида c'i = dk + dr + ... + dp, это выражение можно подставить и получить

si = ci + dk + dr + ... + dp

То есть, поскольку ci должен дополнять до четности биты dk, dr, ..., dp, бит si будет равен 1, если контроль четности не проходит, то есть, если некорректно передан либо один из битов dk, dr, ..., dp, либо сам бит ci. Это в точности то, что нам надо.

Appendix B: Пример
Ну, куда же без примера.

10010110100 -- исходные данные
сс1с001с0110100 -- напихали контрольных битов

c0c113c2050617c309110111012113014015 -- и все пронумеровали для ясности

Теперь вычисляем контрольные биты:
с3 = 09 + 110 + 111 + 012 + 113 + 014 + 015 = 3 = 1
с2 = 05 + 06 + 17 + 012 + 113 + 014 + 015 = 2 = 0
с1 = 13 + 06 + 17 + 110 + 111 + 014 + 015 = 4 = 0
с0 = 13 + 05 + 17 + 09 + 111 + 113 + 015 = 4 = 0

001000110110100 -- итого
001001110110100 -- изменим шестой бит

Заново вычисляем контрольные биты

с'3 = 09 + 110 + 111 + 012 + 113 + 014 + 015 = 3 = 1
с'2 = 05 + 16 + 17 + 012 + 113 + 014 + 015 = 3 = 1
с'1 = 13 + 16 + 17 + 110 + 111 + 014 + 015 = 5 = 1
с'0 = 13 + 05 + 17 + 09 + 111 + 113 + 015 = 4 = 0

В результате c'1 != c1 и c'2 != c2, то есть синдром равен 01102 = 6. Магия!

Appendix C: причем тут матрицы
Посмотрим на преобразование "туда", т.е. кодирование. На входе битовый вектор длины n, на выходе битовый вектор длины m, m > n (добавились контрольные биты). Каждый бит выходного вектора либо просто равен соответствующему биту входного, либо получается как линейная комбинация нескольких входных битов. Это выглядит как работа для матрицы!

Конечно, это можно так записать, взять матрицу m*n, умножить её на вектор длины n и получить закодированный вектор. Строки матрицы, соответствующие информационным битам содержат только одну 1, строки матрицы, соответствующие контрольным -- несколько единиц, те, которые нужны по формуле.

Теперь вычисление синдрома. На входе битовый вектор длины m, на выходе вектор длины m-n, и, как понятно после Приложения A, все биты выходного вектора и тут получаются как линейные комбинации входного. То есть это тоже работа для матрицы. И вот это будет как раз та матрица, которую везде рисуют.

Если изобразить зоны ответственности контрольных битов в виде таблички, она окажется примерно такой (такой, с точностью до перестановок строк):

c0c13c2567c39101112131415
ответственность с0++++++++
ответственность с1++++++++
ответственность с2++++++++
ответственность с3++++++++


теперь осталось заменить + на 1, а в пустые места поставить 0, и это будет в точности матрица, на которую нужно умножить полученный вектор, чтобы вычислить синдром.

Appendix D: обобщаем
На эту матрицу можно посмотреть с другой стороны. Каждый столбец соответствует одному биту вектора. При изменении этого бита окажутся затронуты -- то есть, равны 1 -- те биты синдрома, которые за него "отвечают". То есть, фактически, в столбце под битом номер i записан синдром, который мы получим при изменении этого бита.

И теперь можно раскрутить всё в обратную сторону!

a) Взять матрицу правильного размера, выбрать, где там будут контрольные биты, написать под каждым битом симпатичный синдром -- готово, это будет матрица получения синдрома.
b) По ней понять, что за формулы соответствуют контрольным битам. Этот пункт накладывает ограничения на предыдущий. Формулы для одних контрольных битов не должны включать другие контрольные биты, т.к. их нет в исходном векторе. Это значит, что соответствующий контрольному биту синдром должен состоять из одной единички -- его самого.
с) По ним уже, если хочется, можно сделать матрицу преобразования, тоже поставив в ней контрольные биты на выбранные места.

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

В общем, это не рокет сайнс, конечно, и вроде бы можно эту идею и сразу понять. Но почему-то у меня до сих пор "сразу" не получалось. А сейчас получилось :)

Appendix E: если ошибок больше
Понятно, что происходит, если ошибка не одна. Каждый изменившийся бит меняет те биты синдрома, которые отмечены в его столбце. Если битов изменилось несколько, в результате получится побитовая сумма соответствующих им синдромов. Если все синдромы в матрице уникальны, то никакие два при побитовой сумме не дадут 0, а значит двойную ошибку можно обнаружить, хотя и не исправить. Тройную уже не обязательно, как повезёт.

Обычно говорят, что код Хэмминга позволяет исправить одинарную и обнаружить двойную. Мне кажется, точнее было бы сказать "или". Потому что он не позволяет отличить двойную от одинарной, по синдрому не понятно, можем ли мы это исправить, или нет, это решение, которое нужно принять заранее: либо всё исправляем (и возможно попытаемся исправить лишнее), либо всё замечаем (и не исправляем даже то, что могли бы).

И, кстати, интересный нетривиальный результат: из соображений расстояния Хэмминга (я про это не писал тут, почитайте сами, там просто) возможен код, который умеет замечать одну и две ошибки, но не умеет исправлять, и он должен быть экономнее, чем код Хэмминга. Но при выбранном подходе не получается сэкономить и замечать две ошибки. Потому что если у нас в матрице есть два одинаковых столбца, то ошибка в этих двух битах даст нулевой синдром и мы её не обнаружим. А если все столбцы уникальные, то это аналог Хэмминга, мы уже можем и исправлять... То есть такой код должен строиться по каким-то другим принципам, он уже не может укладываться в линейные комбинации битов и матрицы.
Tags: математика, программинг
Subscribe

  • (no subject)

    Очень простую штуку объяснили, как-то мимо проходила. В книжках про ассемблер и прочее такое пишут про "представление отрицательных чисел в…

  • (no subject)

    Наконец вроде осознал, когда и зачем аксиома выбора нужна, а когда она не нужна. Если у нас есть одно непустое множество X и нам нужно взять…

  • CRC-3: как его обойти

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

  • Post a new comment

    Error

    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 3 comments