26 марта 2012 в 16:12

Код Хэмминга. Пример работы алгоритма

Вступление.


Прежде всего стоит сказать, что такое Код Хэмминга и для чего он, собственно, нужен. На Википедии даётся следующее определение:

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

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

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

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

Как это работает.


Для того, чтобы понять работу данного алгоритма, рассмотрим пример.

Подготовка


Допустим, у нас есть сообщение «habr», которое необходимо передать без ошибок. Для этого сначала нужно наше сообщение закодировать при помощи Кода Хэмминга. Нам необходимо представить его в бинарном виде.



На этом этапе стоит определиться с, так называемой, длиной информационного слова, то есть длиной строки из нулей и единиц, которые мы будем кодировать. Допустим, у нас длина слова будет равна 16. Таким образом, нам необходимо разделить наше исходное сообщение («habr») на блоки по 16 бит, которые мы будем потом кодировать отдельно друг от друга. Так как один символ занимает в памяти 8 бит, то в одно кодируемое слово помещается ровно два ASCII символа. Итак, мы получили две бинарные строки по 16 бит:

и

После этого процесс кодирования распараллеливается, и две части сообщения («ha» и «br») кодируются независимо друг от друга. Рассмотрим, как это делается на примере первой части.
Прежде всего, необходимо вставить контрольные биты. Они вставляются в строго определённых местах — это позиции с номерами, равными степеням двойки. В нашем случае (при длине информационного слова в 16 бит) это будут позиции 1, 2, 4, 8, 16. Соответственно, у нас получилось 5 контрольных бит (выделены красным цветом):

Было:


Стало:


Таким образом, длина всего сообщения увеличилась на 5 бит. До вычисления самих контрольных бит, мы присвоили им значение «0».

Вычисление контрольных бит.


Теперь необходимо вычислить значение каждого контрольного бита. Значение каждого контрольного бита зависит от значений информационных бит (как неожиданно), но не от всех, а только от тех, которые этот контрольных бит контролирует. Для того, чтобы понять, за какие биты отвечает каждых контрольный бит необходимо понять очень простую закономерность: контрольный бит с номером N контролирует все последующие N бит через каждые N бит, начиная с позиции N. Не очень понятно, но по картинке, думаю, станет яснее:

Здесь знаком «X» обозначены те биты, которые контролирует контрольный бит, номер которого справа. То есть, к примеру, бит номер 12 контролируется битами с номерами 4 и 8. Ясно, что чтобы узнать какими битами контролируется бит с номером N надо просто разложить N по степеням двойки.

Но как же вычислить значение каждого контрольного бита? Делается это очень просто: берём каждый контрольный бит и смотрим сколько среди контролируемых им битов единиц, получаем некоторое целое число и, если оно чётное, то ставим ноль, в противном случае ставим единицу. Вот и всё! Можно конечно и наоборот, если число чётное, то ставим единицу, в противном случае, ставим 0. Главное, чтобы в «кодирующей» и «декодирующей» частях алгоритм был одинаков. (Мы будем применять первый вариант).
Высчитав контрольные биты для нашего информационного слова получаем следующее:

и для второй части:


Вот и всё! Первая часть алгоритма завершена.

Декодирование и исправление ошибок.


Теперь, допустим, мы получили закодированное первой частью алгоритма сообщение, но оно пришло к нас с ошибкой. К примеру мы получили такое (11-ый бит передался неправильно):

Вся вторая часть алгоритма заключается в том, что необходимо заново вычислить все контрольные биты (так же как и в первой части) и сравнить их с контрольными битами, которые мы получили. Так, посчитав контрольные биты с неправильным 11-ым битом мы получим такую картину:

Как мы видим, контрольные биты под номерами: 1, 2, 8 не совпадают с такими же контрольными битами, которые мы получили. Теперь просто сложив номера позиций неправильных контрольных бит (1 + 2 + 8 = 11) мы получаем позицию ошибочного бита. Теперь просто инвертировав его и отбросив контрольные биты, мы получим исходное сообщение в первозданном виде! Абсолютно аналогично поступаем со второй частью сообщения.

Заключение.


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

Примечание.


На написание этого топика меня подвигло то, что в поиске я не нашёл на Хабре статей на эту тему (чему я был крайне удивлён). Поэтому я решил отчасти исправить эту ситуацию и максимально подробно показать как этот алгоритм работает. Я намеренно не приводил ни одной формулы, дабы попытаться своими словами донести процесс работы алгоритма на примере.

Источники.


