Фурсов В.А. Лекции по теории информации

Подождите немного. Документ загружается.

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







 

 

 

 

 

 

 

M E P

 

     

 

, (13.2)

где

i j

– проверочные символы.

При умножении в соответствии с (13.1) вектор-строки





, ,

k k

a a

A



на

матрицу

n k

(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)

В данном случае первые

символов вектор-строки

всегда информацион-

ные, а последние

n k



– так называемые проверочные символы являются их

линейными комбинациями:

, 1,

j i i j

a a p j k n



  



. (13.4)

Заметим, что формирование кодовой комбинации по правилу (13.3) сводится к

поразрядному сложению строк образующей матрицы с номерами, соответст-

вующими номерам ненулевых информационных символов вектора

13.3 Построение матрицы-дополнения

Из (13.2) – (13.4) видно, что матрица-дополнение содержит всю информа-

цию о схеме построения кода. Например,

i j



говорит о том, что в образова-

нии

-го проверочного разряда





j k n

  участвовал

-й





i k

 информа-

ционный разряд. Следовательно, по матрице-дополнению всегда можно запи-

сать уравнения кодирования в виде (11.11) или (13.4).

Наоборот если заданы уравнения кодирования, то значение любого симво-

ла

i j

матрицы-дополнения может быть определено путем применения соот-

ветствующего уравнения для формирования j-го проверочного разряда к i-й

строке единичной матрицы.

Существует формальный способ построения матрицы дополнения, осно-

ванный на следующем требовании. Вектор-строка, получающаяся в результате

112

суммирования любых





, 1

l l k

 

строк матрицы дополнения, должна содер-

жать не менее

min

d l



отличных от нуля символов, где

min

– минимальное ко-

довое расстояние. В соответствии с указанным требованием матрица-

дополнение может строиться с соблюдением следующих правил:

1) количество единиц в строке должно быть не менее

min



;

2) сумма по модулю два двух любых строк должна содержать не менее

min



единиц.

При соблюдении указанных требований комбинация, полученная суммирова-

нием любых 2-х строк образующей матрицы, будет содержать не менее

min

не-

нулевых символов.

13.4 Понятие и построение проверочной (контрольной) матрицы

Код представляет собой

-мерное векторное пространство. Образующая

матрица

n k

определяет

-мерное подпространство. Следовательно, сущест-

вует ортогональное подпространство размерности

n k



. Пусть

1,1 1,

,1 ,

n k n k n

h h

 

 

 



 

 



  



(13.5)

– матрица, векторы-строки которой задают это подпространство.

В силу ортогональности указанных подпространств

n k



M H . Следова-

тельно, для разрешенного кодового слова

будем иметь:

T T

n k n k

 

A H A M H . (13.6)

Матрица

, для которой имеет место равенство (13.6), всегда существует и на-

зывается проверочной (контрольной) матрицей, а указанное выражение исполь-

зуется для определения ошибок в кодовой комбинации. Подчеркнем, что в со-

ответствии с (13.6) векторы, соответствующие разрешенным кодовым комби-

нациям, принадлежат нуль-пространству матрицы

Для систематического кода проверочная матрица имеет вид

113

k n k n k

 

 



 

H P E

. (13.7)

Нетрудно заметить, что в данном случае

 

0,0,...,0

k n k

n k n k

n k



 

 

     

 

 

A H A A S

 ,

где

– вектор, компоненты которого определяются как

0, 1,

i i j j

a p a j k n



   



Если кодовый вектор

n i



содержит ошибки:

n n n

 

A A



, (



ξ ),





T T T T

n n n n n

     

   

     

ξ H A H ξ H ξ H

При этом компоненты

, 1,

j i i j j

S p j k n

 



   



вектора

могут отличаться от нуля. Они зависят только от вектора ошибок, а

составленный из них вектор

является опознавателем ошибки (синдромом).

13.5 Границы для числа разрешенных комбинаций

Опираясь на понятие проверочной матрицы можно построить так назы-

ваемую границу Варшамова-Гилберта для числа проверочных символов кода

длины

с заданным минимальным кодовым расстоянием

В соответствии с (13.6) код является разрешенным тогда и только тогда,

когда

i i





h , (13.8)

где

–

-й столбец

m n



матрицы

. Ясно, что число столбцов матрицы

которые входят в (13.8) с ненулевыми коэффициентами, равно весу кодового

слова, а вектор, соответствующий этому кодовому слову, принадлежит нуль-

пространству матрицы

114

Отсюда, в частности, следует, что любой код, принадлежащий нуль-

пространству матрицы

, имеет минимальный вес, а следовательно и мини-

мальное кодовое расстояние равное самое меньшее

