5.1.4. Последовательный детектор максимального правдоподобия. Алгоритм Витерби

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

Чтобы разработать алгоритм максимального правдоподобия для детектирования последовательности символов, рассмотрим в качестве примера ДБНП (NRZI)-сигнал, описанный в разд. 4.3.2. Его память характеризуется решёткой, показанной на рис. 4.3.14. На каждом сигнальном интервале имеем сигнал двоичной AM. Следовательно, имеются два возможных передаваемых сигнала, соответствующих сигнальным точкам где энергия на бит. Выход согласованного фильтра или корреляционного демодулятора для двоичной AM на -м сигнальном интервале можно выразить так:

(5.1.57)

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

(5.1.58)

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

(5.1.59)

где или . Тогда по заданной последовательности на выходе согласованного фильтра или корреляционного демодулятора детектор определяет которая максимизирует условную ФПВ . Такой детектор называется максимально правдоподобным (МП) последовательным детектором.

Взяв логарифм от (5.1.59) и опуская слагаемое, не зависящее от , находим, что эквивалент МП детектора последовательности – это детектор, выбирающий последовательность , которая минимизирует евклидово расстояние

(5.1.60)

При поиске на решётке последовательности, которая минимизирует евклидово расстояние , может показаться, что мы должны вычислить расстояния для всех возможных последовательностей. Например, для ДБНП, которая использует двоичную модуляцию, общее количество последовательностей равно где - число отдельных выходов демодулятора. Однако это не так. Мы можем уменьшить число последовательностей при поиске по решётке, используя алгоритм Витерби для отсечения последовательностей по мере поступления новых данных от демодулятора.

Алгоритм Витерби является алгоритмом последовательного поиска на решётке для обеспечения МП декодирования последовательности. Он описывается в гл. 8 как алгоритм декодирования свёрточных кодов. Мы опишем его ниже применительно к сигналам ДБНП.

Предположим, что процесс поиска начинается первоначально с состояния . Соответствующая решётка показана на рис. 5.1.11.

Рис. 5.1.11. Решетка для сигнала ДБНП (NRZI)

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

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

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

Для двух путей, входящих в узел , вычислим две евклидовы метрики расстояний

(5.1.61)

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

Аналогично для двух путей, входящих в узел в точке мы вычислим две евклидовы метрики расстояний

(5.1.62)

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

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

(5.1.63)

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

(5.1.64)

Эти две метрики сравниваются, и путь с большей метрикой (большим расстоянием) исключается.

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

Относительно просто отобразить поиск по решётке по алгоритму Витерби для -позиционной модуляции. Для примера на рис. 5.1.12 показана решётка на четыре состояния, характеризующая модуляцию с задержкой, использующую сигнала.

Мы видим, что для каждого состояния два сигнальных пути входят в узел и два из него выходят.

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

Из описания алгоритма Витерби, данного выше, не ясно, как выносится решение об индивидуальном детектируемом информационном символе по данным выжившим последовательностям.

Рис. 5.1.12. Один шаг по решетчатой диаграмме для модуляции с задержкой.

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

Пример 5.1.4. Рассмотрим правило решения при детектировании данных последовательности сигналов ДБНП с алгоритмом Витерби и задержкой решения на символов.

Решётка для ДБНП показана на рис. 5.1.11. В этом случае следовательно, задержка при детектировании символа простирается на 5 бит. Следовательно, при имеем две выжившие последовательности, одну для каждого из двух состояний, и соответствующие метрики и . На этом шаге с вероятностью, близкой к единице, символ будет такой же, что и ; это значит, что обе выжившие последовательности будут иметь общую первую ветвь. Если мы можем выбрать символ или , соответствующий меньшей из двух метрик. Затем первый бит исключается из двух выживших последовательностей. При две метрики и используются для определения решения по символу . Этот процесс повторяется на каждом шаге при поиске по решётке наименьших по расстоянию последовательностей. Таким образом, в нашем примере задержка детектора фиксирована на 5 символов.