Лекции по теории информации. Фурсов teoria_informacii. Лекции по теории информации под редакцией Н. А. Кузнецова

• Название: Лекции по теории информации под редакцией Н. А. Кузнецова
• Анкор: Лекции по теории информации
• Дата: 17.04.2022
• Размер: 1.32 Mb.
• Имя файла: Фурсов teoria_informacii.pdf
• Тип: Лекции; #480820
• страница: 12 из 16

12.5 Методы формирования комбинаций и декодирования
циклического кода
Способ 1. Для построения
n
-разрядной разрешенной комбинации много- член
 
a x
, соответствующий кодируемой последовательности информацион- ных символов, умножается на образующий многочлен:
 
   
q x
a x g x

(12.3)
При декодировании (возможно отличающийся от
 
q x
) многочлен
 
q x

, соот- ветствующий принятой комбинации, делят на
 
g x
. Ясно, что в случае отсут- ствия ошибок сразу получится исходный многочлен
 
a x
. Если в принятой комбинации содержится ошибка, при делении образуется остаток
 
r x
, т.е.
 
 
 
 
 
q x
g x
f x
r x
g x



По остатку определяется класс вычетов и производится исправление ошибки.
Недостаток данного способа кодирования заключается в том, что после обнаружения и исправления ошибки необходимо снова делить на
 
g x
для то- го, чтобы выделить информационные символы.

108
Способ 2. Многочлен, соответствующий исходной информационной по- сылке
 
a x
, умножается на
m
x
. Образовавшиеся после умножения свободные младшие разряды заполняются остатком от деления данного выражения на об- разующий многочлен:
 
 
 
m
q x
a x
x
r x



(12.4)
Многочлен
 
q x
обязан делиться на
 
g x
без остатка. Покажем это.
При делении
 
m
a x x
на
 
g x
в общем случае имеем
 
 
 
 
 
m
a x
x
g x
c x
r x
g x



, где
 
c x
– целый полином. Это равенство (с учетом того, что операции вычита- ния и сложения по модулю два совпадают) можно переписать в виде
 
 
 
 
 
m
a x
x
g x
r x
g x
c x



, или
 
 
 
   
m
q x
a x
x
r x
c x g x




Из (12.4) видно, что в данном случае информационные символы всегда ос- таются на первых
k
позициях. Такой код называют систематическим. При та- ком способе кодирования после исправления ошибок сразу становится извест- ной исходная кодовая последовательность, занимающая первые
k
позиций.
Существует также третий способ кодирования, который реализуется в виде рекуррентных соотношений с использованием так называемого генераторного многочлена. Этот способ, реализуемый с использованием так называемых ли- нейных последовательных машин, мы рассмотрим в разделе 14.6.

109
Лекция 13
Матричные представления в теории кодирования
13.1 Групповой код как подпространство линейного
пространства
Линейным (векторным) пространством
V
над полем  называют множе- ство элементов (векторов), для которого выполняются аксиомы:
1) множество
V
является коммутативной группой по сложению;
2) для любого
V

v
и скаляра
c
определено
c
V

v
(замкнутость);
3) для любых
v
,
x
из
V
и

,

из 









v
v
v
,








v
x
v
x
(дистрибутивность);
4) если
v
– вектор из
V
, а

,

– скаляры, то





 

v
v
(ассоциатив- ность к умножению на скаляр) и
1

v
v
Множество
n
-разрядных двоичных комбинаций помехоустойчивого кода можно рассматривать как векторное линейное пространство над полем
 
2

с операцией сложения по модулю 2, а кодовые комбинации – как его векторы.
Действительно, если определить операцию умножения последовательности из
n
элементов поля
 
2

(кодовой комбинации) на элемент
i
a поля
 
2

аналогично правилу умножения вектора на скаляр:

 

1 2
1 2
,
,...,
,
,...,
i
n
i
i
i
n
a a a
a
a a a a
a a

, то все указанные выше аксиомы выполняются.
Подмножество элементов векторного пространства, удовлетворяющее ак- сиомам векторного пространства, называют подпространством. По-видимому, множество векторов, соответствующих разрешенным комбинациям, образует подпространство векторного пространства всех
n
-разрядных кодовых комби- наций над полем
 
2

Заметим, что такое подпространство комбинаций над полем
 
2

, вооб- ще говоря, образует любая совокупность двоичных кодовых комбинаций, яв-

110 ляющаяся подгруппой группы всех
n
-разрядных двоичных кодовых комбина- ций.
13.2 Понятие образующей матрицы, построение разрешенных ко-
довых комбинаций с использованием образующей матрицы
Расположим
2 1
k

