Теоретические основы


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




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

Весом кодовой комбинации : называется число содержащихся в ней двоичных единиц.

Кодовое расстояние или расстояние Хемминга — расстояние между ближайшими кодовыми комбинациями. Оно определяется числом позиций, в которых их двоичные знаки не совпадают. Это значит, что кодовое расстояние между двоичными комбинациями и равно весу некоторой третьей комбинации , получаемой поразрядным сложением по модулю 2 (обозначается знаком ) этих комбинаций т. е.

Пример

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

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

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

Для взаимонезависимых ошибок код, обнаруживающий ошибки кратности , должен иметь минимальное расстояние Хэмминга:

Количество искаженных символов в кодовой комбинации называется кратностью ошибки. Для исправления ошибок кратности минимальное расстояние Хэмминга должно быть:

Для исправления всех ошибок кратности и одновременного обнаружения всех ошибок кратности минимальное расстояние Хэмминга выбирают исходя из условия:

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




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

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

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

Полученное значение в сторону большего целого числа.

Анализируя выражение (6), можно установить, что для некоторого диапазона изменения число контрольных символов не изменяется. Это свойство позволяет наилучшим образом выбирать структуру кодовой группы при передаче информации.




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

Одним из таких размещений является размещение контрольных символов в разрядах, представляющих собой целые степени двойки, т.е. 1=20, 2=21, 4=22 и т.д. Кроме этого при подобном размещении на значения контрольных символов влияют только информационные символы:

Кодовое слово
... 12 11 10 9 23 7 6 5 22 3 21 20

... a8 a7 a6 a5 q4 a4 a3 a2 q3 a1 q2 q1

Cимволами qi — обозначены контрольные символы, а ai — информационные символы.

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

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

Порядковый номер проверки
Проверяемые позиции

1
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...
2
2, 3, 6, 7, 10, 11, 14, 15, 18, 19, 22, 23, ...
3
4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, ...
4
8, 9, 10, 11, 12, 13, 14, 15, 24, ...
...
...

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

Указатель ошибки
...b5b4b3b2b1
q100001-1
q200010-2
a100011-3
q300100-4
a200101-5
a300110-6
a400111-7
q401000-8
a501001-9
a601010-10
a701011-11
a801100-12
a901101-13
...

Если теперь посмотреть на таблицу становится ясно каким именно образом достигается соответствие значения указателя ошибки и номера разряда на ошибку в котором он указывает. Число представляет собой двоичный код позиции.

При этом сама таблица строиться очень просто. Столбцы — значения разрядов указателя ошибки — это двоичные числа начиная с 1. А строчки — это либо контрольные разряды, если номер строки представляет собой двойку в целой степени, либо информационные — в противном случае. Контрольные и информационные разряды записываются от старших к младшим.

Указатель ошибки: формируется следующим образом — для каждого разряда указателя составляется сумма (по модулю 2), в которую включаются значения всех разрядов кодового слова с некоторым множителем. Множитель берется из таблицы указателя ошибки на перечечении разряда указателя ошибки, для которого составляется очередная сумма, и необходимого разряда кодового слова.

Другими словами в сумму входят только те разряды кодового слова, у которых в таблице указателя ошибки для данного разряда ошибки стоит «1».


...
b4 = 0q10q20a10q30a20a30a41q41a51a61a71a81a9...
b3 = 0q10q20a11q31a21a31a40q40a50a60a71a81a9...
b2 = 0q11q21a10q30a21a31a40q40a51a61a70a80a9...
b1 = 1q10q21a10q31a20a31a40q41a50a61a70a81a9...

Указатель ошибки

...
b4 = q4a5a6a7a8a9...
b3 = q3a2a3a4a8a9...
b2 = q2a1a3a4a6a7...
b1 = q1a1a2a4a5a7a9...

(8)

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

При проверке происходит сложение по модулю два контролируемых информационных символов с их контрольными символами. Если при передаче не возникло ошибки, ни один из информационных разрядов не исказился. При этом результат сложения (указатель ошибки) будет равен «0», поскольку значения контрольных символов подбирались именно для выполнения этого условия.