1. Википедия
2. Calculating the Hamming Code
+61
59190
285
tltshnik 9,0

Комментарии (26)

0
akaBd, #
познавательно, спасибо
0
Malerok, #
Очень интересно, надо попробовать реализовать самому, +1 ^_^
+1
Lamaster, #
Всё давно реализовано. Насколько мне известно, кодирование по Хэммингу использовалось в dial-up сетях для устранения помех. Но в любом случае, практика не помешает.
+15
janitor, #
Я писал две статьи про помехоустойчивое кодирование, года полтора назад. Обе лежат в черновиках, так и не дописанные. Правда там не только про код Хэмминга, а еще про код с проверкой на четность и блочное кодирование было… Если кому интересно (к первой статье маленький интерес был, поэтому и затих энтузиазм), могу опубликовать.
0
lukashes, #
Недостаточно кармы для голосования за Ваш коммент, поэтому отпишусь.

Конечно, добавляйте, темы автоматизации и кодирования всегда очень востребованы на хабре. От себя добавлю что очень приятно читать что-то связанное со своей специализацией в ВУЗе.
–1
maratfmu, #
Вы университете лабораторная была
+1
Lampus, #
А я это дело даже в железе реализовал в своё время (кодер/декодер Хэмминга).
+1
lukashes, #
Здорово, помнится, мне я лабораторную работу по коду Хэмминга защищал 2 часа. Проблема была в том, что я пытался объяснить аппаратную реализацию, но неправильно истолковал исходные данные.

Теперь осталось добавить статью по циклическим кодам, я уже начал их забывать.
+1
Arterius, #
Поддерживаю касательно статьи по циклическим кодам.
+1
dzigoro, #
В питерском политехе коды Хемминга на схемотехнике проходят. Спасибо за статью!
0
zodiac, #
А у нас на первом курсе проходят.
+1
lorc, #
Два вопроса:
1. Что будет если изменился контрольный бит? Судя по вашему описанию, мы поменяем какой-то информационный бит. Что не совсем верно.

2. Что будет, если изменилось 2 бита? Ясно, что исправить это мы не сможем, но сможем ли определить, что была ошибка?
+3
jcmvbkbc, #
1. поскольку при проверке не совпадёт единственный контрольный бит (потому что именно он поменялся), сумма номеров несовпадающих контрольных битов укажет как раз на него самого.
2. если изменилось два бита (очевидно, имеющих разные номера), сумма их номеров по модулю 2 будет отлична от 0, а значит такое изменение гарантированно даст ненулевой вклад в синдром (значения контрольных битов). При изменении 3 или более битов сообщение может выглядеть как хорошее (например, изменение битов 1, 2 и 3).
0
lorc, #
По второму пункту: да, синдром будет ненулевой. Но ведь он будет указывать на какой-то один бит. Как определить, что на самом деле была двукратная ошибка?

В данном примере синдром имеет длину 5 бит, так что теоретичиски может указывать за пределы сообщения.
Но в примере (7,4) каждый синдром указывает на какой-то поврежденный бит.

В общем, мне кажется всего этого не хватает в предложенной статье…
0
jcmvbkbc, #
По второму пункту: да, синдром будет ненулевой. Но ведь он будет указывать на какой-то один бит. Как определить, что на самом деле была двукратная ошибка?


К сожалению, никак. Насколько я понимаю, это два разных способа использования кода хэмминга: либо мы в случае ненулевого синдрома бракуем сообщение (и тогда код гарантирует нам, что все 1- и 2- битовые ошибки будут отбракованы), либо мы молча исправляем бит, на который указывает синдром (и тогда даже в случае однобитовых ошибок мы получаем верное сообщение). Какой способ использования выбрать — зависит от поставленной цели и свойств канала/передаваемых данных.
0
lorc, #
Да нет, тут где-то подвох есть. Для обнаружения двухкратных ошибок хватит двух бит и суммы по модулю 4.
Да и везде пишут, что код Хемминга позволяет исправлять однократные и обнаруживать двукратные ошибки.
0
jcmvbkbc, #
позволяет исправлять однократные и обнаруживать двукратные ошибки

