ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 302
Скачиваний: 7
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
8.7.1. Линейно зависимые и независимые векторы
Определение 8.24. Векторы ????
0
, ????
1
, … , ????
????−1
из
???? называются линейно зависимыми, если в ???? существуют такие элементы ????
0
, ????
1
, … , ????
????−1
, для которых
????
0
????
0
+????
1
????
1
+ ⋯ + ????
????−1
????
????−1
= 0, и линейно независимыми, когда
????
0
????
0
+ ????
1
????
1
+ ⋯ + ????
????−1
????
????−1
≠ 0.
Наглядно условие линейной независимости векторов над полем ???? можно изобразить как
????
0
????
1
… ????
????−1
Здесь ????
????
∈ ????. Для двоичных кодов ????
????
∈ {0,1} линейная независимость озна- чает, что суммирование базисных двоичных векторов не образует нулевой век- тор. Максимальное число линейно независимых векторов в ???? называется размер- ностью пространства ???? над полем ????.
8.8. Задания для самостоятельного выполнения
1. Показать, что группа
???? = <{0,1, 2, 3, 4, 5}; +; 0> содержит подгруппы порядков: 1, 2, 3 и 6.
2. Показать, что множество
????
′
= {0, 2, 4} – это подкольцо кольца <
{ℤ
6
= 0, 1, 2, 3, 4, 5 }; +;⋅; 0; 1 >.
3. Задано кольцо целых чисел
ℤ. Построить главный идеал, порожденный целым числом 12.
4. Найти главный идеал пересечения множеств
< 8 > ∩ < 12 >.
5. Найти примитивные элементы расширенного поля Галуа
????????(2 4
).
6. Привести четыре формы представления элементов поля
????????(2 4
). Поле образовано неприводимым над полем ????????(2) полиномом ????(????) = 1 + ???? + ????
4 7. Поле образовано полиномами над полем
????????(2) по модулю неприводи- мого полинома ????(????) = 1 + ???? + ????
3
. Вычислить:
011 0
????
0
∙
+ ????
1
∙
+…
+. . . + ????
????−1
∙
…
≠
156 а) полином, обратный полиному ???? = 1+ α + α
2
; б) полином, обратный полиному ???? = α + α
2
; в) ???? ????
⁄ ; г) √????; д) (111)
−1
157
9. ЛИНЕЙНЫЕ КОДЫ
9.1. Линейные коды, исправляющие ошибки: построение и основные
свойства
Определение 9.1. Линейный [n, k, d]-код есть подпространство размерно- стью k линейного n-мерного пространства над ????????(????) = ????????(????
????
). Подмножество, состоящее из ????
????
последовательностей длиной n, называется q-ичным блоковым кодом длиной n.
Замечания:
1. Если q = 2, то в качестве кодового алфавита используются символы дво- ичного {0, 1} алфавита. Пространство кода над полем ????????(2) образует аддитив- ную подгруппу группы всех двоичных последовательностей длиной n. Оче- видно, что для этой подгруппы должны выполняться все аксиомы группы, и для нее определена одна основная операция – сложение.
2. Так как операция суммирования является линейной операцией, то и код называется линейным.
Примером линейного группового кода является двоичный код Хэмминга.
Для каждого целого положительного числа m существует код Хэмминга с парамет- рами
[2
m
–1, 2
m
–1–m, 3], R = (2
m
–1– m)/(2
m
–1), r = m, t = 1.
Для больших значений m скорость кода R ≈ 1. Например, для m = 8 полу- чаем величину
R = (2 8
– 1– 8)/(2 8
–1) = 247/255 = 0,968.
Линейные коды делятся на следующие виды:
– систематические (разделимые);
– несистематические (неразделимые).
У систематического кода первые k символов кодового слова – информаци- онные.
У несистематического кода нет деления на информационные и провероч- ные символы (все символы являются кодовыми символами).
9.1.1. Кодер систематического кода
Действия систематического кодера (рис. 9.1):
1) кодер разбивает входную информационную последовательность симво- лов на блоки ????
????
????
= (????
0
, ????
1
, … , ????
????−1
) длиной k;
2) для каждого блока ????
????
????
находит слово
????
????
, первые k символов которого совпадают с ????
????
????
;
3) кодер обрабатывает каждый поступающий блок независимо от других
158 так, что каждое новое слово на его выходе оказывается не связанным с предыду- щими кодовыми словами.
Рис. 9.1. Кодер систематического кода
В качестве примера линейного кода приведем [7, 4, 3]-код Хэмминга мощ- ностью М = 2 4
=16. Ненулевые кодовые слова ????
????
= (????
0
, ????
1
, … , ????
????−1
) кода Хэм- минга [7, 4, 3] в порядке возрастания значения информационных весов wt{????
????
} векторов кода записаны в табл. 9.1.
Таблица 9.1
Код Хэмминга [7, 4, 3]
Если информационный вес wt{????
????
} = ????, то число кодовых слов данного ин- формационного веса определяется биноминальным коэффициентом ????
????
????
. Тогда [7,
4, 3]-код Хэмминга содержит
(????
????
1
+ ????
????
2
+ ????
????
3
+ ????
????
4
) = 15 ненулевых слов. Обо- значения ????
0
, ????
1
, ????
2
, ????
3
соответствуют информационным символам. Проверочные символы кода задаются следующими равенствами:
????
4
= ????
0
+ ????
1
+ ????
3
;
????
5
= ????
0
+ ????
1
+ ????
2
;
????
6
= ????
1
+ ????
2
+ ????
3
wt{????
????
} = 1
????
????
x
0
x
1
x
2
x
3
x
4
x
5
x
6
????
0 1
0 0
0 1
1 0
????
0
????
1 0
1 0
0 1
1 1
????
1
????
2 0
0 1
0 0
1 1
????
2
????
3 0
0 0
1 1
0 1
????
3
wt{????
????
} = 2
????
4 1
1 0
0 0
0 1
????
0
+ ????
1
????
0
+ ????
2
????
0
+ ????
3
????
1
+ ????
2
????
1
+ ????
3
????
2
+ ????
3
????
5 1
0 1
0 1
0 1
????
6 1
0 0
1 0
1 1
????
7 0
1 1
0 1
0 0
????
8 0
1 0
1 0
1 0
????
9 0
0 1
1 1
1 0 wt{????
????
} = 3
????
10 1
1 1
0 0
1 0
????
0
+ ????
1
+ ????
2
????
0
+ ????
1
+ ????
3
????
0
+ ????
2
+ ????
3
????
1
+ ????
2
+ ????
3
????
11 1
1 0
1 1
0 0
????
12 1
0 1
1 0
0 0
????
13 0
1 1
1 0
0 1
????????{????
????
} = 4????
14 1
1 1
1 1
1 1
????
0
+ ????
1
+ ????
2
+ ????
3
159
Все множество кодовых слов кода образуется путем суммирования первых четырех строк (базовых векторов) по 2, по 3, по 4, ...., по k (см. табл. 9.1). Таким образом, кодовые слова являются линейными комбинациями строк задающей код матрицы. С точки зрения алгебры все ненулевые слова кода образуют неко- торое векторное пространство, базисом которого являются строки базовой (по- рождающей) матрицы.
9.2. Вектор ошибок
Пусть ДСК характеризуется вероятностью ошибки на символ ????. Введем вектор ошибки ???? = (????
1
… ????
????
… ????
????
), ????
????
= 1 с вероятностью ???? и ????
????
= 0 с вероятно- стью (1 − ????). Найдем вероятность возникновения нескольких конфигураций векторов ???? ошибок для кодового слова длиной ???? = 5:
Prob{
???? = (00000)} = (1 − ????)
5
– вероятность правильного приема кодо- вого слова длиной 5.
Вероятность возникновения конфигурации вектора ошибок вида ???? =
= (10000) равна
Prob{
???? = (10000)} = ????(1 − ????)
4
Вероятность вектора ошибок вида ???? = (10010) равна
Prob{
???? = (10010)} = ????
2
(1 − ????)
3
В общем случае, вероятность возникновения вектора ???? ошибок веса ???? за- пишется в виде
Prob{
????
wt(????)
} = ????
????
(1 − ????)
????−????
. (9.1)
Вероятность правильного приема кодового слова длиной ???? равна
Prob{
????
wt(0)
} = (1 − ????)
????
Пример 9 .1. Пусть ???? = 0,2, ???? = 5. Рассмотрим возможные вероятности возникновения векторов ошибок.
1. Вероятность того, что не произошло ни одной ошибки на длине кодового слова равна
Prob{
????
wt(0)
= (00000)} = (1 − 0,2)
5
≅ 0,32.
2. Вероятность того, что на длине кодового слова имеется ошибка единич- ного веса равна
160
Prob{
????
wt(1)
= (10000)} = ????
1
(1 − ????)
4
= 0,2(1 − 0,2)
4
≅ 0,081.
3. Вероятность того, что произошли две ошибки на длине кодового слова равна
Prob{
????
wt(2)
= (10010)} = ????
2
(1 − ????)
3
= 0,2 2
(1 − 0,2)
3
≅ 0,01.
Из приведенного примера следуют очевидные выводы:
– вектор ошибок единичного веса более вероятен, чем вектор ошибок веса два и т. д.;
– ошибки малого веса необходимо обнаруживать и исправлять в первую очередь.
9.3. Порождающая и проверочная матрица систематического
линейного кода
9.3.1. Способы задания линейных кодов
Линейные коды задаются с помощью:
– порождающей матрицы ???? размерностью ???? × ????;
– проверочной матрицы ???? размерностью ???? × ????.
Матрицы связаны основным уравнением кодирования
???? × ????
????
= 0. (9.2)
Из (9.2) следует, что для всякой матрицы ???? существует матрица ????, удовле- творяющая этому равенству. И наоборот, заданной матрице ???? будет соответство- вать только одна матрица ????. В качестве строк матрицы ???? выбираются линейно- независимые слова длиной ????, отстоящие друг от друга на заданное кодовое рас- стояние ????.
Поскольку линейно независимые векторы могут быть выбраны произволь- ным образом, очевидно, можно построить множество матриц ???? с одним и тем же кодовым расстоянием ????. Например, второй вариант задания [7, 4, 3]-кода Хэм минга (см. табл. 9.1) в виде матрицы ???? представляется как
????
′
????
????
x
0
x
1
x
2
x
3
x
4
x
5
x
6
????
0 1
0 0
0 1
0 1
????
1 0
1 0
0 1
1 0
????
2 0
0 1
0 1
1 1
????
3 0
0 0
1 0
1 1
161
9.3.2. Свойства линейных кодов
Линейно независимые векторы инвариантны относительно двух операций, при выполнении которых минимальное расстояние кода не изменяется. Справед- ливы следующие операции:
– произвольные перестановки столбцов и строк матрицы ????;
– элементарные операции (например сложение) над строками матрицы ????.
Замечание. Перестановка символов кода эквивалентна перестановке столбцов порождающей матрицы.
9.3.3. Эквивалентные коды
Определение 9.2. Два кода эквивалентны тогда, когда их порождающая матрица получается одна из другой на основе свойства инвариантности.
Пример 9.2. Матрица ????
???? = (
????
0
????
1
????
2
) = (
1 1 0 0
0 1 1 0
0 0 1 1
) порождает эквивалентный код ????
′
:
????
′
= (
????
0
+ ????
1
+ ????
2
????
1
+ ????
2
????
2
) = (
1 0 0 1 0
1 0 1 0
0 1 1
).
Пример 9.3 . Эквивалентные коды Хэмминга [7, 4, 3] заданы матрицами
???? и????
′
????
????
????
x
0
x
1
x
2
x
3
x
4
x
5
x
6
????
0 1
0 0
0 1
1 0
????
1 0
1 0
0 1
1 1
????
2 0
0 1
0 0
1 1
????
3 0
0 0
1 1
0 1
????
′
????
????
x
0
x
1
x
2
x
3
x
4
x
5
x
6
????
0 1
0 0
0 1
0 1
????
1 0
1 0
0 1
1 0
????
2 0
0 1
0 1
1 1
????
3 0
0 0
1 0
1 1
162
Следует различать эквивалентный и эквидистантный код.
9.3.4. Эквидистантные коды
Определение 9.3. Эквидистантный код – это множество слов, отстоящих друг от друга на одно и то же расстояние Хэмминга ????
????
Пример эквидистантного [7, 3, 4]-кода (????-код) представлен матрицей
???? = [
1 1 1 0 0 1 0
0 1 1 1 0 0 1
1 0 1 1 1 0 0
].
9.3.5. Каноническая форма порождающей матрицы
Следствием свойства инвариантности векторов относительно вышеназван- ных операций является каноническая (приведенно ступенчатая) форма матриц ???? и ????. Порождающая матрица кода в канонической форме записывается как
???? = [????
????
|????
∗
] (9.3) где ????
????
– единичная подматрица размером
???? × ????, а ????
∗
– подматрица размером
???? ×
(???? − ????).
С учётом формы матрицы (9.3) уравнение кодирования представим как
????????
????
= [????
????
|????
∗
] [
−????
∗
????
????
] = −????
∗
+ ????
∗
= 0.
Отсюда определяем проверочную матрицу ???? размером ???? × ???? в канониче- ской форме:
???? = [−????
∗????
|????
????
], (9.4) где ????
????
– единичная матрица размером
???? × ????.
В поле ????????(2) −????
∗????
= ????
∗????
, поэтому
???? = [????
∗????
|????
????
].
Матрицы (9.3) и (9.4) соответствуют систематическому линейному коду.
Если известна проверочная матрица систематического кода
???? = [????
∗
|????
????
], (9.5) то матрица ???? записывается в виде
163
???? = [????
????
|????
∗????
].
Таким образом, код можно задавать перечислением всех ????
????
, разрешенных для передачи кодовых слов, или перечислением только базисных векторов кодо- вого подпространства. Очевидно, второй способ гораздо компактнее и удобнее для описания кодов. Например, если ???? = 2, ???? =
1 2
,
???? = 256, число кодовых слов достигает порядка ???? = 2 128
. Полная их запись требует
???? ∙ ???? = 2 128
∙ 2 8
= 2 136
битов.
Порождающая матрица этого же кода требует только
128
× 256 = 2 7
∙ 2 8
= 2 15
= 32 768 битов.
9.4. Кодирование линейным кодом
Кодирование представляет собой операцию умножения вектора ???? сообще- ния на порождающую матрицу????:
???? = ????????. (9.6)
При умножении вектора ???? на ????в форме (9.3) образуется систематический код, т. к. умножение ????????
????
= ???? не изменяет входного сообщения. Первые ???? симво- лов кодового слова равны соответствующим символам сообщения. Проверочные символы выбираются так, чтобы кодовые слова удовлетворяли основному урав- нению кодирования:
????????
????
= (????
0
????
1
… ????
????−1
… ????
????−1
)????
????
= (00 … 0). (9.7)
Запишем выражение (9.7) иначе
????????
????
= ????. (9.8)
С учетом выражения (9.5), формулу (9.8) представим в виде
[????
∗
|????
????
]
[
????
0
⋮
????
????−1
????
????
⋮
????
????−1
]
= [
0
⋮
0
].
Найдем из этого уравнения проверочные символы:
164
[
????
????
⋮
????
????−1
] = −????
∗
[
????
0
⋮
????
????−1
].
В поле ????????(2) (−????
∗
) = ????
∗
. Поэтому перепишем последнее выражение как
[
????
????
⋮
????
????−1
] = ????
∗
[
????
0
⋮
????
????−1
]. (9.9)
Пример 9 .4 . Пусть имеется матрица ???? размерностью 3
6. Обозначим элементы матрицы ???? через ℎ
????????
. Выражение (9.8) примет вид
[
ℎ
11
ℎ
12
ℎ
13 1 0 0
ℎ
21
ℎ
22
ℎ
23 0 1 0
ℎ
31
ℎ
32
ℎ
33 0 0 1
]
[
????
0
????
1
????
2
????
3
????
4
????
5
]
= [
0 0
0
].
Умножение матрицы ???? на вектор-столбец
[
ℎ
11
????
0
+
ℎ
12
????
1
+
ℎ
13
????
2
+ ????
3
ℎ
21
????
0
+ ℎ
22
????
1
+ ℎ
23
????
2
+ ????
4
ℎ
31
????
0
+ ℎ
32
????
1
+ ℎ
33
????
2
+ ????
5
] = [
0 0
0
] определяет уравнения для получения проверочных символов из выражений:
[
????
3
????
4
????
5
] = [
ℎ
11
ℎ
12
ℎ
13
ℎ
21
ℎ
22
ℎ
23
ℎ
31
ℎ
32
ℎ
33
] [
????
0
????
1
????
2
],
11 12 13 21 22 23 31 32 33
(3)
(0)
(1)
(2)
(4)
(0)
(1)
(2)
(5)
(0)
(1)
(2)
x
h x
h x
h x
x
h x
h x
h x
x
h x
h x
h x
(9.10)
Из формул (9.9) и (9.10) следует, что для двоичных кодов:
– каждый проверочный символ есть сумма информационных символов;
– в вычислении i -го проверочного символа участвуют те информационные сим- волы, которым соответствуют единицы в ????-й строке матрицы ????;
– ????-й проверочный символ определяется по i -му столбцу подматрицы ????
∗
165
9.5. Линейный код Рида – Маллера
Как правило, в результате кодирования информации кодом Рида – Маллера
(РМ-кодом) получается неразделимый код. При этом используется однородная и регулярная структура порождающей матрицы ????, позволяющая упростить проце- дуры кодирования и декодирования.
Практическое применение этого кода осуществлено сравнительно давно в американской специальной системе скрытной связи «Диджилок». В 1972 г. РМ- коды использовались в американской космической программе «Маринер» по пе- редаче изображений марсианской поверхности. РМ-код имеет следующие пара- метры:
1) значность кода
???? = 2
????
,
???? ⋝ 2;
2) кодовое расстояние
???? = 2
????−????
;
3) порядок кода
????;
4) размерность кода
???? = 1 + ∑
????
????
????
????
????=1
Порождающая матрица РМ-кода порядка ???? строится из определения опера- ции пересечения двоичных векторов. Пусть заданы векторы
???? = (????
0
, ????
1
, . . . , ????
????−1
), ???? = (????
0
, ????
1
, . . . , ????
????−1
).
Результат операции пересечения
???? ∙ ???? = ((????
0
∙ ????
0
)(????
1
∙ ????
1
) … (????
????−1
∙ ????
????−1
)).
При таком определении векторы порождающей матрицы РМ-кода обра- зуют коммуникативную группу.
Например, совокупность векторов, образованная пересечением трех векто- ров ????
????
взятых по 2 имеет вид
???? = {
????
0
∙
????
1
????
0
∙ ????
2
????
1
∙ ????
2
}.
Код Рида – Маллера порядка ???? определяется как код, базисом которого яв- ляются векторы ????
????
, ????
1
, … , ????
????−1
и все векторные пересечения из
???? или меньшего числа этих векторов.
Пример 9 .5 . Построить код Рида – Маллера первого порядка, где ???? = 1,
???? = 3.
Решение. Получаем РМ-код со следующими параметрами:
1)
???? = 2 3
= 8;
2)
???? = 2 3−1
= 4;
3)
???? = 1 + ∑
????
3
????
1
????=1
= 1 + ????
3 1
= 4.
Определение 8.24. Векторы ????
0
, ????
1
, … , ????
????−1
из
???? называются линейно зависимыми, если в ???? существуют такие элементы ????
0
, ????
1
, … , ????
????−1
, для которых
????
0
????
0
+????
1
????
1
+ ⋯ + ????
????−1
????
????−1
= 0, и линейно независимыми, когда
????
0
????
0
+ ????
1
????
1
+ ⋯ + ????
????−1
????
????−1
≠ 0.
Наглядно условие линейной независимости векторов над полем ???? можно изобразить как
????
0
????
1
… ????
????−1
Здесь ????
????
∈ ????. Для двоичных кодов ????
????
∈ {0,1} линейная независимость озна- чает, что суммирование базисных двоичных векторов не образует нулевой век- тор. Максимальное число линейно независимых векторов в ???? называется размер- ностью пространства ???? над полем ????.
8.8. Задания для самостоятельного выполнения
1. Показать, что группа
???? = <{0,1, 2, 3, 4, 5}; +; 0> содержит подгруппы порядков: 1, 2, 3 и 6.
2. Показать, что множество
????
′
= {0, 2, 4} – это подкольцо кольца <
{ℤ
6
= 0, 1, 2, 3, 4, 5 }; +;⋅; 0; 1 >.
3. Задано кольцо целых чисел
ℤ. Построить главный идеал, порожденный целым числом 12.
4. Найти главный идеал пересечения множеств
< 8 > ∩ < 12 >.
5. Найти примитивные элементы расширенного поля Галуа
????????(2 4
).
6. Привести четыре формы представления элементов поля
????????(2 4
). Поле образовано неприводимым над полем ????????(2) полиномом ????(????) = 1 + ???? + ????
4 7. Поле образовано полиномами над полем
????????(2) по модулю неприводи- мого полинома ????(????) = 1 + ???? + ????
3
. Вычислить:
011 0
????
0
∙
+ ????
1
∙
+…
+. . . + ????
????−1
∙
…
≠
156 а) полином, обратный полиному ???? = 1+ α + α
2
; б) полином, обратный полиному ???? = α + α
2
; в) ???? ????
⁄ ; г) √????; д) (111)
−1
157
9. ЛИНЕЙНЫЕ КОДЫ
9.1. Линейные коды, исправляющие ошибки: построение и основные
свойства
Определение 9.1. Линейный [n, k, d]-код есть подпространство размерно- стью k линейного n-мерного пространства над ????????(????) = ????????(????
????
). Подмножество, состоящее из ????
????
последовательностей длиной n, называется q-ичным блоковым кодом длиной n.
Замечания:
1. Если q = 2, то в качестве кодового алфавита используются символы дво- ичного {0, 1} алфавита. Пространство кода над полем ????????(2) образует аддитив- ную подгруппу группы всех двоичных последовательностей длиной n. Оче- видно, что для этой подгруппы должны выполняться все аксиомы группы, и для нее определена одна основная операция – сложение.
2. Так как операция суммирования является линейной операцией, то и код называется линейным.
Примером линейного группового кода является двоичный код Хэмминга.
Для каждого целого положительного числа m существует код Хэмминга с парамет- рами
[2
m
–1, 2
m
–1–m, 3], R = (2
m
–1– m)/(2
m
–1), r = m, t = 1.
Для больших значений m скорость кода R ≈ 1. Например, для m = 8 полу- чаем величину
R = (2 8
– 1– 8)/(2 8
–1) = 247/255 = 0,968.
Линейные коды делятся на следующие виды:
– систематические (разделимые);
– несистематические (неразделимые).
У систематического кода первые k символов кодового слова – информаци- онные.
У несистематического кода нет деления на информационные и провероч- ные символы (все символы являются кодовыми символами).
9.1.1. Кодер систематического кода
Действия систематического кодера (рис. 9.1):
1) кодер разбивает входную информационную последовательность симво- лов на блоки ????
????
????
= (????
0
, ????
1
, … , ????
????−1
) длиной k;
2) для каждого блока ????
????
????
находит слово
????
????
, первые k символов которого совпадают с ????
????
????
;
3) кодер обрабатывает каждый поступающий блок независимо от других
158 так, что каждое новое слово на его выходе оказывается не связанным с предыду- щими кодовыми словами.
Рис. 9.1. Кодер систематического кода
В качестве примера линейного кода приведем [7, 4, 3]-код Хэмминга мощ- ностью М = 2 4
=16. Ненулевые кодовые слова ????
????
= (????
0
, ????
1
, … , ????
????−1
) кода Хэм- минга [7, 4, 3] в порядке возрастания значения информационных весов wt{????
????
} векторов кода записаны в табл. 9.1.
Таблица 9.1
Код Хэмминга [7, 4, 3]
Если информационный вес wt{????
????
} = ????, то число кодовых слов данного ин- формационного веса определяется биноминальным коэффициентом ????
????
????
. Тогда [7,
4, 3]-код Хэмминга содержит
(????
????
1
+ ????
????
2
+ ????
????
3
+ ????
????
4
) = 15 ненулевых слов. Обо- значения ????
0
, ????
1
, ????
2
, ????
3
соответствуют информационным символам. Проверочные символы кода задаются следующими равенствами:
????
4
= ????
0
+ ????
1
+ ????
3
;
????
5
= ????
0
+ ????
1
+ ????
2
;
????
6
= ????
1
+ ????
2
+ ????
3
wt{????
????
} = 1
????
????
x
0
x
1
x
2
x
3
x
4
x
5
x
6
????
0 1
0 0
0 1
1 0
????
0
????
1 0
1 0
0 1
1 1
????
1
????
2 0
0 1
0 0
1 1
????
2
????
3 0
0 0
1 1
0 1
????
3
wt{????
????
} = 2
????
4 1
1 0
0 0
0 1
????
0
+ ????
1
????
0
+ ????
2
????
0
+ ????
3
????
1
+ ????
2
????
1
+ ????
3
????
2
+ ????
3
????
5 1
0 1
0 1
0 1
????
6 1
0 0
1 0
1 1
????
7 0
1 1
0 1
0 0
????
8 0
1 0
1 0
1 0
????
9 0
0 1
1 1
1 0 wt{????
????
} = 3
????
10 1
1 1
0 0
1 0
????
0
+ ????
1
+ ????
2
????
0
+ ????
1
+ ????
3
????
0
+ ????
2
+ ????
3
????
1
+ ????
2
+ ????
3
????
11 1
1 0
1 1
0 0
????
12 1
0 1
1 0
0 0
????
13 0
1 1
1 0
0 1
????????{????
????
} = 4????
14 1
1 1
1 1
1 1
????
0
+ ????
1
+ ????
2
+ ????
3
159
Все множество кодовых слов кода образуется путем суммирования первых четырех строк (базовых векторов) по 2, по 3, по 4, ...., по k (см. табл. 9.1). Таким образом, кодовые слова являются линейными комбинациями строк задающей код матрицы. С точки зрения алгебры все ненулевые слова кода образуют неко- торое векторное пространство, базисом которого являются строки базовой (по- рождающей) матрицы.
9.2. Вектор ошибок
Пусть ДСК характеризуется вероятностью ошибки на символ ????. Введем вектор ошибки ???? = (????
1
… ????
????
… ????
????
), ????
????
= 1 с вероятностью ???? и ????
????
= 0 с вероятно- стью (1 − ????). Найдем вероятность возникновения нескольких конфигураций векторов ???? ошибок для кодового слова длиной ???? = 5:
Prob{
???? = (00000)} = (1 − ????)
5
– вероятность правильного приема кодо- вого слова длиной 5.
Вероятность возникновения конфигурации вектора ошибок вида ???? =
= (10000) равна
Prob{
???? = (10000)} = ????(1 − ????)
4
Вероятность вектора ошибок вида ???? = (10010) равна
Prob{
???? = (10010)} = ????
2
(1 − ????)
3
В общем случае, вероятность возникновения вектора ???? ошибок веса ???? за- пишется в виде
Prob{
????
wt(????)
} = ????
????
(1 − ????)
????−????
. (9.1)
Вероятность правильного приема кодового слова длиной ???? равна
Prob{
????
wt(0)
} = (1 − ????)
????
Пример 9 .1. Пусть ???? = 0,2, ???? = 5. Рассмотрим возможные вероятности возникновения векторов ошибок.
1. Вероятность того, что не произошло ни одной ошибки на длине кодового слова равна
Prob{
????
wt(0)
= (00000)} = (1 − 0,2)
5
≅ 0,32.
2. Вероятность того, что на длине кодового слова имеется ошибка единич- ного веса равна
160
Prob{
????
wt(1)
= (10000)} = ????
1
(1 − ????)
4
= 0,2(1 − 0,2)
4
≅ 0,081.
3. Вероятность того, что произошли две ошибки на длине кодового слова равна
Prob{
????
wt(2)
= (10010)} = ????
2
(1 − ????)
3
= 0,2 2
(1 − 0,2)
3
≅ 0,01.
Из приведенного примера следуют очевидные выводы:
– вектор ошибок единичного веса более вероятен, чем вектор ошибок веса два и т. д.;
– ошибки малого веса необходимо обнаруживать и исправлять в первую очередь.
9.3. Порождающая и проверочная матрица систематического
линейного кода
9.3.1. Способы задания линейных кодов
Линейные коды задаются с помощью:
– порождающей матрицы ???? размерностью ???? × ????;
– проверочной матрицы ???? размерностью ???? × ????.
Матрицы связаны основным уравнением кодирования
???? × ????
????
= 0. (9.2)
Из (9.2) следует, что для всякой матрицы ???? существует матрица ????, удовле- творяющая этому равенству. И наоборот, заданной матрице ???? будет соответство- вать только одна матрица ????. В качестве строк матрицы ???? выбираются линейно- независимые слова длиной ????, отстоящие друг от друга на заданное кодовое рас- стояние ????.
Поскольку линейно независимые векторы могут быть выбраны произволь- ным образом, очевидно, можно построить множество матриц ???? с одним и тем же кодовым расстоянием ????. Например, второй вариант задания [7, 4, 3]-кода Хэм минга (см. табл. 9.1) в виде матрицы ???? представляется как
????
′
????
????
x
0
x
1
x
2
x
3
x
4
x
5
x
6
????
0 1
0 0
0 1
0 1
????
1 0
1 0
0 1
1 0
????
2 0
0 1
0 1
1 1
????
3 0
0 0
1 0
1 1
161
9.3.2. Свойства линейных кодов
Линейно независимые векторы инвариантны относительно двух операций, при выполнении которых минимальное расстояние кода не изменяется. Справед- ливы следующие операции:
– произвольные перестановки столбцов и строк матрицы ????;
– элементарные операции (например сложение) над строками матрицы ????.
Замечание. Перестановка символов кода эквивалентна перестановке столбцов порождающей матрицы.
9.3.3. Эквивалентные коды
Определение 9.2. Два кода эквивалентны тогда, когда их порождающая матрица получается одна из другой на основе свойства инвариантности.
Пример 9.2. Матрица ????
???? = (
????
0
????
1
????
2
) = (
1 1 0 0
0 1 1 0
0 0 1 1
) порождает эквивалентный код ????
′
:
????
′
= (
????
0
+ ????
1
+ ????
2
????
1
+ ????
2
????
2
) = (
1 0 0 1 0
1 0 1 0
0 1 1
).
Пример 9.3 . Эквивалентные коды Хэмминга [7, 4, 3] заданы матрицами
???? и????
′
????
????
????
x
0
x
1
x
2
x
3
x
4
x
5
x
6
????
0 1
0 0
0 1
1 0
????
1 0
1 0
0 1
1 1
????
2 0
0 1
0 0
1 1
????
3 0
0 0
1 1
0 1
????
′
????
????
x
0
x
1
x
2
x
3
x
4
x
5
x
6
????
0 1
0 0
0 1
0 1
????
1 0
1 0
0 1
1 0
????
2 0
0 1
0 1
1 1
????
3 0
0 0
1 0
1 1
162
Следует различать эквивалентный и эквидистантный код.
9.3.4. Эквидистантные коды
Определение 9.3. Эквидистантный код – это множество слов, отстоящих друг от друга на одно и то же расстояние Хэмминга ????
????
Пример эквидистантного [7, 3, 4]-кода (????-код) представлен матрицей
???? = [
1 1 1 0 0 1 0
0 1 1 1 0 0 1
1 0 1 1 1 0 0
].
9.3.5. Каноническая форма порождающей матрицы
Следствием свойства инвариантности векторов относительно вышеназван- ных операций является каноническая (приведенно ступенчатая) форма матриц ???? и ????. Порождающая матрица кода в канонической форме записывается как
???? = [????
????
|????
∗
] (9.3) где ????
????
– единичная подматрица размером
???? × ????, а ????
∗
– подматрица размером
???? ×
(???? − ????).
С учётом формы матрицы (9.3) уравнение кодирования представим как
????????
????
= [????
????
|????
∗
] [
−????
∗
????
????
] = −????
∗
+ ????
∗
= 0.
Отсюда определяем проверочную матрицу ???? размером ???? × ???? в канониче- ской форме:
???? = [−????
∗????
|????
????
], (9.4) где ????
????
– единичная матрица размером
???? × ????.
В поле ????????(2) −????
∗????
= ????
∗????
, поэтому
???? = [????
∗????
|????
????
].
Матрицы (9.3) и (9.4) соответствуют систематическому линейному коду.
Если известна проверочная матрица систематического кода
???? = [????
∗
|????
????
], (9.5) то матрица ???? записывается в виде
163
???? = [????
????
|????
∗????
].
Таким образом, код можно задавать перечислением всех ????
????
, разрешенных для передачи кодовых слов, или перечислением только базисных векторов кодо- вого подпространства. Очевидно, второй способ гораздо компактнее и удобнее для описания кодов. Например, если ???? = 2, ???? =
1 2
,
???? = 256, число кодовых слов достигает порядка ???? = 2 128
. Полная их запись требует
???? ∙ ???? = 2 128
∙ 2 8
= 2 136
битов.
Порождающая матрица этого же кода требует только
128
× 256 = 2 7
∙ 2 8
= 2 15
= 32 768 битов.
9.4. Кодирование линейным кодом
Кодирование представляет собой операцию умножения вектора ???? сообще- ния на порождающую матрицу????:
???? = ????????. (9.6)
При умножении вектора ???? на ????в форме (9.3) образуется систематический код, т. к. умножение ????????
????
= ???? не изменяет входного сообщения. Первые ???? симво- лов кодового слова равны соответствующим символам сообщения. Проверочные символы выбираются так, чтобы кодовые слова удовлетворяли основному урав- нению кодирования:
????????
????
= (????
0
????
1
… ????
????−1
… ????
????−1
)????
????
= (00 … 0). (9.7)
Запишем выражение (9.7) иначе
????????
????
= ????. (9.8)
С учетом выражения (9.5), формулу (9.8) представим в виде
[????
∗
|????
????
]
[
????
0
⋮
????
????−1
????
????
⋮
????
????−1
]
= [
0
⋮
0
].
Найдем из этого уравнения проверочные символы:
164
[
????
????
⋮
????
????−1
] = −????
∗
[
????
0
⋮
????
????−1
].
В поле ????????(2) (−????
∗
) = ????
∗
. Поэтому перепишем последнее выражение как
[
????
????
⋮
????
????−1
] = ????
∗
[
????
0
⋮
????
????−1
]. (9.9)
Пример 9 .4 . Пусть имеется матрица ???? размерностью 3
6. Обозначим элементы матрицы ???? через ℎ
????????
. Выражение (9.8) примет вид
[
ℎ
11
ℎ
12
ℎ
13 1 0 0
ℎ
21
ℎ
22
ℎ
23 0 1 0
ℎ
31
ℎ
32
ℎ
33 0 0 1
]
[
????
0
????
1
????
2
????
3
????
4
????
5
]
= [
0 0
0
].
Умножение матрицы ???? на вектор-столбец
[
ℎ
11
????
0
+
ℎ
12
????
1
+
ℎ
13
????
2
+ ????
3
ℎ
21
????
0
+ ℎ
22
????
1
+ ℎ
23
????
2
+ ????
4
ℎ
31
????
0
+ ℎ
32
????
1
+ ℎ
33
????
2
+ ????
5
] = [
0 0
0
] определяет уравнения для получения проверочных символов из выражений:
[
????
3
????
4
????
5
] = [
ℎ
11
ℎ
12
ℎ
13
ℎ
21
ℎ
22
ℎ
23
ℎ
31
ℎ
32
ℎ
33
] [
????
0
????
1
????
2
],
11 12 13 21 22 23 31 32 33
(3)
(0)
(1)
(2)
(4)
(0)
(1)
(2)
(5)
(0)
(1)
(2)
x
h x
h x
h x
x
h x
h x
h x
x
h x
h x
h x
(9.10)
Из формул (9.9) и (9.10) следует, что для двоичных кодов:
– каждый проверочный символ есть сумма информационных символов;
– в вычислении i -го проверочного символа участвуют те информационные сим- волы, которым соответствуют единицы в ????-й строке матрицы ????;
– ????-й проверочный символ определяется по i -му столбцу подматрицы ????
∗
165
9.5. Линейный код Рида – Маллера
Как правило, в результате кодирования информации кодом Рида – Маллера
(РМ-кодом) получается неразделимый код. При этом используется однородная и регулярная структура порождающей матрицы ????, позволяющая упростить проце- дуры кодирования и декодирования.
Практическое применение этого кода осуществлено сравнительно давно в американской специальной системе скрытной связи «Диджилок». В 1972 г. РМ- коды использовались в американской космической программе «Маринер» по пе- редаче изображений марсианской поверхности. РМ-код имеет следующие пара- метры:
1) значность кода
???? = 2
????
,
???? ⋝ 2;
2) кодовое расстояние
???? = 2
????−????
;
3) порядок кода
????;
4) размерность кода
???? = 1 + ∑
????
????
????
????
????=1
Порождающая матрица РМ-кода порядка ???? строится из определения опера- ции пересечения двоичных векторов. Пусть заданы векторы
???? = (????
0
, ????
1
, . . . , ????
????−1
), ???? = (????
0
, ????
1
, . . . , ????
????−1
).
Результат операции пересечения
???? ∙ ???? = ((????
0
∙ ????
0
)(????
1
∙ ????
1
) … (????
????−1
∙ ????
????−1
)).
При таком определении векторы порождающей матрицы РМ-кода обра- зуют коммуникативную группу.
Например, совокупность векторов, образованная пересечением трех векто- ров ????
????
взятых по 2 имеет вид
???? = {
????
0
∙
????
1
????
0
∙ ????
2
????
1
∙ ????
2
}.
Код Рида – Маллера порядка ???? определяется как код, базисом которого яв- ляются векторы ????
????
, ????
1
, … , ????
????−1
и все векторные пересечения из
???? или меньшего числа этих векторов.
Пример 9 .5 . Построить код Рида – Маллера первого порядка, где ???? = 1,
???? = 3.
Решение. Получаем РМ-код со следующими параметрами:
1)
???? = 2 3
= 8;
2)
???? = 2 3−1
= 4;
3)
???? = 1 + ∑
????
3
????
1
????=1
= 1 + ????
3 1
= 4.