6. Декодирование в системах с переспросом

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

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

В частности, когда система является простой [(V.2.1)-(V.2.3) и декодирование проводится по критерию отношения правдоподобия с заданным критическим уровнем, скорость передачи оказывается максимальной при фиксированной средней вероятности ошибочного опознания сообщения.

В системах с переменными параметрами, где в каждом состоянии канала и

(для всех ) вероятность неправильного декодирования

(V.6.1)

а скорость передачи

(V.6.2)

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

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

Критические состояния канала в первом случае определяются исходя из величины , а во втором — из величины .

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

Пусть для опознания переданного сообщения на

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

(V.6.3)

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

Теорема V.6. Если в простой системе с переспросом на каждом шаге процееса декодирования вероятность (V.6.3) достаточно близка к заданной величине то процесс опознания сообщения заканчивается через число шагов, не большее, чем , со средней вероятностью ошибки

(V.6.4)

При этом скорость передачи

(V.6.5)

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

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

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

Пусть принят первый сложный сигнал (V.1.4), и наивыгоднейшим решением оказалось (послать сигнал переспроса).

Апостериорные вероятности того, что при принятом сигнале было передано сообщение

(V.6.6)

С точки зрения декодера вероятность (V.6.6) можно интерпретировать как «априорную» вероятность повторной передачи сообщения . В соответствии с этим может быть определена новая обобщенная матрица потерь

(V.6.7)

где

(V.6.8)

(здесь имеет прежний смысл).

Проводя рассуждения, аналогичные тем, которые были использованы при выводе теоремы IV.1, легко установить, что при повторной передаче средний риск будет минимален, если в подмножество включить все сигналы, удовлетворяющие условиям, аналогичным (V.1.4)-(V.1.5):

(V.6.9)

Допустим далее, что после повторной передачи был принят сигнал , принадлежащий подмножеству (вновь посылается сигнал переспроса).

Апостериорная вероятность того, что при принятых сигналах и было передано сообщение , равна

(V.6.10)

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

(V.6.11)

где

(V.6.12)

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

(V.6.13)

Для общего случая мы можем сформулировать следующую теорему.

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

(V.6.14)

где

(V.6.15)

и

(V.6.16)

Напомним, что для всех и поэтому .

Рассмотрим, как преломляются приведенные выше соотношения для случая, когда система с переспросом и полной памятью является простой [см. (V.2.1)-(V.2.3)].

В соответствии с теоремой (V.2.1) на шаге декодирования средняя вероятность неправильного опознания сообщения будет минимальной (для данного значения ), если сигналы, включаемые в подмножество , одновременно удовлетворяют двум требованиям:

(V.6.17)

и

(V.6.18)

По аналогии с § 3 можно показать, что разбиение множества близко к оптимальному, если в подмножество включить только сигналы , удовлетворяющие условию[см. (V.3.3)

(V.6.19)

Задаваясь той или иной матрицей , из неравенства (V.6.19) легко получить ряд конструктивных алгоритмов декодирования типа рассмотренных в § 3. Так, например, для симметричных каналов без памяти мы имеем

(V.6.20)

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

(V.6.21)

где определяется формулой (V.3.6) и

(V.6.22)

Из (V.6.21) видно, что когда , то подмножество будет более мощным, чем . Если же , то совпадает с . В случае подмножество менее мощно, чем . В частности, при оно будет содержать лишь комбинацию , а при окажется пустым.

Из анализа (V.6.21) можно сделать несколько выводов. Во-первых, использование для принятия решения процедур типа описанных выше позволяет ограничиться конечным числом алгоритмов декодирования. Во-вторых, вероятность того, что на шаге декодирования будет использован алгоритм, зависит только от ситуации, которая реализовалась на шаге, и не зависит от номера сигнала переспроса. Эти два обстоятельства дают основания полагать, что для расчета средней вероятности неправильного декодирования и среднего числа переспросов может быть использован ряд известных положений из теории цепей Маркова [12]. Наконец, при применении таких процедур декодирования существенно сокращается вероятность посылки сигналов переспроса с номерами два и более.

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

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