Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
6. СВЕРТОЧНЫЕ КОДЫ
6.1. Определение, параметры и классификация сверточных кодов
Сверточные коды (СК) имеют большой научный и практический интерес для
современных систем и сетей телекоммуникаций. Это определяется многими их
достоинствами, а именно: высокой скоростью обработки информации (десятки и
сотни Мбит/с), высокой корректирующей способностью как случайных, так па-
кетных ошибок, реализацией эффективных кодеков и систем ветвевой синхрони-
зации распределителей информации, эффективного использования в каналах свя-
зи с фазовой неопределенностью и др.
В общем виде кодирование информации СК может быть представлено сле-
дующим образом [1..3,15]
где I(x) - последовательность передаваемых информационных символов;
х - оператор задержки: (оператор задержки иногда обозначают через ла-
тинскую букву D);
g(x)— порождающий или образующий полином (многочлен);
k
0
- блок информационных символов, одновременно поступающих на
вход кодирующего устройства (k
0
>l).
Способ формирования кодовых символов, выполняемых согласно (6.1),
соответствует форме записи свертки двух функций, что и послужило названию
данных кодов. Сверточный код — это рекуррентный код с периодической
полубесконечной структурой символов кодовой последовательности. Обобщенная
структурная схема кодера СК представлена на рис.6.1
Рис. 6.1. Обобщенная структура кодера СК
() () ()
∑
=
+==⋅=
0
k
1j
0
(j)(j)(i)
1
ji,k1,2j,xgxIxT K
(6.1)
T
(i)
(x) I(x)
n
0
1
. . .
. . .
1
k
0
Кодер СК
g
(j)
(x), j=1,2,…,k
0
Входные информационные символы I(х) делятся на k
0
символов, которые
одновременно с каждым тактом поступают на входы кодера СК, в котором
согласно (6.1) формируются кодовые символы n
0
. Таким образом, кодовая
последовательность Т
(i)
(х) представляет собой полубесконечную
последовательность блоков n
0
.
К основным характеристикам СК относятся:
− R=k
0
/n
0
=1/2; 2/3; 3/4 и т.д. или R=k
0
/n
0
=1/2; 1/3; 1/4 и т. д. − скорость передачи
кода, которая для СК записывается в виде дроби;
− J≥2 - количество ортогональных проверочных уравнений;
− d
0
=J+1 - минимальное кодовое расстояние;
− d
св
- свободное кодовое расстояние;
− t
исп
≤J/2 - кратность или количество исправляемых ошибок;
− t
обн
≤d
0
-1=J - кратность обнаруживаемых ошибок;
− n
A
=(m+1)*n
0
- длина кодового ограничения или длина кодовой
последовательности, соответствующая кодированию информационных блоков
из k
0
символов в течение (m+1) такта;
− k
A
=R*n
A
- количество информационных символов, приходящих на n
A
кодовых
символов.
Сверточные коды, как и блоковые линейные коды, бывают:
− двоичные и недвоичные;
− алгебраические и неалгебраические;
− линейные и нелинейные;
− систематические и несистематические;
− ортогональные и неортогональные и т.д.
Алгоритм формирования кодовых символов СК таков, что любому входному
информационному блоку из k
0
двоичных символов и "m" (m- максимальная
степень порождающего полинома g(x)) предшествующих информационных
символов, хранящихся в регистре сдвига (RG) кодера, соответствует выходной
кодовый блок из n
0
двоичных символов. В связи с тем, что в процессе
формирования n
0
кодовых символов участвуют "m" предшествующих
информационных символов (введенных m тактами ранее), то такой алгоритм
кодирования называют кодированием с памятью.
У несистематических СК в кодовых блоках из n
0
двоичных символов нет в
"явном виде" (невозможно выделить) информационных символов или блоков из
k
0
двоичных символов. Кодирование входной информации осуществляется с
памятью и процесс кодирования может быть бесконечно продолжительным.
В зависимости от способа формирования проверочных уравнений СК бывают
ортогональными, самоортогональными и ортогонализируемыми.
Ортогональными СК (ОСК) называют такие коды, у которых система из J
(J≤2) проверочных уравнений ортогональна относительно декодируемых k
0
информационных символов и неортогональна относительно информационных
символов, входящих в данные проверочные уравнения.
Самоортогональные СК (ССК) - коды, у которых декодируемый
информационный символ входит одновременно во все проверочные уравнения, а
все остальные символы, участвующие в декодировании в данный момент
времени, входят не более, чем в одно проверочное уравнение, т.е. СК формирует,
так называемую, систему разделенных проверок.
Ортогонализируемыми СК называются такие коды, у которых при
декодировании информационного или k
0
символов требуется выполнить
дополнительные линейные преобразования над проверочными символами для
получения дополнительных, так называемых, составных проверок.
6.2. Способы задания систематических сверточных кодов и их
кодирование
6.2.1. Задание систематических сверточных кодов
Систематические СК задаются [1…3]:
− с помощью порождающей матрицы, G
∞
(x);
− с помощью проверочной матрицы, Н
∞
(х);
− с помощью разностных треугольников;
− с использованием совершенных разностных множеств.
Порождающая матрица систематического СК имеет более сложное
построение, чем группового кода. Это определяется из-за полубесконечной
структуры порождающей матрицы СК, имеющей вид:
где "0" - области матрицы, состоящие полностью из нулевых двоичных
символов,
m - количество порождающих матриц вида
где q
i,j
– коэффициенты равны либо 1, либо 0.
(6.2)
,
G
∞
(x)=
.
.
.
G..GG...00
..
..
..
0..G...GG0
0...G...GG
m10
m10
m10
n
0
столбцов
,
k
0
строк
(6.3)
G
ξ
(x)=
ξ,n
k
ξ1,
k
ξ,n
1
ξ1,
1
0
00
0
q...q
...
q...q
Систематический ССК задаются следующей порождающей матрицей G
∞
(x):
Проверочная матрица Н
∞
(х) СК, как и порождающая матрица, является
полубесконечной:
где n
0
=k
0
+l, l
0
=n
0
-k
0
, N=m+l,
- совокупность проверочных подматриц, имеющих форму треугольника.
.
G*
∞
(x)=[I,G
0
]=
1 0 . . . 0 q
1
ko+1
. . . q
1
no
0 1 . . . 0 q
2
ko+1
. . . q
1
no
. . .
0 0 . . . 1 q
ko
ko+1
. . . q
ko
no
. . .
или
(6.4)
G**
∞
(x)=[I,G
0
]=
1 0 . . . 0 q
1
ko+1
. . . q
1
no
0 0 . . . 0 q
2
ko+1
. . . q
1
no
. . .
0 0 . . . 0 q
ko
ko+1
. . . q
ko
no
. . .
Ф
(6.5)
,
•
•
0
I
0
n
0
N
H
∞
(x)=
Ф
Ф
Ф
0
Порождающая и проверочная матрицы СК, как и у линейных кодов, связаны
выражением: G
∞
(D)*H
T
∞
(D)= G
∞
(D)*H
T
∞
(D)=0 .
Для систематического ССК с алгоритмом порогового декодирования
проверочная матрица H
∞
(D) задается следующим образом:
Из данной проверочной матрицы следует, что для ССК с R = k
0
/n
0
=
=(n
0
-1)/n
0
проверочная матрица Н
∞
(х) содержит (n
0
-k
0
) строк и k
0
столбцов
проверочных треугольников. Для ССК с R = k
0
/n
0
== 1/n
0
, n
0
= 2;3;..., проверочная
матрица Н
∞
(х) содержит k
0
=l, т.е. один столбец и n
0
строк проверочных
треугольников.
Каждый из проверочных треугольников Н
∆
i,k0+i,
i=l,2,...; k
0
=l,2,... проверочной
матрицы H
∞
(х) в общем случае имеет вид:
где q - коэффициенты равные либо 1,либо О,
j, i - номера соответственно строки и столбца матрицы Н∞(х), которыми
определяется проверочный треугольник,
0,...m - порядковые номера степеней, в которые возводятся
n
0
столбцов
k
0
строк
(6.6)
.
H
∞
(x)=
H
∆
1,ko+1
H
∆
2,ko+1
. . . H
∆
ko,ko+1
H
∆
1,ko+2
H
∆
2,ko+2
. . . H
∆
ko,ko+2
. . .
H
∆
1,no
H
∆
2,no
. . . H
∆
ko,no
H
∆
j,i
(x)=
,
− (i),0
(j)
q
(i),1
(j)
q
1m(i),
(j)
q
m(i),
(j)
q
.....
(i),0
(j)
q
(i),1
(j)
q
(i),2
(j)
q
(i),0
(j)
q
(i),1
(j)
q
(i),0
(j)
q
K
соответствующие коэффициенты порождающего полинома.
Основную информацию о самоортогональных сверточных кодах ССК несут
коэффициенты левого столбца и нижней строки проверочного треугольника.
Например, пусть задан проверочный треугольник следующей структуры:
По данному проверочному треугольнику можно определить параметры ССК
с алгоритмом ПД:
1. Поскольку задан один проверочный треугольник, то k
0
=1, n
0
=k
0
+l=2, R=
k
0
/n
0
=1/n
0
;
2. Так как k
0
=l, то ССК задается одним порождающим полиномом,
определяемым коэффициентами левого столбца и нижней строки проверочного
треугольника.
3. Количество ненулевых членов порождающего полинома определяет число
проверочных уравнений J
i
, J=4. Следовательно, ССК может исправлять t
исп
≤ J/2 =
4/2 = 2 ошибки и обнаруживать t
обн
≤ d0-1 = (J + 1) - 1 = 4 ошибки;
4. Строки проверочного треугольника, которые начинаются с ненулевых
двоичных символов, формируют проверочные уравнения, размеры данных
проверок и номера позиций информационных и проверочных символов,
участвующих в формировании проверочных уравнений. Для данного примера
имеем: s
0
=i
0
+e
p.0
, s
1
=i
1
+e
p.3
, s
2
=i
0
+i
3
+i
6
+e
p.6
, s
3
=i
0
+i
2
+i
4
+i
7
+e
p.7
.
Размеры проверок в проверочном треугольнике обозначены цифрами перед
стрелками и определяются количеством ненулевых символов в строке;
(6.7)
H
∆
j,i
(x)=H
∆
1,1
=
.
−
−−
−
110100011
11010001
1101000
1__01010
1____1010
1_____101
1______10
1_______1
n
1
=2
n
1
=3
n
1
=4
n
1
=5
5. Длина кодового ограничения n
A
и эффективная длина кодового
ограничения n
e
СК равны соответственно,
n
A
=(m+1)n
0
=(7+1)2=16, двоичных символов
n
e
=1/2⋅J
2
+1/2⋅J+1=1/2⋅4
2
+1/2⋅4+1=11 двоичных символов.
Так как проверочный треугольник позволяет определить практически все
параметры ССК, то разработано много способов их построения. Однако на
практике наибольшее применение получили два способа их построения, а именно
с помощью нахождения разностных треугольников и совершенных разностных
множеств. Сущность их состоит в следующем.
Разностный треугольник представляет собой совокупность целых,
действительных и неповторяющихся чисел, записанных в форме треугольника.
Для ССК с R = k
0
/n
0
количество разностных треугольников равно числу k
0
. Для
всех разностных треугольников общим числом является "0", который не
указывается в совокупности чисел однако учитывается при выборе степеней
ненулевых членов порождающих полиномов. Очевидно, что число "0" определяет
нулевую степень первого ненулевого члена порождающих полиномов. Степени
ненулевых членов порождающих полиномов по заданным или построенным
разностным треугольникам можно найти путем выбора чисел: левого крайнего
столбца разностного треугольника, считывая их сверху вниз и дополняя числом
"0" или, верхней строки разностного треугольника в следующей
последовательности: первое число - показатель степени второго ненулевого члена
порождающего полинома, сумма первого и второго числа первой строки
разностного треугольника определяют показатель степени третьего ненулевого
члена порождающего полинома и т.д.
Рассмотрим пример определения параметров ССК с алгоритмом ПД при
следующем разностном треугольнике:
2 4 1
6 5
7
1. Так как задан один разностный треугольник, то k
0
=l, n
0
= k
0
+l=2,
R=k0/n0=1/2, код имеет один порождающий полином;
2. Выписывая числа левого крайнего столбца разностного треугольника,
определяем показатели степеней порождающего полинома: (0,2,6,7).
Следовательно, порождающий полином ССК имеет вид: g
l
=1+x
2
+x
6
+x
7
. При
втором способе − 0; 2; 2+4=6; 2+4+1=7. Как правило, в литературе разностные
треугольники табулированы и представлены, например, так ((2,4,1), (3,5,2)). Это
означает, что ССК имеет соответственно параметры: k
0
=2, n
0
=k
0
+l=3, R=k
0
/n
0
=2/3
и g
1
(x)=1+x
2
+x
7
и g
2
(x)=l+x
3
+x
8
+x
10
.
Разностный треугольник ССК может быть построен, если задан проверочный
треугольник и наоборот. Например, используя проверочный треугольник (6.7)
можно построить разностный треугольник, следующим образом.
Числа крайнего левого столбца разностного треугольника определяются как
результат операции вычитания порядковых номеров строк проверочного
треугольника, которые начинаются с "1". Для первого столбца получаем
следующие числа: 3-1=2 (3 - номер позиции третьей строки, 1 - номер позиции
первой строки); 7-1=6 и 8-1=7. Для получения чисел второго столбца за
вычитаемое берем номер позиции третьей строки: 7-3=4 и 8-3=5. Для получения
чисел третьего столбца за вычитаемое берем номер позиции седьмой строки:
8-7= 1.
Как отмечалось выше, числа, входящие в разностные треугольники, должны
быть целыми, действительными и неповторяющимися. Для получения
совокупности таких чисел известно достаточно много способов их нахождений,
но наиболее эффективным является способ основанный на теории совершенных
разностных множеств.
Совершенное разностное множество — это совокупность целых,
действительных и неповторяющихся чисел δ
1
, δ
2
,... δ
ξ
, причем δ
1
<δ
2
<δ
ξ
и разности
этих чисел δ
i
- δ
j
, j>i, полученных по некоторому mod ξ, (ξ≠2) также образуют,
совокупность целых, действительных и неповторяющихся чисел.
Данную совокупность полученных разностных чисел можно использовать в
качестве исходных чисел для формирования разностных треугольников и выбора
соответствующих порождающих полиномов ССК.
При выборе чисел для построения разностных треугольников необходимо
выбирать числа с наименьшим их значением по номиналу, т.к. максимальное
значение числа в построенных разностных треугольниках определяет
максимальную степень m порождающих полиномов ССК.
Рассмотрим построение ССК с алгоритмом ПД с использованием
совершенных разностных множеств[2]:
Пусть, например, имеется совокупность β=3-х целых, действительных и
неповторяющихся чисел (β=1,2,3) и эта совокупность образует β
2
+β=3
2
+3=12
разностей по модулю β
2
+β+1=3
2
+3+1=13, которые равны следующим числам:
1-0≡1 12-8≡4 2-8≡7 0-3≡1
3-1≡2 0-8≡5 8-0≡8 1-3≡11
3-0≡3 8-2≡6 8-12≡9 0-1≡12.
Полученную совокупность разностных чисел можно разбить на
следующие подмножества:
Каждый из столбцов данного множества можно использовать для построения
разностного треугольника. Следовательно, можно построить k0=4 разностных
треугольника, и четыре ССК с R=k0/n0=1/2;2/3;3/4;4/5 c J=4, и с
R=k0/n0=1/2;2/3;3/4 с J=5, разбив данное множество на три подмножества.
Отметим, что используя теорию совершенных разностных множеств были
рассчитаны и табулированы показатели степеней ненулевых членов
порождающих полиномов ССК с R=1/1000 …999/1000 для J=2 …16[1,2].
j
i
711129
51083
4621
.