Глава 6. ОБОБЩЕНИЯ И ПРИЛОЖЕНИЯ

1. Выбор метрики

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

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

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

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

Так как может принимать только значения и , то вычисление выражения (6.2) сводится к определению числа индексов для которых Но это число совпадает с которое было определено как число единиц в последовательности Таким образом, мы видим, что расстояние, с которым мы сравниваем в нашей последовательной процедуре поиска, — монотонно связано с переходной вероятностью

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

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

2. Определить исключающую функцию так, чтобы

где - некоторый заданный заранее вероятностный критерий, не зависящий от Индекс нуль при означает, что вычислено для того которое было в действительности передано.

Для общего канала без памяти так же, как и для

Форма равенства (6.4) подсказывает, что расстояние удобно выбрать в виде

или в виде

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

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

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

апостериорные вероятности". Вудворд [5] показал, что такой приемник идеален в том смысле, что он не приводит к потере информации в отличие от приемника, который выбирает наиболее правдоподобный вход.

На практике, конечно, последовательно декодирующее устройство будет, вероятно, квантовать выход полунепрерывного канала, в результате чего возникнет дискретный канал. Если квантование проводится с двумя уровнями, то возникает двоичный канал, а если оно проводится с тремя или четырьмя уровнями и притом симметричным образом, то возникает канал с нулевой зоной [2], и т. д. Вообще говоря, уменьшение числа уровней квантования приводит к увеличению потерь информации.