Королёв А.И. Коды и устройства помехоустойчивого кодирования
Подождите немного. Документ загружается.
формируются по определенным правилам l проверочных символов и в канал
связи поступают кодовые последовательности (обозначим их через F(x)) длиной
n=(k+l) двоичных кодовых символов. Следовательно, общее количество n-
разрядных (символьных) кодовых последовательностей составит K
общ
=2
n
, из
которых K
зап
=
=
−kn
2
2
l
являются запрещенными и от их количества зависит
корректирующая способность кода.
2.3. Определение взаимосвязи между избыточностью и корректирующей
способностью блоковых кодов
Важнейшей задачей теории кодирования является определение взаимосвязи
между кратностью или длиной корректируемых ошибок и требуемой для этой
цели избыточности кода, т.е. требуется определить какая минимально
необходимая избыточность должна быть разрабатываемого кода, чтобы данный
код гарантировано исправлял ошибки требуемой (заданной) кратности или длины.
Кратность ошибки, как и вводимая избыточность в код, чаще всего
измеряется количеством двоичных символов или бит.
По величине вводимой избыточности принято оценивать эффективность
разработанного или выбранного кода; если сравниваются два, три и т.д. кода,
корректирующих ошибки одинаковой кратности, то наиболее эффективным
считается код, который использует для этого меньшую избыточность. Данный код
чаще всего и надо выбирать для практической реализации.
Коды, которые обеспечивают коррекцию ошибок равной кратности с
другими кодами, но используют для этого меньшую избыточность (меньше
проверочных символов), называются совершенными или плотно упакованными
кодами.
Следовательно, совершенный код будет обеспечивать эффективное
использование пропускной способности как канала связи, так и сети связи в
целом.
Однако на практике совершенные коды часто технически просто
нереализуемы; либо имеют высокую сложность реализации (требуется RG очень
большой длины), либо обеспечивают коррекцию ошибок небольшой кратности:
одиночные и двойные ошибки [1…4].
Следовательно, при разработке или выборе кода важно правильно выбрать
избыточность кода, т.е. какое минимально необходимое число проверочных
символов “l” необходимо ввести в передаваемый информационый блок.
Нетрудно видеть, что это число, т.е. “l”—число проверочных символов, будет
зависеть от статистики ошибок в дискретном канале связи (ДКС).
Данная задача или проблема решается довольно просто, если требуется
построить код, обнаруживающий либо одиночные (нечетные ошибки), либо
двойные (четные) ошибки.
В первом случае для этого достаточно ввести один проверочный
(контрольный) символ, а во втором случае—ввести два проверочных символа.
Абсолютная “l” и относительная “r” избыточность данных кодов
соответственно будет составлять:
l
1
=n
1
-k
1
=1;
1k
1
11k
1
1n
1
1n
1k1n
1r
+
=
+
==
−
= ;
l
2
=n
2
-k
2
=2;
.
2k
2
22k
2
2n
2
2n
2k2n
2r
+
=
+
==
−
=
Откуда следует, что относительная избыточность “r”, которую можно назвать
коэффициентом избыточности, стремится к 0, если n стремится к бесконечности,
т.е. если k стремится к бесконечности.
Задача определения оптимального количества проверочных символов в
кодовой последовательности существенно усложняется, когда требуется
разработать или выбрать код корректирующий ошибки. Общая идея исправления
(коррекции) ошибок кратности не более t
исп.
двоичных символов состоит в
следующем [1].
Общее число кодовых последовательностей n-разрядного кода, равное
K
общ
=2
n
, разбивается на N подклассов по числу N=K
p
=2
k
разрешенных кодовых
последовательностей. Разбиение осуществляется таким образом, чтобы в каждый
подкласс входили одна разрешенная и ближайшие к ней запрещенные кодовые
последовательности. При декодировании определяется, какому подклассу
принадлежит принятая кодовая последовательность. Если кодовая
последовательность принята с ошибкой, т.е. является запрещенной, то она
исправляется на разрешенную, принадлежащую тому же классу, что и
запрещенная, т.е. из одного и того же подкласса.
Пусть имеется блоковый код с параметрами (n, k, d
0
), который исправляет
ошибки кратностью или длиной от “1” до “t” включительно.
Так как количество ошибок кратности “m” двоичных символов (m-общее
обозначение ошибок) на длине “n” двоичных символов, равно числу сочетаний из
“n” по “m”, то общее количество ошибок (которое обозначим N) кратности “1”до
“t”, возможных в одной кодовой последовательности, равно:
∑
=
=
t
1i
m
nt
CN .
Как уже отмечалось выше двоичный блоковый код с параметрами (n,k,d
0
)
образует:
K
общ
=
n
2
– общее число кодовых последовательностей;
k
.раз
2К =
– количество разрешенных кодовых последовательностей;
l
222ККК
kn
.раз.общ.корр
=−=−=
– количество кодовых
последовательностей, которые код может исправить.
Следовательно, значения К
общ.
и К
раз.
должны выбираться так, чтобы
выполнялось следующее неравенство:
.раз.общ.раз
КKN*К −≤ или )N1(*KК
t.раз.общ
+≥ . (2.1)
Произведение
t.общ
N*K
характеризует общее число ошибок, которое может
исправить (n,k,d
0
) –код в К
раз.
разрешенных кодовых последовательностях.
Логарифмируя выражение (2.1) можно получить выражение, которое
позволяет определить необходимое число проверочных или избыточных
двоичных символов для коррекции ошибок заданной кратности, а именно:
l
∑
=
≥−=
t
1i
m
n
Clogkn
.
Наиболее строго соотношение между параметрами линейных блоковых
кодов n, k и l устанавливаются соответствующими границами:
- нижней границей Хэмминга;
- верхней границей Варшамова-Гильберта.
Эти границы устанавливаются следующими неравенствами [1…4]:
))C...CC(log())C...CC(log(
t2t2
1n
2t2
1n
1t2
1n
tt
n
1t
n
t
n
−
−
−
−
−
−
−−
+++<<+++ l
. (2.3)
нижняя граница верхняя граница
Хэмминга Варшамова-Гильберта
Для приближенных расчетов можно пользоваться формулой [1…3]:
l
!t
n..nn
log
tt1tt
2
−−
+++
= . (2.4)
Для кодов, используемых для обнаружения ошибок, и при заданном числе
информационных символов (т.е. “k”=const), справедливо следующее выражение
для определения “l” [1…5]:
l )].1k(log)1k[(log1
22
++++≥ (2.5)
Для кодов корректирующих одиночные ошибки количество “l” проверочных
символов может быть определено из решения следующих равенств-неравенств
(формулы Хэмминга):
)1n(*22
kn
+≥ ; (2.6)
)1n(
2
2
n
k
+
≤ ; (2.7)
n
1
2
l
−
≤
. (2.8)
Для пользования последними тремя формулами необходимо иметь значение
одного параметра, а два остальных находятся методом подбора.
Для кодов Хэмминга, с 3d
o
= , т.е. корректирующих одиночные ошибки,
количество разрешенных кодовых последовательностей должно удовлетворять
следующему равенству:
)1n(
2
K
n
.раз
+
= ,
первые “k” символов кодовой последовательности кода используются в качестве
информационных символов, и их число должно удовлетворять следующему
равенству:
).1n(logn
)1n(
2
logk
2
n
2
+−=
+
= (2.9)
2.4. Принципы построения линейных блоковых кодов
2.4.1.Общие сведения о правилах построения линейных блоковых кодов
Основным принципом построения линейных блоковых кодов (ЛБК) является
отыскание таких процедур, которые позволяют при кодировании получать все
разрешенные кодовые последовательности путем конечного числа несложных
линейных преобразований одной или “k” исходных разрешенных кодовых
последовательностей, а при декодировании для обнаружения и исправления
ошибок не хранить в памяти все разрешенные последовательности, а получать
информацию об ошибках по результатам конечного числа относительно простых,
линейных преобразований над двоичными символами принятых кодовых
последовательностей.
Основная (идея) задача оптимального кодирования или построения
избыточного кода заключается в таком выборе числа разрешенных кодовых
последовательностей заданной длины, чтобы обеспечивалось самое максимальное
кодовое расстояние. В таком случае полученный ЛБК будет обладать наилучшей
корректирующей способностью и минимальной вероятностью некорректируемых
ошибок.
В теории кодирования доказывается, что максимальное (или наибольшее)
число разрешенных кодовых последовательностей (
k
.раз
2K = ) для n-разрядного
(символьного) двоичного (q=2) ЛБК с минимальным кодовым расстоянием
o
d
заданной величины должны удовлетворять следующим равенствам-неравенствам
[1…4]:
при 1d
0
= ,
n
.общ.раз
2КK == ;
,2d
0
= ;2К
1n
.раз
−
=
,3d
0
=
;
)1n(
2
K
n
.раз
+
≤
),1t*2(d
.исп0
+≥ .
C1
2
К
0
d
1i
i
n
n
раз
+
≤
∑
=
Для решения поставленной задачи, т.е. выработки оптимального правила
построения ЛБК необходимо было сформулировать и доказать определенные
условия формирования разрешенных кодовых последовательностей.
2.4.2.Условия и свойства формирования разрешенных кодовых
последовательностей ЛБК
В ЛБК сумма по модулю два любого конечного числа разрешенных кодовых
последовательностей также является разрешенной кодовой последовательностью.
Поэтому, выбрав “k” исходных разрешенных кодовых последовательностей,
которые называют базисными и суммируя их посимвольно в “i” различных
сочинениях, можно построить все
∑
=
==
k
1i
i
k
k
.раз
C2К
разрешенных кодовых последовательностей.
Чтобы каждое сочетание порождало новую разрешенную
последовательность и чтобы в конечном итоге их общее число равнялось
k
2
,
необходимо чтобы выполнялись следующие условия (правила):
1) исходные (базисные) кодовые последовательности должны выбираться
различными;
2) нулевая кодовая последовательность (состоящая из одних “0”) не должна
выбираться;
3) исходные кодовые последовательности должны быть линейно-независимыми и
образовывать алгебраическую группу по отношению к операции суммирования
по модулю два и в этом смысле они являются групповыми кодами;
4) вес (число “1”) каждой исходной кодовой последовательности должен быть не
менее
0
d и в общем случае вес кодовой последовательности равен числу
ненулевых символов;
5) вес приписываемой проверочной части строки к исходной информационной
части строки должен быть не менее 1d
o
− ;
6) кодовое расстояние между любыми парами исходных кодовых
последовательностей должен быть не менее
0
d ;
7) минимальное кодовое расстояние
0
d ЛБК равно наименьшему кодовому
расстоянию из всей совокупности полученных кодовых расстояний (d) при
попарном суммировании по модулю два двоичных символов сравниваемых
последовательностей. Минимальное кодовое расстояние
0
d также будет
определять и минимальный вес кодовых последовательностей конкретного, т.е.
проектируемого или выбираемого кода; т.е.
0min
dw =
.
Последнее свойство является очень важным, так как это свойство
значительно упрощает определение корректирующей способности данных кодов
и принципы их построения.
2.5. Принципы построения систематических двоичных линейных
блоковых кодов
Последнее свойство двоичного ЛБК позволяет выработать довольно простой
общий принцип построения систематического двоичного линейного блокового
кода (СЛБК), основываясь на том, что для данных кодов нет необходимости сразу
же приводить все
k
2
разрешенных кодовых последовательностей, а лишь часть их
и далее указать принцип или способ их преобразования.
В теории кодирования доказывается, что для построения СЛБК достаточно
иметь “k” линейно независимых кодовых последовательностей и указать принцип
или способ построения остальных
)k2(
k
−
разрешенных последовательностей.
Более строгим определением систематического кода является следующее:
систематическим (n,k) – кодом называется такой ЛБК, каждая кодовая
последовательвость которого начинается с блока “k” информационных символов
и заканчивается блоком l=(n-k) проверочных символов и задается соответственно
систематической порождающей матрицей вида ]PI[)x(G
,kk,kn,k l
M= и
систематической проверочной матрицей вида ].I,P[)X(H
T
n,
−=
l
Таким образом, каждый линейный блоковый код будет эквивалентен
систематическому ЛБК, если код формируется путем умножения
информационного блока Q(x) на каноническую порождающего матрицу G
k,n
(x),
т.е. F(x)=Q(x)·G(x)=Q(x)·[
l,kk,k
PI M ] или по-другому – путем умножения Q(x) на
G(x), представленную в систематическом виде.
Как уже отмечалось выше, корректирующая способность любого кода
определяется вводимой избыточностью, т.е. числом проверочных или
избыточных двоичных символов, обозначаемых, чаще всего, буквой “l”, которая
равно l=n-k двоичных символов; “k”– определяет число информационных
символов a, “n”– число кодовых двоичных символов в кодовой
последовательности.
Следовательно, кодовую последовательность или кодовый вектор СЛБК
можно записать в виде следующей последовательности:
l
b...bbba...aaa)х(F
321k321i
=
,
где
k321
a...aaa
- информационные символы (логические “1” и “0”),
l
b...bbb
321
- проверочные символы (логические “1” и “0”).
Проверочные символы
l
b...bbb
321
формируются путем суммирования по
модулю два информационных символов, стоящих на определенных позициях.
Алгоритм формирования проверочных символов в общем виде можно
записать так:
kjk22j11jj
ac...acacb ⋅⊕⊕⋅⊕⋅=
, j=1…l, (2.10)
где
jk2j1j
c,...c,с
- коэффициенты принимающие значение логических “1” и “0”.
Утверждение: Любая кодовая последовательность, состоящая из “k”
информационных символов, все проверочные символы которой сформированы из
информационных символов по формуле (2.10) является разрешенной кодовой
последовательностью (n, k) СЛБЛК.
Доказательство данного утверждения можно выполнить так:
пусть
(
)
l
b...ba...aaaxF
13211 κ
=
и
(
)
l
b...ba...aaaxF
13212 κ
=
— есть две разрешенные
кодовые последовательности СЛБК, то
(
)
(
)
(
)
(
)
(
)
(
)
(
)
(
)
,bb,...,bb,aa,...,aa,aaxFxFxF
l
112211213 l
⊕⊕⊕⊕⊕=⊕=
κκ
где
(
)
( )
( ) ( ) ( )
.,...,2,1j,aac...aacaacbbb
;k,...,2,1i,aaa
kkjk222j111jjjj
iii
l=⊕⊕⊕⊕⊕⊕=⊕=
=⊕=
∗
∗
Из последнего равенства следует, что любые “k” линейно независимые
кодовые последовательности n-мерного линейного векторного пространства
порождают k-мерное подпространство, образуя базис этого подпространства и,
следовательно, полностью доказывает, что для задания СЛБ (n, k) – кода
достаточно выбрать “k” любых линейно независимых разрешенных кодовых
последовательностей, а остальные разрешенные кодовые последовательности
получают как линейные комбинации “k” выбранных исходных кодовых
последовательностей или кодовых векторов.
Обычно набор из “k” линейно независимых кодовых последовательностей
порождающих или формирующих СЛБ (n, k)–код записывают в виде матрицы,
называемой производящей или порождающей матрицей, обозначаемой как G
k,n
(х).
В общем виде порождающая матрица может быть записана так [1…4]:
()
=
1.k
1.2
1.1
n,k
a
a
a
xG
M
k.k2.k
k.22.2
k.12.1
aa
aa
aa
L
M
L
L
1.k
1.2
1.1
b
b
b
2.k
2.2
2.1
b
b
b
L
M
L
L
1.k
1.2
1.1
b
b
b
. (2.11)
Размерность или ранг матрицы определяется параметрами (n,k) —кода, а
именно значениями k, n и l.
Говорят, что размерность или ранг матрицы равен (k x n); это означает, что
матрица содержит k — строк и n — столбцов.
Очевидно, что порождающая матрица
G
k,n
(х) двоичного кода порождает
ровно 2
k
разрешенных кодовых последовательностей.
Представленная G
k,n
(x) может быть разделена на две подматрицы:
И – информационную подматрицу рангом (k x k), т.е. содержащая k – строк
и k – столбцов;
П – проверочную подматрицу рангом (k x l), т.е. содержащая k – строк и l –
столбцов;
Следовательно, порождающую матрицу G
k,n
(x) можно представить так:
G
k,n
(x)=
1.k
1.1
a
a
M
L
L
k.k
k.1
a
a
M
.
1.k
1.1
b
b
M
L
L
l
l
.k
.1
b
b
M
=
И
·
П
. (2.12)
Так как информационные символы занимают обычно первые “k” позиций в
кодовых последовательностях то G
k,n
(x), содержащую “k” линейно независимых
кодовых последовательностей целесообразно представить состоящий из
единичной матрицы, т.е. матрицы, содержащей главную диагональ, составленную
из логических “1” и имеющей ранг (k x k) и которая полностью характеризует
кодовые последовательности простого (безызбыточного) кода.
Единичная матрица имеет следующий вид [1…4]:
=
0
.
0
1
)x(I
k,k
0
.
1
0
0
.
0
0
L
L
L
.
1
.
0
0
. (2.13)
Если теперь к единичной матрице приписать справа проверочную
подматрицу, то получим каноническую порождающую матрицу, которую можно
записать так [1…4]: