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

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

Для обнаружения на приёмной стороне или исправления такой ошибки применяют корректирующие коды.

Предположим, что исходные кодовые комбинации формируются из “ m ” символов (разрядов). Например, в двоичном коде возможны только два символа “0” или ”1”. Т.е. m =2. число “ m ” называется основанием кода (основание системы счисления). Другое название – позиционность кода. (в десятичной системе счисления m =10).

Мы будем рассматривать именно двоичные коды, т.е. m =2. при этом будем учитывать только дискретные искажения, при которых “1” переходит в ”0” или наоборот.

Переход 1®0 или 0®1 только в одном элементе кодовой комбинации будем называть единичной ошибкой (единичным искажением) и обозначим её D=1. в общем случае возможны двукратные (D=2) и многократные (D>2) искажения элементов кодовой комбинации в пределах 1 D n, где n – количество знаков в кодовой комбинации (разрядность кодового сообщения).

У корректирующих кодов кодовая комбинация “ n ” состоит из “ n ₀” информационных элементов незащищённого (неизбыточного) кода и “ k ” проверочных элементов, добавляемых с целью обнаружения и исправления ошибок. Т.е.

n = n ₀+ k (*)

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

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

1. Двоичный код с проверкой на чётность.

Формула его работы:

n = n ₀+1 (**)

(сравнить (**) с (*))

Это означает, что к “ n ₀” информационным элементам неизбыточного кода добавляется только один проверочный элемент.

Причём если данная кодовая комбинация (n = n ₀+1) содержит чётное число единиц в информационной части n₀, то на передающей стороне добавляется проверочный элемент, имеющий значение”0”. Если же в кодовой комбинации нечётное число единиц в информационной части, то на передающей(!) стороне в конце кодовой комбинации “1”.

Пример:

Рис.

На приёмной стороне тракта передачи кода декодирующее устройство контролирует чётность числа информационных единиц с помощью переключаемого триггера. При этом анализирует как принятый проверочный элемент (“0 или 1”), так и чётность принятых информационных единиц.

Если, например, проверочный элемент 0, а число единиц в n₀ – чётное, то это разрешённая комбинация и сигнал проходит на выход декодера.

В общем случае возможны следующие ситуации:

Проверочный элемент	Кол-во единиц в неизбыточном коде n 0	Заключение о разрешённости комбинации n
	Чётное Нечётное Нечётное чётное	Разрешённая Разрешённая Запрещённая Запрещённая

Рис.

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

При этом обеспечивается защита от любых единичных (!) ошибок (D=1) в кодовой комбинации. Ошибки при этом только обнаруживаются, но не исправляются (не корректируются)!!

Теперь рассмотрим принципы реализации корректирующих кодов.

Разработку этих принципов впервые начал Хэмминг, который предложил код с автоматическим исправлением единичной (!) ошибки в кодовой комбинации.

Формула его работы:

n = n ₀+ k,

где k – проверочные элементы;

n ₀ – информационные элементы.

Причём, автоматическое определение местоположения ошибочного элемента обеспечивается в результате проведения “ k ” проверок на чётность (т.е. число проверок на чётность равно числу проверочных элементов!).

Рассмотрим подробнее код Хэмминга.

Хемминг ввёл понятие “расстояние d ” – это параметр, определяющий различие между кодовыми комбинациями. Например, для двоичного кода расстояние – это число символов, на которые одна кодовая комбинация отличается от другой.

Дадим геометрическое представление кодов в виде n – мерного куба, где n – число разрядов двоичного кода.

1. Длина каждого ребра куба d =1 (“кодовое расстояние”) и соответствует единичному переходу 0®1 или 1®0 в соответствующем разряде (элементе) двоичного кода;

2. Вершины n – мерного куба отображают кодовые комбинации;

3. Координаты этих точек – это значения соответствующих символов.

Если взять n =3, то трёхмерный куб с длиной ребра d =1:

Рис.

(Проиллюстрировать положения 1, 2, 3 на этом рисунке)

Эта геометрическая модель иллюстрирует следующее:

1. Ближайшие кодовые комбинации 000 и 010, 00 и 100, 111 и 110 и другие отстоят друг от друга на длину одного ребра куба (d =1), что соответствует переходу 0à1 или 1à0.

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

