Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
=
0
0
1
)x(G
n,k
M
0
1
0
0
0
0
K
K
K
L
1
0
0
M
1.k
1.2
1.1
b
b
b
M
2.k
2.2
2.1
b
b
b
K
K
K
K
l
l
l
.k
.2
.1
b
b
b
M
. (2.14)
Существует сокращенная запись канонической порождающей матрицы, а
именно:
]RI[)x(G
k),kn(k,kn,k −
⋅= , (2.15)
где
k,k
I –единичная подматрица рангом k
×
k,
k),kn(
R
−
–подматрица рангом (n-k),k, составленная из (n-k) проверочных
символов исходных кодовых последовательностей, т.е. она выполняет функции
проверочной подматрицы.
Каноническая порождающая матрица называется также приведенно-
ступенчатой, т.е. в такой матрице информационные и проверочные двоичные
символы разделены.
При использовании канонической порождающей матрицы
)x(G
n,k
для
построения СЛБК с заданной или необходимой корректирующей способностью,
т.е.
0
d
необходимо руководствоваться следующими правилами:
а) при выборе ранга (размерности) проверочной подматрицы П или все
равно, что при определении количества проверочных символов и приписываемых
к единичной подматрице необходимо, чтобы вес (т.е. количество логических “1”)
в приписываемой части строки должен быть не менее, чем 1d
0
− ;
б) сумма по модулю два любых двух строк канонической матрицы должна
быть равной весу 1d
0
−=ϖ
ε
;
в) каноническая матрица должна содержать “k” исходных разрешенных
кодовых последовательностей, полученных в соответствии с правилами (а) и (б),
а остальные
k
2
k
−
разрешенных последовательностей строятся суммированием по
модулю два символов строк посимвольно: 1строка
⊕
2строка (1
⊕
2), 1
⊕
3, 1
⊕
4 и
т.д.
При выборе проверочной подматрицы необходимо учитывать следующее
свойство СЛБК:
– чем больше логических “1” в приписываемых строках проверочной
матрицы, тем большей корректирующей способностью обладает
разрабатываемый код, но тем больше будет иметь кодек сумматоров по модулю
два и тем больше сложность его реализации.
При соблюдении перечисленных выше условий и правил любую
порождающую матрицу )x(G
n,k
СЛБК можно привести к следующему
каноническому виду:
1
a
2
a
3
a
K
k
a
1
b
2
b
K
l
b
=⋅=
0
0
1
ПИ)x(G
n,k
M
0
1
0
0
0
0
K
K
K
1
0
0
M
1.k
1.2
1.1
b
b
b
M
2.k
2.2
2.1
b
b
b
K
K
K
l
l
l
.k
.2
.1
b
b
b
M
. (2.16)
Для СЛБК с 2d
0
= порождающая )x(G
n,k
имеет вид:
=)х(G
n,k
0
0
1
M
0
1
0
0
0
0
L
L
L
1
0
0
M
1
1
1
M
=
0
0
1
M
0
1
0
0
0
0
L
L
L
L
1
0
0
M
.
1
1
1
M
. (2.17)
Для СЛБК с 3d
0
≥ построение порождающей матрицы вида (2.17) зависит: от
размерности информационной (единичной) подматрицы, т.е. от величины “k”; от
длины кодограммы, т.е. “n” и от величины
0
d
.
Например, требуется построить порождающую матрицу для СЛБК с
3d
0
=
,
.4k
=
Решение. Используя выражение )1n(22
kn
+⋅≥ методом подбора находим, что
n=7. Выбираем единичную подматрицу
)х(I
k,k
рангом k x k=4x4 вида
=)х(I
4,4
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
.
Далее необходимо к каждой строке дописать символы проверочной
подматрицы, вес дописываемой строки должен быть не менее d
0
-1=3-1=2, т.е.
необходимо к каждой строке дописать по две “1”; в этом случае вес каждой
строки )х(G
n,k
равен ,3dw
0стр
== но число столбцов данной матрицы равно n=6,
т.е. не соответствует заданному коду, а поэтому в проверочную часть каждой
строки дописываем еще один символ (выбор произвольный). Окончательно
)х(G)х(G
7,4n,k
= будет иметь следующий вид:
1
a
2
a
3
a
4
a
5
a
6
a
7
a
=)х(G
6,4
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
1
1
1
1
1
1
1
;
=)х(G
7,4
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
1
1
0
1
0
1
1
1
1
0
1
.
Анализируя свойства и структуру порождающих матриц )х(G
n,k
СЛБК можно
сделать следующие выводы:
1). В зависимости от выбранного базиса “k”- мерного подпространства (т.е.
величины “k” или количества информационных символов) и “n”- мерного
кодового пространства (т.е. величины “l” и
0
d
) порождающая матрица
)х(G
n,k
будет иметь разный ранг или размерность. Таким образом, строки матрицы
)х(G
n,k
линейно независимы и число строк “k” равно размерности
подпространства
)2(GF
k
. Пространство строк матрицы )х(G
n,k
есть ЛБК, а любая
кодовая последовательность есть линейная комбинация строк матрицы )х(G
n,k
.
Порождающая матрица )х(G
n,k
является сжатым описанием СЛБК. Поскольку
)2(GF
k
СЛБК является подпространством, то оно имеет ортогональное
(согласованное) дополнение ,)2(F)х(G
1n
n,k
= которое состоит из всех кодовых
последовательностей (кодовых векторов), ортогональных к пространству
)2(F)х(G
n
n,k
= .
Ортогональное дополнение также является подпространством и, таким
образом, может рассматриваться как код. Когда ортогональное дополнение
1n
n,k
)2(F)х(G = рассматривается как код, то это дополнение называется дуальным к
коду )2(F)х(G
n
n,k
= . Ортогональное дополнение
1n
n,k
)2(F)х(G = имеет размерность
(n-k)=l и любой его базис также состоит из l=(n-k) кодовых последовательностей
(кодовых векторов).
Например, для двух кодов Хэмминга )3,4,7()dkn(
0111
= и )4,3,7()dkn(
0222
=
порождающие матрицы будут иметь соответственно следующие размерности или
вид:
1
a
2
a
3
a
4
a
5
a
6
a
7
a
=
7,4
G
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
1
1
1
0
1
0
1
1
1
1
0
1
;
=
7,3
G
0
0
1
0
1
0
1
0
0
1
1
1
1
1
0
1
0
1
1
1
1
, (2.18)
(для кода (7,4,3) можно построить 29 вариантов порождающих матриц вида
2.18);
2). Имея порождающую матрицу )х(G
n,k
и исходный информационный блок
из “k” символов, кодовую комбинацию можно получить путем умножения
исходного информационного блока на
)х(G
n,k
, что можно записать так:
)x(G)x(Q)x(F
n,k
⋅=
,
где F(x)-формируемая кодовая последовательность;
Q(x)- информационный блок.
Например,
[
1)x(G)x(F =⋅
0
]
1
.
0
0
1
0
1
0
1
0
0
0
1
1
1
0
1
1
1
0
1
1
1
1011010=
.
Порядок вычисления соответствует правилам матричного умножения, но все
операции выполняются по модулю два;
3). При построении СЛБК с параметрами (n,k)- кода ставится задача
оптимального размещения кодовых векторов в n – мерном кодовом пространстве
в соответствии с заданной статистикой ошибок и, в частности, обеспечения
максимально возможного минимального кодового расстояния;
4). Возможно другое представление порождающей матрицы )х(G
n,k
,
формирующей СЛБК с “k” линейно независимыми исходными (базисными)
кодовыми последовательностями, а именно:
пусть −)x(F),...,x(F),x(F),x(F
k321
кодовые последовательности-строки, то
порождающая матрица )х(G
n,k
может быть представлена в следующем виде:
)х(G
n,k
=
)(
)(
)(
2
1
xF
xF
xF
k
M
. (2.19)
Тогда разрешенную кодовую последовательность СЛБК (n,k)- кода можно
представить в виде линейной комбинации кодовых векторов:
),x(Fc)x(Fc)x(Fc)x(F
kk2211i
⋅⊕⊕⋅⊕⋅= L
где −
k1
cc K коэффициенты, принимающие значения либо “0”, либо “1”;
5). Проверочные символы
l
bb
1
K
кодовой последовательности
l
bbaaa)x(F
1k21i
KK=
формируется в соответствии с формулой
kk,i22,i11,ii
acacacb ⋅⊕⋅⊕⋅= K ; (2.20)
6). Это же правило может быть использовано при приеме для проверки
достоверности приема кодовой последовательности.
Равенство (2.20) должно выполняться, если ошибки отсутствуют.
Таким образом, с каждой принятой кодовой последовательностью можно
связать систему проверок по числу проверочных символов, которая для кодовой
последовательности
l
bbaaa)x(F
1k21i
KK= может быть описана следующей
системой уравнений:
=⊕⋅⊕⊕⋅⊕⋅
=⊕⋅⊕⊕⋅⊕⋅
=⊕⋅⊕⊕⋅⊕⋅
,0bacacac
.................................................................
0bacacac
0bacacac
lkk,22,11,
2kk,222,211,2
1kk,122,111,1
lll
K
K
K
(2.21)
где
{
}
.k,,1j,,,1i,1,0c
j,i
KK ==∈ l
Нули в правых частях равенства (2.21) соответствует случаю, когда в
принятой кодовой последовательности ошибок нет.
Для удобства систему проверок (2.21) обычно представляют в матричной
форме, а именно как произведение матрицы-строки
l
bbaaa)x(F
1k21i
KK= ,
соответствующей принятой кодовой последовательности, на матрицу
проверочных коэффициентов.
Структура порождающих матриц, обозначенных номером (2.18),так же
может рассматриваться как форма определения проверочных символов.
В порождающей матрице )x(G
7,4
символы
−
4321
aaaa
информационные, а
−
765
aaa проверочные, которые могут быть получены путем суммирования по
модулю два определенных информационных символов. Правило формирования
проверочного символа
i
b
для любой кодовой последовательности одинаково и
определяется номерами позиций логических “1” в каждом столбце проверочной
подматрицы
)x(G
7,4
. Так символ
)a(b
51
формируется путем суммирования по
модулю два информационных символов соответственно:
.aaaab
aaaab
aaaab
43173
42162
43251
⊕⊕==
⊕⊕==
⊕
⊕
=
=
Таким образом, систему проверок, представленных в форме (2.21),
целесообразно представить в матричной форме и тем самым выполнять
указанную систему проверок в соответствии с расположением ее коэффициентов.
Данная матрица называется проверочной (она позволяет выполнить систему
проверок, отсюда и ее название - проверочная) и обозначается как )x(H
n,l
и
записывается в общем виде так [1…4]
=
1.
1.2
1.1
n,
c
c
c
)x(H
l
l
M
2,
2,2
2,1
c
c
c
l
L
L
L
k,
k,2
k,1
c
c
c
l
L
0
0
1
0
1
0
0
0
0
L
L
L
1
0
0
M
: (2.22)
1. Размерность или ранг проверочной матрицы равен (n-k)*n=l*n .
Поскольку каждый СЛБК имеет несколько порождающих матриц, то им
соответствует столько же проверочных матриц;
2. Проверочная матрица должна удовлетворять следующему соотношению
или равенству:
[ ]
,0PP
I
P
PI)x(H)x(G
T
n,n,k
=+−=
−
∗=⋅ LM
l
(2.23)
где T- означает операцию транспонирования;
3. Из соотношения (равенства) (2.23) следует, что при умножении кодовой
последовательности принятой без ошибок на )x(H
T
, должны получать нулевую
последовательность или нулевой вектор, что можно записать так:
.0)x(H)x(F
T
n,2i
=⋅ (2.24)
В общем случае результат умножения может быть отличен от нуля, т.е.
,ccc)x(Hbbaaa
21
T
k,n1k21 ll
LLL =×
где
{
}
...,2,1i,1,0a
i
=∈ l
Матрица – строка
l
c,...cc
2,1
, полученная в результате умножения, называется
синдромом ошибки.
Как видно, всего может быть
1
2
−
l
различных ненулевых синдромов,
разбивающих множество возможных ошибок на
1
2
−
l
класса. Это позволяет по
виду синдрома ошибки определять к какому классу относится ошибка.
Рассматривая разрешенную кодовую последовательность СЛБ (n,k)- кода как
линейную комбинацию кодовых последовательностей или кодовых векторов
порождающей матрицы и подставляя выражение
),x(Fc)x(Fc)x(Fc)x(F
kk2211i
⋅⊕⊕⋅⊕⋅= L в равенство (2.24), получаем:
.0))x(HF(c))x(HF(c))x(HF(c
)x(H)FcFcFс(
T
kk
T
22
T
11
T
kk2211
=×⋅⊕⊕×⋅⊕×⋅=
=×⋅⊕⊕⋅⊕⋅
L
L
Из данного выражения следует, что для того, чтобы для любой разрешенной
кодовой последовательности СЛБ (n,k)- кода выполнялось равенство (2.24),
необходимо и достаточно, чтобы выполнялось равенство
0)x(H
)x(F
)x(F
)x(F
T
n,
k
2
1
=×
l
L
или 0)x(H)x(G
T
n,n,k
=×
l
. (2.25)
Последнее равенство устанавливает связь между G(x) и H(x) СЛБ (n,k)- кода
и может служить для определения одной из них, если известна другая матрица.
Проверочная матрица )x(H
n,l
, записанная в форме (2.22) по аналогии с
порождающей матрицей )х(G
n,k
, представленной в форме (2.16), является
канонической проверочной матрицей. Замена коэффициентов “b” в формуле
(2.16) )х(G
n,k
на коэффициенты “c” в формуле (2.22) несущественна.
Используется так же сокращенная форма записи канонической проверочной
матрицы в форме:
[
]
kn,kn,
IR)x(H
−
⋅=
ll
.
Каноническая форма, представления порождающей матрицы )х(G
n,k
, удобна
тем, что она реализует простую связь между элементами )х(G
n,k
и )x(H
n,l
, суть
которой состоит в следующем:
для определения проверочной матрицы СЛБ (n,k)- кода, порождаемого
канонической матрицей )х(G
n,k
вида
=
0
0
1
)x(G
n,k
M
0
1
0
L
L
L
1
0
0
1.k
1.2
1.1
b
b
b
2.k
2.2
2.1
b
b
b
L
L
L
l
l
l
.k
.2
.1
b
b
b
необходимо транспонировать подматрицу проверочных символов матрицы
)х(G
n,k
и приписать справа к полученной подматрице единичную подматрицу
рангом l x l;
– транспонирование подматрицы проверочных символов матрицы
)х(G
n,k
производится следующим образом: а) проверочные части строк
записываются соответственно последовательно в виде столбцов проверочной
матрицы; б) далее к правой части )x(H
n,l
дописывается единичная подматрица.
Таким образом, транспонированная проверочная матрица СЛБ (n,k)-кода будет
иметь следующую форму:
)x(H
n,l
=
1.k
1.2
1,1
b
b
b
2.k
2.2
2.1
b
b
b
L
L
L
l
l
l
.k
.2
.1
b
b
b
0
0
1
M
0
1
0
L
L
L
1
0
0
. (2.26)
Из данной формы записи
)x(H
n,l
следует, что ее можно построить
следующим образом:
- первый столбец проверочной подматрицы )х(G
n,k
записать в виде первой
строки )x(H
n,l
;
- второй столбец проверочной подматрицы
)х(G
n,k
записать в виде второй
строки )x(H
n,l
;
- к полученной проверочной подматрице )x(H
n,l
дописать единичную
подматрицу.
Общие выводы по построению и применению проверочной матрицы
)x(H
n,l
:
– проверочная матрица
)x(H
n,l
дает простую процедуру алгоритма
кодирования и декодирования информации СЛБ (n,k) – кодами, сущность которой
состоит в том, что проверочные символы определяются путем суммирования по
модулю два информационных символов строк, номера которых совпадают с
ненулевыми позициями символов строк проверочной подматрицы проверочной
матрицы )x(H
n,l
;
– с помощью )x(H
n,l
в принятой кодовой последовательности осуществляется
l=n-k проверок “на четность”; если ошибок нет, то в каждой из l проверок
участвует четное число “l”. (Приведенное выше правило проверки “на четность”
может выполняться при четном числе ошибок).
Рассмотрим пример на построение проверочной матрицы СЛБ (7,4)– кода,
при использовании порождающей матрицы )х(G
n,k
.
Пример. Построить проверочную матрицу
)x(H
n,l
СЛБК по заданной
производящей матрице )х(G
n,k
= )x(G
7,4
вида
=
7,4
G
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
0
1
1
1
1
0
1
1
1
1
0
1
=
0
0
0
1
0
0
1
0
0
1
0
0
1
0
0
0
×
0
1
1
1
1
0
1
1
1
1
0
1
.
И П
Решение:
для заданной )х(G
n,k
кода строим проверочную матрицу
)x(H
n,l
=
)x(H
7,3
вида:
1
a
2
a
3
a
4
a
1
b
2
b
3
b
)x(H
7,3
=
0
1
1
1
0
1
1
1
0
1
1
1
0
0
1
0
1
0
1
0
0
,
.1111aaab
1111aaab
1111aaab
4313
4212
3211
=⊕⊕=⊕⊕=
=⊕⊕=⊕⊕=
=
⊕
⊕
=
⊕
⊕
=
проверочные символы
для 1-ой строки )x(G
7,4
.
Из приведенных выше сведений о порождающей )х(G
n,k
и проверочной
)x(H
n,l
матрицах следует, что основными свойствами данных матриц являются
[1…4]:
1. Порождающая матрица
)х(G
n,k
(n,k) – кода является проверочной
матрицей H(x) дуального кода (n′,k′,
0
d );
2. (n,k)- код содержит ненулевое слово веса Хэмминга не более
0
d
ω тогда и
только тогда, когда матрица H(x) содержит множество из
0
d
ω линейно зависимых
столбцов;
3. (n,k)- код имеет минимальный вес не менее
0
d
ω
тогда и только тогда, когда
каждое множество из (
0
d
ω
-1) столбцов матрицы H(x) линейно независимы.