502 ГЛ. 14. композиция и ХАРАКТЕРИСТИКИ КОДОВ

14.2. ВЕРОЯТНОСТИ ОШИБОЧНОГО

ДЕКОДИРОВАНИЯ И НЕУДАЧНОГО ДЕКОДИРОВАНИЯ

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

Рассмотрим случай использования линейных кодов в каналах, вносящих в символы ошибки независимо и симметрично. Выражения для указанных вероятностей зависят от распределения весов {Ai\ кода и поэтому полезны лишь в случае, когда оно известно. В предыдущем параграфе получено распределение весов для кодов Рида-Соломона, так что для этих кодов мы можем вычислить вероятности ошибочного декодирования и неудачного декодирования.

Рассматриваемые каналы представляют собой -ичные каналы, вносящие ошибки в передаваемые символы независимо с вероятностью Р и передающие символы правильно с вероятностью 1 - Р. Каждое из д - 1 ошибочных значений принимается с вероятностью Р/{д -• 1). Каждая конфигурация k ошибок наблюдается с вероятностью

Мы рассмотрим лишь неполный декодер, который не принимает решения о декодировании вне радиуса упаковки кода. Каждое принятое слово, лежащее от ближайшего кодового слова на расстоянии, не превышающем t, декодируется в это кодовое слово; здесь t-фиксированное число, удовлетворяющее неравенству

2/+ 1 < d*.

Исследуем условные вероятности ошибочного и неудачного декодирования в случае линейного кода при условии, что передано слово, целиком состоящее из нулей. Кажл.ое другое переданное слово приводит к тем же самым условным вероятностям, так что они являются также безусловными вероятностями. На рис. 14.2 изображены три области, в которые может попасть принятое слово.

Койобые слова

Переданное коЭовое слово

Рис. 14.2. Области декодирования.

Вероятность правильного декодирования - это вероятность того, что принятое слово попадает в область, покрытую редкой штриховкой. Вероятность неправильного декодирования - это вероятность того, что принятое слово попадет в область, покрытую частой штриховкой. Вероятность неудачного декодирования - это вероятность того, что принятое слово попадет в незаштрихо-ванную область. Сумма этих трех вероятностей равна 1, поэтому достаточно найти формулы лишь для двух из них. Начнем с самого простого.

Теорема 14.2.1. Вероятность правильного декодирования декодера, исправляющего ошибки в пределах радиуса упаковки кода, равна

Доказательство. Число способов, которыми можно разместить конфигурации из v ошибок, равно ("j; каждая из них имеет место с вероятностью {\ - Р)"-. Отсюда следует утверждение теоремы. □

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

фигурации ошибок, вероятности которых нужно просуммировать, приведены на рис. 14.3. й*

Пусть N (1, h; s)означает число конфигураций ошибок веса h, находящихся на расстоянии s от кодового слова веса /. Ясно, что (/, h; s) не зависит от выбора кодового.слова веса /. Заметим, что если N {I, h; s) Ф О, то / - s < Л / + s. В приведенной ниже теореме это условие выполняется автоматически, так как

мы условились считать = О при m < О или т > п.

Теорема 14.2.2, Число конфигураций ошибок веса h, находящихся на расстоянии s от конкретного кодового слова веса I, равно

Nii,h;s)= S (,;: :,) С) (7) (9-1)/+-(9-2)-.

i+2i+h:=s+i

Доказательство. Равенству, которое требуется доказать, эквивалентно равенство

Nit,h;si= Т [Г:)(Я-Ш)(а-2у]Ш,

I, ], к i+i+k=s l+k-j=h

ЧТО может быть проверено подстановкой k = } h - /. В нем фигурируют три ирщекса суммирования и два ограничения. Суммируется числокодовых слов, которые могут быть получены замерюй любых k т п - / нулевых компонент кодового слова на любой из 9 - 1 ненулевых символов, любых i из / ненулевых

ПерейаннОЕ мЭоеое c/ioeo

( ( (

Рис. 14.3. Некоторые слова, вызывающие ошибку декодирования,