Лекция № 13. Корректирующий код Хэмминга

Корректирующий код Хэмминга

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

Общие принципы построения систематических кодов

Если обозначить информационные символы буквами с, а контрольные – буквами е, то любую кодовую комбинацию, содержащую k информационных и r контрольных символов d можно представить последовательностью:

c ₁, c ₂, c ₃, _…, c_k, е ₁, е ₂, е ₃, …, е_r, где с и е в двоичном коде принимают значения 0 или 1.

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

, (1)

где j = 1, 2,...., r; – коэффициенты, равные 0 или 1; и – знаки суммирования по модулю два.

Значения выбираются по определенным правилам, установленным для данного вида кода. Иными словами, символы е представляют собой суммы по модулю два информационных символов в различных сочетаниях.

Процедура декодирования принятых комбинаций может осуществляться различными методами. Один из них, так называемый метод контрольных чисел, состоит в следующем. Из информационных символов принятой кодовой комбинации образуется по правилу (1) вторая группа контрольных символов . Затем производится сравнение обеих трупп контрольных символов путем их суммирования по модулю два:

(2)

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

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

Контрольное число X записывается в двоичной системе; поэтому общее количество различных контрольных чисел, отличающихся от нуля, равно . Очевидно, это количество должно быть не меньше числа различных сочетаний ошибочных символов подлежащих исправлению. Например, если код предназначен для исправления одиночных ошибок, то число различных вариантов таких ошибок равно . В этом случае должно выполняться условие

. (3)

Формула (3) позволяет при заданном количестве информационных символов k определить необходимое число контрольных символов r, с помощью которых исправляются все одиночные ошибки.

Коды Хемминга

Коды Хемминга относятся к систематическим кодам, позволяющие исправлять все одиночные ошибки.

Рассмотрим построение девятизначного кода Хэмминга, каждая комбинация которого содержит пяти информационных и трех контрольных символа. Такой код, условно обозначаемый (9, 5). Он удовлетворяет неравенству (3) и имеет избыточность .

Если информационные символы с занимают в комбинации первые пять мест, то последующие четыре контрольных символа образуются по общему правилу (1) как суммы:

. (4)

Декодирование осуществляется путем четырех проверок на четность (2):

(5)

Так как x равно 0 или 1, то всего может быть шестнадцать контрольных чисел : 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110 и 1111. Первое из них имеет место в случае правильного приема, а остальные пятнадцать появляются при наличии искажений и должны использоваться для определения местоположения одиночной ошибки в девятизначной комбинации.

Рассмотрим, каким образом устанавливается взаимо­связь между контрольными числами и искаженными символами. Если искажен один из контрольных символов: , то, как следует из (5), контрольное число примет соответственно одно из трех значений: 1000, 0100, 0010 или 0001. Остальные четыре контрольных числа используются для выявления ошибок в информационных символах. Порядок присвоения контрольных чисел ошибочным информационным символам может устанавливаться любой, например, как показано в табл. 1. Покажем, что этому распределению контрольных чисел соответствуют коэффициенты , приведенные в табл.2.

Таблица 1

Распределение контрольных чисел для определения местоположения ошибки

Искаженный символ
Контрольное число (синдром)

Таблица 2

Контрольные числа для принятого распределения

	= 0	= 0	= 0	= 1	= 1
	= 0	=1	=1	=0	=1
	= 1	=0	=1	=0	=0
	= 1	=1	=0	=1	=0

Используя коэффициенты из табл. 2, по формуле (5) вычислим контрольные числа:

(6)

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

Т.о., при одиночной ошибке можно вычислить контрольное число, позволяющее по табл. 1 определить тот символ кодовой комбинации, который претерпел искажения. Исправление искаженного символа двоичной системы состоит в простой замене 0 да 1 или 1 на 0.

Рассмотрим пример передачи комбинации, в которой информационными символами является =10011. Используя формулу (4) и табл. 2, вычислим контрольные символы:

При этом передаваемая комбинация будет =10011.0110. Предположим, чтопринята комбинация – 1 1 011.0110 (искажен символ с ₂). Подставляя соответствующие значения в формулу (6), получим:

Вычисленное таким образом контрольное число = 0101 позволяет согласно табл. 1 исправить ошибку в символе с ₂ с «1» на «0»: =10011.

Следует отметить, что в коде (9, 5) при появлении много­кратных ошибок контрольное число также может отличаться от нуля. Однако декодирование в этом случае будет проведено не­правильно, так как оно рассчитано на исправление лишь одиночных ошибок.

Методика кодирования сообщения кодом Хэмминга

Процесс кодирования выполняется в 3 этапа:

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

2. Для каждой кодовой комбинации по формуле (4) вычисляются контрольные символы е ₁, е ₂, е ₃, …, е_r.

3. По результатам вычисления контрольных чисел формируется избыточный код Хэмминга: c ₁, c ₂, c ₃, _…, c_k, е ₁, е ₂, е ₃, …, е_r.

Рассмотрим пример кодирования сообщения «ПРИМЕР».

По табл. П.1 преобразуем сообщение в двоичный код (табл. 3).

Таблица 3

Кодовые комбинации сообщения

Символ	Кодовые комбинации
П
Р
И
М
Е
Р

Пользуясь выражением (4), вычислим контрольные символы (табл.4).

По результатам расчета сформируем код Хэмминга для приведенного сообщения (табл. 5).

Таблица 4

Контрольные символы

Символ	Контрольные символы
П
Р
И
М
Е
Р

Таблица 5

Код Хэмминга для символов сообщения

Символ	Код Хэмминга
П
Р
И
М
Е
Р

Методика декодирования сообщения закодированного кодом Хэмминга

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

Процесс декодирования сообщений закодированных кодом Хэмминга осуществляется в 3 этапа:

1. По принятой кодовой комбинации, используя коэффициенты из табл. 2, по формуле (5) вычисляются контрольные числа (синдром) .

2. Используя таблицу распределения контрольных чисел (см. табл. 1) по результатам расчета синдрома X определяется местоположение ошибки в каждой кодовой комбинации и исправляется ошибка, путем замены ошибочного символа на противоположный: .

3. По результатам декодирования с помощью таблицы двоичных кодов русского алфавита (см. табл. П.1) формируется текст декодированного сообщения.

Рассмотрим пример. Предположим, что закодированное сообщение: «ПРИМЕР» подвернулось искажению при передаче в канале связи (табл. 6).

Таблица 6

Принятое с ошибками закодированное сообщение

Код Хэмминга

Произведем декодирование. По формуле (5) вычислим контрольные числа синдрома для каждой кодовой комбинации и по табл. 1 определим место ошибочного символа в каждой кодовой комбинации (табл. 7).

Таблица 7

Контрольные числа для приятого сообщения

Ошибочный символ
нет
нет

С учетом обнаруженных ошибок и таблицы кодов русского алфавита (см. табл. П.1), составим коды символов (табл. 8).

Таблица 8

Кодовые комбинации декодированного сообщения

Принятый символ	Кодовые комбинации
П
Р
И
М
Е
Р

В результате, получим текст: «ПРИМЕР».