разрешенных
n
-разрядных кодовых комбинаций друг под другом в виде строк матрицы M размерности


2 1
k
n

 . Поскольку
n
k

проверочных символов каждой строки этой матрицы формируются в виде ли- нейных комбинаций информационных символов, только
k
столбцов этой мат- рицы будут линейно независимыми, т.е. rank
k

M
. Это означает, что среди строк (кодовых комбинаций) матрицы M только
k
линейно независимых.
Образующей (порождающей) называется матрица, состоящая из любых
k
линейно независимых векторов (строк). Совокупность этих векторов образует базис пространства. Все остальные разрешенные комбинации могут быть пред- ставлены в виде линейной комбинации базисных векторов. Если образующая матрица содержит
k
строк по
n
элементов поля
 
2

, соответствующий код называют


,
n k
-кодом.
Если известна образующая матица
,
n k
M
, любая
n
-разрядная разрешенная комбинация (
1
n 
-вектор
n
A ) может быть получена путем умножения
k
-разрядной комбинации, составленной из информационных символов
(
1
k 
-вектора
k
A ) на образующую матрицу:
,
n
k
n k


A
A
M
(13.1 )
Перестановка строк (столбцов) образующей матрицы приводит к эквивалент- ному коду с той же корректирующей способностью.
Если формируемый код должен быть систематическим, образующая мат- рица представляется в виде двух блоков: единичной
k
k

-матрицы
k
E и так на- зываемой матрицы-дополнения
,
k n k

P
размерности


k
n
k


:

111 1,
1 1,
,
,
,
,
1
,
1 0 |
|
0 1 |
k
n
n k
k
k n k
i j
k k
k n
p
p
p
p
p



















M
E P



  




,
(13.2) где
,
i j
p
– проверочные символы.
При умножении в соответствии с (13.1) вектор-строки


1
,
,
k
k
a
a

A

на матрицу
,
n k
M
(13.2) получаем


,
,
n
k
n k
k
k
k
k n k
k
n k









A
A M
A E A P
A A


(13.3)
В данном случае первые
k
символов вектор-строки
n
A всегда информацион- ные, а последние
n
k

– так называемые проверочные символы являются их линейными комбинациями:
,
1
,
1,
k
j
i
i j
i
a
a p
j
k
n





(13.4)
Заметим, что формирование кодовой комбинации по правилу (13.3) сводится к поразрядному сложению строк образующей матрицы с номерами, соответст- вующими номерам ненулевых информационных символов вектора
k
A .
13.3 Построение матрицы-дополнения
Из (13.2) – (13.4) видно, что матрица-дополнение содержит всю информа- цию о схеме построения кода. Например,
,
1
i j
p

говорит о том, что в образова- нии
j
-го проверочного разряда


1,
j
k
n


участвовал i -й


1,
i
k

информа- ционный разряд. Следовательно, по матрице-дополнению всегда можно запи- сать уравнения кодирования в виде (11.11) или (13.4).
Наоборот если заданы уравнения кодирования, то значение любого симво- ла
,
i j
p
матрицы-дополнения может быть определено путем применения соот- ветствующего уравнения для формирования j-го проверочного разряда к i-й строке единичной матрицы.
Существует формальный способ построения матрицы дополнения, осно- ванный на следующем требовании. Вектор-строка, получающаяся в результате

112 суммирования любых


,
1
l
l
k
 
строк матрицы дополнения, должна содер- жать не менее min
d
l
 отличных от нуля символов, где min
d
– минимальное ко- довое расстояние. В соответствии с указанным требованием матрица- дополнение может строиться с соблюдением следующих правил:
1) количество единиц в строке должно быть не менее min
1
d
 ;
2) сумма по модулю два двух любых строк должна содержать не менее min
2
d
 единиц.
При соблюдении указанных требований комбинация, полученная суммирова- нием любых 2-х строк образующей матрицы, будет содержать не менее min
d
не- нулевых символов.
13.4 Понятие и построение проверочной (контрольной) матрицы
Код представляет собой
n
-мерное векторное пространство. Образующая матрица
,
n k
M
определяет
k
-мерное подпространство. Следовательно, сущест- вует ортогональное подпространство размерности
n
k

. Пусть
1,1 1,
,1
,
n
n k
n k n
h
h
h
h






 





H





(13.5)
– матрица, векторы-строки которой задают это подпространство.
В силу ортогональности указанных подпространств
,
0
T
n k

M
H
. Следова- тельно, для разрешенного кодового слова
n
A будем иметь:
,
0
T
T
n
k
n k