Контрольный блок
...
q4 = a5a6a7a8a9...
q3 = a2a3a4a8a9...
q2 = a1a3a4a6a7...
q1 = a1a2a4a5a7a9...

(9)




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

Для заданного или найденного определяется число контрольных символов .

Далее в кодовой группе определется расположение контрольных и информационных символов:

Кодовое слово
... 12 11 10 9 8 7 6 5 4 3 2 1

... a8 a7 a6 a5 q4 a4 a3 a2 q3 a1 q2 q1

Составляются выражения и расчитываются контрольные символы.

В соответствии с определенными местами в кодовом слове записываются информационные и контрольные символы.

Пример

Необходимо в коде Хэмминга, обнаруживающим двукратную ошибку и исправляющим однократную ошибку, передавать алфавит из 132 символов.

По формуле (7) находим необходимое количество информационных разрядов: =8

По формуле (6) находим требующееся количество контрольных символов: =4

Структура кодовой группы для полученного количества информационных разрядов, в принятых ранее обозначениях (qi — контрольные символы, ai — информационные символы.) будет следующей:

Кодовое слово
12 11 10 9 8 7 6 5 4 3 2 1

a8 a7 a6 a5 q4 a4 a3 a2 q3 a1 q2 q1

Будем передавать символ алфавита (в данном случае для кодировки символов может использоваться любой из восьмиразрядных двоичных кодов, например ASCII). Допустим символ имеет следующий двоичный код:

Информационный блок
a8 a7 a6 a5 a4 a3 a2 a1

1 1 0 1 0 1 0 1

По формулам (8) подсчитываем значения контрольных символов:

Контрольный блок
q4 = a5a6a7a8
q3 = a2a3a4a8
q2 = a1a3a4a6a7
q1 = a1a2a4a5a7


q4 = 1011 = 1
q3 = 0101 = 0
q2 = 11001 = 1
q1 = 10011 = 1

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

Кодовое слово
12 11 10 9 8 7 6 5 4 3 2 1
a8 a7 a6 a5 q4 a4 a3 a2 q3 a1 q2 q1

1 1 0 1 1 0 1 0 0 1 1 1




Рассмотрим, каким образом происходит обнаружение и исправление ошибок.

В принятой кодовой структуре выделяются информационные и констрольные разряды. Согласно формул (9) формируются и рассчитываются формулы разрядов указателя ошибки .

При отсутствии ошибок значение указывает на это.

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

При однократной ошибке эти разряды указателя ошибки равны «1» и указывают на разряд в котором произошла ошибка. Число представляет двоичный код позиции, в которой произошла ошибка. Инвертируя значение соответствующего разряда можно исправить ошибку.

При двукратной ошибке эти разряды также равны «1», однако уже не указывают разряд в котором произошла ошибка. То есть имеется возможность обнаружить, но не исправить двукратную ошибку.

Пример

Необходимо декодировать принятую в коде Хэмминга, обнаруживающим двукратную ошибку и исправляющим однократную ошибку, кодовую последовательность:

Принятое кодовое слово
12 11 10 9 8 7 6 5 4 3 2 1
a8 a7 a6 a5 q4 a4 a3 a2 q3 a1 q2 q1

1 0 0 1 1 0 1 0 0 1 1 1

Используя значения контрольных и информационных подсчитаем согласно формул (9) указатель ошибки:


b4 = q4a5a6a7a8
b3 = q3a2a3a4a8
b2 = q2a1a3a4a6a7
b1 = q1a1a2a4a5a7


b4=11001 = 1
b3=00101 = 0
b2=111000 = 1
b1=110010 = 1

Число — это двоичный код разряда, в котором обнаружена ошибка.

По полученному значению указателя ошибки можно определяем, что ошибка произошла в 10112 = 1110 т.е. в 11 позиции. Инвертируя значение соответствующего разряда (в т.ч. и контрольного), можно исправить ошибку, если была однократная ошибка. В противном случае, т.е. при числе ошибок более одной, может вместо исправления ошибки добавиться еще одна ошибка.

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

Исправленный информационный блок
a8 a7 a6 a5 a4 a3 a2 a1

1 1 0 1 0 1 0 1




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

Код Хэмминга может использоваться при последовательной и параллельной передаче информации по каналу.