6.4.3. Двоичный симметричный широковещательный канал.

В качестве примера ШК рассмотрим двоичный симметричный т. е. такой ШК, у которого и первая и вторая составляющие являются обычными ДСК с вероятностями ошибок соответственно. На этом примере будет проиллюстрирована основная идея кодирования в УШК.

Покажем вначале, что ДСШК действительно является УШК. Рассмотрим последовательное соединение двух ДСК, первого с вероятностью ошибки а второго — (см. рис. 6.4.5). Тогда результирующий канал будет ДСК с вероятностью ошибки

Если то последнее соотношение, рассматриваемое как уравнение относительно дает следовательно, рассматриваемый ШК является ухудшающимся. Мы будем называть сверткой операцию, обозначенную в (6.4.5) знаком таким образом, есть свертка Свертка обладает следующими легко проверяемыми свойствами: 1) если если либо либо

Рассмотрим следующий метод построения кода для ДСШК при передаче в ситуации Пусть имеются три последовательно соединенных ДСК с вероятностью ошибок (см. рис. 6.4.6). Первый канал, имеющий вероятность ошибки а, будем называть

тест-каналом, а его входной алфавит обозначать через Результирующий канал, как легко видеть, снова является ДСК- Его вероятность ошибки равна На входном алфавите тест-канала зададим равномерное распределение вероятностей и построим код

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

где для которого вероятность ошибки Кодовые слова этого кода будем обозначать через и называть центрами концентрации.

Рис. 6.4.6. К построению кода для ДСШК в ситуации

Если на входе первого ДСК фиксирована некоторая последовательность то в силу закона больших чисел при большом с вероятностью, близкой к единице, появится такая последовательность которая отличается от примерно в символах. Так как фиксированной последовательности соответствует следующее условное распределение на

то высоковероятное множество этого распределения состоит из последовательностей отличающихся от примерно в символах. Заметим далее, что

где последнее равенство следует из независимости от при фиксированном В силу симметрии каналов имеем

и, следовательно,

Таким образом, если на фиксировано распределение вероятностей то

В соответствии с неравенством Файнстейна (см. теорему 3.8.1) для любого и любого при достаточно большом можно построить код для ДСК с вероятностью ошибки слова которого принадлежат высоковероятному множеству ансамбля и вероятность ошибки декодирования Скорость такого кода удовлетворяет неравенству

Кодовые слова для ДСШК получаются так. Построим кодов для каждого центра концентрации

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

Рассмотрим следующее правило декодирования построенного кода. Декодер на выходе второй составляющей ДСШК по принятой последовательности определяет центр концентрации так, как если был он передавался по ДСК с вероятностью ошибки Так как при фиксированном кодовые слова принадлежат высоковероятному множеству распределения а центры концентрации являются кодовыми словами кода для ДСК с вероятностью ошибки то при и достаточно большом вероятность неправильного определения центра концентрации может быть сделана сколь угодно малой. Декодер на выходе первой составляющей ДСШК работает в два этапа. На первом этапе он определяет по принятой последовательности у центр концентрации Так как вторая составляющая является ухудшенным вариантом первой, то декодер первой составляющей также может определить с произвольно малой вероятностью ошибки. На втором этапе, зная декодер осуществляет декодирование кода в результате которого определяется переданная последовательность Если то при достаточно большом вероятность ошибки декодирования на втором этапе при условии, что определен верно, может быть сделана также сколь угодно малой.

Таким образом, мы показали, хотя и не вполне строго, что в ДСШК допустимы все такие пары скоростей которые при некотором удовлетворяют неравенствам

Область допустимых пар скоростей, задаваемая этими неравенствами, показана на рис. 6.4.7.

Рассмотренный пример наводит на мысль о том, что и для произвольного дискретного УШК без памяти допустимые пары скоростей могут быть получены аналогичным способом. А именно, пусть некоторое конечное множество и некоторое распределение вероятностей на Рассмотрим ансамбль распределение вероятностей на котором имеет следующий вид:

Рис. 6.4.7. Область допустимых пар скоростей

Наше предположение состоит в том, что для произвольного дискретного УШК без памяти допустимой является любая пара скоростей такая, что

где средние взаимные информации вычислены в соответствии с распределением вероятностей (6.4.8) на ансамбле Ниже мы докажем прямую и обратную теоремы кодирования, из которых будет следовать, что область пропускной способности для дискретного УШК без памяти состоит из всех пар скоростей, удовлетворяющих неравенствам (6.4.9) при некотором 5 и некотором распределении на