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

Пусть имеется канал связи C, содержащий источник помех:

,

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

,

называется помехоустойчивым.

Если A=B={0,1}, то ошибки в канале могут быть следующих типов:

· 01, 10 – ошибка типа замещения разряда;

· 0, 1– ошибка типа выпадения разряда;

· 1, 0 – ошибка типа вставки разряда.

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

Теорема 9.3. Чтобы существовало помехоустойчивое кодирование с исправлением всех ошибок, необходимо и достаточно, чтобы , то есть необходимо и достаточно, чтобы существовало разбиение множества B* на множества , такое что .

Доказательство. Если кодирование помехоустойчивое, то очевидно, что . Обратно: по разбиению строится функция .

Рассмотрим множество из всех двоичных последовательностей (векторов), имеющих вид

.

Введем в множестве операцию сложения +, определив для последовательностей и их сумму с помощью соотношения: , где – это сумма по модулю два.

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

Пример 9.4.(0, 1, 0, 1)+(1, 1, 1, 0)=(1, 0, 1, 1).

Поэтому расстояние Хэмминга можно определить как число компонент вектора , которые равны 1.

Введенное таким образом расстояние Хэмминга удовлетворяет следующим условиям:

·

· ;

· – «неравенство треугольника».

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

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

Предположим, что из используются только слов: . Если эти слова таковы, что при всех :

, (7.1)

то можно исправлять любые ошибки кратности .

Допустим, что в некоторых компонентах слова при передаче возникли ошибки, в результате которых символы 0 были приняты как 1, а символы 1 – как 0 (ошибки типа замещения). Получившееся в результате слово находится на расстоянии от слова . Следовательно, если считать, что ошибки при передаче могут возникать не более чем в компонентах, то совокупность всех слов, которые могут получиться из , представляет собой множество .

Из неравенства треугольника и условия (7.1) следует , если только . Действительно, допустим, что существует слово . Тогда и .

Согласно неравенству треугольника

,

что приводит к противоречию с условием (9.1).

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

Так как число элементов в множестве равно числу способов выбора некоторых () компонент слова , то

.

Далее, так как , то: , то есть

. (9.2)

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

Пример 9.5.Пусть =8, тогда . Поскольку , то ; ; ; ; .

Если =4, то .

Если =3, то .

Если =2, то .

Если =1, то .

Если =0, то .

Таким образом, если встречаются только одиночные ошибки типа замещения, то при использовании 8 бит можно безошибочно передавать 28 слов. В общем случае, если имеется бит и нужно исправлять одиночные ошибки типа замещения, то граница Хэмминга определяется следующим выражением, являющимся частным случаем формулы (9.2):

. (9.3)

Обозначим минимальное число бит, необходимое для передачи слов, буквой . Тогда:, и из формулы (9.3) следует

. (9.4)

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

Пример 9.6.Для сообщения длиной потребуется дополнительных разрядов, поскольку 64=.

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