, тогда и только тогда, ко-

гда любые



или меньше столбцов матрицы

линейно-независимы.

Матрица

, обладающая указанным свойством, может быть построена пу-

тем последовательного добавления столбцов по следующему правилу. В каче-

стве первого столбца берется любая ненулевая последовательность длины

m n k

 

. Вторым столбцом может быть любая некратная первой ненулевая по-

следовательность длины

. Третий столбец – любая последовательность длины

не являющаяся линейной комбинацией первых двух. Вообще в качестве

-го

столбца берется любая последовательность длины

, не являющаяся линейной

комбинацией никаких



или меньше предыдущих столбцов. При этом ни-

какая линейная комбинация из



или меньше столбцов матрицы не обраща-

ется в нуль.

Число всех возможных двоичных линейных комбинаций из



или

меньше столбцов, выбранных из общего числа

столбцов, в наихудшем случае

(когда все они различны) равно

1 2 2

...

d i

n n n n

C C C C





   



. (13.9)

Очередной столбец может быть присоединен к матрице в том случае, если

число комбинаций определяемых суммой (13.9) меньше, чем общее число от-

личных от нуля последовательностей длины

2 1

i m





 



. (13.10)

Таким образом, возможно построение кода длины

с минимальным расстоя-

нием

проверочными символами, где

– наименьшее целое число,

удовлетворяющее неравенству (13.10).

Соответствующая неравенству (13.10) граница (Варшамова-Гилберта) по-

лучена в расчете на наихудший случай. Она указывает лишь на принципиаль-

ную возможность реализации

-разрядного кода с заданной корректирующей

115

способностью. Представляет интерес установить также верхнюю границу для

оптимального кода, обеспечивающего заданную корректирующую способность

при минимальной избыточности. Определим наибольшее число разрешенных

кодовых комбинаций для

-значного помехоустойчивого кода, обладающего

способностью исправлять ошибки до кратности

включительно.

Подмножество запрещенных комбинаций для каждой разрешенной содер-

жит

, 1,

C i s





элементов. Вместе с разрешенной общее число комбинаций

в подмножестве составляет

, 0,

C i s





. Следовательно, при разложении

группы на непересекающиеся классы число разрешенных комбинаций не может

превышать величину, определяемую неравенством

2 2

k n i







. (13.11)

Приведенное соотношение (13.11) называют оценкой Хэмминга. Если в этом

выражении имеет место равенство, код называют плотно упакованным.

13.6 Матричное представление циклических кодов

Циклический код является групповым кодом, поэтому он может строиться

с использованием матричных представлений так, как описано выше. Однако в

данном случае появляются также некоторые дополнительные возможности,

связанные со свойством цикличности. Рассмотрим способы построения обра-

зующей матрицы циклического кода.

Способ 1. Пусть образующий многочлен задан в виде





1 0

...

g x g x g x g

   

Тогда образующая матрица может быть построена путем умножения





g x

на

одночлен

x k n m



 

и последующим циклическим сдвигом так, что каждая

-я строка образующей матрицы составляется из коэффициентов многочлена





k i

g x x





(

i k

 ):

116

1 0

0 0

m m

n k

m m

g g g



 

 



 

 

 

 

      

 

. (13.12)

Способ 2. Рассматриваются многочлены





Q x

, соответствующие коду, со-

держащему только один ненулевой разряд:





, 1,

n i

Q x x i k



  . Для них вычис-

ляются остатки













i i

r x Q x g x

 . Каждая

-я строка образующей матрицы

формируется путем сложения по модулю два указанных многочленов и соот-

ветствующих им остатков. При этом образующая матрица (в данном случае

систематического кода) представляется двумя подматрицами:

, ,

n k k k n k



 



 

M E P

где

– единичная

k k



- матрица, а строками матрицы дополнения

k n k



P яв-

ляются остатки





, 1,

r x i k

 .

13.7 Построение проверочной матрицы циклического кода

Проверочная матрица в данном случае может строиться так же, как в слу-

чае обычного группового кода, например, с использованием проверочных ра-

венств и/или матрицы-дополнения. Однако для циклического кода существует

еще один способ построения проверочной матрицы, заключающийся в делении

многочлена



на многочлен





g x



, являющийся дополнением к образую-

щему. Многочлен дополнения соответствует кодовой комбинации, которая по-

лучается из комбинации, соответствующей образующему многочлену путем

перестановки символов в обратном порядке.

Предположим, что в результате деления двучлена



на многочлен до-

полнения получен некоторый многочлен:

 

1 0

...

b x b x b

g x





  

. (13.13)

Из коэффициентов этого многочлена составляется первая строка проверочной

