Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
6.2.2. Кодирование информации сверточными кодами
Рассмотрим кодирование информации на примере систематического ССК с
R=l/2 и корректирующего двойные ошибки. Для ССК, как и для блочных
циклических кодов, структура кодера полностью определяется порождающим
полиномом g(x) и реализуется с помощью линейных автоматов без обратной
связи с вынесенными или встроенными сумматорами по модулю два.
Для ССК корректирующего двойные ошибки достаточно использовать один
порождающий полином вида g(x)= l+x
2
+x
5
+x
6
, у которого имеется J=2t
ортогональных проверок и соответственно столько же ненулевых членов. Данный
ССК исправляет двукратные ошибки на длине кодового ограничения равного n
A
=
(m+1)*n
0
== (6+1)*2 =14 символам. Отметим, что для высокоскоростных ССК
(R≥2/3) в кодере целесообразно использовать линейные автоматы со встроенными
сумматорами по модулю два; в теории СК его называют кодером Месси.
На рис 6.1 и рис 6.2 приведены кодеры со встроенными и вынесенными
сумматорами по модулю два для данного кода.
Рис 6.1. Кодер ССК со встроенными сумматорами по модулю два
Рис 6.2. Кодер ССК с вынесенными сумматорами по модулю два
Для дальнейшего анализа алгоритмов кодирования и декодирования ССК ис-
пользуем обобщенную структурную схему кодера ССК, представленную на
рис 6.3.
P(x)
I(x)
I(x)
T
6
M2
T
5
T
4
T
3
M2
T
2
T
1
M2
P(x)
I(x)
I(x)
T
2
T
4
T
5
T
1
T
3
T
6
M2
M2
M2
Рис 6.3. Обобщенная структурная схема кодера ССК
В связи с тем, что кодер ССК формирует два синхронных потока (n
0
=2)
кодовых символов, то для получения единого потока можно использовать
синхронный мультиплексор (MX). Управление работой блока кодера и
мультиплексора осуществляется блоком фазовой автоподстройки
частоты(ФАПЧ).
Кодирование информации ССК осуществляется следующим образом.
Входная информационная последовательность I(х) одновременно поступает на
вход мультиплексора и блока кодирования, на выходе которого формируются
проверочные символы Р(х), которые поступают на второй информационный вход
мультиплексора.
Выходная кодовая последовательность T
(i)
(x)=t
0
(i)
(х
0
)+t
1
(i)
(х
1
)+t
2
(i)
(x
2
)+ …,
i=j+l, j= 1,2, ... , k
0
и входная информационная последовательность I
(j)
(х)= =i
0
(j)
(x
0
)+i
1
(j)
(x
1
)+i
2
(j)
(х
2
)+... , j=l,2,3,...,k
0
связаны выражением:
Для кодера, представленного на рис.6.3, каждый входной информационный
символ оказывает влияние на формирование кодовой последовательности в
течение (m+1)==(6+1)=7 тактов и, следовательно, с выхода кодера будет считано
n
A
=(m+1)*n
0
=7*2=14 кодовых символа. Откуда видно, что данный процесс
кодирования СК осуществляется с памятью в отличие от циклических кодов.
T(x)
f
T
P(x)
I(x)
T
6
MX
Y
I
T
1
T
2
T
5
T
3
T
4
M2
M2
M2
ФАПЧ
кодера
(6.8)
∑
=
⋅
=
0
k
1
j
(j)
(i)
g(x) .
(x)
I
(x)
T
С выхода кодера ССК символы кодовой последовательности Т(х) поступают
на вход модулятора, где преобразуются в аналоговый сигнал и далее передаются
по каналу связи. Данный способ кодирования получил название прямого
(непосредственного) способа кодирования информации. Этот способ требует
небольших затрат на кодирование информации, что связано с использованием
минимального объема оборудования.
При независимом кодировании нечетных и четных информационных
символов СК информация от источника поступает на вход коммутатора
распределения информации, где распределяется на два потока: I
1
(x)- поток
нечетных информационных символов, I
2
(х)- поток четных информационных
символов. Двоичные символы данных потоков кодируются независимо друг от
друга СК и поступают на соответствующие входы модулятора и далее передаются
в канал связи. К достоинствам данного способа кодирования следует отнести:
возможность выбора СК с меньшей избыточностью и, следовательно, с меньшей
сложностью реализации кодексе. К недостаткам относится двукратное
увеличение объема оборудования и сложность реализации устройств ветвевой
синхронизации распределителей информации кодеков.
При кодировании информации с перемежением символов обеспечивается
коррекция группирующихся ошибок кодами корректирующие независимые
ошибки. К недостаткам данного способа кодирования относятся: увеличение
задержки информации при декодировании и сложность реализации устройств
ветвевой синхронизации распределителей информации кодека СК.
Используется также способ каскадного кодирования информации СК
(рис.6. 4).
Рис. 6.4. Способ каскадного кодирования информации СК
К каналу
св
я
зи
T
2
(x) T
1
(x) I(x)
Внешний
кодер ка-
нала
Внутренний
канал кодера
Модулятор
В этом случае информационные символы I(х) первоначально кодируются
внешним кодером, используемым для коррекции пакетных ошибок определенной
кратности, а затем кодовые символы последовательности T
1
(x) кодируются
внутренним кодером рассчитанным для коррекции независимых ошибок. С
выхода внутреннего кодера кодовые символы последовательности Т
2
(х)
поступают на вход модулятора и далее в канал. С целью повышения
корректирующей способности к группирующимся ошибкам возможно
дополнительное перемежение кодовых символов либо после внешнего кодера,
либо после внутреннего кодера.
Достоинством данного способа кодирования является возможность
одновременной коррекции как пакетных, так и независимых ошибок, защита
информации от несанкционированного доступа при использовании во внутреннем
кодере несистематических СК. Недостатком системы является высокая
избыточность каскадного кода и большая задержка информации при
декодировании.
6.3. Способы задания и кодирование несистематических древовидных и
решетчатых сверточных кодов
Как отмечалось выше, информация, подлежащая кодированию СК, поступает
непрерывно на вход кодера по одному символу либо блоками по k
0
символов, а с
выхода кодера выдается кодовый блок из n
0
кодовых символов: n
0
=k
0
+l, k
0
≥l. При
этом реализуется алгоритм кодирования с памятью. Сформированные таким
образом коды получили название древовидных. К ним относятся и СК, если они
обладают дополнительными свойствами линейности и постоянства во
времени[1…3].
Древовидные СК
Древовидным (n
0
, k
0
, d
св
) − кодом называется такой СК, который образует
бесконечно длинные кодовые последовательности, при бесконечно большом во
времени процессе кодирования.
Важнейшими характеристиками древовидного кода являются:
k' - длина (количество ячеек памяти) регистра сдвига кодера. В общем случае
длина регистра сдвига древовидных кодов может быть бесконечной, но на
практике с целью минимизации сложности реализации кодеков и задержки
информации при декодировании значение k' ограничивается.
Решетчатые СК
Решетчатым (n
0
, k
0
, d
св
) − кодом называют древовидный код с конечной
длиной кодового ограничения и с конечной длиной кодового блока.
Древовидные и решетчатые коды чаще всего описывают соответственно с
помощью "кодового дерева" и "кодовой решетки".
Сущность кодирования, кодового дерева и кодовой решетки рассмотрим на
примере СК с R = 1/2 , k=2, g
1
(x)=l+x+x
2
и g
2
(x)=l+x
2
. Структурная схема кодера
данного СК представлена на рис. 6.5.
Рис. 6.5. Структурная схема кодера несистематического СК
Кодирование информации СК осуществляется путем умножения входной
информации на порождающие полиномы и суммирования по модулю два
информационных символов, стоящих на следующих позициях для первого
полинома – i
0
, i
1
и i
2
; для второго полинома — i
0
и i
2
. В результате кодирования
каждому входному информационному символу соответствуют два кодовых
символа кодовых последовательностей T
1
(x) и Т
2
(x), при этом в кодовых
последовательностях T
1
(x) и Т
2
(x) отсутствуют в "явном виде" входные
информационные символы последовательности I(х).
Для рассматриваемого кодера СК кодовое дерево имеет вид (рис 6.6).
T
1
(x)
T
2
(x)
I(x)
M2
M2
M2
T
2
T
1
•
•
•
Очевидно, что данный кодер СК можно рассматривать как конечный автомат,
состояния которого описываются с помощью диаграмм вида кодового дерева и
кодовой решетки.
Точки, помеченные на кодовом дереве, носят название вершин или узлов
ветвления, а линии, соединяющие вершины (узлы) кодового дерева, носят
название кодового ребра или кодовой ветви.
Каждое ребро этого дерева соответствует некоторому входному
информационному символу. При этом входному символу "0" соответствует
верхнее ребро, а входному символу "1" - нижнее ребро; принятое соответствие
символов и ребер является условным. Таким образом, с помощью кодового дерева
можно отобразить как входные, так и выходные последовательности двоичных
символов: входные последовательности двоичных символов отображаются с
помощью кодового ребра (ветви) диаграммы, а выходные последовательности – с
помощью двоичных символов вдоль ребер дерева. Например, входной
последовательности I(х)=01101… соответствует кодовый путь на дереве, идущий
вверх на первом уровне ветвления, вниз - на втором и третьем уровнях ветвления
и снова вверх на четвертом уровне ветвления. При этом СК формирует на выходе
двоичные символы, указанные на горизонтальных ребрах: 00, 11, 10, 01. Таким
образом, на кодовом дереве (диаграмме) можно проследить все 2
5
=32 выходные
кодовые последовательности, состоящие из пяти двоичных символов.
Из структуры кодового дерева видно, что после первых трех ребер структура
кодового дерева повторяется; за третьим ребром кодовые символы на ребрах,
исходящих из двух вершин, намеченных буквой "а", совпадают. То же самое
происходит и с любой другой парой вершин, помеченных одинаковыми буквами.
Такое свойство кодового дерева определяется структурой кодера СК, а именно,
когда третий входной символ вводится в кодер, то первый входной символ
покидает кодер и поэтому в дальнейшем уже не оказывает никакого влияния на
формирование выходных кодовых символов. Следовательно, информационным
последовательностям 100 х у и 000 х у (х, у ∈0,1) будут соответствовать кодовые
последовательности, полностью совпадающие на всех ребрах после третьего.
Следовательно, два узла, помеченные на кодовом дереве буквой "а", могут быть
объединены в один узел. Данное свойство кодового дерева позволяет установить:
во первых, что при непрерывном поступлении двоичных символов
информационной последовательности число возможных путей кодового дерева
растет экспоненциально, и, во вторых, что структура кодового дерева является
периодической, что позволяет ограничить экспоненциальный рост объема
вычислений.
На рис. 6.6 каждая вершина помечена числом от "0" до "3" в соответствии с
содержимым двух левых ячеек памяти RG кодера СК в данном узле кодового
дерева; младший разряд записывается левее. Данное число называется состоянием
кодера СК. Ребра, выходящие из любых двух узлов, имеющих одинаковые
состояния, полностью тождественны.
Так, например, на рис. 6.6 верхнее и нижнее поддеревья на уровне 3 (запись
пунктиром на кодовом дереве) рассматриваемого дерева являются одинаковыми
и, следовательно, их можно объединить. На уровне четыре имеется множества, по
четыре узла в каждом, которые также можно объединить.
Возможность объединять пути кодового дерева, которые приводят к одному
и тому же состоянию кодера СК, позволяют преобразовать диаграмму кодового
дерева в диаграмму, которая называется кодовой решеткой (решетчатой
диаграммой, решеткой). Решетка - это древовидная структура со слившимися
узлами или графом узлы, которого находятся в прямоугольной координатной
сетке полубесконечной справа и с конечным числом узлов в каждом столбце.
Рассмотренное кодовое дерево преобразуется в кодовую решетку
вида(рис.6.7).
На рис. 6.7 условно принято, что входному символу "0" соответствует
сплошная линия, a '"1" - пунктирная.
К основным свойствам кодовой решетки относятся:
1. Кодовая решетка СК всегда сходится в вершину 'а' после подачи на вход
кодера N = m⋅k информационных символов;
Рис. 6.6. Кодовое дерево СК с R=l/2 и k'=2
2. Количество состояний кодера СК, т.е. вершин в одном столбце не зависит
от числа входных информационных символов, а зависит только от количества
ячеек памяти RG кодера, т.е. от длины кодового ограничения k' u равно 2
k'
. Это
определяется также тем, что избыточные части кодового дерева объединяются.
Однако объединение кодовых путей может привести при декодирования к ошиб-
кам из-за того, что выбранный неверный путь будет отождествляться с верным
путем u равно 2
k'
. Это определяется также тем, что избыточные части кодового
дерева объединяются. Однако объединение кодовых путей может привести при
декодирования к ошибкам из-за того, что выбранный неверный путь будет ото-
ждествляться с верным путем;
Рис. 6.7. Кодовая решетка кодера СК с R=l/2 и k=2
3. Так как кодовая решетка однородна, то постоянный во времени кодер СК
может быть преобразован в постоянный во времени конечный автомат, который
можно описать диаграммой состояний. Например, кодер СК представленный на
рис. 6.5 может быть преобразован в конечный автомат (рис. 6.8):
Рис. 6.8. Возможные состояния кодера СК с R=l/2 и k'=2
Состояния на рис. 6.8 обозначаются аналогично обозначениям узлов на
кодовой решетке (данные состояния указаны в квадратах). Диаграмма состояний
кодера представляет направленный граф, который содержит все состояния и
описывает возможные переходы (на рис. 6.8 указаны стрелками) из одного
состояния в другое, а также выходные кодовые символы, соответствующие
входным информационным символам.
На рис 6.8 текущий входной символ представляется ребром, указывающим
на переход автомата (кодера) из одной вершины (узла) в другую вершину(узел), а
два предыдущих входных символа (в это же время) определяют вершину (узел) , в
которой автомат (кодер) находится.
11 11
01 01
00
10
00
10
a= 00
c= 10
b= 01
d= 11
Так, например, если кодер СК находится в состоянии 01011, то эта
совокупность символов на диаграмме состояний представляется переходом из
состояния Ь=01 в состояние d=11 , а на соответствующем ребре диаграммы
указываются выходные символы 01 кодера СК.
Решетчатая диаграмма строится следующим образом[1…3]:
1. В начальный момент времени кодер СК находится в состоянии "00". При
поступлении на вход кодера нулевого символа кодер остается в прежнем
состоянии (это состояние на рис 6.8 обозначено петлей "00") и на выход кодера
поступит блок из двух нулей, один из последовательности T
1
(x), а другой из
последовательности Т
2
(х);
2. При поступлении на вход кодера единичного символа "1" , кодер перейдет
из состояния "00" в состояние "01" пунктирная линия на рис. 6.7 и рис. 6.8, а на
выход кодера поступит блок из символов 11;
3. При поступлении "1" или "0" кодер переходит соответственно в состояние
"11" или "10", а с выхода поступят блоки из символов 01 или 10;
4. Если кодер СК находится в состоянии "11" и на его вход поступает символ
"1" , то состояние кодера не изменится (на рис 6.8 это обозначено второй петлей)
, а с выхода кодера поступит блок из символов 10 , в противном случае (когда на
входе кодера "0") кодер СК перейдет в состояние "10" , а с выхода кодера
поступит блок из символов 0 1;
5. Как следует из рис. 6.8 кодер СК из состояния "10" может перейти либо в
состояние "00" , когда на его вход поступит символ "0" (на выход кодера поступит
блок 11), либо перейти в состояние "01", если на входе кодера символ "1" (на
выход кодера поступит блок 00).
Очевидно, что переходы состояний кодера СК повторяются при поступлении
на вход нулевых и единичных символов. Например, как следует из рис. 6.6 и 6.7
входной последовательности 01011 соответствует выходная последовательность
00110101111.
Анализ кодовой решетки и соответствующего ей автомата позволяет сделать