6.4.5. Прямая теорема кодирования.

Теперь покажем, что любая пара скоростей допустима для дискретного УШК без памяти при передаче в ситуации Для этого достаточно будет показать, что для любого распределения вероятностей на удовлетворяющего условию (6.4.8), найдется и найдется код со скоростями обеспечивающий вероятности ошибок с где и — произвольные положительные числа. Установление этого факта завершит описание области пропускной способности для УШК.

Доказательство прямой теоремы кодирования будет проводиться методом случайного кодирования, аналогичным тому, который использовался при доказательстве прямой теоремы кодирования для каналов с множественным доступом. При построении кода для УШК будут использованы идеи, лежащие в основе построения кода для двоичного симметричного ШК (см. п. 6.4.3).

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

— множество слов кода

— связанное с ним множество центров концентрации. Каждому коду из ансамбля припишем вероятность

где

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

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

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

для всех , где

Декодер на выходе первой составляющей ШК работает в два этапа. На первом этапе по выходной последовательности он выносит решение о том, какому центру коцентрацин принадлежит передаваемое кодовое слово. Выносится решение если

для всех , то

На втором этапе по выходной последовательности у и по решению полученному на первом этапе, декодер выносит решение о том, какое кодовое слово передавалось, причем выносится решение если

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

кодовое слово Согласно описанному выше правилу декодирования

где

Функции равны единице соответственно в случаях, когда происходят ошибки декодирования на выходе второго декодера, и на первом и втором этапах на выходе первого декодера.

Теорема 6.4.2 (прямая теорема кодирования). Пусть фиксировано распределение вероятностей на множестве и задан дискретный УШК без памяти Тогда в ансамбле распределение вероятностей на котором определяется соотношениями и (6.4.37), существует код такой, что и вероятности, ошибок где произвольные положительные числа, и средние взаимные информации вычислены в соответствии с распределением на

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

угодно малыми. Для этого воспользуемся следующими очевидными оценками фукнций

Подставим неравенства в (6.4.40) и (6.4.41) и усредним обе части полученных неравенств по ансамблю , выбирая При усреднении будем учитывать, что

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

б) при фиксированном кодовые слова статистически независимы в ансамбле кодов (см. (6.4.36));

в) для всех имеет место неравенство где произвольная случайная величина и черта сверху означает усреднение;

г) средние по ансамблю кодов значения вероятностей не зависят от индексов

В результате операций усреднения и преобразований, подобных тем, которые производились в § 3.12, с учетом соотношений получим следующие неравенства при

где

Полагая

получим, что

Непосредственной проверкой легко убедиться в том, что

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

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

Задачи, упражнения и дополнения

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

КРАТКИЙ ИСТОРИЧЕСКИЙ КОММЕНТАРИЙ И ЛИТЕРАТУРА

Задача кодирования зависимых источников без памяти впервые была поставлена и решена Д. Слепяном и Дж. Вулфом [17]. Доказательства теорем кодирования, приведенные в § 6.1, принадлежат Р. Алсведе и Я. Кернеру |3].

Задача кодирования источников с дополнительной информацией впервые была поставлена и решена для одного частного случая двоичных источников А. Вайнером [6]. Решение этой задачи для произвольных зависимых источников без памяти было независимо получено Р. Алсведе и Я. Кернером [3] и А. Вайнером (7]. Обобщение задачи кодирования зависимых источников было рассмотрено в работах С. И. Гельфанда и М. С. Пинскера [10] и Я. Кернера и К. Мартон [13].

Постановка задачи кодирования в канале с множественным доступом впервые встречается у К. Шеннона [19]. Решение этой задачи принадлежит Р. Алсведе [1, 2]. Более общая постановка (см. задачу 6.3.5) рассмотрена в работе Д. Слепяна и Дж. Вулфа [18].

Постановка задачи кодирования в широковещательных каналах принадлежит Т. Коверу [14]. В этой же работе изложены некоторые идеи по кодированию в ШК. Область пропускной способности УШК была определена в работе Р. Галлагера [8] и Р. Алсведе и Я. Кернера [3].

Имеется значительное число работ, посвященных кодированию в системах с большим числом пользователей. В приведенной ниже библиографии содержатся лишь те из них, результаты которых использованы либо в основном тексте шестой главы, либо в задачах к этой главе. Интересующемуся читателю можно порекомендовать обзоры ван дер Мейлена [5] и С. И, Гельфанда и В. В. Прелова [11].

(см. скан)

(см. скан)

ПРИЛОЖЕНИЕ I

(см. скан)

ПРИЛОЖЕНИЕ II

(см. скан)

(см. скан)