double arrow

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

Лекция 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 наложенных разрядов.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: