§ IV.3. ОПТИМАЛЬНЫЕ СООТНОШЕНИЯ МЕЖДУ ПАРАМЕТРАМИ n, M и P И ОПТИМАЛЬНОЕ ДЕКОДИРОВАНИЕ

Приступим к решению поставленной в § IV.2 задачи. Будем составлять кодовую таблицу А из входных кодовых комбинаций. Будем считать, что каждая входящая в А входная кодовая комбинация возникает с вероятностью

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

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

Абсолютные вероятности выходных кодовых комбинаций

имеют вид

где число повторений символа в выходной кодовой комбинации

Вычислим теперь условные вероятности

выходных кодовых комбинаций при фиксации входных кодовых комбинаций кодовой таблицы А.

Легко показать, что если передавалось и было принято х, то

где означает число пар вида при посимвольном сопоставлении (их символы сопоставляются для одних и тех же моментов времени).

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

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

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

Поэтому так же, как и в бинарном случае (см. гл. 2, § 2.3, п. 2.3.6), естественно перейти к другой параметризации задачи, характеризуя гипотезы самими параметрами в случае и в случае

Тогда задача выбора между гипотезами сведется к задачам выбора между двумя гипотезами

и

Оптимальное решение об одном таком выборе содержится в гл. 2, § 2.3, п. 2.3.6 и основывается на логарифме коэффициента правдоподобия, который в нашем случае имеет вид

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

Поэтому является реализацией случайной величины

Случайная величина имеет также представлений [см. (2.121) и (2.122)]

где — независимые случайные величины, одинаково распределенные со случайной величиной С. Последняя имеет вид

и

Так как

если верна гипотеза и

если верна гипотеза то, учитывая соотношения (IV.5 — 8), будем иметь

если верна гипотеза и

если верна гипотеза

Для случая близких гипотез, чему соответствует в нашем случае малость величин

(высокий уровень шумов в канале), используя соотношения и (1.66), имеем

Поэтому случайная величина как сумма независимых, одинаково распределенных случайных величин в силу центральной предельной теоремы с ростом асимптотически -нормальна, если верна гипотеза и асимптотически -нормальна, если верна гипотеза

Откуда случайная величина

с ростом асимптотически

если верна гипотеза и

если верна гипотеза что позволяет предвидеть асимптотические оценки (2.126) и (2.127).

С их помощью для случая близких гипотез может быть доказана (см. приложение 1, п. 4) следующая теорема.

Предельная теорема [83]. Пусть - кодовая таблица А составлена из входных кодовых комбинаций длины выбранных из полиноминальной генеральной совокупности с параметрами

Передача входных кодовых комбинаций ведется по дискретному каналу с независимыми шумами, определяемому матрицей переходов

Пусть для каждой конкретно выбранной кодовой таблицы А процедура декодирования выходной кодовой комбинации х состоит в однопороговых классических процедурах выбора между двумя гипотезами

основанных на нормированных логарифмах коэффициента правдоподобия

с одним и тем же порогом , где

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

Тогда вероятность правильного декодирования кодовой таблицы А с ростом имеет следующие асимптотические оценки:

и

где

Оптимизируем соотношения между параметрами приведенные в предельной теореме при фиксированных

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

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

Таким образом, оптимальные соотношения между параметрами при фиксированной матрице

переходов малых имеют вид

если

Например, в простейшем случае бинарного симметрического канала, определенного матрицей перехода

где имеет смысл вероятности искажения символа, оптимальное распределение, как легко показать, имеет вид

Откуда согласно фундаментальная константа канала

Оптимальным оказывается (см. далее) и приводящий к соотношениям и способ декодирования, указанный в предельной теореме. Что касается оптимального способа кодирования, то предельная теорема не дает никаких указаний об эффективном способе построения конкретной оптимальной кодовой таблицы А.

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

по множеству всевозможных кодовых таблиц, где вероятность кодовой таблицы а вероятность правильного декодирования при ее использовании, Поэтому

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

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

Построение оптимальных кодовых таблиц, а также доказательство обратной теоремы требуют применения новых комбинаторных методов [83, 84, 91], не имеющих прямого отношения к используемым в этой книге статистическим методам. Поэтому мы здесь не будем их касаться.

Заметим лишь, что использование комбинаторных методов позволяет оценить вероятность того, что конкретная кодовая таблица, состоящая из входных кодовых комбинаций, выбранных из оптимальной генеральной совокупности, окажется оптимальной в указанном выше смысле. Можно показать [83], что с ростом вероятность стремится к единице быстрее вероятности правильного декодирования Поэтому указанный алгорифм построения оптимальной кодовой таблицы практически всегда приводит к цели и приведенный в предельной теореме способ декодирования оказывается оптимальным.

Следует отметить, что предельная теорема может быть доказана [83] без допущения о близости гипотез. При этом сохраняются предельные соотношения, но явное выражение оценок оказывается более громоздким.

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

которая следует из соотношений