ФОРМИРОВАНИЕ БАНКА ПРОВЕРОЧНЫХ МАТРИЦ СИСТЕМАТИЧЕСКИХ ПОМЕХОЗАЩИЩЕННЫХ КОДОВ С ПОМОЩЬЮ МАТРИЧНОГО МУЛЬТИПЛИКАТИВНОГО КОМПОНЕНТА
КРАТКИЕ СООБЩЕНИЯ
УДК [517.938 + 519.713/.718]: 621.398 ФОРМИРОВАНИЕ БАНКА ПРОВЕРОЧНЫХ МАТРИЦ СИСТЕМАТИЧЕСКИХ ПОМЕХОЗАЩИЩЕННЫХ КОДОВ С ПОМОЩЬЮ МАТРИЧНОГО МУЛЬТИПЛИКАТИВНОГО КОМПОНЕНТА А.В. Ушаков, Е.С. Яицкая
С помощью невырожденного матричного мультипликативного компонента формируется банк проверочных матриц систематических помехозащищенных кодов. Ключевые слова: помехозащитное преобразование кодов, проверочная и образующая матрицы.
Помехозащитное преобразование кодов (ППК) представляет собой пятифазный процесс: помехо-
защитное кодирование (ПК) помехонезащищенного информационного кода (ПНЗИК); искажение поме-
хозащищенного кода (ПЗК) при передаче по двоичному каналу связи (КС); помехозащитное декодирова-
ние (ПД) с целью формирования синдрома (опознавателя) ошибки, свидетельствующего о факте, а, воз-
можно, и месте ошибки в коде; формирование сигнала коррекции (ФСК) и коррекция [1].
Алгоритмически ППК может быть описано тремя способами:
1. y aG ; f y ; E fH; ˆ EH ; yˆ f ˆ ;
2. yx arg rest yxg1x 0 ;
f x yxx ;
Ex rest f xg1x ;
ˆx ˆEx;
yˆx f x ˆx ;
3. yk Nak ; xк k 1 Axк k Bкak, k 1,kи ; xкk 1 Axкk,k 1,m ; xк 0 xк kи ;
yk Cxкk ; f k yk k; xдk 1 Axдk Bд f k,k 1,n ; E xд' n; ˆ EH ;
yˆ row f k,k 1,n ˆ ,
где a – ПНЗИК; y – ПЗК; – код помехи в КС, искажающей код y в аддитивной форме;
f – искаженный в КС ПЗК; E – код синдрома факта или места искажения; ˆ – код коррекции;
yˆ – откорректированный принятый из КС код, удовлетворяющий условию yˆ arg mˆin y yˆ ;
xк, xк – векторы состояния кодирующего устройства (КУ), размерности dim xк dim xк m ; Bк –
(m1) -матрица входа КУ; C 1 O1n1 - матрица выхода КУ [2]; N 1 – матрица вход-выход КУ;
A – нильпотентная матрица с индексом ν m ; xд – вектор состояния декодирующего устройства
(ДКУ), размерности dim xд m ; A – (m m) -матрица состояния КУ и ДКУ; Bд – (m1) - матрица вхо-
да ДКУ [2]; G kи n -образующая матрица ПЗК; H n m - проверочная матрица ПЗК.
Символ « » опускается, если все коды, задействованные в процедуре ППК, рассматриваются как вектора-строки; принимает значение переменной x , если коды рассматриваются как модулярные много-
члены (ММ) над полем Галуа GF p p2 ; принимает смысл дискретного времени k , выраженного в чис-
ле тактов длительности t , если все коды рассматриваются как кодовые последовательности, преобра-
зование которых осуществляется рекуррентным образом в силу векторно-матричных соотношений, параметризованных дискретным временем k .
Примечание 1. Помехозащитное ДКУ формирует:
1. нулевой код синдрома E 0 в случае отсутствия искажений в принятом коде ( 0 );
2. ненулевой код синдрома E 0 в случае наличия искажений в принятом коде ( 0 ).
Выясним, каким свойством должна обладать пара матриц G, H с тем, чтобы она порождала ПЗК.
С этой целью сформулируем утверждение.
Утверждение 1 (У.1). Пара G, H порождает ПЗК при необходимом условии GH O .
□ (1)
Доказательство строится на использовании системы соотношений
y aG; f y ; E fH y H aG H aGH H 0 aGH O GH O .
■
Ставится задача формирования банка проверочных матриц систематических ПЗК с помощью не-
вырожденного матричного мультипликативного компонента.
Основным результатом исследования является следующее утверждение. Утверждение 2 (У.2). Умножение проверочной матрицы H справа на невырожденную произ-
вольную (m m) -матрицу P порождает матрицу H~ arg GH~ O , при этом H~ также является прове-
рочной матрицей ПЗК.
Доказательство. Подстановка H~ HP в (1) дает: GH~ GHP GHP OP O.
□ ■
158
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
КРАТКИЕ СООБЩЕНИЯ
Примечание 2. Максимальная мощность банка проверочных матриц H~ достигается при P Al , l 0, n 1, если (m m) -матрица A имеет неприводимый характеристический ММ и принадле-
жит показателю 2m 1 . Для подтверждения основного результата приведем иллюстративный пример. Рассмотрим ПЗК, задаваемый неприводимым ММ g(x) x3 x 1 . Тогда ППК характеризуется
следующими компонентами:
1 0 1
1 1 H 0 1 0
1 1 1 0 1
1 0 1;G 0 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 1 1 0
0 1 1 1
1
10; A 1
0 1 1
1 0 0
0 1 , 0
0 0 1
причем условие (1) выполняется, и матрица A принадлежит показателю 2m 1 23 1 7 .
1 1 1 Сформируем проверочную матрицу H~ согласно утверждению У.2, приняв P A4 0 1 1 :
1 1 0
1 0 1
0 0 1
1 1 1
0 1 0
1 1 01 1 1 1 0 0
H~ HP 0
1
10
1
1 1
0
1 ,
1 0 01 1 0 1 1 1
0 1 0
0 1 1
0 0 1
1 1 0
при этом выполняется условие утверждения У.1 GH~ O , т.е. пара матриц G, H~ порождает ПЗК.
Полученный банк проверочных матриц позволяет обеспечить скрытность процесса ППК.
1. Ушаков А.В., Яицкая Е.С. Рекуррентное систематическое помехозащитное преобразование кодов: возможности аппарата линейных двоичных динамических систем // Изв. вузов. Приборостроение. – 2011. – Т. 54. – № 3. – С. 17–25.
2. Ушаков А.В., Яицкая Е.С. Динамическое наблюдение нелинейных двоичных динамических систем // Научно-технический вестник СПбГУ ИТМО. – 2010. – Т. 68. – № 4. – С. 38–44.
Ушаков Анатолий Владимирович – Санкт-Петербургский государственный университет информационных техно-
логий, механики и оптики, доктор технических наук, профессор, ushakov-AVG@yandex.ru Яицкая Елена Сергеевна – Санкт-Петербургский государственный университет информационных технологий, механики и оптики, аспирант, yaitskayaes@mail.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
159
УДК [517.938 + 519.713/.718]: 621.398 ФОРМИРОВАНИЕ БАНКА ПРОВЕРОЧНЫХ МАТРИЦ СИСТЕМАТИЧЕСКИХ ПОМЕХОЗАЩИЩЕННЫХ КОДОВ С ПОМОЩЬЮ МАТРИЧНОГО МУЛЬТИПЛИКАТИВНОГО КОМПОНЕНТА А.В. Ушаков, Е.С. Яицкая
С помощью невырожденного матричного мультипликативного компонента формируется банк проверочных матриц систематических помехозащищенных кодов. Ключевые слова: помехозащитное преобразование кодов, проверочная и образующая матрицы.
Помехозащитное преобразование кодов (ППК) представляет собой пятифазный процесс: помехо-
защитное кодирование (ПК) помехонезащищенного информационного кода (ПНЗИК); искажение поме-
хозащищенного кода (ПЗК) при передаче по двоичному каналу связи (КС); помехозащитное декодирова-
ние (ПД) с целью формирования синдрома (опознавателя) ошибки, свидетельствующего о факте, а, воз-
можно, и месте ошибки в коде; формирование сигнала коррекции (ФСК) и коррекция [1].
Алгоритмически ППК может быть описано тремя способами:
1. y aG ; f y ; E fH; ˆ EH ; yˆ f ˆ ;
2. yx arg rest yxg1x 0 ;
f x yxx ;
Ex rest f xg1x ;
ˆx ˆEx;
yˆx f x ˆx ;
3. yk Nak ; xк k 1 Axк k Bкak, k 1,kи ; xкk 1 Axкk,k 1,m ; xк 0 xк kи ;
yk Cxкk ; f k yk k; xдk 1 Axдk Bд f k,k 1,n ; E xд' n; ˆ EH ;
yˆ row f k,k 1,n ˆ ,
где a – ПНЗИК; y – ПЗК; – код помехи в КС, искажающей код y в аддитивной форме;
f – искаженный в КС ПЗК; E – код синдрома факта или места искажения; ˆ – код коррекции;
yˆ – откорректированный принятый из КС код, удовлетворяющий условию yˆ arg mˆin y yˆ ;
xк, xк – векторы состояния кодирующего устройства (КУ), размерности dim xк dim xк m ; Bк –
(m1) -матрица входа КУ; C 1 O1n1 - матрица выхода КУ [2]; N 1 – матрица вход-выход КУ;
A – нильпотентная матрица с индексом ν m ; xд – вектор состояния декодирующего устройства
(ДКУ), размерности dim xд m ; A – (m m) -матрица состояния КУ и ДКУ; Bд – (m1) - матрица вхо-
да ДКУ [2]; G kи n -образующая матрица ПЗК; H n m - проверочная матрица ПЗК.
Символ « » опускается, если все коды, задействованные в процедуре ППК, рассматриваются как вектора-строки; принимает значение переменной x , если коды рассматриваются как модулярные много-
члены (ММ) над полем Галуа GF p p2 ; принимает смысл дискретного времени k , выраженного в чис-
ле тактов длительности t , если все коды рассматриваются как кодовые последовательности, преобра-
зование которых осуществляется рекуррентным образом в силу векторно-матричных соотношений, параметризованных дискретным временем k .
Примечание 1. Помехозащитное ДКУ формирует:
1. нулевой код синдрома E 0 в случае отсутствия искажений в принятом коде ( 0 );
2. ненулевой код синдрома E 0 в случае наличия искажений в принятом коде ( 0 ).
Выясним, каким свойством должна обладать пара матриц G, H с тем, чтобы она порождала ПЗК.
С этой целью сформулируем утверждение.
Утверждение 1 (У.1). Пара G, H порождает ПЗК при необходимом условии GH O .
□ (1)
Доказательство строится на использовании системы соотношений
y aG; f y ; E fH y H aG H aGH H 0 aGH O GH O .
■
Ставится задача формирования банка проверочных матриц систематических ПЗК с помощью не-
вырожденного матричного мультипликативного компонента.
Основным результатом исследования является следующее утверждение. Утверждение 2 (У.2). Умножение проверочной матрицы H справа на невырожденную произ-
вольную (m m) -матрицу P порождает матрицу H~ arg GH~ O , при этом H~ также является прове-
рочной матрицей ПЗК.
Доказательство. Подстановка H~ HP в (1) дает: GH~ GHP GHP OP O.
□ ■
158
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
КРАТКИЕ СООБЩЕНИЯ
Примечание 2. Максимальная мощность банка проверочных матриц H~ достигается при P Al , l 0, n 1, если (m m) -матрица A имеет неприводимый характеристический ММ и принадле-
жит показателю 2m 1 . Для подтверждения основного результата приведем иллюстративный пример. Рассмотрим ПЗК, задаваемый неприводимым ММ g(x) x3 x 1 . Тогда ППК характеризуется
следующими компонентами:
1 0 1
1 1 H 0 1 0
1 1 1 0 1
1 0 1;G 0 0
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
1 1 1 0
0 1 1 1
1
10; A 1
0 1 1
1 0 0
0 1 , 0
0 0 1
причем условие (1) выполняется, и матрица A принадлежит показателю 2m 1 23 1 7 .
1 1 1 Сформируем проверочную матрицу H~ согласно утверждению У.2, приняв P A4 0 1 1 :
1 1 0
1 0 1
0 0 1
1 1 1
0 1 0
1 1 01 1 1 1 0 0
H~ HP 0
1
10
1
1 1
0
1 ,
1 0 01 1 0 1 1 1
0 1 0
0 1 1
0 0 1
1 1 0
при этом выполняется условие утверждения У.1 GH~ O , т.е. пара матриц G, H~ порождает ПЗК.
Полученный банк проверочных матриц позволяет обеспечить скрытность процесса ППК.
1. Ушаков А.В., Яицкая Е.С. Рекуррентное систематическое помехозащитное преобразование кодов: возможности аппарата линейных двоичных динамических систем // Изв. вузов. Приборостроение. – 2011. – Т. 54. – № 3. – С. 17–25.
2. Ушаков А.В., Яицкая Е.С. Динамическое наблюдение нелинейных двоичных динамических систем // Научно-технический вестник СПбГУ ИТМО. – 2010. – Т. 68. – № 4. – С. 38–44.
Ушаков Анатолий Владимирович – Санкт-Петербургский государственный университет информационных техно-
логий, механики и оптики, доктор технических наук, профессор, ushakov-AVG@yandex.ru Яицкая Елена Сергеевна – Санкт-Петербургский государственный университет информационных технологий, механики и оптики, аспирант, yaitskayaes@mail.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
159