Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
10101
1)(
)(
245
91
1
=
+++
==
−
xxx
x
xP
x
xR
n
, R
2
(x)=11111, R
3
(x)=01011, R
4
(x)=00011 и
R
5
(x)=10011.
Формирование кодовых последовательностей осуществляется по прави-
лу, приведенному в примере 3.1, т.е. F(x)=Q(x)⋅G
5.10
(x).
3.2.2. Назначение и способы построения проверочной матрицы цикличе-
ского кода
Проверочные матрицы ЦК могут использоваться для выбора как спосо-
бов кодирования информации, так и алгоритмов декодирования. Проверочные
матрицы ЦК могут быть построены с использованием порождающей матрицы
G
k,n
(x), единичной матрицы проверок и проверочного полинома h(x).
Сущность способа построения проверочной матрицы H
l,n
(x) с использо-
ванием канонической порождающей матрицы G
k,n
(x) состоит в следующем.
Пусть задана следующая каноническая порождающая матрица ЦК с па-
раметрами (n,k,d
0
)=(7,4,3) вида:
a
1
a
2
a
3
a
4
a
5
a
6
a
7
. (3.7)
.
=
0110001
1100010
1110100
1011000
)x(G
7,4
=
0010111
0101110
1001011
)x(H
7,3
Первый столбец проверочной матрицы H
3,7
(x) для данного кода записы-
ваем, используя проверочные символы первой строки G
4,7
(x), второй, третий и
четвертый столбцы H
3,7
(x) формируем путем записи проверочных символов
второй, третьей и четвертой строк G
4,7
(x), а далее записываем три столбца еди-
ничной подматрицы. В результате получаем следующую проверочную матрицу
(3.7). Ненулевые символы строк проверочной матрицы определяют позиции
информационных символов, участвующие в формировании проверочных урав-
нений. Так для построенной проверочной матрицы H
3,7
(x) можно сформулиро-
вать следующие три проверочных уравнения: b
1
=a
1
⊕a
2
⊕a
3
, b
2
=a
2
⊕a
3
⊕a
4
,
b
3
=a
1
⊕a
2
⊕a
3
.
Принцип построения проверочной матрицы с использованием единичной
подматрицы и остатков от деления аналогичен принципу построения порож-
дающей матрицы. Количество остатков от деления x
n
+1 на P(x) должно быть
равно количеству строк единичной подматрицы.
Сущность принципа построения проверочной матрицы ЦК с использова-
нием проверочного полинома h(x) состоит в следующем. Первоначально опре-
деляем проверочный полином как отношение x
n
+1 на P(x), т.е. h(x)=x
n
+1/P(x).
Полученный полином переводим в двоичную форму записи, записываем в виде
первой строки проверочной матрицы H
l,k
(x) и дополняем нулями до количества
столбцов, равное “n”. Далее выполняем (l-1) циклический сдвиг двоичных сим-
волов первой строки.
Пример 3.3. Построить проверочную матрицу ЦК с параметрами
(n,k,d
0
)=(7,4,3), если P(x)=x
3
+x
2
+1.
Решение:
1) определяем проверочный полином
1
1
1
)(
234
23
7
+++=
+
+
+
= xxx
x
x
x
xh
;
2) переводим в двоичную форму записи h(x)=11101;
3) записываем в виде первой строки H
3,7
(x) и дополняем двумя нулевыми сим-
волами до n=7;
4) выполняя (l-1)=(3-1)=2 циклических сдвига двоичных символов первой
строки H
3,7
(x) строим проверочную матрицуH
3.7
(x) следующего вида:
a1 a2 a3 a4 b1 b2 b3
;
=
1011100
0101110
0010111
)x(H
7,3
5) далее можно сформировать проверочные уравнения вида (нумерация пози-
ций двоичных символов строк проставлена вверху матрицы H
3,7
(x)),
b
1
=a
1
⊕a
2
⊕a
3
, b
2
=a
2
⊕a
3
⊕a
4
, b
3
=a
3
⊕a
4
⊕a
5
.
3.2.3. Способ формирования кодовых последовательностей цикличе-
ского кода с использованием образующего полинома
Данный способ формирования кодовых последовательностей ЦК находит
широкое применение на практике в виду его существенной простоты. При по-
строении ЦК с использованием образующего полинома P(x) могут быть сфор-
мированы кодовые последовательности как систематических, так и несистема-
тических кодов.
При формировании кодовых последовательностей несистематического
ЦК необходимо выполнить умножение передаваемого информационного блока
Q(x) степени (k-1) на порождающий полином с приведением по модулю два ко-
эффициентов при слагаемых с одинаковыми показателями степеней. Таким об-
разом, F
i
(x)=Q(x)⋅P(x).
Пример 3.4. Сформировать кодовую последовательность несистематиче-
ского ЦК с параметрами (n,k,d
0
)=(10,5,4), если P(x)=x
5
+x
4
+x
2
+x+1.
Решение:
1. выбираем информационный блок Q(x
) следующего вида
Q(x)=x
4
+x
2
+x=10110;
2. формируем кодовую последовательность по правилу
F(x)=Q(x)⋅P(x)=(x
4
+x
2
+x)⋅(x
5
+x
4
+x
2
+x+1)= x
9
+x
8
+x
7
+x
6
+x+1=1111000010.
В данной кодовой последовательности нет четкого (явного) деления на блоки
информационных и проверочных символов.
Сущность построения систематического ЦК с использованием образую-
щего полинома состоит в следующем:
1) передаваемый информационный блок из «k» двоичных символов представ-
ляется многочленом Q(x) степени (k-1);
2) многочлен Q(x) умножается на член P(x) с максимальной степенью x
l
=x
n-k
,
т.е. Q(x)⋅x
l
, что эквивалентно приписыванию к Q(x) со стороны младших разря-
дов l=n-k нулевых двоичных символов (разрядов);
3) выполняется деление произведения Q(x)⋅x
l
на образующий полином P(x) до
получения остатка R(x) со степенью меньшей максимальной степени образую-
щего полинома P(x). Данный остаток R(x) представляет собой сформированные
проверочные символы;
4) дописать остаток R(x) к произведению Q(x)⋅x
l
. Следовательно, процесс фор-
мирования кодовой последовательности ЦК с использованием образующего
полинома можно записать так:
F(x)= Q(x)⋅x
l
/P(x)+ Q(x)⋅x
l
=R(x)+ Q(x)⋅x
l
. (3.8)
Пример 3.5. Сформировать кодовую последовательность систематическо-
го ЦК с параметрами (n,k,d
0
)=(13,8,5).
Решение:
а) так как k
=8, то выбираем информационный многочлен
Q(x)=x
7
+x
5
+x
4
+x
2
+1, а максимальную степень образующего полинома принима-
ем равной l=n-k=13-8=5. Выбираем табулированный образующий полином вида
P(x)=x
5
+x
3
+1;
б) далее в соответствии с выше рассмотренными операциями получаем:
1) Q(x)⋅x
l
=Q(x)⋅x
5
= (x
7
+x
5
+ x
4
+x
2
+1)⋅x
5
= x
12
+ x
10
+ x
9
+ x
7
+ x
5
;
2) )(
1)(
)(
24
35
5791012
xRxx
xx
xxxxx
xP
xxQ
l
=+=
++
++++
=
⋅
;
3) следовательно, F(x)=R(x)+Q(x)⋅x
l
=x
2
+x
4
+x
5
+x
7
+x
9
+x
10
+x
12
=0010110101101;
старшие разряды (двоичные символы) кодовой последовательности представ-
лены справа.
3.2.4. Способ построения кодовых последовательностей и определе-
ние параметров циклического кода с использованием корней
образующего полинома
Как отмечалось выше, теория построения кодовых последовательностей и
определение параметров кодов с использованием корней образующего полино-
ма, была разработана одновременно и независимо друг от друга Боузе-Рой-
Чоудхури-Хоквингеймом и в настоящее время называются БЧХ – кодами.
Данные коды являются разновидностью ЦК и позволяют корректировать
как независимые, так и пакетные ошибки и параметры кодов находятся через
элементы расширенного поля Галуа, суть которого состоит в следующем [3,4,6,7].
Пусть P(x) является образующим полиномом кодовой последовательно-
сти F
i
(x) некоторого ЦК. Так как P(x) относится к примитивному полиному, т.е.
который не раскладывается на сомножители более низких степеней, чем сте-
пень полинома P(x), то можно, найти корни полинома при которых P(x)=0.
Пусть
12
,...,
2
,
1 −⋅
исп
t
mmm
– корни некоторого примитивного полинома, и
которые, в свою очередь, являются степенями некоторых минимальных (при-
митивных) полиномов соответственно:
)(
12
),...,(
2
),(
1
x
t
mxmxm
исп
−⋅
. Тогда, ес-
ли F
i
(x) принадлежит ЦК, то кодовая последовательность F
i
(x) должна делиться
без остатка на образующий полином вида )](
12
...)(
3
)(
1
[)( x
t
mxmxmHOKxP
исп
−⋅
⋅⋅⋅= ,
т.е. HOK произведения минимальных нечетных полиномов.
Порядок (количество) минимальных полиномов определяется как
i=2⋅t
исп
-1. Существуют минимальные полиномы одного и того же порядка (i), но
с различными значениями степеней (γ). Максимальная степень произведения
минимальных полиномов (m
i
), входящих в полином P(x), должна быть равна
величине l=n-k, которая и определяет длину кодовой последовательности по
формуле n=2
l
-1=2
ε
-1 двоичных символов.
Так как порядок (номер) самого старшего минимального полинома P(x)
равен 2⋅t
исп
-1, то количество полиномов (β), входящих в образующий полином
P(x), равно кратности исправляемых ошибок, т.е. β= t
исп.
Например, если t
исп
=5 двоичных символов, то 2⋅t
исп
-1=9 и в выражение
P(x) будут входить β=5 минимальных полиномов: m
1
(x), m
3
(x), m
5
(x), m
7
(x) и
m
9
(x). Минимальные полиномы для большинства БЧХ-кодов табулированы [3,4,7].
Для нахождения образующего полинома P(x) по формуле
)](
12
...)(
3
)(
1
[)( x
t
mxmxmHOKxP
исп
−⋅
⋅⋅⋅= необходимо выписать из таблицы все зна-
чения табулированных минимальных полиномов, соответствующих степени ε
(соответствующий столбец таблицы) до порядка i=2⋅t
исп
-1 (соответствующая
строка таблицы) включительно. При отсутствии в таблице минимального поли-
нома «нужного» порядка необходимо выбрать ближайший меньший, а если
среди минимальных полиномов окажется два одинаковых, то для выражения
P(x) необходимо взять только один полином.
Для определения параметров БЧХ-кода необходимо, чтобы было задано:
n – длина кодовой последовательности и t
исп
– длина или кратность исправляе-
мых ошибок.
Пример 3.6. Определить параметры БЧХ-кода корректирующего 2≤
исп
t -х
кратные ошибки на длине кодовой последовательности n=15 двоичных символов.
Решение:
а) из равенства-неравенства 12 −≤
ε
n определяем степень минимальных
полиномов, входящих в P(x); одновременно определяем номер столбца табули-
рованных корней образующего полинома [4,6]: n=15=2
ε
-1, откуда 16=2
ε
, а ε=4;
б) определяем порядок корней образующего полинома, т.е. i=2⋅t
исп
=
=2⋅2-1=3, что также определяет номер строки, (3-я строка) табулированных
корней образующего полинома;
в) из таблицы 4.1[4]для i=3-ей строки и ε=4-го столбца выписываем ми-
нимальные полиномы, которые заданы в восьмеричной форме записи, а имен-
но: m
1
(x)=23, m
3
(x)=37, которые будут иметь соответственно следующие степе-
ни: m
1
(x)=010011=x
4
+x+1, m
3
(x)=01111=x
4
+x
3
+x
2
+x+1. Следовательно,
P(x)=HOK[(x
4
+x+1)⋅(x
4
+x
3
+x
2
+x+1)]=x
8
+x
7
+x
6
+x
4
+1;
г) определяем количество проверочных символов, используя следующие
варианты:
1) 82)15(42)1(
0
=−=−= dl ε двоичных символов;
2) 824 =⋅=⋅≥
исп
tl ε двоичных символов;
3) l=8, т.е. равной максимальной степени P(x);
д) определяем число информационных символов как:
1) k=n-l=15-8=7 двоичных символов;
2) 72)15(4)12(2)1()12(
4
0
=−−−=−⋅−−= dk ε
ε
двоичных символов.
Таким образом, БЧХ-код будет иметь следующие параметры:
(n,k,d
0
)=(15,7,5) и P(x)=x
8
+x
7
+x
6
+x
4
+1.
В [3,6] приведены другие варианты построения БЧХ-кодов, как правило, с
21
≥
n двоичный символ. Кодирование и декодирование БЧХ-кодов может про-
изводится различными способами, которые рассматриваются в следующем раз-
деле.
В реальных системах связи широкое применение для коррекции одиноч-
ных пакетов ошибок получили ЦК, способ построения которых была разрабо-
тан Файром.
3.2.5. Способ построения кодовых последовательностей цикличе-
ского кода с использованием образующего полинома вида
P(x)=s(x)⋅(x
c
+1)
Способ задания ЦК с использованием образующего полинома вида
P(x)=s(x)⋅(x
c
+1) был предложен Файром и поэтому были названы кодами Файра.
Циклические коды Файра используются для обнаружения и коррекции
одиночных пакетов ошибок любой длины (t
n
), разделенных безошибочным ин-
тервалом в
)(
nзащ
tnl −≥
двоичных символов. Как уже отмечалось данные коды
задаются образующим полиномом вида [1…3]
P(x)=s(x)⋅(x
c
+1), (3.10)
где s(x) – неприводимый полином максимальная степень, которого равна
кратности исправляемого пакета ошибок, т.е.
n.исп
tε ≥ ;
c – степень двучлена, равная или больше t
n.исп
+t
n.обн
-1; t
n.обн
– длина или
кратность обнаруживаемого пакета ошибок.
Величина “c” не должна делиться на некоторое числоχ=2
t
n.исп
-1. Если ис-
пользовать ЦК Файра только для обнаружения пакетных ошибок, то для этого
необходимо, чтобы количество проверочных символов кода соответствовало
следующему равенству-неравенству
обнn
tl
.
≥
двоичных символов, а при коррек-
ции t
n
ошибок
испn
tl
.
2⋅≥
.
Длина кодовой последовательности “n” данных кодов определяется ра-
венством n=HOK[χ,c] двоичных символов. Минимальное кодовое расстояние
кода определяется равенством-неравенством вида 1
..0
++≥
обнnиспn
ttd .
Пример 3.7. Рассчитать параметры ЦК Файра корректирующего пакет
ошибок кратностью
3
.
≤
испn
t
двоичных символов и обнаруживающего пакет
ошибок кратностью
4
.
≤
обнn
t
двоичных символа.
Решение:
а) выбираем неприводимый полином s(x) степени 3==
n.исп
tε , т.е. s(x)=x
3
+x+1;
б) определяем степень “с” двучлена (x
c
+1) по формуле c=t
n.исп
+t
n.обн
-1=
=3+4-1=6;
в) вычисляем образующий полином по формуле P(x)=s(x)⋅(x
c
+1)=
=(x
3
+x+1)⋅(x
6
+1)=x
9
+x
7
+x
6
+x
3
+x +1;
г) определяем количество проверочных символов по формуле
936
=
+
=
+
≥
tcl двоичных символов, что равно максимальной степени обра-
зующего полинома P(x);
д) вычисляем величину χ по формуле χ=2
tn.исп
-1=2
3
-1=7;
е) определяем длину кодовой последовательности кода, т.е. n=HOK[χ,c]=
=HOK[7,6]=42 двоичных символа;
ё) определяем количество информационных символов как k=n-l=42-9=33
двоичных символа;
ж) находим минимальное кодовое расстояние кода по формуле
81431
..0
=++=++≥
обнnиспn
ttd .
Таким образом, циклический код Файра имеет следующие параметры
(n,k,d
0
)=(42,8,33) и P(x)=x
9
+x
7
+x
6
+x
3
+x +1. Дополнительные сведения, а также
принципы построения кодирующего и декодирующего устройства ЦК Файра
приводятся в разделе 5.3.
Контрольные вопросы и задачи
1. Дать определение циклическому коду и пояснить его сущность.
2. Перечислить основные свойства циклических кодов и пояснить их сущ-
ность.
3. Дать определение и перечислить основные свойства образующих поли-
номов. Записать образующий полином, заданный в восьмеричный форме, на-
пример, как 771.
4. Разложить двучлен вида (x
10
-1) на сомножители и определить парамет-
ры кода с максимальной корректирующей способностью.
5. Назначение и способы построения порождающих матриц.
6. Назначение и способы построения проверочных матриц.
7. По заданному преподавателем “n” и P(x) построить порождающую и
проверочную матрицы.
8. По заданному преподавателем “n” и P(x) сформировать кодовую
последовательность несистематического циклического кода.
9. Сформировать кодовую последовательность систематического цикли-
ческого кода с параметрами (n,k,d
0
)=(15,10,4) и P(x)=x
5
+x+1.
10. Доказать, что циклический код с параметрами (n,k)=(10,5) и
P(x)=x
5
+x
4
+x
2
+x+1 корректирует пакеты ошибок кратностью t
пак
=2 двоичных
символов.
11. По заданной преподавателем проверочной матрице определить пара-
метры кода n, k, d
0
, t
исп
и сформировать проверочные уравнения.
12. Доказать, что кодовая последовательность F(x)=x
12
+x
10
+x
9
+x
7
+x
5
+x
4
+x
2
является разрешенной кодовой последовательностью циклического кода с па-
раметрами (n,k)=(13,8) и P(x)=x
5
+x
3
+1.
13. Рассчитать параметры циклического кода БЧХ-кода, если n=31 двоич-
ный символ, а кратность исправляемых ошибок 3≤
исп
t двоичных символа.
14. Рассчитать параметры циклического кода Файра корректирующего па-
кеты ошибок кратностью 4
.
≤
исппак
t двоичных символа.
15. Назвать и пояснить наиболее целесообразные области применения
БЧХ-кодов и циклических кодов Файра.