Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
3. По заданной преподавателем порождающей матрице G(x) построить
проверочную матрицу H(x). Определить параметры кода.
4. Сформировать кодовую последовательность с использованием заданного
преподавателем информационного блока Q(x) и порождающей матрицы G(x).
Определить класс кода.
5. Сформировать и пояснить сущность проверочных уравнений по заданной
проверочной матрице H(x).
6. Дать определение и пояснить сущность дуального кода.
7. Дать определение и пояснить сущность эквивалентного кода.
8. Дать определение и пояснить сущность кодов максимальной длины.
9. Дать определение и пояснить сущность ортогонального и
биортогонального кода.
10. По проверочной матрице
=
1
1
0
)x(H
1
1
1
1
0
1
0
1
1
0
0
1
0
1
0
1
0
0
определить минимальное
кодовое расстояние и кратность корректируемых ошибок.
11. Доказать, что двоичный линейный блоковый код исправляет любые
одиночные ошибки тогда и только тогда, когда все столбцы его проверочной
матрицы ненулевые и различные. Верно ли это утверждение для любого
двоичного линейного кода?
12. Как изменится минимальное кодовое расстояние двоичного линейного
блокового кода при добавлении ко все его строкам порождающей матрицы одного
проверочного символа?
13. Дать геометрическую интерпретацию СБЛК с параметрами
(n,k,d
0
)=(3,2,2). Определить его корректирующие свойства.
14. Определить R, l, r, t
исп
и t
обн
для СЛБК с параметрами (n,k,d
0
)=(3,1,3) и
дать его геометрическую интерпретацию.
3. ЦИКЛИЧЕСКИЕ КОДЫ: ОПРЕДЕЛЕН
ИЕ, ОСНОВНЫЕ
СВОЙСТВА И ПРИНЦИПЫ ПОСТРОЕНИЯ
3.1. Определение и основные свойства циклических кодов
Важнейшим недостатком СБЛК, как отмечалось выше, является высокая
трудоемкость их построения при длине кодовой последовательности n≥31 дво-
ичный символ и коррекции ошибок кратностью t
ош
≥3
двоичных символа. Поиск
более простых принципов построения СБЛК привел к открытию нового широ-
кого класса групповых линейных блоковых кодов, получивших название цик-
лических кодов (ЦК). Основоположником ЦК является Прейндж [6]. Дальней-
шее развитие теория построения ЦК получила в работах Боуза, Чоудхури, Хок-
вингейма, Файра, Рида-Соломона, Гоппы и др.
Циклические коды являются подклассом в классе линейных блоковых
кодов, удовлетворяющих определенным требованиям. Свое название данные
коды получили по причине того, что основной операцией построения кодовых
последовательностей (F
i
(x)) является цикл, а точнее циклическая перестановка
двоичных символов разрешенных кодовых последовательностей [4,6].
В соответствии с [3,4,6] циклическим кодом называется линейный блоко-
вый код, который представляет собой конечное множество, замкнутое относи-
тельно операции циклического сдвига кодовых последовательностей, образую-
щих данный код. С математической точки зрения ЦК является идеалом в ли-
нейной коммутативной алгебре многочлена (полинома) n-го порядка по моду-
лю двучлена x
n
-1 над полем коэффициентов. Это означает, что кодовые после-
довательности ЦК имеют длину “n” двоичных кодовых символов и описывают-
ся полиномами степени (n-1), в которых коэффициентами при соответствую-
щих степенях формальной переменной, обозначаемой через “x”, являются дво-
ичные символы кодовой последовательности. Формальная переменная “x”, ко-
торая носит название оператора Хаффмана или оператора задержки и не оказы-
вает никакого влияния на свойства кода. Таким образом, кодовую последова-
тельность ЦК в общем виде можно записать так:
F
i
(x)=c
n-1
⋅x
n-1
+ c
n-2
⋅x
n-2
+…+c
1
⋅x
1
+ c
0
⋅x
0
, (3.1)
где x – форменная переменная,
n-1, n-2 ,…, 1, 0 – показатели степеней, в которые возводятся основания
кодов, и одновременно порядковые номера, которые занимают двоичные сим-
волы (разряды) кодовой последовательности, начиная со старшего и заканчивая
нулевым;
c
i
– коэффициенты формальной переменной, которые могут принимать
или быть равными логической 1 (ненулевой член F
i
(x)) или логического 0 (ну-
левой член F
i
(x)). Например; F
i
(x)=1⋅x
4
+0⋅x
3
+0⋅x
2
+1⋅x
1
+0⋅x
0
=x
4
+x=10010.
Представление кодовых последовательностей в виде многочленов позво-
ляют установить однозначное соответствие между ними и свести действия над
кодовыми последовательностями к действиям над полиномами: умножение,
сложение, деление и вычитание этих полиномов производится по обычным
правилам алгебры, но коэффициенты с одинаковыми степенями “x” суммиру-
ются по модулю два. Например; F
i
(x)=(x
3
+x
2
+1)⋅F
j
(x)=(x+1)=x
4
+x
3
+x
3
+x
2
+x+1=
=x
4
+((1+1)mod2)⋅x
3
+x
2
+x+1=x
4
+0⋅x
3
+x
2
+x+1=x
4
+x
2
+x+1.
Уточним сущность понятия циклического сдвига или циклической пере-
становки двоичных символов кодовой последовательности. Пусть F
i
(x)=c
n-1
x
n-1
+
+c
n-2
x
n-2
+…+c
1
x
1
+c
0
x
0
, то циклический сдвиг на один разряд дает
F
i
(x)=c
n-1
x
n
+c
n-2
x
n-1
+…+c
1
x
2
+c
0
x
1
. Чтобы степень новой кодовой последователь-
ности F
i
(x) не превышала (n-1), член c
n-1·
x
n
заменяется единицей, поэтому
F
i
(x)=c
n-2
x
n-1
+ c
n-3
x
n-2
+…+c
1
x
2
+c
0
x+ c
n-1
x
0
.
Например, пусть F(x)=x
5
+x
3
+x
2
+x=0101110, при n=7 двоичных символов.
(Заметим, что запись кодовой последовательности в виде многочлена, а затем
перевод ее в двоичную форму записи, не всегда определяет длину кодовой по-
следовательности “n”. Например, при n=5, многочлен F(x)=x
2
+1=101, т.е. n=3,
что неверно. В таких случаях надо дописать старшие нулевые символы, т.е.
F(x)=x
2
+1=00101, что дает n=5 двоичным символам).
Сдвигаем F(x) на один разряд (символ) влево, и получаем
F(x)=1011100=x
6
+x
4
+x
3
+x
2
. Очевидно, что x
1
(x
5
+x
3
+x
2
+x)=x
6
+x
4
+x
3
+x
2
. Отсюда
вытекает второе определение ЦК, а именно, циклический сдвиг двоичных сим-
волов разрешенной кодовой последовательности влево или вправо на один,
два,…, (k-1) символов вновь приводит к формированию разрешенной кодовой
последовательности.
Таким образом, циклическую перестановку двоичных символов разре-
шенной кодовой последовательности можно рассматривать как умножение F(x)
на “x” при первом сдвиге, на “x
2
” при втором сдвиге и т. д., что можно в общем
виде записать или представить так:
⋅
⋅
⋅
−
)x(Fx
.
.
.
)x(Fx
)x(Fx
)x(F
1k
2
. (3.2)
Последний вывод можно рассматривать еще следующим образом: так как
при сложении по модулю два двучлен x
n
-1 можно записать как x
n
=1, то замена
x
n
на 1 в произведении x⋅F(x) дает новый многочлен, коэффициенты которого
образуют новую разрешенную кодовую последовательность. Следовательно, в
кодовой последовательности, имеющей длину “n” двоичных кодовых символов,
степень полинома не может превышать n-1, так как в противном случае длина
кодовой последовательности превысит “n”, а поэтому x
n
заменяется логической 1.
Таким образом, можно сделать следующие выводы:
1. ЦК – это такой линейный код, который обладает свойством цикличности ко-
довых последовательностей, т.е. когда каждая разрешенная кодовая последова-
тельность содержит ее циклическую перестановку;
2. ЦК относятся к групповым линейным кодам, если они образуются путем
умножения каждой последовательности равнодоступного (простого) кода, вы-
раженных в виде многочлена Q(x) с максимальной степенью (k-1), на некото-
рой полином P(x) степени l=n-k. Приведение подобных членов производится по
модулю два; порядок поля кодирования преобразуется с K
раз
=2
k
до K
общ
=2
n
, но
число разрешенных кодовых последовательностей кода при этом остается рав-
ным K
раз
=2
k
, и они образуют циклическую подгруппу группы K
общ
=2
n
, отли-
чающуюся тем, что все элементы подгруппы имеют общее свойство делимости
на полином P(x), получивший название образующего или порождающего поли-
нома.
В соответствии с [3,4,6] в качестве образующего полинома используются
полиномы, обладающие следующими свойствами:
− во-первых, образующий полином P(x) должен быть делителем двучлена
x
n
+1;
− во-вторых, образующий полином не должен раскладываться на сомножите-
ли более низких степеней, и делиться без остатка на самого себя и на 1, т.е. на x
0
;
− в-третьих, максимальная степень образующего полинома должна быть рав-
ной l=n-k, т.е. соответствовать количеству проверочных символов используемо-
го кода.
Так как ЦК являются дальнейшим развитием групповых СБЛК, то дан-
ные коды обладают всеми свойствами СБЛК, а так же имеют, ряд дополнитель-
ных свойств.
К основным свойствам ЦК относятся:
1. Вес (w
к.п.
) разрешенной кодовой последовательности ≥ d
0
;
2. Вес проверочной части w
пр.ч.
разрешенной кодовой последовательности ≥ d
0
-1;
3. Сдвиг кодовых символов разрешенной кодовой последовательности влево
или вправо на один, два,…, (k-1) символ вновь приводит к разрешенной кодо-
вой последовательности. Если же при циклическом сдвиге всегда будет полу-
чатся новая кодовая последовательность, то такой код будет называться квази-
циклическим; данные коды имеют несколько большую корректирующую спо-
собность и сложность реализации, чем ЦК;
4. Разрешенная кодовая последовательность без ошибок F
р
'(x) при делении на
полином P(x) дает нулевой остаток, т.е. F
р
'(x)/P(x)=R(x)=0 и R(x) не равно 0 –
при наличии ошибок;
5. Сумма по модулю два символов двух, трех,…, (k-1) разрешенных кодовых
последовательностей вновь образует разрешенную кодовую последователь-
ность;
6. Двучлен вида x
n
+1 должен делиться на порождающий полином P(x) без ос-
татка (имеется в виду обычная операция деления многочленов);
7. Если все операции над полиномами (кодовыми последовательностями) про-
водятся в двоичном поле Галуа (GF(2)), т.е. действия над коэффициентами по-
линомов осуществляется по модулю два, а умножение полиномов производится
по модулю образующего полинома P(x), то применение указанных операций не
приводит к кодовым последовательностям, длина которых больше длины за-
данного кода, т.е. “n”;
8. Результат деления двучлена x
n
+1 на образующий полином P(x) дает поли-
ном, который носит название проверочного полинома и обозначается как h(x),
т.е. h(x)=(x
n
+1)/P(x) и который в теории и практике помехоустойчивого кодиро-
вания играет важную роль. Произведение h(x)⋅P(x)=x
n
+1=0, а потому многочле-
ны h(x) и P(x) рассматривается как ортогональные и операция деления
(x
n
+1)/P(x) ипользуется в основе построения алгоритмов декодирования;
9. Двучлен ЦК вида x
n
-1 можно разложить на множители
x
n
-1=(x-1)(x
n-1
+ x
n-2
+…+1), (3.3)
которые можно использовать в качестве образующих полиномов ЦК с n=const,
k=var и d
0
=var.
Например, разложить двучлен x
n
-1=x
7
-1 на множители вида (3.3) и опре-
делить образующие полинома и параметры кодов.
Решение: двучлен x
7
-1 раскладывается на следующие многочлены:
x
7
-1=(x-1)(x
3
+x
2
+1)(x
3
+x+1) (3.4)
Из данного выражения видно, что можно образовать шесть делителей для
двучлена x
7
-1, путем комбинирования полученных трех сомножителей (3.3).
Следовательно, для двучлена x
7
-1 существует шесть разных двоичных линей-
ных ЦК со следующими образующими полиномами и параметрами:
P
1
(x)=(x-1)=(x+1); l=1, n=7, k=6, d
0
=1 – простой код: l, k, n и t
исп
(t
исп
– кратность
исправленных ошибок) – измеряются в двоичных символах;
P
2
(x)=(x
3
+ x
2
+1); l=3, n=7, k=4, d
0
=3, t
исп
=1;
P
3
(x)=(x
3
+ x
2
+1); l=3, n=7, k=4, d
0
=3, t
исп
=1;
P
4
(x)=P
2
(x)⋅P
3
(x)=(x
4
+x
3
+x
2
+1); l=4, n=7, k=3, d
0
=4, t
исп
=1;
P
5
(x)=P
2
(x)⋅P
3
(x)=(x
4
+x
2
+x+1); l=4, n=7, k=3, d
0
=4, t
исп
=1;
P
6
(x)=P
1
(x)⋅P
5
(x)=(x
6
+x
5
+x
4
+ x
3
+x
2
+x+1); l=6, n=7, k=1, d
0
=7, t
исп
≤3.
ЦК, задаваемые образующими полиномами P
1
(x), P
2
(x) и P
3
(x), относятся
к классу ЦК Хэмминга. ЦК, задаваемые полиномами P
4
(x), P
5
(x) и P
6
(x), явля-
ются двойственными кодами Хэмминга и называются кодами максимальной
длины (КМД).
Известно [1…4], что корректирующая способность групповых СБЛК су-
щественно зависит от вида (структуры) образующего полинома, т.е. от количе-
ства ненулевых членов данного полинома и его максимальной степени l=n-k. В
соответствии с этим можно отметить следующие свойства ЦК:
а) обнаруживающих ошибки:
− ЦК, образующий полином которого имеет более одного члена и не имеет
общего множителя “x”, обнаруживает все одиночные ошибки и любое нечетное
число ошибок. Простейшим образующим полиномом ЦК, обладающими дан-
ными свойствами, является полином вида P(x)=1+x;
− ЦК, образующий полином которого имеет вид P(x)=1+x
c
, обнаруживает лю-
бое нечетное число ошибок. Доказательство этого утверждения становится яс-
ным, если образующий полином представить в следующем виде
P(x)=1+x
c
=(1+x)⋅(1+x+x
2
+…+x
c-1
).
б) обнаруживающих и корректирующих ошибки:
ввиду того, что полином P(x)=1+x
c
нацело делится на 1+x, то согласно
предыдущему свойству ЦК обеспечивает обнаружение любого нечетного коли-
чества ошибок;
− ЦК, образующий полином которого имеет максимальную степень l=n-k, об-
наруживает любой пакет ошибок длиной t
пак.обн.
=l и менее двоичных символов
или корректирует пакеты ошибок длиной t
пак.исп.
= l/2 двоичных символов;
− количество пакетов длиной l+1, не обнаруживаемых ЦК, составляет 1/2
l-1
части всех пакетов (l+1) двоичных символов. Количество пакетов ошибок дли-
ной более l+1, необнаруживаемых ЦК, составляет часть всех пакетов ошибок
длиной от (l+2) до “n” двоичных символов включительно. Доказательство дан-
ных утверждений свойств ЦК можно найти в [4,6].
3.2. Матричное представление циклических кодов корректирую-
щие независимые ошибки
3.2.1. Способ построения кодовых последовательностей с использо-
ванием порождающей матрицы
Кодовая последовательность ЦК при заданной порождающей матрице
G
k,n
(x) и заданном информационном блоке Q(x) формируется по правилу
F(x)= Q(x)⋅G
k,n
(x), т.е. произведения вектора-строки Q(x), содержащего “k” ин-
формационных двоичных символов, на порождающую матрицу G(x) рангом
(k×n). При этом, если используется каноническая (приведенно-ступенчатая)
G(x), то будут формироваться кодовые последовательности систематического
разделимого ЦК. Порождающая матрица G(x) строится довольно просто, если
задан образующий полином P(x) и длина кодовой последовательности “n”. Рас-
смотрим следующие примеры на матричное представление ЦК.
Пример 3.1. Сформировать кодовую последовательность ЦК с парамет-
рами (n,k,d
0
)=(10,5,5), если P(x)=x
5
+x
4
+x
2
+1.
ΏηάΰΩξΣβάΩ
:
Решение: переводим P(x) из записи в форме полинома в двоичную форму
записи, т.е. P(x)= x
5
+x
4
+x
2
+1=110101. Далее формируем первую строку порож-
дающей матрицы G
5.10
(x) следующим образом: двоичную последовательность
110101 дополняем справа четырьмя нулями; в результате получаем разрешен-
ную кодовую последовательность вида 1101010000 длиной n=10 двоичных
символов. Следующий шаг – выполнение (k-1)=(5-1)=4 циклических сдвига
двоичных символов первой строки G(x).
В результате получаем следующую порождающую матрицу
=
1010110000
0101011000
0010101100
0001010110
0000101011
)x(G
10,5
. (3.5)
Этот способ построения порождающей матрицы G
5.10
(x) можно рассмот-
реть со следующей позиции:
а) переводим P(x) из записи в форме полинома в форму двоичной после-
довательности (можно и не переводить), т.е. P(x)=x
5
+x
4
+x
2
+1=110101;
б) умножаем P(x)=110101 на одночлен вида x
k-1
, т.е. на 1000; в результате
получаем первую строку или первую разрешенную кодовую последователь-
ность 1101010000, а далее используем рассмотренную методику, т.е. цикличе-
ский сдвиг двоичных символов первой строки (k-1) раз.
В общем случае построение порождающей матрицы G(x) ЦК с использо-
ванием образующего полинома можно записать так:
⋅⋅⋅⋅⋅⋅
⋅⋅
⋅⋅
⋅⋅
⋅⋅⋅⋅⋅⋅
⋅⋅⋅⋅⋅⋅
→
⋅
⋅⋅
⋅⋅
⋅⋅
⋅
⋅
=
−
−
−
−
i1i10
011ii
011ii
1k
2
qqqq00
00qqqq0
00qqqq
0)x(Px
0)x(Px
0)x(Px
0)x(P
)x(G
, (3.6)
где q=0;1 – коэффициенты образующего полинома, которые могут при-
нимать значение либо 0, либо 1,
0 – нулевые символы, дополняющие каждую строку до значения “n” дво-
ичных символов.
Формирование кодовой последовательности F(x), т.е. процесс кодирова-
ния информации с помощью G(x) осуществляется по правилу
F(x)=Q(x)⋅G(x):первый символ Q(x) умножаем на первый символ первого
столбца G(x), второй символ Q(x) умножаем на второй символ первого столбца
G(x) и суммируем по модулю два с первым результатом, третий символ Q(x)
умножаем на третий символ первого столбца G(x) и суммируем по модулю два
с предыдущем результатом и т. д. Затем первый символ Q(x) умножаем на пер-
вый символ второго столбца G(x) и далее все повторяется аналогично форми-
рованию первого кодового символа F(x).
Пример 3.2. Рассмотрим способ формирования кодовых последователь-
ностей ЦК с использованием единичной матрицы и остатков от деления
x
n-1
/P(x).
Для рассмотрения сущности формирования кодовых последовательно-
стей ЦК используем данные предыдущего примера.
Так как k=5, то используем следующие единичные векторы: Q
1
(x)=10000,
Q
2
(x)=01000, Q
3
(x)=00100, Q
4
(x)=00010 и Q
5
(x)=00001. Записываем
Q
1
(x)…Q
5
(x) в виде единичной подматрицы рангом (5×5).
=
1100110000
1100001000
1101000100
1111100010
1010100001
)x(G
10,5
.
Далее определяем проверочные символы каждой строки по следующей
методике: делим x
n-1
/P(x) и берем остатки от деления для первой строки – от
первого такта деления, т.е. R
1
(x), для второй строки – после двух тактов деле-
ния, т.е. R
2
(x) и т. д. Полученные символы дописываем к соответствующим
строкам единичной подматрицы: