Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Надежность передачи сообщений - часть 2


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

(1)   вероятность полнить неверный знак была по возможности мала;

(2)   вероятность обнаружения ошибки была по возможности больше;

(3)   вероятность того, что появившаяся ошибка исправима, была, возможно, больше.

При двоичном кодировании в случае односторонних помех при m-из-n кодах каждая помеха ведет к слову, которое не является кодовым словом, и потому может быть обнаружена.

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

Лемма (обнаружение ошибок). Если код имеет расстояние Хэмминга h, то все ошибки, которые встречаются меньше чем в h битах, могут быть обнаружены.

При предположениях, сформулированных в этой лемме, справедливо, что все ошибки, появившиеся меньше чем в h/2 битах, могут быть успешно устранены, если для коррекции обнаруженной ошибки применяется кодовое слово с наименьшим расстоянием Хэмминга Hd. Получаются следующие простые следствия: если Hd = 2, то ошибочный бит может быть обнаружен; если Hd = 3, то могут быть обнаружены два ошибочных бита, а один ошибочный бит может быть успешно исправлен; корректировка передачи с двумя ошибочными битами ведет к неопределенному, а следовательно, некорректное результату.

Чтобы достичь исчерпывающей сохранности кодов, заданные коды часто снабжаются дополнительными битами: «битами четности» или «контрольными битами».

Пример (код Флексорайта). К каждому кодовому слову добавляется контрольный бит. Его значение берется таким, чтобы общее число L в коде было четным. Если в кодовом слове с контрольным битом испорчен только 1 бит, то контрольный бит для возникшего слова некорректен и тем самым ошибка обнаруживаема.

Адекватный выбор и подходящее число контрольных битов существенно определяются характером возможным помех.

Надежность передачи

Рассмотрим двоичный канал для передачи двоичных слов, о которых (и их избыточности) мы ничего не знаем.


Содержание  Назад  Вперед