Наиболее удаленные вершины n – мерного находятся на расстоянии d _max=n единичных переходов (n ребер). Так для 3-хмерного куба (см. пунктир на рис.) максимальное расстояние d _max=3 (вершины 000 и 111 или 001 и 110 и т.д.).

Вывод:

Для повышения помехоустойчивости кода к импульсным помехам, которые могут вызывать единичные ошибки (Δ=1), двойные (Δ=2) и большое число ошибок, нужно выбирать рабочие комбинации кода, отстоящие одна от другой на большие расстояния. Это достигается ценой повышения избыточности кода. Если кодовое расстояние d >= 2, то единичные ошибки не будут переводить одну рабочую комбинацию в другую, и ложные сигналы для единичных искажений будут исключены.

При этом единичные ошибки будут вызывать на приемной стороне защитный отказ. Например, если в качестве разрешенных использовать комбинации 000, 101, 011, 110 (см. куб на рис.), то искажения одного любого символа даст комбинацию, отсутствующую среди принятых, а, значит, ошибочную!!!

Избыточность кода (обеспечивающая коррекцию кода) количественно определяется выражением:

R = (n - n ₀) / n ₀.

n ₀ – количество информационных элементов достаточных для образования нужного числа комбинаций кода.

Например, для реализации 8 комбинаций имеется неискаженный 3-хразрядный код (n ₀=3) (2­­³=8) с введением одного дополнительного разряда k =1 (как в коде с проверкой на четность), т.е. n =3+1=4.

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

d_min =1 + Δ + S,

где Δ – кратность (количество) обнаруживаемой ошибки;

S – кратность (количество) исправленной ошибки.

Здесь Δ >= S.

Так, если рассматривать однократные ошибки (Δ=1, S =1), то расстояние d=1+1+1=3 обеспечивает обнаружение и исправление однократной ошибки (либо только обнаружение двукратной ошибки!).

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

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

Рассмотрим такой важный практический вопрос: как определить кодовое расстояние d для конкретных кодовых комбинаций?

Для этого необходимо производить сложение по модулю 2 соответствующих элементов (единиц) в табличных записках кода.

(Напомним, что “сложение по модулю 2” обозначается и производится без переноса единицы в старший разряд, т.е. 1 1=0; 1 0=1)

Так, например, если заданы две комбинации 5-разрядного кода (см. предыдущий пример – первые две комбинации)

0 1 0 0 1

0 1 1 1 0,

то суммируем поразрядно “по модулю 2”, получим:

0 1 0 0 1

0 1 1 1 0

0 0 1 1 1.

Теперь определяем общее (суммарное) количество единиц в результате этого суммирования, которое и будет искомым кодовым расстоянием:

D = 3 (три единицы в сумме по модулю 2)

Далее, используя известную нам формулу для d_min:

получаем Δ = S = 1, что означает:

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

Определим избыточность этого кода (в данном примере).

n = 5 (пятиразрядный код) при передаче 4-х комбинаций.

Т.к. комбинаций 4, то для их составления достаточно двух символов, т.е. n ₀ = 2. Тогда избыточность .

Обратим внимание на то, что подобный код позволяет исправлять (корректировать) однократные ошибки, и только обнаруживать – двукратные ошибки. Тогда, используя формулу для “хеммингова (кодового) расстояния” d =1+Δ+ S, можно определить, что для обнаружения, например, 3-х кратных ошибок и коррекции 2-укратных должно быть d _min=1+3+2=6.

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

ПРИМЕР. Пусть принята искаженная комбинация кода:

0 1 1 1 0 0 0

1 2 3 4 5 6 7 – позиции

Здесь общее число символов n =7, n = n ₀+ k,

n ₀=4 – информационные элементы;

k =3 – контрольные элементы

1. Проверяем на четность соответствующие разряды кодовой комбинации. Количество проверок равно k – в данном случае 3.

а) 1-я проверка. Суммируем единицы по модулю 2 на позициях кода 1,3,5,7.

(Напомним, что “сложение по модулю 2” обозначается и производится без переноса единицы в старший разряд, т.е. 1 1=0; 1 0=1).

