§ IV.4. ПОСЛЕДОВАТЕЛЬНОЕ ДЕКОДИРОВАНИЕ И ТЕХНИЧЕСКИЕ ВОЗМОЖНОСТИ ЕГО РЕАЛИЗАЦИИ

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

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

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

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

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

с двумя порогами

и

вид которых определяется существенно разными по порядку малости вероятностями ошибок первого и второго рода

(см. приложение 1, п. 4).

Из соотношений и (1.122), получим отношение среднего длины части выходной кодовой комбинации до вынесения решения к соответствующей фиксированной ее длине в классическом случае

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

Приступим теперь к оценке эффективности последовательного декодирования в целом.

Для этого заметим, что, вообще говоря, имеются два способа осуществления декодирования, состоящего из элементарных процедур выбора между двумя гипотезами:

1. Можно производить одним устройством

выборов между двумя гипотезами один за другим во времени;

2. Можно одновременно осуществлять таких выборов устройствами. (Технически это, по-видимому, неоправдано особенно при больших

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

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

При втором способе осуществление декодирования близко по структуре к многоканальному приему сигнала в одном из каналов [см. § 4.5.)]. В рассматриваемом случае больших выигрыш от последовательного декодирования нивелируется из-за необходимости ждать для вынесения окончательного решения окончания всех элементарных последовательных процедур.

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

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

Остановимся теперь на вопросе о принципиальных технических возможностях осуществления рассмотренных схем кодирования и декодирования.

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

В связи с этим может представить интерес возможность избежать устройства с большим объемом памяти на входе канала [94].

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

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

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

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

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

Однако на выходе необходимо иметь синхронный с входом экземпляр преобразования

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

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