Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
Для того, чтобы выполнялось основное условие F'
i
(х) · H
T
(х) = 0, провероч-
ная матрица БЧХ-кода должна иметь вид [1]:
−⋅−−⋅
−⋅
−
−
=
1)t1)(2(n1)t2(2
1t2
1)3(n
,
963
1n
,
32
...αα ,α , 1
...αα ,α ,α 1,
α ...α ,α α, 1,
)(xH
Откуда следует, что кодовые последовательности БЧХ-кода с конструктив-
ным кодовым расстоянием δ имеют δ – 1 последовательных нулевых спектраль-
ных коэффициентов. Однако в проверочной матрице (5.17) количество строк
примерно в два раза меньше, чем значение δ. Это объясняется особенностями по-
ля характеристики два (2), т.е. GF(2), в котором всегда справедливо равенство
спектральных коэффициентов f
2·i
= (f
i
)
2
, и для вычисления коэффициентов с чет-
ными номерами не требуется проводить дискретного преобразования Фурье
(ДПФ). Таким образом, основным признаком принадлежности произвольной ко-
довой
последовательности F
i
(х) к БЧХ-коду является наличие δ-1 нулевых коэф-
фициентов его ДПФ и совершенно безразлично, в каком участке спектра выбира-
ется этот нулевой отрезок. Так корнями образующего полинома могут быть взяты
элементы: α
e
, α
e+1
, α
e+δ-2
. Если ДПФ дает ненулевые значения коэффициентов на
этом участке спектра, то кодовая последовательность F
i
(x) не принадлежит БЧХ-
коду и это будет свидетельствовать также о наличии искажений кодовой последо-
вательности.
Синдром содержит δ-1 составляющую вида S
1
(x)= F
′
ι
(x)·H
T
(x)= (S
1
, S
2
, S
3
, …
, S
2t-1
,
S
2·t
), где компоненты S
2
=(S
1
)
2
, S
4
=(S
2
)
2
, S
6
=(S
3
)
2
и т.д., которые восстановле-
ны по S
1
, S
3
, S
5
и т.д. Компоненты синдрома в точках, где спектральные коэффи-
циенты кодовых последовательностей равны нулю, зависят от номеров (позиций)
искаженных символов. Пусть, например, искажения символов произошли на по-
зициях с номерами, выраженные элементами конечного поля:
β
1
,
β
2
,…,
β
t
. Из
проверочной матрицы (5.17) следует, что S
1
- сумма номеров искаженных
(5.17)
.
символов, S
2
-сумма квадратов этих номеров и т.д., S
3
- сумма (2t-1) степеней
β
.
Извеcтно, что такую структуру имеют последовательности S
1
, S
2
,…, S
2t
,
удовлетворяющие рекуррентному уравнению, называемому также тождеством
Ньютона или разностным уравнением
S
j+t
+
σ
1
·S
j+t-1
+
σ
2
·S
j+t-2
+…+
σ
t
·S
j
=0, j=1,t, (5.18)
где
σ
1
,
σ
2
,…,
σ
t
-коэффициенты полинома локатора ошибок, которые требуется
определить. Следует отметить, что коэффициенты ДПФ (S
i
, i ≥2·t) принятой ко-
довой последовательности, т.е. вычисленные за пределами нулевого спектра кода
зависят как от вектора ошибки, так и передаваемой кодовой последовательности,
которое неизвестно. Это затрудняет использование коэффициентов S
i
для коррек-
ции ошибок. Таким образом, задача коррекции ошибок произвольной кратности
БЧХ-кодом с произвольной проверочной матрицей вида (5.17) состоит в решении
рекуррентного уравнения вида (5.18).
Алгоритм декодирования двоичных БЧХ-кодов, исправляющих все конфи-
гурации ошибок кратности t (t≥1) двоичных символов, состоит из выполнения
трех этапов, а именно [3,7,8]:
первый этап декодирования предусматривает вычисление каждого
компонента синдрома S
i
с нечетным номером путем деления принятой кодовой
последовательности F
′
i
(x) на минимальный полином m
i
(x) элемента α
i
и
вычисление значения остатка от деления R
i
(x) в точке x= α
i
: S
i
=F
′
(α
i
)=R(α
i
);
i-нечетное значение и меньше значения 2·t. Компоненты синдрома с четными но-
мерами определяются путем возведения в квадрат S
i
, так как S
2·
i
= (S
i
)
2
. (Возведе-
ние элемента в квадрат делается по правилам вычисления в конечных полях). Ре-
зультатом первого этапа декодирования является получение последовательности
компонентов синдрома S
1
, S
2
, S
3
,…, S
2t
, которую можно представить полиномом
вида S(z)=S
1
·z
1
+S
2
·z
2
+S
3
·z
3
+…+S
2
·t
·z
2·
t
с коэффициентами из поля GF(2
ε
);
второй этап декодирования предусматривает по полученному
синдрому определение полинома локаторов ошибок вида,
σ
)(
z
=
∑
=
⋅−
t
i
i
z
1
)1( β =
1
+
σ
1
,...
3
3
2
2
1 t
t
zzzz ⋅++⋅+⋅+⋅ σσσ корни которого
1
z
=
1
1
−
β
,
11
22
,...,
−−
==
tt
zz ββ
обратны номерам искаженных символов. Основная сложность
данного этапа состоит в том, что
σ
)(
z
определяется по S(z) неоднозначно. В соот-
ветствии с алгоритмом декодирования по максимуму правдоподобия оптимальное
решение уравнения состоит в нахождении вектора ошибок минимального веса,
т.е. в нахождении полинома локаторов наименьшей степени. Известно несколько
способов определения
σ
)(
z
по известному синдрому S(z), основанных на реше-
нии однородного рекуррентного уравнения (5.18). Доказано, что
σ
)(
z
и S(z)
удовлетворяют уравнению вида
[
]
),()()(1 zwzzS =⋅+ σ по mod ,
12 +⋅t
z (5.19)
где )(
z
w
- некоторый полином: при декодировании двоичных БЧХ-кодов опреде-
ление данного полинома не требуется.
В соответствии с [1,3,7,8] уравнение вида (5.19) из-за своего важного и
определяющего значения называется ключевым уравнением декодирования.
Разработаны многочисленные алгоритмы решения данногого уравнения и в
частности, основанный на применении алгоритма Эвклида поиска наибольшего
общего делителя полиномов S(z) и z
2·t+1
. Таким образом, результатом выполнения
второго этапа декодирования является определение полинома локаторов ошибок
σ(z) наименьшей степени;
третий этап декодирования включает коррекцию ошибок при условии, что
кратность ошибок не превосходит значения t и номера позиций искаженных ин-
формационных символов обратны корням полиномов σ(z). Процедура коррекции
ошибок заключается в поиске корней полинома σ(z), т.е. в последовательной про-
верке всех ненулевых элементов поля GF(2
ε
) на выполнение равенства σ(α
i
)=0. В
общем случае уравнение σ(x)=0 может выполняться t раз и соответственно t раз
будут формироваться сигналы на коррекцию ошибочных информационных сим-
волов.
Для синтеза функциональных схем кодека БЧХ-кода необходимо задание
образующего полинома P(x) и алгоритма декодирования. Если алгоритм декоди-
рования кода выбирается исходя из обеспечения минимальной задержки инфор-
мации при декодировании и сложности реализации декодера, то параметры кода
рассчитываются на основании заданной длины n кодовой последовательности и
корректируемой кратности t
исп
ошибок. Методика расчета параметров БЧХ-кода
рассмотрена в разделе 3.2.4.
Используя данные БЧХ-кода примера 3.6, а именно n=15 двоичных симво-
лов, t
исп
=2 двоичных символа, k=7 двоичных символов, d
o
=5 и
P(x)=x
8
+x
7
+x
6
+x
4
+1, выполним синтез функциональных схем кодера и декодера.
Функциональная схема кодера БЧХ-кода может быть выполнена в виде по-
следовательного регистра сдвига с обратной связью и со встроенными суммато-
рами по модулю два. На рис. 5.16 приведена обобщенная функциональная схема
кодера БЧХ-кода, реализующая данный принцип построения. Нумерация ячеек
памти принята слева направо.
Рис. 5.16. Обобщенная функциональная схема кодера БЧХ-кода:
(n, k)=(15,7), P(x)=x
8
+x
7
+x
6
+x
4
+1
Принцип работы кодера аналогичен принципу работы кодера ЦК приве-
денного на рис. 5.12.
T
1
T
2
T
3
T
4
T
5
T
6
M2
T
7
M2
T
8
M2
&
&
&
1
ФСУ
ключами кодера
Вх
.
f
T
Вых
F(x)
Вх.Q(x)
CУ 2 (Кл.3)
CУ 1 (Кл.1 и Кл.2)
Кл.1
Кл.2
Кл.3
M2
Сравнительно малая задержка информации при декодировании и сложность
реализации декодера БЧХ-кодов обеспечивается при реализации алгоритма вы-
лавливания ошибок. Обобщённая функциональная схема декодера, реализующего
алглритм вылавливания ошибок приведена на рис. 5.17. На рис. 5.18 приведены
временные диаграммы, поясняющие принцип работы декодера. Декодер содержит
следующие основные функциональные блоки: синдромный регистр с дешифрато-
ром (ДШ) на все нули, буферное устройство (БУ) с выходным сумматором по мо-
дулю два и ключом Кл.2, формирователь сигналов управления ключами
(ФСУ Кл.) декодера и ключи управления : Кл.1-входной ключ, Кл.2-выходной
ключ.
Рис. 5.17. Обобщенная функциональная схема декодера БЧХ-кода,
реализующая алгоритм вылавливания ошибок:(n,k)=(15,7),
P(x)=x
8
+x
7
+x
6
+x
4
+1
M2
M2
Синдромный р
е-
Вх.
F’(x)
T
1
T
2
T
3
T
4
T
6
M2
M2
T
7
M2
T
5
T
8
Д Ш. на все “0”
&
&
1
T
1
T
2
T
3
T
15
……….
M2
&
&
ФСУ
ключами декодера
Вх.
f
cp
Вых.
Q(x)
Кл.2
Кл.3
Кл.1
a
15
a
1
БУ
Рис. 5.18. Временные диаграммы сигналов управления ключами декодера
Декодер работает следующим образом. В течение первых 15-ти тактов
ключ Кл.1 открыт, а ключ Кл.2 и Кл.3-закрыты; производится запись кодовых
символов в БУ и формирование синдрома. С 16-го по 30-й такт декодирования
ключ Кл.1 и Кл.3-закрыты, а ключ Кл.2-открыт; производится перезапись кодо-
вых символов в БУ и коррекция первого ошибочного информационного символа.
Затем с 31 такта ключ Кл.3 открывается и в течение семи тактов осуществляется
выдача информационного сообщения получателю информации с одновременной
коррекцией второй ошибки (второго ошибочного информационного символа).
Далее ключи Кл.2 и Кл.3 закрываются, а ключ Кл.1 открывается; производится
запись и декодирование аналогичным способом следующей кодовой последова-
тельности.
15
30 37
СУ2
15 30
37
СУ1
Кл.1
Кл.2 t
t
15
30 37
СУ3
Кл.3
t
5.5. Коды Рида-Маллера: определение, параметры, матричное
представление, алгоритмы декодирования и синтез
функциональных схем кодеков
5.5.1. Определение, параметры, матричное представление и основные
алгоритмы декодирования кодов
В соответствии с [3,4,7,8] коды Рида-Маллера (КРМ) относятся к
групповым несистематическим (неразделимым) кодам с простым способом
задания. Декодирование КРМ чаще всего реализуется мажоритарным и
синдромным способами, однако возможно декодирование кодов по максимуму
правдоподобия. В общем, КРМ эквивалентны циклическим кодам с добавлением
общей проверки на четность. Достоинствами данных кодов являются простота их
задания и минимальная сложность реализации алгоритмов кодирования и
декодирования. Недостатком КРМ является слабая (низкая) корректирующая
способность; данные коды чаще всего применяются для коррекции ошибок
кратностью не более трех двоичных символов.
Сущность КРМ и, следовательно, их определение состоит в следующем
[3,7,8] : пусть F
0
(x) есть кодовая последовательность (кодовый вектор) ,
состоящая из одних логических единиц (1), а кодовые последовательности F
1
(x),
F
2
(x),…, F
m
(x) образуют строки матрицы, столбцами которой являются все
двоичные наборы длиной m двоичных символов; m может иметь разное значение
(величину), т.е. величина m ≥ 2. В этом случае для любых целых чисел m и E
(E<m) можно построить помехоустойчивый код длины n=2
m
двоичных символов,
который называется кодом Рида-Маллера E-го порядка. В реальных системах
связи КРМ с E>3 практически не используются.
КРМ E-го порядка содержит в качестве базиса (основы) кодовые
последовательности F
0
(x), F
1
(x),…,F
m
(x) и все поэлементные (покомпонентные)
произведения E или меньшего числа этих последовательностей. В данном
определении поэлементные произведения кодовых последовательностей
(условно: a=(a
1
a
2
…a
n
) и b=(b
1
b
2
…b
n
)) задается формулой a·b=(a
1
·b
1
, a
1
·b
1
,…, a
n
·b
n
).
КРМ E-го порядка дуален (двойственен) помехоустойчивому коду (m-E-1)
порядка.
КРМ E-го порядка длины n=2
m
двоичных символов задается (строится)
порождающей матрицей вида [3,7,8]:
,
(x)G
.
.
.
(x)G
(x)G
G(x)
E
1
0
=
где G
0
(x)-кодовый вектор (кодовая последовательность) длиной n=2
m
двоичных
символов, состоящих из одних “1”;
G
1
(x)- матрица размерности (m*2
m
), содержащая в качестве столбцов все
двоичные m-последовательности;
G
E
(x)- матрица, строки которой получаются из строк матрицы G
1
(x) как все
возможные произведения E строк из матрицы G
1
(x); для определенности обычно
принимают, что первый столбец в G
1
(x) состоит из одних “0”, а последний из
одних “1”.
Коды Рида-Маллера имеют простые выражения для определения
основных параметров данных кодов, а именно: n=2
m
двоичных символов - длина
кодовой последовательности:
∑
=
=
E
i
m
i
C
0
k
двоичных символов - длина или
количество информационных символов;
d
0
=2
m-E
-минимальное кодовое расстояние;
d =
2
n
- кодовое расстояние.
Кроме того, возможно определение параметров КРМ по следующей
методике:
длина кодовой последовательности определяется рангом порождающей
матрицы, т.е. n=2
m
двоичных символов;
параметры k и l=n-k КРМ E-го порядка можно определить используя
следующие выражения:
,
E
m
...
2
m
1
m
1k
++
+
+=
.
1Em
m
...
2
m
1
m
1rnl
−−
++
+
+=−=
Далее установим связь КРМ с другими линейными блоковыми кодами.
КРМ нулевого порядка (E=0) является (n, k)=(n,1)- кодом и соответствует
коду с повторением и использует мажоритарный алгоритм декодирования.
Минимальное кодовое расстояние такого кода равно d
0
=2
m
, а так как в этом
случае m=2 , то d
0
=2
2
=4.
КРМ первого порядка (E=1) тесно связаны с кодами максимальной
длины, которые, в свою очередь, дуальны кодам Хэмминга. Если начать
построение помехоустойчивого кода с построения кода максимальной длины и
расширять его путем добавления общей проверки на четность, то получим
ортогональный код. Данный код имеет длину n=2
m
двоичных символов и вес
каждой ненулевой кодовой последовательности равен
1
2
−
==
m
i
dw .
Следовательно, любые две кодовые последовательности совпадают в 2
m-1
позициях и различаются в остальных 2
m-1
позициях. Используя этот код с
противоположными сигналами, получим множество из 2
m
ортогональных
сигналов для 2
m
кодовых последовательностей; отсюда и название ортогональных
сигналов.
КРМ первого порядка получаются непосредственно из ортогонального
кода добавлением кодовой последовательности состоящей целиком из “1”. Если
же рассматривать передаваемые сигналы, то эта процедура эквивалентна
добавлению дополнительных сигналов к первоначальному множеству
ортогональных сигналов. По этой причине полученный код называют
биортогональным кодом [3,4].
Рассмотрим принцип построения КРМ с использованием следующих
исходных данных кода: m=4 и E=3. Следовательно, необходимо определить все
параметры КРМ третьего порядка. Далее определяем параметры кода n , k и d
0
:
n=2
m
=2
4
=16 двоичных символов - длина кодовых последовательностей;
1546411
321
1k
321
=+++=+++=
+
+
+=
mm
m
CCC
mmm
двоичных
символов - длина информационного блока;
222d
34
0
===
−
−
Em
.
Данный КРМ задается порождающей матрицей вида
.
(x)G
(x)G
(x)G
(x)G
G(x)
3
2
1
0
=
Строим порождающие матрицы G
0
(x), G
1
(x), G
2
(x) и G
3
(x).
Порождающая матрица G
0
(x) содержит одну строку (обозначим строку
буквой a
0
) логических единиц с количеством равной n=2
m
=2
4
=16 двоичных
символов и имеет следующий вид:
[
]
[
]
01
a1111111111111111)x(G
=
=
.
Порождающая матрица G
1
(x) содержит m=4 строки; первая строка матрицы
содержит
8
2
16
2
n
==
логических нулей (0) и логических единиц (1).
Последующие строки данной матрицы строятся аналогичным способом, т.е.
делением последовательностей 1 и 0 строк на два. Порождающая матрица G
1
(x)
имеет следующее построение:
.
a
a
a
a
0101010101010101
1100110011001100
0011110000111100
1111110000000011
(x)
1
G
4
3
2
1
=
=