Меню
Главная
Авторизация/Регистрация
 
Главная arrow Техника arrow Анализ систем телемеханики

Избыточные коды

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

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

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

001 000

Разрешенные 010 Запрещенные 011

слова 100 слова 101

111 110

Если в результате искажения разрешенное кодовое слово переходит в запрещенное, то ошибка обнаруживается, если же разрешенное слово переходит в разрешенное, то ошибка не обнаруживается, например:

Число искаженных разрядов принято называть кратностью ошибки, и обозначать г. В приведенных примерах кратность ошибок и. Способность кода обнаруживать или исправлять ошибки определяется так называемым минимальным кодовым расстоянием. Кодовым расстоянием или расстоянием по Хэммингу между двумя словами называется число разрядов, в которых символы слов не совпадают. Если длина слова n, то кодовое расстояние может принимать значение от 1 до n. Минимальным кодовым расстоянием данного кода называется минимальное количество разрядов, которыми различаются два кодовых слова. Слова и имеют кодовое расстояние . В общем случае, чтобы избыточный код позволял обнаруживать ошибки кратностью r, должно выполняться условие

,

а для исправления r-кратной ошибки условие

.

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

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

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

Пусть на контрольном пункте принято слово 11000. Поскольку оно отсутствует среди разрешенных слов то, следовательно, имеется ошибка. Найдем данное слово среди запрещенных слов. Так как по условию произошла ошибка кратности 1, то это слово имеется среди запрещенных слов. Исправление состоит в том, что принятое запрещенное слово 11000 сравнивается с разрешенным, и в искаженный разряд записывается правильная информация. В данном случае произошло искажение второго разряда (типа ). Необходимым условием исправления ошибок является однозначность такого отождествления, т.е. запрещенное слово 11000 не должно быть записано в других столбцах таблицы. Таким образом, множества запрещенных слов, в которые переходят разные разрешенные слова, не должны пересекаться.

В общем случае для одновременного обнаружения ошибок кратностью r и исправления ошибок кратностью q должно выполняться условие

,

где r - кратность ошибок исправления, q - кратность ошибок обнаружения, причем .

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Естествознание
Журналистика
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Математика, химия, физика
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Право
Психология
Религиоведение
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика
Прочее