<< Предыдущая

стр. 42
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

0 1 000
1 2 101 010
3
2 0 1 011 100
2 001
3 3 ПО



5. Так как кодирование должно заканчиваться в нулевом состоянии
кодера, добавим к информационной последовательности два нуля и
получим
{v[n2}} = {1,1,1,0,1,0,1,1,0,0,1,1,0,1,0,1,0,1,0,1,1}. (4.37)

Графическое отображение состояний и переходов между ними
дает возможность показать весь процесс кодирования непрерывно во
времени в виде сетевой диаграммы (иногда ее называют решетчатой
или треллисной диаграммой).
Пример: Сетевая диаграмма кодирования сверточного (3,1,2)-
кода.
На сетевой диаграмме рис. 4.7 для каждого временного шага по-
казаны все возможные состояния кодера. На переходах между ними
Г234 Глава 4- Свершенные коды

(ребрах), в качестве веса, представлены соответствующие информа-
ционные и кодовые биты. Так как в рассматриваемом примере к = 1,
из каждого состояния выходят и в каждое состояние ведут в точно-
1
сти 2 = 2 ребра.
Замечание. Расположение состояний по вертикали специально
подобрано таким образом, чтобы все ребра, содержащие нулевой
информационный бит, вели вниз.




Такты
л+1


Рис. 4.7. Граф потока сигналов сверточного (3,1,2)-кода.




\fy\ vLA4 \fLXv


6 Takle 7



Рис. 4.8. Кодирование информационной последовательности.

На рис 4.8 показано кодирование информационной последова-
4-5. Структура сверточных кодов

тельности (4.36). Это кодирование начинается из нулевого состояния
So. Так как первый информационный бит равен щЩ = 1, мы попа-
даем в состояние Si. Этому переходу соответствует первая тройка
кодовых символов «111». Второй информационный бит щ[1] = 1 при-
водит нас в состояние 5з с выработкой следующей кодовой тройки
«010» и т.д. В конце кодирования мы попадаем в нулевое состояние SQ.


4.5. Структура сверточных кодов
В предыдущем разделе было проведено описание сверточных кодов
на основе диаграммы состояний и сетевой диаграммы. Ясно, что
обе диаграммы содержат полную информацию об исследуемом ко-
де. Описание сверточных кодов с помощью диаграмм состояний и
переходов между ними открывает возможность более глубокого ис-
следования их структуры и свойств.
До сих нор вопросы декодирования не обсуждались. Декодирова-
нию сверточных кодов будет посвящен следующий раздел этой кни-
ги. Однако, на основании сетевой диаграммы рис. 4.8, основные тре-
бования к хорошим кодам можно наметить уже сейчас.
Каждой кодовой последовательности соответствует свой путь на
сетевой диаграмме, поэтому, ясно, что чем больше различий между
путями, тем легче распознать истинное кодовое слово, тем меньше
вероятность ошибки декодирования.
Как следует измерять различие между путями?
Когда мы обсуждали свойства двоичных линейных блоковых ко-
дов (главы 2, 3), основным критерием "различия было число несов-
падающих символов, т.е. расстояние Хэмминга. Для блоковых ко-
дов минимальное расстояние Хэмминга dmin играло особую роль, но
также не менее важным было распределение весов слов линейного
блокового кода. Эти же рассуждения можно применить и к сверточ-
ным кодам. В этом случае нулевым словом будем считать кодовый
вектор, состоящий из одних нулей.
Если рассматривать сверточные коды с конечной длиной инфор-
мационных векторов, то можно считать их линейными блоковыми
кодами и к ним применимы все рассуждения, проведенные в главах
2иЗ.
Расстояния между кодовыми словами или расстояния между пу-
тями на сетевой диаграмме будем искать в метрике Хэмминга. В
качестве базы используем нулевую последовательность, т.е. последо-
вательность нулевых состояний. Без ограничения обпшости считаем,
Глава 4- Свврточные коды


что кодирование начинается и заканчивается в нулевом состоянии,
поэтому, ненулевой кодовой последовательности на сетевой диаграм-
ме соответствует путь, ответвляющийся от нулевого состояния, а за-
тем сливающийся с ним.
Рассмотрим ненулевую последовательность, изображенную на
рис. 4.8: Ей соответствует путь, состоящий из двух участков, ответв-
ляющихся, а затем сливающихся с нулевым состоянием. В дальней-
шем такие участки будем называть базовыми путями. Исследование
структуры кода сводится к анализу базовых путей.
Методику такого анализа покажем на конкретном примере.
Пример: Модифицированная диаграмма состояний сверточного
(3,1,2)-кода.




Конец




