Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Приступим теперь к доказательству этих теорем в частном случае ДСК. Начнем с рассмотрения произвольного (N, R)-кода и найдем нижнюю границу для Ре, которая не зависит от кода и, таким образом, является нижней границей Р е для всех кодов с заданными N и R. Пусть хъ ..., хм — кодовые слова кода, М = \~~eNR j и пусть Yu ..., Ум — области декодирования этого кода (т. е. Ym является множеством последовательностей на выходе канала, которые декодируются в сообщение т). Если сообщение т поступает на кодер, то передается хт и произойдет правильное декодирование, если будет принято у ? 176
(5.8.10)
(5.8.9)
Ре > ехр (- N { Esl [R - о3 (А01 + о4 (N)}). (5.8.11)
*" ? Ут- Поскольку при условии, что задано т, это событие имеет вероятность
S ^(У I хт)’
то общая вероятность правильного декодирования равна
1 м
S Ж У !хт). (5.8.12)
М т= 1 у GV
1,0
,5
^ex(R)
Eso(R)
*)
Eex(R) fsp (R) Ep(R)
,68 ,70 ,72
3)
Рис. 5.8.2. Границы для функции надежности (те же каналы, что и на рис. 5.8.1).
Определим теперь расстояние Хэмминга d (у; х) между двумя двоичными последовательностями как число позиций, в которых отличаются эти две последовательности. Например, расстояние Хэмминга между (0, 0, 1, 1, 1) и (1, 0, 1, 0, 1) равно 2. В ДСК с вероятностью ошибки е, если d (у; xm) = п, то Р (у | хт) = гп (1 — e)N~n. Если через Ап,т обозначить число последовательностей у, которые декодируются в сообщение т и расстояние которых от хт равно п, то (5.8.12) можно представить в виде
2 м N
Рс = — S S Лп,те"(1-е)"-\ (5.8.13)
М т=I п=0
177
Используя равенство для биномиального распределения
1= 2 (' N W(l-e)w-",
п=0 V п 1
находим, что вероятность ошибки Ре = 1 — Рс будет равна
j Af iV
= ( )-Лп,т e”(l—e)v-«. (5.8.14)
М т—1п=0 L\ л / J
Чтобы истолковать это выражение, заметим, что если было передано сообщение т, то Ап т равно числу последовательностей, находящихся на расстоянии п от хт, прием которых приводит к правильному декодированию. В силу того, что (^) равно общему числу последовательностей, находящихся на расстоянии п от хт, то [(„) — Ап>гп\ из этих последовательностей будут приводить к ошибочному декодированию при передаче т.
Найдем теперь некоторые ограничения на множество целых чисел [Ап,т}> которые справедливы для всех кодов с данными N и М и затем найдем минимум правой части (5.8.14) при соблюдении этих ограничений. Ограничения, которые будут использованы, имеют вид
А„
ЛП,ТП
{ N ) при всех пит, (5.8.15)
V п )
М N
2 (5.8.16)
т—1п=0
Ограничение (5.8.16) связано с тем, что имеются всего 2N выходных последовательностей; каждая последовательность декодируется не более чем в одно сообщение и расстояние от сопоставленного ей кодового слова определяется однозначно.
Минимум (5.8.14) при соблюдении этих ограничений достигается при е < 1/2 и для всех т, когда
А
п,т
(5.8.17)
где k выбирается так, что
k-i м м
л* 2 ( ) + 2 = 0<2\mar . (5.8.18)
n=z0 \ П ] т~1 т= I \ k )
Отдельные значения Ah m не существенны, если их сумма по т удовлетворяет (5.8.18). Для того чтобы убедиться, что такой выбор приводит к минимуму (5.8.14), заметим, что при любом другом выборе можно найти п' и п, п' С п, такие, что АП'П><, (^) для некоторого т' и Ап,т 0 для некоторого т. При таком выборе можно увидеть, что
(5.8.14) уменьшается при увеличении Ап,т> на 1 и уменьшении АПзТП на 1. Подставляя (5.8.17) в (5.8.14) и замечая, что в результате 178
получится нижняя граница Ре для всех кодов, с заданными значе-
где (/V, УИ) определяется как минимальная вероятность ошибки по всем кодам с данной длиной блока N и с данным числом кодовых слов М.
Эта граница называется границей сферической упаковки. Множество последовательностей, находящихся на расстоянии k или меньше от кодового слова, можно интерпретировать как сферу радиуса k вокруг этого кодового слова. Граница, представленная (5.8.19), является вероятностью ошибки, которая бы имела место, если бы можно было выбрать кодовые слова так, чтобы множество сфер радиуса k, описанных вокруг различных кодовых слов, исчерпывало все пространство двоичных последовательностей длины N и сферы имели бы пересечения друг с другом только по внешним слоям радиуса k. Такие коды называются сферически упакованными кодами и код, изображенный на рис. 5.2.1, дает пример такого кода (в этом случае нет пересечений даже на внешнем слое радиуса 1). Часто при выводе этой границы сначала находится вероятность ошибки для сферически упакованного кода и затем показывается, что сферически упакованный код имеет вероятность ошибки не большую, чем любой другой код с теми же самыми N и М. В таком выводе имеется логическая ошибка, состоящая в том, что для большинства значений N и М не существует сферически упакованных кодов.