Ну да. Для 2-битовой ошибки синдром ненулевой? — ненулевой. Ошибка обнаружена? — обнаружена. Там же не пишут, что он позволяет исправлять, обнаруживать и отличать случаи, когда можно исправлять, от случаев когда нельзя (: Для этого просто недостаточно избыточности этого кода. С другой стороны, добавление общего бита чётности решает эту проблему (см. www.sernam.ru/book_tec.php?id=85):
Расширенный код Хэмминга образуется из совершенного путем добавления общей проверки на четность, т. е. проверочного символа, равного сумме всех символов кода Хэмминга. Код имеет кодовое расстояние, что позволяет исправить все однократные и одновременно обнаружить все двукратные ошибки. Такой режим целесообразен, в частности, в системах передачи информации с обратной связью.
0
jcmvbkbc, #
… кодовое расстояние d = 4, что позволяет…
0
lorc, #
Хм, действительно. Спасибо.
А я столько лет жил в уверености что код Хэмминга позволяет одновременно делать и то и другое :)
0
lorc, #
А нет, с двумя битами я поторопился, каюсь :/ Не выйдет так.
0
serbod, #
На практике, обычно сообщение дополняется контрольной суммой (CRC), и если после коррекции контрольная сумма не сошлась, значит бракуем нафиг все сообщение.
–2
vvsh, #
а почему бы не привести реализацию алгоритма на c++ или java?
+1
jcmvbkbc, #
На С например так (использование, правда, не (21, 16) как в статье, а (38,32)):

#include <assert.h>
#include <string.h>
#include <stdint.h>
#include <limits.h>

int get_bit(const void *in, size_t n)
{
    return (((const uint8_t*)in)[n / CHAR_BIT] & (1 << (n % CHAR_BIT))) != 0;
}

void set_bit(void *out, size_t n, int bit)
{
    if (bit)
        ((uint8_t*)out)[n / CHAR_BIT] |= (1 << (n % CHAR_BIT));
    else
        ((uint8_t*)out)[n / CHAR_BIT] &= ~(1 << (n % CHAR_BIT));
}

void flip_bit(void *out, size_t n)
{
    ((uint8_t*)out)[n / CHAR_BIT] ^= (1 << (n % CHAR_BIT));
}

size_t encode(void *out, const void *in, size_t in_bits)
{
    size_t i, j, k;
    unsigned s = 0;

    for (i = j = 0; j < in_bits; ++i) {
        if ((i + 1) & i) {
            if (get_bit(in, j))
                s ^= i + 1;
            set_bit(out, i, get_bit(in, j));
            ++j;
        }
    }
    for (k = 1; k < i; k <<= 1) {
        set_bit(out, k - 1, s & k);
    }
    return i;
}

size_t decode(void *out, const void *in, size_t in_bits, unsigned *out_syndrome)
{
    size_t i, j;
    unsigned s = 0;

    for (i = j = 0; i < in_bits; ++i) {
        if (get_bit(in, i))
            s ^= i + 1;
        if ((i + 1) & i) {
            set_bit(out, j, get_bit(in, i));
            ++j;
        }
    }
    *out_syndrome = s;
    return j;
}

size_t decode_and_fix(void *out, const void *in, size_t in_bits)
{
    unsigned s;
    size_t out_bits = decode(out, in, in_bits, &s);

    if (s && s <= in_bits && (s & (s - 1))) {
        unsigned k;

        for (k = 0; 1u << k < s; ++k);
        flip_bit(out, s - k - 1);
    }
    return out_bits;
}

int main()
{
    char habr[4] = "habr";
    char encoded[5];
    char decoded[4];
    unsigned s;
    size_t i;

    size_t encoded_bits = encode(encoded, habr, sizeof(habr) * CHAR_BIT);
    size_t decoded_bits = decode(decoded, encoded, encoded_bits, &s);
    assert(s == 0);
    assert(encoded_bits == sizeof(habr) * CHAR_BIT + 6);
    assert(decoded_bits == sizeof(habr) * CHAR_BIT);
    assert(memcmp(habr, decoded, sizeof(habr)) == 0);

    for (i = 0; i < encoded_bits; ++i) {
        flip_bit(encoded, i);
        decoded_bits = decode(decoded, encoded, encoded_bits, &s);
        decoded_bits = decode_and_fix(decoded, encoded, encoded_bits);
        assert(decoded_bits == sizeof(habr) * CHAR_BIT);
        assert(memcmp(habr, decoded, sizeof(habr)) == 0);
        flip_bit(encoded, i);
    }
    return 0;
}
+1
Teacher, #
Я когда на лекциях расказывал про код Хемминга, обычно использовал вот эти слайды:
0
davopetrosyan, #
Положим, есть сообщение A, а P дополнительные биты, тогда сумма всех битов по модулю 2 нe покажет нам есть ли другая ошибка?
0
mr47, #
Я конечно все понимаю, у вас 2й проверочный, НЕ ВЕРНЫЙ.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.