A H
A M
H
(13.6)
Матрица H , для которой имеет место равенство (13.6), всегда существует и на- зывается проверочной (контрольной) матрицей, а указанное выражение исполь- зуется для определения ошибок в кодовой комбинации. Подчеркнем, что в со- ответствии с (13.6) векторы, соответствующие разрешенным кодовым комби- нациям, принадлежат нуль-пространству матрицы
T
H
Для систематического кода проверочная матрица имеет вид

113
,
T
k n k
n k




 

H
P
E

(13.7)
Нетрудно заметить, что в данном случае




,
0,0,..., 0
k n k
T
n
k
n k
n k








   







P
A H
A A
S
E

, где
S
– вектор, компоненты которого определяются как
,
1 0,
1,
k
i
i j
j
i
a p
a
j
k
n






Если кодовый вектор
,
n i
A

содержит ошибки:
n
n
n


A
A
ξ

, (
0
n

ξ
),


T
T
T
T
n
n
n
n
n
















A
ξ H
A H
ξ H
ξ H
При этом компоненты
j
S
:
,
1
,
1,
k
j
i
i j
j
i
S
p
j
k
n








вектора
S
могут отличаться от нуля. Они зависят только от вектора ошибок, а составленный из них вектор
S
является опознавателем ошибки (синдромом).
13.5 Границы для числа разрешенных комбинаций
Опираясь на понятие проверочной матрицы можно построить так назы- ваемую границу Варшамова-Гилберта для числа проверочных символов кода длины
n
с заданным минимальным кодовым расстоянием
d
В соответствии с (13.6) код является разрешенным тогда и только тогда, когда
1 0
n
i
i
i
a



h
,
(13.8) где
i
h – i -й столбец
m n

матрицы H . Ясно, что число столбцов матрицы H , которые входят в (13.8) с ненулевыми коэффициентами, равно весу кодового слова, а вектор, соответствующий этому кодовому слову, принадлежит нуль- пространству матрицы
T
H

114
Отсюда, в частности, следует, что любой код, принадлежащий нуль- пространству матрицы H , имеет минимальный вес, а следовательно и мини- мальное кодовое расстояние равное самое меньшее
d
, тогда и только тогда, ко- гда любые
1
d 
или меньше столбцов матрицы H линейно-независимы.
Матрица H , обладающая указанным свойством, может быть построена пу- тем последовательного добавления столбцов по следующему правилу. В каче- стве первого столбца берется любая ненулевая последовательность длины
m
n
k
 
. Вторым столбцом может быть любая некратная первой ненулевая по- следовательность длины
m
. Третий столбец – любая последовательность длины
m
не являющаяся линейной комбинацией первых двух. Вообще в качестве i -го столбца берется любая последовательность длины
m
, не являющаяся линейной комбинацией никаких
2
d 
или меньше предыдущих столбцов. При этом ни- какая линейная комбинация из
1
d 
или меньше столбцов матрицы не обраща- ется в нуль.
Число всех возможных двоичных линейных комбинаций из
2
d 
или меньше столбцов, выбранных из общего числа
n
столбцов, в наихудшем случае
(когда все они различны) равно
2 1
2 2
1
d
d
i
n
n
n
n
i
C
C
C
C








(13.9)
Очередной столбец может быть присоединен к матрице в том случае, если число комбинаций определяемых суммой (13.9) меньше, чем общее число от- личных от нуля последовательностей длины
m
:
2 1
2 1
d
i
m
n
i
C





(13.10)
Таким образом, возможно построение кода длины
n
с минимальным расстоя- нием
d
и
m
проверочными символами, где
m
– наименьшее целое число, удовлетворяющее неравенству (13.10).
Соответствующая неравенству (13.10) граница (Варшамова-Гилберта) по- лучена в расчете на наихудший случай. Она указывает лишь на принципиаль- ную возможность реализации
n
-разрядного кода с заданной корректирующей

115 способностью. Представляет интерес установить также верхнюю границу для
оптимального кода, обеспечивающего заданную корректирующую способность при минимальной избыточности. Определим наибольшее число разрешенных кодовых комбинаций для
n
-значного помехоустойчивого кода, обладающего способностью исправлять ошибки до кратности
s
включительно.
Подмножество запрещенных комбинаций для каждой разрешенной содер- жит
,
1,
i
n
C
i
s


элементов. Вместе с разрешенной общее число комбинаций в подмножестве составляет
,
0,
i
n
C
i
s


. Следовательно, при разложении группы на непересекающиеся классы число разрешенных комбинаций не может превышать величину, определяемую неравенством
0 2
2
s
k
n
i
n
i
C



(13.11)
Приведенное соотношение (13.11) называют оценкой Хэмминга. Если в этом выражении имеет место равенство, код называют плотно упакованным.