II. Алгоритмы кодирования и декодирования

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

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

а) каждый информационный символ участвовал в образовании входных символов канала (это требование обеспечивает древовидность структуры множества передаваемых последовательностей);

б) декодирующий алгоритм допускал произвольное изменение относительных частот входных символов канала (это позволяет минимизировать сложность декодирования или же вероятность ошибки);

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

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

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

Если задано распределение вероятностей на входных символах то распределение вероятностей на выходных символах определяется следующим образом:

Предположим, что аппроксимированы рациональными дробями

где

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

Рис. 1. Схема последовательного кодирования.

На рис. 1 схематически показано, как в действительности может быть выполнено последовательное кодирование. Здесь 2 представляет собой последовательность символов источника сообщений каждый из которых отображается посредством функции в один из элементов конечного поля в результате чего образуется последовательность элементов поля Отображение взаимно однозначно. Для того чтобы скорость, с которой создаются символы сообщения, соответствовала заданной скорости передачи по каналу, к последовательности X могут быть добавлены нули, чередующиеся в определенном порядке с ее символами.

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

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

Можно показать [5], что в среднем по множеству всех возможных последовательностей имеющих равные вероятности быть выбранными, схема кодирования обладает следующими свойствами:

2) если конечная последовательность и то

3) если две конечные -последовательности длины да с порожденные последовательностями

и

такими, что для то

Свойства 1 и 2 непосредственно следуют из предположения о равновероятности последовательностей Доказательство свойства 3 несколько сложнее; его можно найти в работе автора [5].

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

Пусть переданная, принятая последовательность; последовательность назовем укороченной принятой последовательностью.

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

Последовательное декодирование основано на использовании метрики

где случайная величина, принимающая значения

Здесь некоторое распределение вероятностей на множестве выходных символов канала, так что

В дальнейшем будет использовано то обстоятельство, что распределение выбирается произвольно.

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

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

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

Назовем критерием величину определяемую из условия

здесь индекс 1 означает, что вероятность берется в соответствии с распределением (7).

Применяя неравенство Чернова (см. приложение II), можно построить оценку для величины зависящую от величины и порождающей функции семиинвариантов случайной величины I, распределенной по закону (7). Это построение описано в разд. III. Сам

процесс последовательного декодирования для дискретного канала без памяти в точности совпадает с процессом, описанным в приложении I для двоичного симметричного канала. Вопросы, связанные с оценкой сложности этого алгоритма декодирования и с выбором величин будут рассмотрены в разд. IV. Наконец, в разд. V исследуется поведение вероятности ошибки при последовательном декодировании.