Р и с . 4.9. Модифицированная диаграмма состояний свер-
точного (3,1,2)-кода.

Возьмем диаграмму состояний, изображенную на рис. 4.6. Будем
исходить из того факта, что кодирование начинается и заканчива-
ется в нулевом состоянии So, поэтому, модифицируем эту диаграм-
му таким образом, чтобы состояние SQ было только или начальным
или конечным (рис. 4.9). Для дальнейшего анализа промаркируем
приросты весов Хэмминга информационной или кодовой последова-
тельностей, а также прирост длины проходимого пути. С этой целью
введем следующие неременные: для каждой информационной «1»
переменную /, для возрастания веса Хэмминга кодовой последова-
тельности на I единиц переменную D1, и, наконец, для каждой
смены состояний - переменную J. Промаркированные таким обра-
зом переходы нанесены на диаграмму состояний рис. 4.9. В этом
случае каждому пути соответствует произведение маркеров всех пе-
реходов, из которых этот путь состоит. Например, информационной
4.5. Структура сверточных кодов

последовательности
{«[п]} = {1,1,0,0} (4.38)
с последовательностью состояний
r
{a[n]} = {S0,Si,S 2,Sb} (4-39)

в качестве весовой функции будет приписано выражение
3 2 2 73
(4.40)
ID J • D J • D J = ID J .

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

1. / с показателем, равным весу Хэмминга информационной по-
следовательности;

2. D с показателем, равным весу Хэмминга кодовой последова-
тельности;

3. J с показателем, равным числу переходов, осуществленных на
этом пути.

Пример: Базовые пути и веса сверточного (3,1,2)-кода.
В таблице 4.5 представлены четыре кратчайших базовых пути и
их весовые функции сверточного (3,1,2)-кода. Самый короткий из
них имеет вес Хэмминга, равный 7, то есть соответствующая ему ко-
довая последовательность имеет единицы в семи разрядах. Из таб-
лицы 4.5 может создасться впечатление, что с ростом длины путей
их вес Хэмминга также возрастает. Проверим, так ли это для свер-
точного (3,1,2)-кода.
Для ответа на этот вопрос рассмотрим модифицированную диа-
грамму состояний рис. 4.9 и табл. 4.5. Каждое последующее удли-
нение пути требует прохождения некоторой «петли» на диаграмме
состояний. Так как любая петля содержит минимум один переход ве-
са $ илн больше, то вес Хэмминга будут расти с увеличением длины
путей, поэтому, не существует путей, отличных от нулевой последо-
вательности, с весом Хэмминга, меньшим 7.
Анализ кода с помощью модифицированных диаграмм состояний
базируется на математической теории графов, топологии и теории
систем.
238 Глава 4' Сверточные коды
V


Таблица 4.5. Базовые пути и их весовые функции(.ЛГ нес
Хэмминга информационной последовательно-
сти; О вес Хэмминга кодовой последователь-
ности; К - длина пути

Весовые функции N С К
Состояния S[n]
s2,So 1
2 2
3 73
7 3
ID J •D JD J = ID J
So, Si

ID3J •IDJ- D2J • D2J = I2Da J4 2 8 4
--
S 2 ,S 0
So, Si S3,

s3, s 3 , s 2 ,S ID3J •IDJ •IDJ- D2J • D2J = I3D9J5 3 9 5
--
So, Si 0

So, s, s2, Si, S2 , So ID3J D2J- IDJ-1 D2J • D2J =I2Dl0J5 2 10 5
И. 'г- Д




Каждому состоянию рис. 4.9 поставим в соответствие переменные
Ze - начальному, Z\,Z2,Z3 соответственно 51,5г,5з и Za конечному
состояниям.
Определим производящую функцию как

(4.41)

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

Zx = ID3J (4.42)
• Ze + IDJ • Z2
(4.43)
Z2 = D2J • Zx + D2 J • Z3
Zz = ID J • Zx + IDJ • Z3 (4.44)
Za = D2J • Z2. (4.45)

Для решения этой системы уравнений требуется несколько ша-
гов. Из (4.44) следует

IDJ
(4.46)

Используя (4.43), имеем




1-JDJ
(4.48)
Zl
=
\ 239/
J^.5. Структура сверточных кодов

Подставляя в (4.42), получаем

1-IDJ
Z2 = ID3J • Ze + IDJ • Z2, (4.49)
2
DJ
что приводит к
" / г>r5'Jт2
" ID
2



> = 1-IDJ-IB>J- z .
Z

re
Теперь уже вес готово для того, чтобы непосредственно связать Za
и Ze

ID5 / 2 1

<< Предыдущая

стр. 42
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>