Решетчатая диаграмма
Решетчатая диаграмма (trellis diagram).
Решетчатая диаграмма представляет процесс изменения состояний сверточного кодера при поступлении на его вход битовой последовательности. Пример приведен для кодера с четырьмя состояниями. Пунктирные линии показывают изменения состояний при поступлении на вход кодера нуля, сплошные линии – при поступлении единицы. Каждый переход помечен соответствующей кодовой комбинацией, появляющейся на выходе кодера.
Каждой входной последовательности соответствует определенный путь в решетке и соответствующая этому пути «правильная» выходная последовательность. Начальное состояние - 00.
Один из алгоритмов декодирования (алгоритм Витерби, или алгоритм максимального правдоподобия), сравнивает принятую декодером кодовую комбинацию с правильными, соответствующими различным путям в решетке, и заменяет на ту, которая по кодовому расстоянию ближе всех к принятой. Число различных путей в решетке очень велико. Объем вычислений минимизируется благодаря использованию итерационного (пошагового) алгоритма, аналогичного алгоритму динамического программирования.
Как видно из диаграммы, после К переходов (К=3) картина переходов повторяется. В каждое состояние ведут 2 пути. Для каждого пути длиной в i переходов, начинающегося из начального состояния и заканчивающегося в момент ti (на первом шаге вычислений i=3), определяется метрика - кодовое расстояние между принятой последовательностью и правильной последовательностью, соответствующей данному пути. Из всех путей, ведущих в данное состояние, выбирается один путь с минимальным кодовым расстоянием, остальные пути отбрасываются как "тупиковые". После просмотра путей длиной в i переходов просматриваются и отбрасываются тупиковые пути длиной в i +1 переходов и т.д. Начиная с некоторого момента ti , начальный участок у всех "выживших" путей оказывается одним и тем же. Соответствующая этому участку кодовая комбинация считается достоверной. По мере роста номера i длина общего участка, а следовательно и скорректированной части принятой кодовой последовательности, увеличивается.
