Лекция 12. Коды обнаруживающие ошибки.
Связь корректирующей способности кода с кодовым расстоянием.
Степень различия двух КК называется расстоянием между ними (по Хэммингу) т.е. кодовое расстояние:
Å
1011011
0011110 d=7
Определяется сложением 2-х кодовых комбинаций по модулю 2.
Минимальное кодовое расстояние - определяется по всем парам кодовых комбинаций данного кода. Декодирование по методу максимального правдоподобия осуществляется следующим образом, чтобы принятая КК отождествлялась с разрешенной, которая отличается в наименьшем числе символов. При d=1 – все КК являются разрешенными.
Рассмотрим код n=3
пример равнодоступного кода. |
пример равнодоступного кода. Любая ошибка трансформирует КК данного кода в другую – разрешенную. Это случай - доступного кода который не обладает обнаружением и исправляющими свойствами.
При d=2
разрешенная КК |
запрещенная КК |
Такой код обнаружит все одиночные ошибки.
В общем случае для обнаруживающего кода кодовое расстояние определяется:
. r – число обнаруженных ошибок.
Для исправления ошибки необходимо локализовать ошибку. Т.е. разбить всю КК на не пересекающиеся множества.
Допустим разрешенные КК: 1000 -> 001 010 100
1111 -> 110 101 110
Геометрическая интерпретация блоковых корректирующих кодов. Любая n – разрядная КК может быть представлена как вершина n – мерного единичного куба, длин ребра =1
Цель лекции: Ознакомление cпомехоустойчивыми корректирующими кодами.
Содержание:
а) коды обнаруживающие ошибки;
б) математическое введение к групповым кодам;
в) избыточность сообщений;
г) построение двоичного группового кода;
д) определение числа избыточных символов.
Как указывалось выше для обнаружения ошибки кодовое расстояние по Хэммингу должно быть равно:, где r – число обнаруженных ошибок.
1) Примером кода с обнаружением ошибки является код с проверкой на четность
Исходная КК | Контрольные символы | Выходная КК |
2) Код с удвоением элементов (корреляционный код). Корреляционный код строится таким образом: каждый элемент двоичного кода передается двумя символами:
1 -> 10 1010011 ->
0 -> 01 -> 10011001011010.
Корреляционный код содержит в два раза больше символов чем исходный, обнаружение ошибки осуществляется таким соображениями в парных элементах должны быть разные символы, т.е. элементы 00 или 11 – бракуются. Не обнаруживаются ошибки типа:
10 –> 01
01 -> 10.
Высокая помехоустойчивость корреляционного кода достигается большой избыточностью.
Достоинства: нет постоянной составляющей т.к. число 1 = 0
3) Инверсный код
Информационные символы | Контрольные символы | Инверсный код |
(Тутевич стр.65-69.)
Линейные коды.
Линейные коды - значения проверочных символов которые определяются с использованием линейных операций над определенными информационными символами.
Обычно проверочный символ m =1, если, число проверочных равенств, номера конкретных входящих в каждое проверочное равенство определяется видом и характеристиками кода.
При декодировании осуществляется справедливость избыточных равенств. Для двоичных линейных кодов определение также сводится к проверке на четность числа единиц, входящих в каждое равенство.
Совокупность проверок дает информацию о наличии ошибки, а в случае необходимости и NN наложенных разрядов.