Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
Сформированная порождающая матрица позволяет построить
транспонированную проверочную матрицу )x(H
T
32,6
, которая имеет следующий
вид или структуру:
.
000001|
000010|
000100|
001000|
010000|
100000|
01111110011001011000101101
10111101110110100100101101
11000100101100011101110111
01001001010101101110111011
10010000011010101111011101
00100011100011011111101110
(x)H
T
6,32
=
Ненулевые символы строк данной матрицы определяют позиции
информационных символов
)...aa(
26
1
, участвующие в формировании
проверочных символов
)b...b(
61
.
Синтез структурной схемы кодирующего устройства (кодера) выполняем
с определения основных его функций. Основными функциями кодера являются:
− разделение символов входного информационного потока на 26
параллельных подпотоков,
− формирование проверочных символов, образующих шесть
параллельных подпотоков,
− объединение символов 32 параллельных подпотоков в единый
кодовый поток, т.е. формирование и передачу символов кодовой
последовательности в последовательном коде.
Для реализации данных функций в кодере необходимо иметь следующие
функциональные блоки: КРИ-1/26 – коммутатор распределения информации на 26
параллельных подпотоков, ФПСк – формирователь проверочных символов
кодера, КОИ-32/1 – коммутатор объединения 32 параллельных подпотоков в
а
1
…
а
26
b
1
=a
27
….b
6
=a
32
последовательный кодовый поток
)
x
(
F
и БСК блок синхронизации кодера,
содержащего делитель частоты на 26 и кольцевого счетчика на 32. В соответствии
с этим структурная схема кодера будет иметь следующее построение (рис. 5.19)
Рис. 5.19. Структурная схема кодера кода Рида-Маллера с параметрами
)4,26,32()d,k,n(
0
=
Кодирование информации производится следующим образом. После
преобразования передачи информации из последовательного кода в параллельный
код 26 информационных символов поступают одновременно на соответствующие
входы КОИ-32/1 и ФПСк. В ФПСк проверочные символы
61
b...b
формируются в
соответствии с транспонированной проверочной матрицей )x(H
T
32,6
, а именно:
2723201817131211987543211
aaaaaaaaaaaaaaaab
=
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
=
282421191715141087643212
aaaaaaaaaaaaaaab
=
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
=
29252219181614121097653213
aaaaaaaaaaaaaaaab
=
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
=
30262221201615131098654214
aaaaaaaaaaaaaaaab
=
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
=
31
26252423211917161413121087525
aaaaaaaaaaaaaaaaab
=
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
=
b
1
=a
27
b
6
=a
32
…
КОИ-32/1
Вых.
F(x)
ФПСк
…
…
…
a
1
a
2
a
26
БСК
f
2
=(n/k) f
T
Вх.
ДШ Дв.сч.
…
f
T
:26
f
T1
Вх.
КРИ
-
1/26
Вх.
Q(x)
32262524232220181514111087516
aaaaaaaaaaaaaaaab
=
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
⊕
=
ФПСк может быть выполнен либо с помощью сумматоров по модулю два
(двухвходовые схемы Исключающее «ИЛИ»), либо с помощью многовходовых
схем контроля четности. КРИ-1/26 и КОИ-32/1 могут быть выполнены по
принципу построения рассмотренному в разделе 5.2.1. В этом случае сигналы
управления )C...C(
51
мультиплексором будут представлять собой кодовые слова
(комбинации) содержащие пять символов.
Синтез структурной схемы декодирующего устройства (декодера),
реализующего синдромный алгоритм декодирования кода Рида-Маллера,
выполняем по методике рассмотренной в подразделе 5.2.3. Реализация алгоритма
синдромного декодирования сводится к выполнению следующих основных
операций: формирование синдрома, дешифрация синдрома, коррекция ошибок. В
соответствии с матрицей )x(H
T
32,6
синдром будет представлять кодовое слово,
содержащее шесть символов, структура которых, при наличии ошибок, будет
совпадать со структурой соответствующего столбца данной матрицы, т.е.
)x(H
T
32,6
. Синдром может быть сформирован различными способами. Например,
как произведение принятой кодовой последовательности )x(F
'
на
транспонированную проверочную матрицу )x(H
T
32,6
, т.е. )x(H)x(F)x(S
T
6,32
'
⋅=
или как )bb(),...,bb(),bb()x(S
'
66
'
22
'
11
⊕⊕⊕= , где b'
1
,…b'
6
- проверочные
символы сформированные из принятых информационных символов )a,...,a(
'
26
'
1
по
алгоритму (правилу) аналогично используемому в кодере.
Основными функциями декодера, реализующего алгоритм синдромного
декодирования, являются:
− преобразование кодовых символов последовательности )x(F
'
из
последовательного кода в параллельный код;
− формирование проверочных символов
1
6
'
1
b...b
из принятых
информационных символов;
− формирование синдромных символов S
1
…S
6
по правилу: )bb(S
'
111
⊕= ,
)bb(S
'
222
⊕=
,
)bb(S
'
333
⊕=
,
)bb(S
'
444
⊕=
,
)bb(S
'
555
⊕=
,
)bb(S
'
666
⊕=
;
− дешифрация синдрома;
− коррекция ошибок;
− преобразование информационных символов a
1
…a
26
из параллельного
кода в последовательный и выдача их получателю.
Для реализации данных функций в декодере необходимо иметь следующие
функциональные блоки: КРИ-1/32 – коммутатор распределения информации на 32
параллельных подпотока, ФПСд – формирователь проверочных символов
декодера, ФСС – формирователь синдромных символов, ДШС – дешифратор
синдрома, КО – корректор ошибок, КОИ-26/1 – коммутатор объединения
информации 26 параллельных подпотоков в единый поток и БСд – блок
синхронизации декодера в составе делителя частоты на 32 и кольцевого счетчика
на 26. Структурная схема декодера приведена на рис 5.20. Корректор ошибок на
данном рисунке представлен в виде совокупности 26-ти двухвходовых
сумматоров по модулю два.
Формирователь синдромных символов выполняется в виде шести
двухвходовых сумматоров по модулю два.
Дешифратор синдрома может быть выполнен различными способами,
например, в виде комбинационного автомата.
Рис.5.20. Структурная схема декодера, реализующего синдромный алгоритм
декодирования кода Рида-Маллера с параметрами (32,26,4)
КРИ
-
1/32
КОИ
-
26/1
ФСС
ФПСд
…
b'
1
b'
6
b'
6=
a'
32
b'
1=
a'
27
…
s'
1
s'
6
ДШ
1
ДШ
26
…
ДШС
Вых.
Q(x)
Вх.
F'(x)
f
T
:32
f
T1
Вх.
Вх.
…
f
T
ДШ Дв.сч.
с
1
с
5
…
a'
1
a'
26
…
…
М2
М2
КО
…
5.6. Коды Рида-Соломона: определение, параметры, матричное пред-
ставление, алгоритмы декодирования и синтез структурных схем
кодека
5.6.1. Определение, параметры и матричное представление кодов Рида-
Соломона
Коды Рида-Соломона (РС-коды) являются дальнейшим развитием БЧХ-
кодов и в связи с высокой корректирующей способностью широко применяются в
современных системах связи, обработки информации, записи и воспроизведения
информации. РС-коды – это такие БЧХ-коды, у которых мультипликативный по-
рядок алфавита символов кодовой последовательности делится на длину кода.
При a=1 поле символов GF(g)совпадает с полем локаторов ошибок GF(g
a
). По-
скольку поле символов и поле локаторов ошибок совпадает, то все минимальные
полиномы линейны. Чаще всего корни α образующего полинома P(x) РС-кодов
выбираются примитивными [3,4,7].
Образующий полином РС-кода записывается в виде произведения двучле-
нов (x-
ji
α
), т.е. )α)...(xα(x)α(xP(x)
12tj1j
j
000
−
+
+
−−⋅−= , где j
0
-любое целое
положительное число (j
0
≥1),
α
-корни полинома,
t
-кратность (длина) корректи-
руемых ошибок. РС-коды допускают выбор любого значения
0
j , но при разумных
значениях
0
j
возможно уменьшение сложности реализации кодека. Максималь-
ная степень образующего полинома всегда равна
t
2
⋅
. Следовательно, провероч-
ные символы и параметры кода “
n
” и “
k
” связаны равенством l=2t=(n-k), двоич-
ных символов.
К основным параметрам РС-кодов, корректирующие одиночные пакеты
ошибок длинной
n
t
двоичных символов, относятся:
)12(tn
n
t
n
+= - длинна кодовой последовательности;
)12(tk
n
t
n
−= - количество информационных символов, входящих в кодо-
вую последовательность;
l=2t
n
- количество проверочных символов;
d
0
=n-k+1=2t
n
+1- минимальное кодовое расстояние. РС-коды относятся к по-
мехоустойчивым кодам с максимальным значением d
0
;
1x...xx)x(P
1t2t2
nn
++++=
−
- образующий полином.
Кодирование информационного сообщения 1..xx)x(Q
2k1k
+++=
−
−
и деко-
дирование кодовых последовательностей 1...xx)x(F
2n1n
+++=
−
−
осуществляется
с помощью соответственно порождающей матрицы )x(G
n,k
и проверочной мат-
рицы )x(H
n,l
, что в общем виде можно записать так:
)
x
(
G
)
x
(
Q
)
x
(
F
⋅
=
- кодирование информации,
)x(H)x(F)x(S
'
⋅=
- декодирование информации.
Для того, чтобы в процессе кодирования
)
x
(
Q
кодовые последовательности
)
x
(
F
получались систематического вида, необходимо использовать каноническую
порождающую матрицу, т.е. матрицу вида
[
]
HI(x)
nk,
G M= , а также использовать
транспонированную проверочную матрицу, т.е. матрицу вида
= I
T
H(x)
ln,
H M .
При несистематическом кодировании информации РС-кодами информаци-
онный полином Q(x) умножается на образующий полином P(x), т.е.
F(x)=Q(x)·P(x), при этом предполагается, что k>l, т.е. когда k<l целесообразнее
при кодирование Q(x) использовать проверочный полином h(x) степени “k”.
Систематическое кодирование информационных сообщений
)
x
(
Q
произво-
дится во временной области и в этом случае декодирование кодовых последова-
тельностей
)
x
(
F
можно выполнять как во временной, так и в частотной области, а
также возможно смешанная реализация алгоритмов декодирования. (По стандарту
на цифровую запись и воспроизведение информации и при использовании поме-
хоустойчивого кодирования проверочные символы размещаются внутри кодовой
последовательности F(x)).
С целью минимизации сложности рассмотрения принципа построения коде-
ка циклического РС-кода принимаем, что РС-код корректирует одиночные пакеты
ошибок кратностью
n
t двоичных символов. В соответствии с [3,4,8] проверочная
матрица двухизбыточного циклического РС-кода корректирующего одиночные
пакеты ошибок кратностью
n
t
двоичных символов имеет следующее построение
=
B
f2420
B
f210
I0h...hhh
0Ih...hhh
)x(H , (5.23)
где
B
0
Ih =
- единичная матрица размерностью
nn
tt
×
.
Пакет ошибок кратностью t
n
двоичных символов рассматривается как q-
значный разряд, принимающий одно из “q” значений от “0” до “q-1”. В этом слу-
чае в проверочной матрице (5.23) элементами столбцов являются не двоичные
символы “1” и “0”, а подматрицы вида 0; 1;
β
h
, значения которых определяется
выражением вида
−
+
−
+
−
+
−
+
−
+
==
β
2
n
tβ1
n
tββ
n
tβ2
n
tβ1
n
tβ
β
...ααα...αααh
, (5.24)
где
jt
n
−+β
α - столбец подматрицы, соответствующий остатку от деления
jt
n
−+β
α (или
jt
n
x
−+β
) на образующий полином
)
x
(
P
степени
n
t
;
β
- показатель степени матрицы, который может находиться в пределах
121
n
t
−≤β≤ .
Если в качестве образующего полинома выбран неприводимый примитив-
ный полином степени
n
t
, то можно образовать
1
2
n
t
−
различных матриц вида
β
h
.
Проверочная матрица
)
x
(
H
вида (5.23) может быть преобразована путем
нормализации, а именно путем перемножения каждого элемента столбца матриц
β
h
на инверсию его первого элемента, т.е. следующим образом
⋅
=
⋅
−
−
1
B
1
0
1
1
2
1
h
I
h
h
h
h
h
h
. (5.25)
В этом случае проверочная матрица H(x) вида (5.23) будет иметь следующее
построение
.
I0h...hhI
0II...III
)x(H
B
f21
B
BBBBB
n,l
=
(5.26)
Порождающая матрица G(x) циклического РС-кода может быть построена
по правилу
[
]
(x)H:I(x)G
T
B
kn,
= , (5.27)
где
B
I - единичная подматрица размерностью
k
k
×
,
)x(H
T
- транспонированная проверочная подматрица размерностью
l
×
k
.
5.6.2. Синтез структурных схем кодека циклического кода Рида-
Соломона
Синтез структурных схем кодека циклического РС-кода полностью опреде-
ляется заданием параметров (
−
q
),
x
(
P
,
k
,
n
основание кода), количества и кратно-
сти пакетов ошибок, алгоритма декодирования и способа обработки информации
при кодировании. Далее выполним синтез структурных схем кодека двоичного
циклического РС-кода корректирующего одиночные пакеты ошибок кратностью
4t
n
=
двоичных символа при последовательном способе обработки информации
и реализующего синдромный алгоритм декодирования.
Так как главной функцией кодера циклического кода является формирова-
ние проверочных уравнений или проверок, правило формирования которых мо-
жет быть определено либо порождающей матрицей вида
[
]
HI)x(G
n,k
M
=
, либо
проверочной матрицей вида
[
]
IH(x)H
T
ln,
M=
.
Определяем основные параметры РС-кода, а именно:
68)12(4)12(tn
4
t
n
n
=+⋅=+=
двоичных символов,
60)12(4)12(tk
4t
n
n
=−⋅=−= двоичных символов,
9160681knd
0
=
+
−
=
+
−
=
,
l=n-k=68-60=8 двоичных символов,
151212
4t
n
=−=−=γ - количество подматриц вида
β
h
.
Выбираем образующий полином вида 1xx)x(P
4
++= .
Следовательно, проверочная матрица (5.23) будет иметь следующую струк-
туру
где
151
U...U - пакеты информационных двоичных символов,
321
C,C,C - пакеты проверочных двоичных символов.
Подматрицы
β
h
проверочной матрицы (5.28) имеют следующие структуры:
=
0001
1001
0100
0010
h
1
,
=
0010
0011
1001
0100
h
2
,
=
0100
0110
0011
1001
h
3
,
=
1001
1001
0110
0011
h
4
,
=
0011
1010
1101
0110
h
5
,
=
0110
0101
1010
1101
h
6
,
=
1101
1011
0101
1010
h
7
,
=
1010
0111
1011
0101
h
8
,
=
0101
1111
0111
1011
h
9
,
=
1101
0111
1111
1110
h
10
,
=
1110
0011
0111
1111
h
11
,
=
1111
0001
0011
0111
h
12
,
=
0111
1000
0001
0011
h
13
,
=
0011
0100
1000
0001
h
14
,
=
0001
0010
0100
1000
h
15
.
,
321151413121110987654321
1311975311412108642
1413121110987654321
CCCUUUUUUUUUUUUUUU
I00hhhhhhhhhhhhhhI
0I0hhhhhhhhhhhhhhI
00IIIIIIIIIIIIIIII
H(x)
=
(5.28)