Код Хэмминга

Введение

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

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

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

Исправление ошибок при помехоустойчивом кодировании

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

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

1. Кодовая скорость R, характеризующая долю полезных (несущих информацию) данных в сообщениях. Вычисляется по следующей формуле: $R = k / n = k / m+k$, где:

   • $n$ является числом символов кодового сообщения.
   • $m$ является числом символов, предназначенных для проверки.
   • $k$ число символов информации.

   Величины $n$ и $k$ иногда приводятся совместно с именем кода, чтобы можно было его однозначно идентифицировать. К примеру, код Хэмминга (7, 4).

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

3. Величина кратности исправленных ошибок. То есть число символов с ошибками, которые код способен скорректировать (обозначим символом t). Контроль чётности

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

При нечётном количестве единиц прибавляем нуль:

1 0 1 0 0 1 0 0 | 0

При чётном количестве единиц прибавляем единицу:

1 1 0 1 0 1 0 0 | 1

Когда при приёме информации полученный бит чётности не соответствует рассчитанному биту чётности, то фиксируется ошибка.

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

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

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

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

• Двоичное кодирование. Используется битовая система.
• Не двоичное кодирование. Используется преобразование исходных двоичных кодов в различные символы.

В свою очередь блочные коды подразделяются на:

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

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

Код Хэмминга

Ниже приведена методика кодирования по Хэммингу:

Рисунок 1. Методика кодирования по Хэммингу. Автор24 — интернет-биржа студенческих работ

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

Декодирование кодировки Хэмминга выполняется посредством определения синдрома по выражениям:

Рисунок 2. Декодирование кодировки Хэмминга. Автор24 — интернет-биржа студенческих работ

Синдромом является сложение битов по модулю два. Если синдром не равняется нулю, то коррекция ошибки выполняется согласно таблице декодирования:

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