Приложение I. Краткое описание последовательного кодирования и декодирования в приложении к двоичному симметричному каналу

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

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

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

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

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

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

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

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

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

5. Каждая из возможных входных последовательностей проверяется следующим образом: на первых позициях она складывается по модулю два с принятой последовательностью, после чего определяется метрика равная числу единиц в сумме, взятому со знаком минус, т. е. расстоянию Хэмминга со знаком минус. Эта величина сравнивается с фиксированным числом которое выбирается независимо от принятой последовательности. Если то проверяемая последовательность увеличивается до длины и проверяется снова. Если то последовательность отвергается (вместе со всеми последовательностями, для которых она является общим началом длины

6. В действительности имеется не один набор фиксированных чисел а последовательность таких наборов:

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

7. Величина определяется как наименьшая из величин, удовлетворяющих неравенству

индекс 1 означает, что вероятность вычисляется для

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