Код Хэмминга: алгоритм

Введение

Системы кодирования, являющиеся средствами тайнописи, появились ещё в древние времена. Древнегреческий учёный Геродот ещё в пятом веке до нашей эры сообщал о методиках написания писем, которые сможет понять только адресат письма. При трансляции данных по информационным каналам также начали применяться различные системы кодирования и в числе первых стоит кодовая система Самуэля Морзе. В его системе точек и тире было разное количество знаков для кодирования числовой и символьной информации.

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

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

Код Хэмминга

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

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

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

Рисунок 1. Перевод сообщения в двоичный код. Автор24 — интернет-биржа студенческих работ

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

Рисунок 2. Строка кода. Автор24 — интернет-биржа студенческих работ

Рисунок 3. Строка кода. Автор24 — интернет-биржа студенческих работ

Далее кодирование выполняется отдельно для каждой части. Приведём в качестве примера кодирование первой части. Как указывалось выше, нужно выполнить вставку контрольных битов в сообщение. Вставка выполняется в чётко заданных местах, а конкретно, это позиции с нумерацией, определяемой степенями основания системы счисления, то есть цифры два. Для нашего примера эти позиции равны 1, 2, 4, 8, 16. Таким образом, получаем пять контрольных бит, которые на рисунке ниже выделяются красным:

Рисунок 4. Строка кода. Автор24 — интернет-биржа студенческих работ

Отметим, что размер сообщения вырос на пять бит, но ещё необходимо вычислить значения контрольных битов, которые пока обозначены нулями. Величина всех контрольных битов имеет зависимость от величин информационных разрядов, только не от всех подряд, а только от контролируемых данным битом. Правило здесь следующее, контрольный бит, имеющий номер N, отвечает за контроль всех последующих N битов через каждые N. Отсчёт начинается именно с позиции N. Проиллюстрируем это правило изображением ниже:

Рисунок 5. Таблица. Автор24 — интернет-биржа студенческих работ

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

Рисунок 6. Строка кода. Автор24 — интернет-биржа студенческих работ

Для оставшейся части:

Рисунок 7. Строка кода. Автор24 — интернет-биржа студенческих работ

Во второй части алгоритма выполняется повторное вычисление всех контрольных битов, и они сравниваются с полученными в сообщении битами. Предположим, что после вычислений контрольных битов обнаружен неверный одиннадцатый бит, что даст следующее:

Рисунок 8. Строка кода. Автор24 — интернет-биржа студенческих работ

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