матрицы, а остальные строки образуются циклическим сдвигом:

117

1 0

0 0

b b b

 

 



 

 

 

      

 

. (13.14)

В качестве примера построим проверочную матрицу для кода (7,4), порож-

даемого образующим многочленом





 xxxg . Соответствующий много-

член дополнения





231





xxxg . В результате деления на него двучлена



получаем многочлен

234



. Соответствующая этому многочле-

ну проверочная матрица имеет вид















1011100

0101110

0010111

Нетрудно убедиться, что любая разрешенная комбинация

A , полученная

путем умножения некоторого заданного информационного многочлена





xa на

указанный выше образующий многочлен:





xg , в результате умножения на

транспонированную проверочную матрицу:

HA дает синдром, состоящий из

одних нулей.

118

Лекция 14

Кодирование линейными последовательными машинами

14.1 Понятие линейной последовательной машины

Линейная последовательная машина (ЛПМ) – это система с конечным

числом входов

, 1,

u i l



и выходов

, 1,

y j m

 , сигналы на которых наблюдают-

ся в дискретные моменты времени, и

выполняющая следующие элементар-

ные функции (рис. 14.1) [2]:

1) сложение:

y u





;

2) умножение на постоянную:

y u





;

3) задержка:









y t u t

 

Здесь и далее под аргументом сигнала подразуме-

вается номер момента времени.

Общая схема ЛПМ может быть представлена в

виде, показанном на рис. 14.2. Число задержек оп-

ределяет размерность ЛПМ. Запрещаются петли,

не содержащие ни одной задержки, т.к. это приво-

дит к неопределенности в описании состояний





, 1,

s t i k

 . Для ЛПМ размерности

имеют место равенства









1 , 1,

i i

s t s t i k



   или в векторном виде









' 1

t t

 

s s

где





–



-вектор состояний. Множество векторов





образует простран-

ство состояний ЛПМ.

Рис. 4.1 – Элементы ЛПМ

Рис. 14.2 – Общая схема

ЛПМ

119

14.2 Матричное описание ЛПМ

В соответствии с общей схемой (рис. 14.2) работу ЛПМ можно описать

следующими соотношениями

     

1 1

1 , 1,

k l

i ij j ij j

j j

s t a s t b u t i k

 

   

 

, (14.1)

     

1 1

, 1,

k l

i ij j ij j

j j

y t c s t d u t i m

 

  

 

. (14.2)

Равенства (14.1), (14.2) можно представить компактно в векторно-матричной

форме:













t t t

  

s As Bu

, (14.3)













t t t

 

y Cs Du

, (14.4)

где

–

k k



k l



m k



m l



-матрицы, а

–



-векторы соответственно.

По соотношениям (14.3), (14.4) нетрудно выписать реакцию системы на

любом шаге. В частности, при отсутствии входного сигнала (







u ), выход-

ной сигнал на шаге

связан с начальным состоянием ЛПМ соотношением вида

















1 .... 0

t t t    

y Cs CAs CA s

. (14.5)

14.3 Каноническая и естественная нормальная форма ЛПМ

Аннулирующим многочленом для матрицы

является многочлен







та-

кой, что









A .

Аннулирующий многочлен минимальной степени со старшим коэффициентом,

равным единице, называется минимальным.

Многочлен









det

x x



 

A E

называется характеристическим. По теореме Гамильтона-Кэли всякая матрица

удовлетворяет своему характеристическому многочлену, т.е.









A .

120

Следовательно, характеристический полином всегда является аннулирующим,

но не обязательно минимальным.

Матрица

 

0 1 1



  



 

 



 

  

 



    

 

(14.6)

называется канонической (сопровождающей) матрицей для многочлена\





1 1 0

...

k k

x x x x

   



    

Многочлен







может быть разложен на элементарные множители:

             

1 2

1 2 1 2

l l l

r r

x x x x p x p x p x

   

 

     

     

  .

Многочлены





, 1,

x i r



 называют элементарными делителями матрицы

 



A . С использованием указанного разложения на элементарные делители

может быть построена естественная нормальная форма матрицы:

 

0 0



 

 



 

 



   



, (14.7)

где

 

, 1,

i r





A – матрицы вида (14.6).

14.4 Подобные и минимальные ЛПМ

Преобразование





A PAP

, где

– невырожденная матрица, называется

преобразованием подобия. Преобразование подобия не изменяет собственные

значения матрицы, следовательно, подобные матрицы имеют одинаковые эле-

ментарные делители. В частности, если

 



A подобна некоторой матрице

элементарными делителями









, ,

x x

 



, то она также подобна естествен-

ной нормальной форме (14.7).