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

Степень различия двух КК называется расстоянием между ними (по Хэммингу) т.е. кодовое расстояние:

1001101

Å

1011011

0011110 d=7

Определяется сложением 2-х кодовых комбинаций по модулю 2.

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

Рассмотрим код n=3

000 001 010 011 100 101 110 111

пример равнодоступного кода.

пример равнодоступного кода. Любая ошибка трансформирует КК данного кода в другую – разрешенную. Это случай - доступного кода который не обладает обнаружением и исправляющими свойствами.

При d=2

001 001 101 110

разрешенная КК

001 010 100 111

запрещенная КК

Такой код обнаружит все одиночные ошибки.

В общем случае для обнаруживающего кода кодовое расстояние определяется:

. r – число обнаруженных ошибок.

Для исправления ошибки необходимо локализовать ошибку. Т.е. разбить всю КК на не пересекающиеся множества.

Допустим разрешенные КК: 1000 -> 001 010 100

1111 -> 110 101 110

Геометрическая интерпретация блоковых корректирующих кодов. Любая n – разрядная КК может быть представлена как вершина n – мерного единичного куба, длин ребра =1

Лекция 12. Коды обнаруживающие ошибки.

Цель лекции: Ознакомление cпомехоустойчивыми корректирующими кодами.

Содержание:

а) коды обнаруживающие ошибки;

б) математическое введение к групповым кодам;

в) избыточность сообщений;

г) построение двоичного группового кода;

д) определение числа избыточных символов.

Коды обнаруживающие ошибки.

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

1) Примером кода с обнаружением ошибки является код с проверкой на четность

Исходная КК	Контрольные символы	Выходная КК
00001	1	000011
00010	1	000101
00011	0	000110
00100	1	001001
00101	0	001010

2) Код с удвоением элементов (корреляционный код). Корреляционный код строится таким образом: каждый элемент двоичного кода передается двумя символами:

1 -> 10 1010011 ->

0 -> 01 -> 10011001011010.

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

10 –> 01

01 -> 10.

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

Достоинства: нет постоянной составляющей т.к. число 1 = 0

3) Инверсный код

Информационные символы	Контрольные символы	Инверсный код
111001	111001	111001111001
101111	010000	101111010000

(Тутевич стр.65-69.)

Линейные коды.

Линейные коды - значения проверочных символов которые определяются с использованием линейных операций над определенными информационными символами.

Обычно проверочный символ m =1, если , число проверочных равенств, номера конкретных входящих в каждое проверочное равенство определяется видом и характеристиками кода.

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

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