Информатика. Код Хэмминга

Введение

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

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

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

Код Хэмминга

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 6. Код первого фрагмента сообщения. Автор24 — интернет-биржа студенческих работ

Для второй части будет сформирован следующий код:

Рисунок 7. Код второго фрагмента сообщения. Автор24 — интернет-биржа студенческих работ

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