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

Сколько ошибок обнаруживает 7 битный код хэмминга и сколько ошибок он позволяет исправить

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

Подготовка

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

Простейший пример – мажоритарный метод, он же многократная передача, в котором один символ передается многократно, а на приемной стороне принимается решение о том символе, количество которых больше.

Допустим есть 4 символа информации, А, B, С, D, и эту информацию повторяем несколько раз. В процессе передачи информации по каналу связи, где-то возникла ошибка. Есть три пакета (A1B1C1D1|A2B2C2D2|A3B3C3D3), которые должны нести одну и ту же информацию.

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

Необходимо найти ошибку с помощью голосования, каких символов больше, символов В или символов С? Явно символов В больше, чем символов С, соответственно принимаем решение, что передавался символ В, а символ С ошибочный.

Для исправления ошибок нужно, как минимум 3 пакета информации, для обнаружения, как минимум 2 пакета информации.

Параметры помехоустойчивого кодирования

Первый параметр, скорость кода R характеризует долю информационных («полезных») данных в сообщении и определяется выражением: R=k/n=k/m+k

Параметры n и k часто приводят вместе с наименованием кода для его однозначной идентификации. Например, код Хэмминга (7,4) значит, что на вход кодера приходит 4 символа, на выходе 7 символов, Рида-Соломона (15, 11) и т. д.

Второй параметр, кратность обнаруживаемых ошибок – количество ошибочных символов, которые код может обнаружить.

Третий параметр, кратность исправляемых ошибок – количество ошибочных символов, которые код может исправить (обозначается буквой t).

Контроль чётности

Самый простой метод помехоустойчивого кодирования это добавление одного бита четности. Есть некое информационное сообщение, состоящее из 8 бит, добавим девятый бит.

Если нечетное количество единиц, добавляем 0.

1 0 1 0 0 1 0 0 | 0

Если четное количество единиц, добавляем 1.

1 1 0 1 0 1 0 0 | 1

Если принятый бит чётности не совпадает с рассчитанным битом чётности, то считается, что произошла ошибка.

1 1 0 0 0 1 0 0 | 1

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

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

Прямоугольный код – код с контролем четности, позволяющий исправить одну ошибку:

И если в процессе передачи информации допустим ошибку (ошибка нолик вместо единицы, желтым цветом), начинаем делать проверку. Нашли ошибку во втором столбце, третьей строке по координатам. Чтобы исправить ошибку, просто инвертируем 1 в 0, тем самым ошибка исправляется.

Этот прямоугольный код исправляет все одно-битные ошибки, но не все двух-битные и трех-битные.

Рассчитаем скорость кода для:

Здесь R=16/24=0,66 (картинка выше, двадцать пятую единичку (бит четности) не учитываем)

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

Классификация помехоустойчивых кодов

По используемому алфавиту:

Блочные коды делятся на

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

Смотря на картинку выше, код 1 1 0 0 0 1 0 0 | 1 является систематическим, на вход поступило 8 бит, а на выходе кодера 9 бит, которые в явном виде содержат в себе 8 бит информационных и один проверочный.

Код Хэмминга

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

Код Хэмминга (7,4) — 4 бита на входе кодера и 7 на выходе, следовательно 3 проверочных бита. С 1 по 4 информационные биты, с 6 по 7 проверочные (см. табл. выше). Пятый проверочный бит y5, это сумма по модулю два 1-3 информационных бит. Сумма по модулю 2 это вычисление бита чётности.

Декодирование кода Хэмминга

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

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

Готовые работы на аналогичную тему

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

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

Для иллюстрации действия того алгоритма, приведём конкретный пример. Предположим, имеется информация «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, и осталось просто выполнить его инверсию, убрать биты контроля, после чего получается исходное сообщение без ошибок. Таким же образом декодируется и вторая часть сообщения.