Это суммирование дает 1, т.е. нечетное число единиц, следовательно записывается справа – налево на первой позиции кода.

7 поз. 6 поз. 5 поз. 4 поз. 3 поз. 2 поз. 1 поз.

Примечание 2: Порядок всех проверок на четность однозначно определен исходной таблицей (справочный материал!) вида:

Номер позиции	Проверяемые позиции кода

Порядок составления этой таблицы будет изложен позже!

б) 2-я проверка. Суммируем единицы по модулю 2 на позициях 2,3,6,7 и получаем четное число единицы, следовательно, результат проверки на четность равен 0, каждый записываем в контрольной строке:

7 поз. 6 поз. 5 поз. 4 поз. 3 поз. 2 поз. 1 поз.

в) 3-я проверка. Суммируем единицы по модулю 2 на позициях (см. справочную таблицу) 4,5,6,7 и получаем нечетное число единиц, следовательно результат 1(на 3 поз).

Примечание 3: Результаты проверок на четность записываются в виде 0 при отсутствии ошибок (т.е. при четном числе единиц) и в виде 1 при наличии ошибки (т.е. при нечетном числе единиц)

В результате всех трех проверок (4-ю делать бессмысленно, т.к. в справочной таблице 4-я проверка предусматривает работу с разрядами, начиная с 8 и выше, которых у нас нет) получаем контрольное число 101, которое означает в десятичном счислении цифру 5.

Это означает, что в исходном коде 0111 0 00 искажен элемент кода на 5-ой позиции, т.е. подчёркнутая позиция. Следовательно, восстановленная кодовая комбинация имеет вид:

0111 1 00

В реальных ИИС исправление ошибки производится на приёмной стороне автоматически.

Если в код Хэмминга ввести дополнительно 8-ю позицию для проверки на чётность, то это увеличивает кодовое расстояние на единицу и позволяет исправлять одну (S=1), а обнаруживать уже две ошибки (D=2)

d _min=1+2+1=4.

Кстати, код Хэмминга даёт хорошие результаты по обнаружению и исправлению ошибок, если мала вероятность возникновения “пакета” ошибок, т.е. групповых помех.

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

Выводы (обобщение сказанного):

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

Порядок построения кода Хэмминга следующий:

1. Определяется необходимое количество информационных “n₀” и проверочных “k” разрядов.

Количество n₀ информационных разрядов определяется необходимым числом кодируемых комбинаций (2 ^{n 0}).

Количество проверочных разрядов k определяется из условия:

или

Код Хэмминга, следовательно, должен иметь разрядов.

2. Число проверок на чётность в дальнейшем будет равно числу проверочных разрядов “k”.

Все проверки заключаются в вычислении суммы по “модулю 2” кодовых элементов в соответствующих разрядах кодовой комбинации.

При первой проверке выбираются те разряды кодов, двоичный номер которых содержит единицу в первом разряде, т.е. 1, 3, 5, 7, 9-й и т.д.

Рис.

(По этому принципу и была составлена справочная таблица).

При второй проверке выбираются разряды, двоичный номер которых содержит “1” во втором разряде, т.е. 2, 3, 6, 7, 10-й и т.д.

При третьей проверке вбираются 4, 5, 6, 7, 12, 13-й разряды и т.д.

3. Место расположения проверочных разрядов в кодовой комбинации в принципе может быть выбрано произвольным(!), однако, при выбранном правиле проверок (см. п. 2) удобнее их размещать в разрядах, номера которых равны целой степени числа 2, т.е. в 1-м, 2-м, 4-м, 8-м и т.д.

4. Способ заполнения проверочных разрядов определяется правилом проверки корректирующего кода (проверкой на чётность с учётом рекомендаций п. 2 по номерам проверяемых разрядов при соответствующих порядковых номерах проверок).

После приёма кодовой комбинации делается проверка её наличия в кодовой таблице и, если этой комбинации там нет, тогда делаются “ k ” проверок на чётность. Результаты проверок в виде символов “0” или ”1” записываются справа налево и образуют контрольное число, соответствующее номеру искаженного разряда в проверяемой кодовой комбинации.

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

2-й метод повышения помехоустойчивости: