LEKTsIYa_11

Пусть первый входной бит «1», тогда на выходе 111. Пусть второй входной бит «0». Тогда он записывается в первую ячейку, а «1» продвигается во вторую ячейку. В результате ячейки сдвига находятся в состоянии 010. Тогда на выходе имеем 001. Пусть третий входной бит «1». Тогда состояние ячеек сдвига будет следующее: 101, а на выходе формируется последовательность

100 и т.д.

Генератор можно отобразить векторами g1 (100) , g2 (101) , g1 (111) .

Генераторы (порождающие полиномы) задаются в восьмеричной форме:

g(4,5,7) , т.е. 4 100; 5 101; 7 111.

Вобщем случае, когда k 1эти n генераторов отображаются k - мерными векторами.

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

Пример 2. Древовидная диаграмма для примера 1.

Видно, что структура повторяет себя после третьего такта.

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

Здесь обозначено a - 00, b – 01, c – 10, d – 11.

С учетом состояний можно изобразить решетчатую диаграмму:

Диаграмма состояний для данного примера выглядит следующим образом:

101

Обозначения: «сплошная линия» - входной бит «0», «пунктирная линия» - входной бит «1».

Передаточная функция сверточного кода.

Передаточная функция определяет дистанционные свойства и характеристики качества (вероятность ошибки) сверточного кода. Вернемся к примеру 1 и 2. Пометим на диаграмме состояний ветви как D0 , D1, D2 , D3 , где показатель у D - расстояние Хемминга между выходной битовой последовательностью соответствующей ветви и последовательностью из одних нулей. Собственную петлю у узла a можно исключить, т.к. она ничего не вносит в дистанционные свойства кодовой последовательности относительно последовательности из одних нулей. Узел a делится на 2 узла: один входной (a) другой выходной (e).

d

Диаграмма состоит из пяти узлов: a, b, c, d, e. Тогда уравнения состояния имеют вид:

выражение для передаточной функции:

Передаточная функция (6.20) этого кода показывает, что существует единственный путь с расстоянием Хемминга d 6 от пути из одних нулей, который сливается с путем из одних нулей при данном узле. Это путь acbe. Второе слагаемое говорит о том, что есть 2 пути от a до e с d 8 : acdbe и acbcbe и т.д. Таким образом, передаточная функция T (D) дает дистанционные свойства сверточного кода. Минимальное расстояние кода называется

минимальным свободным расстоянием dсв . Для разобранного примера

dсв 6.

Для получения более детальной информации введем множитель N для всех переходов ветвей, вызванных входным битом «1» и множитель J для каждой ветви диаграммы так, что он будет служить счетной величиной, указывающей число ветвей для любого пути от узла a к узлу e. Тогда

d

Уравнения диаграммы состояний в этом случае имеют вид:

X c JND3 X a JNDX b ; X b JDX c JDX d ;

X d JND2 X c JND2 X d ; X e JD2 X b .

Тогда передаточная функция записывается в следующей форме:

T (D, N, J ) J 3 ND6 J 3ND6 J 4 N 2D8 J 5 N 2D8 J 5 N 3D10 2J 6 N 3D10

1 JND2 (1 J )

J 7 N 3D10

Первое слагаемое говорит о том, что путь с расстоянием d 6 имеет длину 3 и , что один из 3 –х бит – «1». Второе и третье слагаемые указывают на то, что из двух слагаемых с d 8 одно длиной 4, а второе длиной 5. Два из 4 –х и два из 5 –ти бит в пути длиной 4 и 5 являются «1».

Множитель J особенно важен, если передается последовательность конечной длины, например, m бит. Тогда сверточный код повторяется после m узлов или m ветвей и передаточная функция получается при усечении по слагаемому J m

Оптимальное декодирование сверточных кодов. Алгоритм Витерби.

Оптимальное декодирование сверточных кодов включает в себя поиск по решетке наиболее правдоподобной последовательности. Рассмотрим опять пример 1. Если за метрику взять расстояние Хемминга (поиск жестких решений) между принятой кодовой последовательностью Y и путем, то выбирается тот путь, у которого dmin . Это правило максимизирует вероятность правильного решения или минимизирует вероятность ошибки в информационной последовательности.

Пусть Y 101000100 . Рассмотрим все пути у сливающегося узла a, b, c, d после трех переходов. Тогда по решетке (уровень 3):

Y: 1 0 1 0 0 0 1 0 0

a: 0 0 0 0 0 0 0 0 0 d 3

1 1 1 0 0 1 0 1 1 d 5 b: 0 0 0 1 1 1 0 0 1 d 7

d: 0 0 0 1 1 1 1 1 0 d 6

1 1 1 1 1 0 1 0 1 d 4

Далее для каждого узла оставляем путь с d dmin : a: 0 0 0 0 0 0 0 0 0 d 3

b: 1 1 1 1 1 0 0 1 0 d 5

c: 1 1 1 0 0 1 1 0 0 d 2 d: 1 1 1 1 1 0 1 0 1 d 4 .

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