10.1.3. Алгоритм Витерби для модели фильтра с дискретным временем и белым шумом

Алгоритм МППО для оценки информационной последовательности  наиболее легко описывается через принимаемую последовательность  на выходе обеляющего фильтра. В присутствии МСИ, которое покрывает  символа ( интерферирующий компонент), реализация правила MППО эквивалентно оцениванию состояния конечного автомата с дискретным временем. Конечный автомат в этом случае является эквивалентом канала с дискретным временем с коэффициентами , а его состояние в любой момент времени определяется  новыми (последними) входами, т.е. состояние в точке  определяется так:

,                    (10.1.20)

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

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

.                        (10.1.21)

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

.                      (10.1.22)

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

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

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

                      (10.1.23)

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

,                        (10.1.24)

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

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

Пример 10.1.2. Для иллюстративных целей предположим, что для передачи четырехуровневой  AM используется дуобинарный сигнальный импульс. Таким образом, каждый символ - это число, выбираемое из ряда . Контролируемая МСИ в этом сигнале с парциальным откликом представлена эквивалентной моделью канала с дискретным временем, показанной на рие. 10.1.4. Предположим, мы приняли отсчеты  и , где

                        (10.1.25)

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

,                       (10.1.26)

где для .

Рис. 10.1.4. Эквивалентная модель дискретного времени для межсимвольной интерференции, образованной дуобинарным импульсом

Заметим, что не все последовательно принимаемые сигналы включают в себя . Таким образом, на этом шаге мы можем исключить 12 из 16 возможных пар . Этот шаг иллюстрирует древовидная диаграмма, показанная на рис.10.1.5.

Рис. 10.1.5. Древовидная диаграмма для декодирования по Витерби дуобинарного импульса

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

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

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

.                         (10.1.27)

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