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

Концепция избыточности может использоваться не только для уменьшения ошибочных передач при общении между людьми. Ее можно с успехом применять и при техническом обмене сообщениями, чтобы предохранить закодированную информацию от помех и ошибок. Следующая ситуация является типичной для передачи сообщений. От источника передаются параллельно сообщения через пучок проводов к некоторому приемнику (адресату) (рис. 7.1.).

Источник — Приемник

Канал

Рис. 7.1. Cxeмa передачи

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

и в дальнейшем ограничимся рассмотрением этого простого случая.

При так называемом двоичном канале

из-за ошибок передачи всегда возникают тоже двоичные знаки. Оба знака О и L имеют вероятности ошибок соответственно ро и pl.

Специальными являются случай односторонних помех, при котором имеет место р0 == 0 или рL=0 и случай симметричных помех,

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

При канале с потерей знаков

из-за ошибок передачи появляются испорченные знаки которые, впрочем, распознаваемы как искаженные знаки и которые могут быть представлены знаком искажения 1. Такого рода знак приходит, например, при передачах, которые нарушаются через шум. Таким образом, канал в качестве входа принимает слова над множеством знаков {L . 0} и выдает слова над множеством знаков {L, О, 1}.

Надежность кодов

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть в канале имеют место симметричные помехи. Это означает, что имеется фиксированная вероятность ошибок, с которой выход в одном знаке отличается от входа. Допустим, далее, принимая во внимание скорость передачи (мощность канала), что источник должен передать определенное число So знаков, а канал может передать Si знаков в единицу времени. Тогда R == So/Si назовем темпом источника.

Если R < 1, то возможно - с помощью соответствующей кодировки входа для передачи - достичь еще дополнительной избыточности и тем самым устойчивости к ошибкам. Таким образом, передача сообщения следует схеме, приведенной на рис. 7.2:

Источник — Кодировка —Декодировка— Приемник

Рис.7.2.

Схема передачи сообщения

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

Пример (надежность через избыточность). Если, например, имеет место R == 1/3, то канал может передать втрое больше знаков, чем их вырабатывает источник. Каждый знак может быть троекратно закодирован перед передачей и в конце концов должен быть снова декодирован:

пересылаемое слово   LOLOO,

кодировка                   LLLOOOLLLOOOOOO.

Если, предположим, например, что вследствие шума биты с номерами ] 5, 6, 12 и 13 будут искажены (норма ошибок 1/3), то адресат получит последовательность знаков

LOLOLLLLLOOLLOO.

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

LLLOO.

Некорректно будет устранена только ошибка в передаче второго бита эта ошибка и останется в декодированном сообщении. Норма ошибок тогда задается так, что для малой вероятности ошибки р это значительно лучше, чем вероятность ошибки р при однократной передаче знака. Ошибка достигает адресата только в том случае, когда будут искажены 2 или 3 бита в кодировке одного знака.

Если темп источника больше ½, то стратегия неоднократной передачи непосредственно невозможна. Тогда можно работать с дополнительными битами, например битами четности, которые, однако, должны выбираться очень тщательно. Следующая стратегия битов четности называется кодом Хэмминга: если имеет место R == n/(n+1), то возможен только один дополнительный бит для n-битового кода. Для передачи n-битового двоичного слова выбирается бит Xn+1 таким образом, что с W(L) == 1 и W(0) == 0 справедливо.

Это значит, что каждое двоичное слово дополняется еще одним знаком так, чтобы число знаков L во всем кодовом слове было четным. Расстояние Хэмминга для (n+1, n)-кода Хэмминга, равно по меньшей мере двум. Для такого кода единичная

ошибка обнаруживаема, но не устранима.

Если, например, R = 4/7 и пересылаются слова детины 4, то можно cвободно выбирать 3 бита четности. Если должно передаваться слово

nо при (7, 4)-коде Хэмминга биты х4,x5,x6 могут быть выбраны в качестве битов четности.

При декодировании (в предположении, что имеется не более одной ошибки) можно поступать следующим образом. Адресат при пересылке двоичного слова х = <хо ... x6>

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

Итак, наряду с вероятностью ошибки р для канала на передаваемый бит при темпе источника R < 1 при использовании избыточности мы получаем меньшую вероятность ошибки ре < р на подлежащий передаче знак. Если имеет место R > 1, то мы ожидаем ре > р

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

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

pe=p/R+(R-l)/(2R).

Лучшая мера корректно переданных битов поддается путем их упаковки в передаваемые блоки. Проиллюстрируем это на примере. Для R == 3 источник делит сообщение на блоки трехразрядных двоичных слов и пересылает значение большинства. Адресат утраивает каждый переданный бит. Тогда мы получаем в совокупности вероятность ошибки

ре=(2р+1)/4.

При вероятности ошибки р == 0 примерно ¾ знаков передаются корректно.

Описанная выше идея улучшения значения ре может быть применена и в других случаях, если для темпа источника справедливо R > 0. Всегда можно пытаться многие биты передаваемого слова уплотнить в I 6ит (или в меньшее число бит), передать это и добавить целиком к подлежащему передаче сообщению. Это приводит к вопросу: насколько при заданных темпе источника R и вероятности р ошибки в бите можно улучшить с помощью кодирования вероятность ошибки ре при передаче н подлежащий передаче бит? Принципиально можно сказать:

в случае R == 1 определенно ре = р является достижимым оптимумом, в случае R < 1 определенно ре < р, а в случае R > 1 определенно ре > р.

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

Н2(Р) == р • lg(l/p) + (1 - р) lg (l/(1-p) В частности, справедливо Н2(0) = Н2(1) = 0.

Меру для достижимой надежности передачи дает мощность канала.

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

С(p)=1-H2(p).

Содержание раздела