Дополнение. ПОСЛЕДОВАТЕЛЬНОЕ ДЕКОДИРОВАНИЕ ДЛЯ КАНАЛОВ БЕЗ ПАМЯТИ С ДИСКРЕТНЫМ ВХОДОМ

Б. Рейффен

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

1. Введение и краткое изложение результатов

Шеннон [11] в 1948 г. показал, что по каналу с пропускной способностью С можно передавать сообщения

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

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

Теоретическая эффективность блоковых кодов для дискретных каналов без памяти теперь хорошо понята. Недавняя работа Фано [8] объединяет и развивает более ранние работы Файнстена [7], Элайеса [14] и Шеннона [12]. Наилучший из блоковых кодов обладает вероятностью ошибки, большей, чем некоторая величина, убывающая экспоненциально с ростом длины блока. Кроме того, средняя вероятность сшибки в некотором соответствующим образом определенном множестве блоковых кодов оказывается меньше некоторой другой величины, также убывающей экспоненциально с ростом длины блоков. Обе экспоненты являются функциями канала и убывают с увеличением скорости передачи. Для наиболее интересного интервала скоростей вблизи С экспоненты нижней и верхней границ совпадают.

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

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

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

Кодирующее устройство на передающем конце сопоставляет каждое из сообщений с одной из последовательностей, используемых в данном коде. При вычислении апостериорных вероятностей приемник вынужден дублировать работу кодирующего устройства. Ясно, что для реализации произвольного кода требуется кодирующее устройство, сложность которого, вообще говоря, пропорциональна Для некоторых типов каналов предложены системы кодирования, для которых вероятность ошибки ведет себя оптимальным образом, а сложность зависит от не экспоненциально, а линейно [3, 6, 14]. Однако соответствующие им системы декодирования все еще приводят к экспоненциальной зависимости объема памяти или объема необходимых вычислений от длины кода.

Возенкрафт, исследовавший двоичный симметричный канал (ДСК), первым предложил алгоритм декодирования, сложность которого растет лишь как степень числа и и для которого вероятность ошибки убывает экспоненциально с ростом При этом экспонента оптимальна для скоростей передачи, близких к пропускной способности канала [1, 21. Этот способ, названный последовательным декодированием, описан в приложении I с обозначениями, принятыми в настоящей статье.

Целью статьи является распространение идеи последовательного декодирования на более общие типы каналов. Ниже приводятся основные результаты.

1. Для произвольного канала без памяти с дискретным входом определяется алгоритм последовательного кодирования и декодирования.

2. При использовании этого алгоритма получается осредненная (по ансамблю кодов) вероятность ошибки для которой

Экспонента растет с уменьшением

3. Для произвольного дискретного канала без памяти определено пороговая вычислительная скорость передачи. Для осредненный по ансамблю кодов объем вычислений ограничен величиной, пропорциональной Для верхняя оценка для этого объема с ростом растет экспоненциально.

4. Результаты 2 и 3 обобщаются на полунепрерывный канал, т. е. на канал с дискретным входом, выход которого, однако, является континуальным.

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

6. Для дискретного симметричного по выходу канала без памяти с равномерным распределением вероятностей на входе определена пороговая вычислительная скорость передачи Для осредненный по ансамблю кодов объем вычислений при декодировании ограничен сверху величиной, пропорциональной Для граница растет экспоненциально с ростом