Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
коррекцию как одиночных, так и многократных ошибок[16].
Корректирующая способность каждой ступени декодирования определяется
выбранным значением порога декодирования. Так, например, для ССК с R=l/2 и
J=3 величина порога в первой ступени декодировании двухпорогового декодера,
приведенного на рис.6.11, выбирается равным П
1
=J=3, а во второй ступени
декодирования П
2
=J-1=3-1=2. При J=4 порог в первой ступени декодирования
выбирается равным П
1
=J, а во второй ступени П
2
≥J/2+1=4/2+1=3; при J≥5 порог в
первой и второй ступенях декодирования выбираются соответственно равными
П
1
=J=5, П
2
=J-1=5-1=4, а в третьей ступени декодирования П
3
=J/2+1=5/2+1=3.
Рис.6.11. Обобщенная структурная схема двухпорогового декодера ССК с
R=l/2
Таким образом, коррекция ошибок каждой ступенью декодирования
обеспечивает более высокую достоверность исправления ошибок последующими
ступенями декодирования. Следовательно, при оптимально выбранном
количестве ступеней декодирования можно обеспечить высокую достоверность и
скорость обработки информации при невысоких затратах на реализацию
декодера.
Определение вероятности ошибочного декодирования многопорогового
декодера является достаточно сложной математической задачей. Это
определяется тем, что ошибки, поступающие на входы соответственно второй,
третьей и последующих ступеней декодирования, являются зависимыми.
Приближенная оценка вероятности ошибочного декодирования порогового
KO2
KO1
I(x)
S’(x)
S(x)
Pпр(x)
I’(x)
…
…
…
…
RC
M2
RC
M2
БАС
БАС
БВС
ПЭ
ПЭ
декодера с двумя ступенями декодирования определяется выражением:
где P
1ступ.
- вероятность ошибочного декодирования первой ступени декодера.
В выражении (6.12) самым "важным" членом является P
1ступ.
- вероятность
ошибочного декодирования первой ступени порогового декодера, которая
рассчитывается по формуле:
где P
k
- вероятность ошибочного приема двоичного символа на выходе
канала.
На рис 6.12 приведены зависимости вероятности ошибочного декодирования
двухпорогового декодера определенные согласно выражению(6.12).
Анализ многопорогового декодирования показывает, что энергетический
выигрыш увеличивается на 0,21 дБ при последовательном увеличении количества
ступеней декодирования при R=const и J=const. При R=const и увеличении
количества проверок (J+1) энергетический выигрыш увеличивается на 0,3 ... 0,4
дБ.
Расчеты вероятности ошибочного декодирования многопорогового декодера
ССК с R=l/2 и J=9, используемого в каналах с ДФМ, Q=8-MИ уровнях квантования
и Р
с
/Р
ш
=10дБ показывают, что многопороговый декодер с 4-мя ступенями
декодирования обеспечивает энергетический выигрыш в 4,7 дБ при сохранении
всех достоинств ПД СК. Аналогичное значение энергетического выигрыша
обеспечивает декодер Витерби при R=l/2, k=5, Q=8. Однако сложность декодера
Витерби более чем в 10 раз превышает сложность порогового декодера.
(6.13)
,)P(1
n
P
P
00
nd
k
0
k
1ctyn
−
−⋅≈
,
∑
+
=
−
−
⋅
⋅
≈
E
E
E
n
1
2
j
i
i
n
1ctyn
1ctya
i
n
i
)
P
(1
P
C
P
(6.12)
Рис. 6.12. Вероятности ошибочного декодирования двухпорогового декодера СК с
R=l/2 J==4 и m==6;1;2;3; - вероятности ошибочного декодирования
соответственно при 2,3, и 4 ступенях в декодере
6 .4.4. Табличное декодирование СК
Декодер СК, реализующий алгоритм табличного декодирования СК
(называемый также алгоритмом синдромного декодирования СК с табличным
поиском) имеет много общего с многопороговым декодером.
Обобщенная схема кодека, реализующего синдромное декодирование СК с
табличным поиском приведена на рис. 6.13.
Принципиальное отличие данного кодека от кодека, реализующего ПД,
состоит в блоке анализа синдрома (БАС).
Регистры сдвига, используемые в блоках декодера содержат по m ячеек
памяти, а синдромный регистр сдвига БАС содержит 2⋅m ячеек памяти. В данном
блоке декодера реализуется алгоритм декодирования с использованием обратной
связи, позволяющей удалить влияние синдромных символов
3
2
1
ДФМ
P
с
/P
ш
. дБ
0
2
4
6
8
10
12
14
16
1
2
3
4
5
6
7
8
lg P
К
(S(x)=S
0
S
1
S
2
…S
m
S
m+1
…), использованных для оценки достоверности
информационного символа i
ξ
(х) на принятие решения о достоверности
информационного символа i
ξ+1
(х).
Рис. 6.13. Обобщенная схема кодека, СК с R=1/2
Табличный декодер и пороговый декодер СК работают одинаково
включительно до окончания записи в регистр сдвига БАС М=2⋅n
0
синдромных
символов. Последние (m’+1) синдромных символов данного регистра сдвига
используются для определения адреса в таблице решающего устройства, согласно
которому таблица извлекает соответствующий вектор ошибок. Решающее
устройство выбирает такую комбинацию ошибок, при которой получается
наименьшая вероятность ошибочного приема информации. Если это сочетание
ошибок содержит ошибку, соответствующую информационному символу
поступившему на один из входов выходного сумматора по модулю два
•
M
T
1
T
2
T
m
M
M
M
T
1
T
2
T
m
M
T
1
T
2
T
m
M
T
1
T
m
T
m
T
1
Решающее устройство для
оценки E
(j)
(x)
g(x)
M
m’
Кодер
канал
связи
БАС
Корректор
E
(p)
(x)
E
(i)
(x)
P
пер
(D)
P
сф
(x)
Вых
)(
)(
^
xE
i
I(x)
I(x)
корректора, то решающее устройство формирует сигнал коррекции Е
(i)
(х). Этот
сигнал поступает на второй вход корректирующего сумматора по модулю два и
инвертирует значение данного символа.
Символы коррекции одновременно поступают в регистр БАС по цепи
обратной связи, исключая тем самым синдромные символы, используемые для
декодирования в момент времени ξ на принятие решения декодером в
последующие моменты времени.
Решающее устройство обычно реализуется на основе программируемого
запоминающего устройства (ПЗУ), в котором каждому синдрому записывается
наиболее вероятная комбинация ошибок. Таким образом, в ПЗУ необходимо
записать как минимум S
M
=2
2m+1
комбинацией синдрома и далее использовать
принцип их полного перебора. Так как в решающем устройстве используется
только 2⋅m+l синдромных символов, то для построения решающего устройства
можно использовать усеченную транспонированную проверочную матрицу на М
ветвей и применять для формирования синдрома матричное уравнение вида:
S
M
= H
M
T
.
E
M
(6.14)
которое формирует систему из М линейных уравнений, связывающих М
синдромных символов с 2⋅М ошибками в канале связи. Таким образом, для
каждого вектора синдрома имеется значительное множество векторов ошибок,
удовлетворяющих уравнению (6.14). Вероятность ошибочного декодирования или
вероятность первой ошибки декодирования будет минимальной, если для каждого
из 2
M
возможных синдромов можно найти вектор ошибок Е
м
с минимальным
весом Хэмминга, удовлетворяющий уравнению (6.14).
Совокупность решений для всевозможных S
M
формируется путем их
перебора, этот перебор выполняется один раз и найденные решения заносятся в
таблицу, в которой осуществляется поиск. Данный алгоритм декодирования
может обеспечивать минимальную вероятность первой ошибки, но не
обеспечивает минимальную вероятность ошибочного приема двоичного символа,
т.к. для этого требуется построить оптимальную таблицу, что является
трудоёмкой задачей. Кроме того, для некоторых СК необходимо учитывать
эффект размножения ошибок.
Сложность реализации решающего устройства и, следовательно, декодера
СК растет линейно с ростом "m" и экспоненциально с увеличением М; объем
таблицы равен 2
M
. Отсюда следует, что необходимо выбирать СК, которые
оптимизируют характеристики при соответствующих значениях "m".
Общий энергетический выигрыш при табличном декодировании составляет
(1...2) дБ для СК с R=l/2...3/4 и зависит от значений "m", Р
с
/Р
ш
и вида модуляции.
При меньших значениях R (R<1/2) табличное декодирование СК не приводит к
увеличению энергетического выигрыша. При таком табличном декодировании СК
наблюдается высокая сложность реализации кодека. Эффективность табличного
декодирования СК существенно повышается при перемежении кодовых
символов, в этом случае можно использовать СК, рассчитанные для коррекции
случайных ошибок.
6.4.5. Пороговое декодирование диффузных СК
Диффузные сверточные коды (ДФСК) обладают способностью
корректировать случайные и группирующиеся (пакетные) ошибки и,
следовательно, наиболее приемлемы для реальных каналов. Коррекция
независимых и пакетных ошибок ДФСК осуществляется на большей длине
кодового ограничения, чем у обычных СК По способу построения ДФСК могут
быть как ортогонализируемыми, так и самоортогональными, низкоскоростными и
высокоскоростными.
Принципиальное отличие ДФСК с ПД, разработанных Месси, состоит в
изменении структуры "коротких" кодов с целью обеспечения коррекции пакетных
ошибок. Однако используемый способ изменения структуры "коротких" кодов
Месси принципиально отличается от перемежения кодовых символов. Известно
достаточно много способов построения ДФСК с ПД. Один из них состоит в
увеличении расстояния между информационными символами, участвующие в
формировании проверочных символов. Это достигается с помощью увеличения
разности между показателями степеней ненулевых членов порождающих
полиномов.
В общем случае ДФСК может быть построен следующим образом:
1) первоначально строится СК, корректирующий одиночные пакеты ошибок
кратностью t
n
двоичных символов (бит) и формируются (J≥2) проверочных
уравнений для каждого информационного символа;
2) данный СК модифицируется для коррекции независимых ошибок
кратностью t
н
< J/2 двоичных символов (бит).
В таблице 6.1 представлены некоторые самоортогональные ДФСК,
полученные Тонгом.
Таблица 6.1.Самоортогональные ДФСК
R J
t
н
(бит)
t
n
(бит)
Порождающие поли-
номы
n
A
(бит)
2
-
3
4
6
2
3
3
7
x
0
+x
b
+x
4b
+x
8b+3
=
=1+x
3
+x
12
+x
27
x
0
+x
2b
+x
6b+1
+x
7b+2
=
=1+x
6
+x
19
+x
23
x
0
+x+x
b+2
+x
4b+7
x
10b+10
=
1+x+x
35
+x
47
+x
30
x
0
+x
2
+x
2b+2
+x
6b+4
+
+x
7b+4
+x
9b+7
=
=1+x
2
+x
16
+x
46
+x
53
+x
70
3(8b+4)=81
3(10b+1)=234
1
-
2
3
4
1
2
1
2
x
0
+x
b
+x
3b
=1+x+x
3
x
0
+x
b
+x
3b
+x
4b+1
=
=1+x+x
3
+x
5
2(3b+1)=8
2(4b+2)=20
3
-
4
4
2
6
x
0
+x
b
+x
6b
+x
9b+2
=
=1+x
6
+x
36
+x
56
x
0
+x
2b
+x
11b+3
+x
12b+5
=
=1+x
12
+x
69
+x
77
x
0
+x+x
4b
+x
7b
+x
8b+1
=
=1+x
24
+x
42
+x
49
4(12b+6)=320
В таблице 6.2 представлены параметры лучших ДФСК по критерию
минимальной длины кодового ограничения.
Таблица 6.2.Модифицированные ДФСК
Ниже рассматривается задание ДФСК с R=2/3 и построение
соответствующего кодека. Обобщенная структурная схема проверочной матрицы
ДФСК имеет вид:
Проверочная матрица ДФСК имеет полубесконечную форму, состоящую из
прямоугольников (В
0
), высота которых равна N=m+1, где m - максимальная
R J
t
н
(бит)
t
n
(бит)
Порождающие пол
и-
номы
n
A
(бит)
2
-
3
4
5
2
2
3
5
x
0
+x
5
+x
16
+x
22
=
=1+x
5
+x
16
+x
22
x
0
+x
9
+x
12
+x
19
=
=1+x
9
+x
12
+x
19
1+x
14
+x
31
+x
36
+x
47
1+x
7
+x
20
+x
26
+x
41
69
144
1
-
2
4
5
2
2
2
3
x
0
+x
b
+x
2b+1
+x
2b+1
=1+x
2
+
x
5
+x
11
x
0
+x
b
+x
2b+1
+x
3b+3
+x
4b+6
=
=1+x
3
+x
7
+x
12
+x
18
24
38
3
-
4
4
2
5
1+x
12
+x
23
+x
48
1+x
6
+x
28
+x
43
1+x
17
+x
33
+x
38
196
B
0
B
0
B
0
B
0
n
0
=b
l=η
H
∞
(x)=
.
степень порождающих полиномов, n
0
-длина блока кодовой последовательности
Т(х), l=η - количество проверочных символов, входящих в блок n
0
кодовых
символов. Ненулевые символы проверочной матрицы, определяющие количество
и структуру ортогональных и самоортогональных проверочных уравнений,
находятся в заштрихованных областях прямоугольников В
0
.
Транспонированная проверочная матрица ДФСК содержит единичные
подматрицы; например матрицы рангом (n
0
*n
0
), (n
0
о*2n
0
) имеют вид:
Диффузные СК с матрицей размерности (n
0
*n
0
) могут корректировать как
независимые ошибки, так и пакетные ошибки. Проверочная матрица,
соответствующая одному прямоугольнику В
0
, для СК с R=2/3, корректирующего
одиночную ошибку и одиночный пакет кратностью t
n
=7 бит имеет вид:
Проверочные матрицы ДФСК эффективнее задавать в виде матриц
00...01
00...10
....
....
....
01...00
10...00
00...01
00...00
00...10
....
....
01...00
00...00
10...00
....
....
00...00
n
0
n
0
n
0
.
(6.15)
2
⋅
n
0
(6.16)
==
001
000
010
000
100
000
001
010
100
)(
0
BxH
.
треугольного вида, которые наглядно позволяют определить параметры кодов,
порождающий многочлен, количество кодовых символов, одновременно
участвующих в определении достоверности t
n
-l=( n
0
-1) информационных
символов, коэффициент перемежения проверок или коэффициент диффузности
кода (или интервал разнесения информационных символов, участвующих в
формировании проверочных символов) Для вышеприведенной проверочной
матрицы проверочный треугольник выглядит следующим образом:
001
010 001
100 010 001
000 100 010 001
A
N
=001 000 100 010 001 (6.17)
000 001 000 100 010 001
010 000 001 000 100 010 001
000 010 000 001 000 100 010 001
100 000 010 000 001 000 100 010 001.
Формируемую кодовую последовательность можно представить в виде:
в которой первый кодовый символ блока t
1
(1)
отстоит на t
n
символов от первого
символа второго блока, что позволяет эту зависимость записать так:
Это означает, что в кодовой последовательности T
(j)
(x) I(x)=R⋅T
(i)
(x)
символов являются информационными:
Для ДФСК с R=2/3 последнее выражение имеет вид:
Если предположить, что имеется ДФСК с R=2/3 и используются следующие
),,t,,t,t,t,,t,(t(x)T
(b)
1
(2)
1
(1)
1
(b)
0
(2)
0
(1)
0
(i)
KKK=
].tttt[tt
(1)
8i
(2)
6i
(3)
4i
(1)
2i
(2)
1i
(3)
1 −−−−−
++++−=
∑
=
⋅+⋅−=
2
1j
(2)(2)(1)(j)(3)
(x)].G(x)I(x)G(x)(I[(x)T
1,2,...k
0
.
j
(x);
(j)
I
(x)
(j)
T
=