§ 5.2. Двоичный стирающий канал

Весьма эффективный метод декодирования сверточных кодов был развит для этих каналов Эпстейном [26]. Метод Эпстейна приводит к экспоненциальному убыванию вероятности ошибки при любой скорости передачи, меньшей пропускной способности канала, а среднее число операций на один

декодированный символ не зависит от длины кодовой комбинации.

В этом параграфе мы бегло коснемся АВ-декодирования для двоичного стирающего канала, изображенного на рис. 13. Канал имеет пропускную способность и характеризуется тем, что принятый символ может оказаться сомнительным, но никогда не бывает ошибочным [16, стр. 129]. В § 4.2 мы видели, что этот канал можно свести к двоичному каналу, если все стертые символы заменить нулями и считать их неверными с вероятностью Выражение для можно сразу написать в виде

Справедливость равенства (156) видна из следующего рассуждения: символ немедленно можно определить из любой проверки, в которой нет ни одного другого стертого символа; с другой стороны, если имеется другой стертый символ, то такая проверка не несет никакой информации относительно Таким образом, с вероятностью будет допущена ошибка тогда и только тогда, когда соответствует стертому символу и каждая из проверок, ортогональных относительно контролирует по крайней мере еще один стертый символ. Равенство (156) можно переписать в виде

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

Используя равенство (157), можно вычислить величину для двух двоичных стирающих каналов на рис. 22.

Рис. 22. (см. скан) Характеристика ПО-кода при для двоичного стирающего канала вероятность стирания). Остальная часть схемы такая же, как на рис. 11. Код из табл.

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

Если код удовлетворяет следствию теоремы 10, то, как и в случае двоичного симметричного канала,

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

Теорема 17. Пусть сверточный код используется для передачи со скоростью по двоичному стирающему каналу с вероятностью стирания Если система состоящая из проверок, ортогональных относительно образована так, что этих проверок имеют для любого то вероятность при пороговом декодировании удовлетворяет условию

где

Доказательство. Для кода теоремы 17 равенство (157) принимает вид

Ясно, что правая часть монотонно убывает с ростом Имеем также

Если удовлетворяет равенству (159), тогда выражение (161) превращается в

Из неравенства (162) следует, что произведение всех членов в равенстве (160) не может быть меньше, чем

половина произведения членов с индексами от 1 до включительно, а это и есть утверждение теоремы.