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

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

ОГЛАВЛЕНИЕ

Следующая >>



Самым простым способом проверки правильности (4.30) является ко-
дирование информационного вектора (100- --0). В этом случае, ре-
зультатом должны быть чередующиеся друг с другом импульсные
отклики кодера. Таким образом

/ 1 1 0 1 1 1 1 1 0 0 0 0 •• \

001101111100 • •
( 1 0 0 •••) = (4.31)
000011011111 • •
• /



= ( 1 1 0 1 1 1 1 1 О-• • ) ,

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


4.4. Граф состояний
Регистры кодеров содержат ограниченное число двоичных разрядов,
следовательно, число состояний, в котором может находиться кодер,
всегда конечно. Именно поэтому процесс кодирования можно опи-
сать как последовательность смены состояний кодера. Такой подход
является ключевым и ведет к более глубокому пониманию свойств
сверточных кодов. Более того, он способствует разработке эффек-
тивных алгоритмов кодирования и декодирования. Мы разовьем эту
идею на нескольких примерах.

Пример: Описание состояний сверточного (2,1,3)-кода.
Скопируем схему кодера рис. 4.2 с единственной разницей: вместо
разрядов регистра сдвига поставим переменные Xi,X2 и Х$. Такая
модифицированная схема представлена на рис. 4.3. '
229J
4-4- Граф состояний




хъ X




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

Так как Х\, Х2, Хз - двоичные переменные, то кодер, изображен-
ный на рис. 4.3, может находиться в одном из 2 3 = 8 состояний. Эти
состояния пронумерованы в лексикографическом порядке и приве-
дены в таблице 4.1. Нумерация состояний может быть произволь-
ной, однако, лексикографический порядок наиболее удобен для про-
граммной реализации.
Таблица 4.1. Таблица состояний.

Состояние Sj
Состояние регистра
г = хз + 2x2 + 2 2 ц
XI
Хз Х2

0
0 0 0
1
1 0 0
2
0 1 0
1 1 3
0
4
1
0 0
1 5
1 0
1 6
0 1
1 1 1 7



Смена состояний регистра кодера происходит следующим обра-
зом: переменные Xj и Хг заменяются на Хг и Хз соответственно, а в
разряд Хз загружается новый информационный бит, поэтому, каж-
дое состояние может переходить только в два последующих в зави-
симости от того, «О» или «1» были поданы на вход регистра сдвига.
Все возможные смены состояний, их зависимость от загружаемого
бита, а также кодовые символы для этих переходов показаны на рис.
4.4. Процесс кодирования начинается с So, T-e- состояния, в котором
Хг = Х 2 = Х 3 = 0.
1. Если первый информационный бит равен «0», кодер остается
Глава 4- Сверточные коды

в состоянии So- На выход выдаются кодовые символы «00».
Такой исход на рис. 4.4 обозначен через «0/00».
2. Если первый информационный бит равен «1», кодер переходит
в состояние $1 (см табл. 4.1). Выход в этом случае равен «11».
Этот переход обозначен «1/11». Продолжая этот процесс впра-
во, можно построить всю диаграмму состояний (рис. 4.4).
Диаграмма рис. 4.4 содержит всю информацию о сверточном ко-
де. Кодирование информационной последовательности эквивалентно
движению по некоторому неразрывному пути по диаграмме состо-
яний. При программной реализации, например, кодирование может
быть наиболее эффективно осуществлено исключительно с помощью
заранее записанных в памяти таблиц переходов между состояниями.
Рассмотрим такое альтернативное кодирование на.нримере.

11
/0
о/оо




/v"v"
Состояние
Ребро: Переход в состояние на /-ом шаге


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

Пример: Кодирование сверточного (2,1,3)-кода с помощью таб-
лиц переходов.
Выпишем для каждого состояния два его последующих, в зави-
симости от значения очередного бита («0» или «1»). Для этих путей
выпишем также соответствующие пары кодовых бит. Полученные
результаты сведены в таблицу 4.2.
Рассмотрим кодирование информационной последовательности
и[п] = 1,0,1,1,1. Процесс начнем из состояния So и в нем же и за-
кончим, добавив к и[п) «хвост» из трех нулей. В результате получим
последовательность состояний
{S[n]} = {50,51,52,55,53,57,^6,64,-So} (4-32)
и кодовое слово
{v[n}} = {1,1,0,1,0,0,0,1,0,1,0,1,0,0,1,1}. "(4.33)
231
4-4- Граф состояний

Таблица 4.2. Таблица переходов для сверточного (2,1,3)-
кода.

Новое состояние S[n + 1] Кодовые биты
Состояние
1 1
0
0
11
1
0 00
0
10
1 2 3 01
11
4 00
2 5
6 7 01
10
3
1 11
4 0 00
2 3 01
5 10
11
4 00
6 5
10
7 6 7 01




Таблица переходов в некоторых случаях может помочь оценить ка-
чество выбранного сверточного кода. Сравним, например, построч-
но пары кодовых бит в последних двух столбцах таблицы 4.2. Мы
увидим, что различие между этими парами (расстояние Хэмминга)
в каждой строчке максимально и равно 2. Это значит, что на на-
чальных отрезках любых двух альтернативных путей («0» и «1»)
всегда достигается максимальное расстояние Хэмминга и, поэтому,
мы можем сказать, что, на первый взгляд, выбранный код является
хорошим. Конечно же, для более точного анализа необходимо рас-
сматривать длинные отрезки альтернативных путей. Здесь возника-
ет понятие свободного кодового расстояния djree, о чем пойдет речь
ниже.
Из диаграммы состояний рис. 4.4 становится очевидным, что
сложность кодирования (а также и декодирования) возрастает с ро-
стом числа состояний. Число состояний, в свою очередь, однозначно
определяется количеством двоичных разрядов памяти кодера т.
Для сверточного (п, к, т)-кода полная память кодера определя-
ется как
(4.34)
М=
г=1

Заметим, что именно М последних информационных разрядов ока-
зывают влияние на процесс кодирования. Этим разрядам соответ-
ствуют в точности 2м различных состояний схемы кодера.
232 Глава 4- Сверточные коды


Пример: Сверточный (ЗД,2)-код.
Заданы порождающие многочлены
(4.35)
2 2
<h(X) = 1 + X,g2(X) = 1+ X + X
= 1 + X ,g3(X)

и информационная последовательность

(4.36)
{и[п}} = {1,1,0,0,1}.

Найдите:

1. Схему кодера.

2. Состояния кодера.

3. Диаграмму состояний.

4. Таблицу переходов между состояниями.
5. Кодовую последовательность для и[п], если кодирование начи-
нается и заканчивается в нулевом состоянии.
Решение.
1.


*2 X 1*1




Рис. 4.5. Схема кодера сверточного (3,1,2)-кода.

2.
Таблица 4.3. Состояния кодера.

Состояние регистра CoCTOHHHeSi
i = х 2 + 2xi
XI
12

0 0 0
1 1
0
1 2
0
1 1 3
233,
4-4- Граф состояний

3.




Г
Рис. 4.6. Диаграмма состояний сверточного (3,1,2)-кода.

4.
Таблица 4.4. Таблица переходов между состояниями свер-
точного (3,1,2)-кода.

Состояние Новое состояние S[n + 1] Кодовые биты
0 1 1
0
0 111

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

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

ОГЛАВЛЕНИЕ

Следующая >>