АНАЛИЗ СТРУКТУРЫ ПРОСТРАНСТВА СОСТОЯНИЙ ЛИНЕЙНЫХ ДВОИЧНЫХ ДИНАМИЧЕСКИХ СИСТЕМ НА ОСНОВЕ ИХ РЕКУРРЕНТНОГО МОДЕЛЬНОГО ПРЕДСТАВЛЕНИЯ
А.В. Ушаков, Е.С. Яицкая
4 АНАЛИЗ И СИНТЕЗ СЛОЖНЫХ СИСТЕМ
УДК [517.938 + 519.713/.718]: 621.398
АНАЛИЗ СТРУКТУРЫ ПРОСТРАНСТВА СОСТОЯНИЙ ЛИНЕЙНЫХ ДВОИЧНЫХ ДИНАМИЧЕСКИХ СИСТЕМ НА ОСНОВЕ
ИХ РЕКУРРЕНТНОГО МОДЕЛЬНОГО ПРЕДСТАВЛЕНИЯ
А.В. Ушаков, Е.С. Яицкая
Рассматриваются проблемы, связанные со спецификой структуры пространства состояний линейных двоичных динамических систем (ЛДДС), характеризующихся наличием неподвижных состояний и замкнутых циклов при отсутствии и наличии экзогенной задающей последовательности на входе ЛДДС. Показывается, что решаемая задача связана с особенностью структуры алгебраического спектра собственных значений матрицы состояния ЛДДС, особенностями структуры геометрического спектра собственных векторов той же матрицы и в значительной степени зави-
сит от показателя , которому принадлежит эта матрица. Предлагается алгоритм анализа структуры пространства
состояний ЛДДС. Приводится пример. Ключевые слова: двоичная динамическая система, структура пространства состояния, собственный вектор, принадлежность показателю, неподвижные состояния, замкнутые циклы.
Введение
Класс линейных динамических систем как объект научных исследований появился в последней четверти прошлого века благодаря работам [1, 2]. Авторы указанных работ называли линейные динамические системы линейными последовательностными машинами (ЛПМ), потому что они возникли из задач преобразования временных последовательностей с дискретным временем над конечными полями
Галуа GFp 0,1,...p 1 с произвольной характеристикой (модулем) p и модулярной арифметикой
по mod p . Достаточно быстро в силу наибольшей практической применимости выделился класс ЛПМ с
характеристикой p 2 , который стал именоваться линейными двоичными динамическими системами
(ЛДДС).
В это же время завершалось формирование такой системной парадигмы, как аппарат пространства
состояний (АПС), опирающийся на возможности векторно-матричного формализма линейной алгебры,
который разрабатывался в основном для систем над бесконечным полем с непрерывным и дискретным
временем. Возможности указанного формализма АПС не могли быть не замечены специалистами по
ЛДДС. Без сомнения, перенос положений АПС на класс ЛДДС имеет свою специфику, которая опреде-
ляется в основном конечностью числа возможных состояний.
В этой связи становится достаточно логичной постановка задачи анализа структуры пространства
состояний ЛДДС на основе их рекуррентного модельного представления [1–5]
x k +1= A x k+B u k , x 0 ,
(1)
где x, u – соответственно вектор состояния и вектор входной последовательности размерности
dim x m, dimu r с элементами; A – m m матрица состояния; B – m r матрица входа. Эле-
менты векторов и матриц принадлежат двоичному полю Галуа GFp 0,1. Исследования, результаты
которых приводятся ниже, выполнены для случая r = 1, т.е. матрица B представляет собой m -мерный
вектор-столбец. Следует ожидать, что структура пространства состояний автономной ЛДДС, т.е. ЛДДС (1) при
u k= 0 , определяется свойствами матрицы A состояния системы, а структура ЛДДС при u k 0
определяется свойствами пары матриц A,B.
Предпринятые исследования начнем с рассмотрения базовых свойств квадратных матриц над двоичным полем Галуа.
Базовые свойства квадратных m m матриц над двоичным полем Галуа
Свойство 1 (С.1). (Теорема Гамильтона–Кэли). Произвольная квадратная m m – матрица A
над простым полем Галуа GF p при p = 2 обладает тем свойством, что обнуляет свой характеристи-
ческий модулярный многочлен (ХММ) так, что выполняется равенство
det I + A |=A= a0Am + a1Am1 ++ am1A+ amI = O .
□
Доказательство утверждения строится по той же схеме, что и теорема Гамильтона–Кэли над бес-
конечным полем [3].
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
43
АНАЛИЗ СТРУКТУРЫ ПРОСТРАНСТВА СОСТОЯНИЙ…
Свойство 2 (С.2). Будем говорить, что квадратная m m– матрица A с элементами из GF 2
обладает свойством нильпотентности индекса , если она удовлетворяет условию
A = O ,
□
при этом 1 m .
Свойство 3 (С.3). Будем говорить, что квадратная m m– матрица A с элементами из GF 2
обладает свойством принадлежности показателю , если она удовлетворяет условию
Aμ = I .
□ (2)
Примечание 1 (П.1). Нетрудно видеть, что в силу правил модулярной двоичной арифметики со-
отношение (4) имеет эквивалентное представление
Aμ +I = O .
(3)
Для целей дальнейших исследований сформулируем следующее утверждение.
Утверждение 1 (У.1). Для того чтобы матрица A обладала свойством принадлежности показате-
лю достаточно, чтобы ее ХММ D = det I+A входил в разложение двучлена +1 .
□
Доказательство. Предположим, что D входит в разложение двучлена +1 , тогда становится
справедливым представление
+1= Q D .
(4)
Построим на скалярном соотношении (4) матричное соотношение, заменив скаляр матрицей
A . Тогда будем иметь
A +I = Q A D A.
Нетрудно видеть, что в соответствии с теоремой Гамильтона–Кэли D(A) = 0 , а, следовательно,
выполняется соотношение (3).
■
Примечание 2 (П.2). Из доказанного утверждения следует, что является наименьшей степенью
двучлена вида +1 , который характеризуется делимостью без остатка
= min j : j
rest
j
+1
D
=
0
,
при
этом
показатель
удовлетворяет
неравенству
m .
на
ХММ
Постановка задачи анализа структуры пространства состояния ЛДДС с различными показателями принадлежности их матриц состояния
Структура пространства состояний ЛДДС определяется наличием неподвижных состояний, замкнутых циклов, возвратных состояний и состояний, из которых под действием входной последовательности ЛДДС переходит в нулевое состояние.
Неподвижные состояния линейных ДДС
Определение 1 (О.1). Состояние x k автономной ЛДДС (АЛДДС), т.е. ЛДДС (1) при u k= 0 ,
называется неподвижным, если оно удовлетворяет равенству
x k +1= A x k= x k , k .
□ (5)
Примечание 3 (П.3). АЛДДС при любой m m реализации матрицы A имеет в качестве непо-
движного состояния нулевое
x k0 .
Примечание 4 (П.4). Все ненулевые состояния АЛДДС оказываются неподвижными, если ее мат-
рица состояния является единичной A = I .
Утверждение 2 (У.2). Неподвижным состоянием АЛДДС является собственный вектор матри-
цы A , соответствующий собственному значению = 1.
□
Доказательство утверждения строится на определении понятия собственного вектора [6], в силу
которого выполняется соотношение
A = |=1 = .
Если x k выбран в форме x k= , тогда для АЛДДС получим цепочку равенств
x k +1= A x k|xk== A = = x k.
□
Рассмотрим теперь структуру неподвижных состояний ЛДДС (1) для случая u k 0 ( u k= 1).
44 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 4 (74)
А.В. Ушаков, Е.С. Яицкая
Определение 2 (О.2). Состояние x k ЛДДС (1) для случая u k=1 называется неподвижным,
если оно удовлетворяет равенству
x k +1= A x k+B = x k, k .
□
Примечание 5 (П.5). Нулевое состояние x k 0 не принадлежит множеству неподвижных со-
стояний ЛДДС при u k=1, так как система (1) при x k 0 и u k=1 переходит в состояние
x k +1= B, k.
Утверждение 3 (У.3). Неподвижное состояние ЛДДС (1) при u k =1 задается выражением
x k= I+ A1B ,
(6)
если матрица I + A обратима.
□
Доказательство утверждения строится на подстановке x k +1= x k и u k=1 в (1), в резуль-
тате чего получаем
I+A x k= B .
(7)
Если матрица I + A обратима, то выполняется (6).
■
Примечание 6 (П.6). При обратимости матрицы I + A неподвижное состояние, определенное
соотношением (6), представляет собой линейную комбинацию столбцов матрицы I + A1 . Матрица I + A есть матричная функция f A от матрицы A , по свойству которой [6] ее спектр I+ A соб-
ственных значений равен I+ A = λi =1+λi ; i =1, m , а потому ее обратимость возможна при
условии
λ i
=
1+
λ i
0,
i =1,
m
.
(8)
Условие (8) выполняется тогда, когда матрица A является нильпотентной с любым индексом
нильпотентности или обладает неприводимым характеристическим многочленом [1–3]. При этом в слу-
чае, когда матрица A ЛДДС (1) такова, что ее характеристический полином имеет четное число ненуле-
вых элементов, включая единичный свободный член, то такая система при u k =1 не имеет ненулевого
неподвижного состояния.
Определим теперь состояния x k , из которых возможен переход в нулевое состояние
x k +1= 0 . При u k= 0 нулевое состояние x k= 0 является неподвижным, поэтому переход в него
возможен только из него. При u k=1 состояние x k , из которого возможен переход в нулевое состо-
яние x k +1= 0 , в силу (1) определяется выражением x k = A1B .
Замкнутые циклы линейных ДДС
Вынесенную в название данного параграфа проблему, как и при исследовании неподвижных со-
стояний, будем решать с использованием модельных представлений ЛДДС отдельно для каждого из слу-
чаев: u k= 0 и u k=1.
Введем понятие замкнутый цикл в структуре пространства состояний линейной ДДС с помощью
следующего определения.
Определение 3 (О.3). Пусть множество X~ мощности X~ = N~ = 2m состояний линейной ДДС (5),
тогда подмножество X~~ множества X~ , содержащее T состояний, на котором выполняется соотношение
x k= x k +T ,
(9)
называется замкнутым циклом длиной T .
□
Примечание 7 (П.7). Нетрудно видеть, что условие (9), по существу, содержит определение поня-
тия возвратных состояний, множество которых мощности T образует замкнутый цикл той же длины.
Рассмотрим структуру возвратных состояний, образующих цикл некоторой длины T = T u , при
двух возможных значениях u k . Нетрудно видеть, что при u k= 0 множество возвратных состояний
замкнутого цикла длиной T (9) состоит из состояний, определяемых в силу соотношений
x k ; x k +1= Ax k ; x k +2= Ax k +1= A2x k ,
, x k +T 1= AT 1x k .
(10)
При u k= 1 возвратные состояния задаются системой соотношений
x k; x k 1 Ax k B; x k 2 Ax k 1 B A2x k AB B, , x k T 1 AT 1x k AT 2B AB B .
□ (11)
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
45
АНАЛИЗ СТРУКТУРЫ ПРОСТРАНСТВА СОСТОЯНИЙ…
Рассмотрим факторы, определяющие длину T замкнутых циклов на множестве состояний ЛДДС
при u k= 0 . С этой целью соотношение (9) запишем в форме
x k= AT x k .
(12)
Сформулируем следующее утверждение.
Утверждение 4 (У.4). При x k 0 соотношение (12) выполняется в случаях, когда матрица A
принадлежит показателю = T .
□
Доказательство справедливости первой части утверждения строится на определении показателя
, которому принадлежит матрица A , в соответствии с которым выполняется матричное равенство (2),
подстановка = T делает справедливым (12). Доказательство справедливости второй части утверждения
строится на определении собственного вектора с учетом специфики простого поля Галуа GF p при
p=2.
■
Очевидно, что длина T замкнутых циклов при u k= 0 и u k=1 удовлетворяет неравенствам
1 T 2m 1.
(13)
Очевидно, что в структуре пространства m m матрицы A состояний ЛДДС (5) имеется цикл
длины T =1 , когда x k является собственным вектором матрицы A . Иначе говоря, ненулевое непо-
движное состояние образует цикл длиной T =1 . Максимальная длина T = 2m 1 имеет место, когда
m m матрица A и ее характеристический многочлен D = det I+A принадлежат показателю
= 2m 1.
Наложим на неравенства (13), определяющие возможные по длине T циклы на множестве ненуле-
вых состояний ~x мощности ~x = N~ = 2m 1, неравенства, оценивающие возможные показатели , которым могут принадлежать m m матрица состояний ЛДДС и ее характеристический многочлен D
m 2m 1 .
Рассмотрим теперь структуру замкнутых циклов линейной ДДС при u k =1 . Описание ЛДДС
для этого случая задается представлениями (1), в которых следует положить u k =1 так, что получим:
x k +1= Ax k+B ; x 0.
(14)
Следует заметить, что введенное с помощью О.3 определение замкнутого цикла длиной T сохраняется, однако структура этих циклов не только зависит от показателя , которому принадлежит матри-
ца A , структуры собственных векторов f степенных матричных функций f A= AT от m m
матрицы A состояний ЛДДС, но и от матрицы B . Последняя может принадлежать пространству столбцов матрицы A , т.е. ее образу
B Jm A ,
тогда пара матриц A, B оказывается неполностью управляемой, простейшим случаем такой ситуации
является случай, когда матрица B является собственным вектором матрицы A . В этой связи сформулируем утверждение.
Утверждение 5 (У.5). Если матрица B векторно-матричного описания ЛДДС является собствен-
ным вектором матрицы A , то ЛДДС с такой парой матриц A, B не является полностью управляемой,
при этом размерность подпространства управляемости равна единице.
□
Доказательство. Тот факт, что матрица B есть собственный вектор матрицы A состояний ЛДДС
над простым полем Галуа GF 2 , позволяет записать A B = B .
Составим матрицу управляемости пары A, B
Wy A, B = B A B A2 B Am1 B . Для элементов Wу A, B можно записать
A B = B ; A2 B = A B = B, , Am1 B = A Am2 B = = B .
(15)
Подстановка полученных матричных равенств в (15) дает для матрицы управляемости
rank Wу A, B= rank B B B B= rank B =1< m .
■
Составим следующий алгоритм анализа структуры замкнутых циклов линейных ДДС с системной
матрицей A , имеющей своим характеристическим модулярным многочленом D = det I+A не-
приводимый многочлен степени m .
46 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 4 (74)
А.В. Ушаков, Е.С. Яицкая
Алгоритм 1 (А.1) 1. Построить векторно-матричное представление линейной двоичной динамической системы в рекур-
рентной форме (1).
2. Перейти от представления ЛДДС (1) к ее представлению в форме (5), положив в (1) u k = 0 .
3. Вычислить характеристический многочлен D матрицы A состояний ЛДДС в силу соотношения
D = det I+A .
4. Определить показатель , которому принадлежит характеристический многочлен D и матрица
A состояний ЛДДС, с использованием таблиц многочленов, принадлежащих конкретному , или
возведением матрицы A в степень над полем Галуа GF 2 до момента выполнения равенства (2).
5. Проанализировать полученное значение по соотношению
2m 1= m+ r ,
из которого определить m – число циклов длины T = и r – суммарную длину циклов, длительности 1 Tr r . 6. Определить состав и последовательность изменения состояний в замкнутых циклах длиной T = ,
порожденных фактом принадлежности матрицы A состояний ЛДДС показателю , используя
представление циклов в форме (10), в котором за исходное состояние x k цикла взять любое со-
стояние множества X~ . 7. Сформировать структуру замкнутых циклов и неподвижных состояний линейной ДДС (5) (при
u k = 0 ) п.п. 5, 6, дополнив их нулевым неподвижным состоянием.
8. Перейти от представления ЛДДС (1) к ее представлению в форме (14), положив в (1) u k =1 .
9. Определить неподвижное состояние x k: x k +1= x k , используя соотношение (6) или (7).
10. Определить состав и последовательность изменения состояний в замкнутых циклах длиной T = ,
порожденных фактом принадлежности матрицы A состояний ЛДДС показателю , используя
представление циклов в форме (11), в котором за исходное состояние x k цикла взять любое со-
стояние множества X~ .
11. Сформировать структуру замкнутых циклов и неподвижных состояний линейной ДДС (14) (при
u k =1 ) п. 10, дополнив их неподвижным состоянием п. 9.
■
Пример анализа структуры пространства состояний ЛДДС, представленной ее неподвижными состояниями и замкнутыми циклами
В качестве примера рассматриваются ЛДДС с матрицами A состояний размерности
m m= 33. Структура пространства изучается на реализациях пар матриц A, B, в которых матрицы A обладают характеристическими многочленами D , принадлежащими классу неприводимых
степени degD = m , а множество ненулевых матриц B характеризуется мощностью B= 2m 1.
Исследования начнем со случая, когда ХММ матрицы A имеет вид D = 3 ++1. Тогда, следуя ал-
горитму А.1: 1. выполним п.п. 1–2, в результате чего ЛДДС будет иметь матрицу A состояний, заданной во фробе-
ниусовой форме так, что она получает представление
0 1 0 A = 0 0 1 ;
1 1 0
4. путем вычисления степенной матричной функции f A= Al установим, что при l = 7 выполняется
равенство Al = I , на основании чего становится справедливым соотношение = 7 , где – показа-
тель, которому принадлежит матрица A ; 5. анализируя значение , обнаружим справедливость разложения мощности 2m 1 множества нену-
левых состояний в форме 2m 1= 7 =1 7+0 , что свидетельствует о наличии в структуре пространства матрицы A состояний ЛДДС одного замкнутого цикла длиной T = = 7 ;
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
47
АНАЛИЗ СТРУКТУРЫ ПРОСТРАНСТВА СОСТОЯНИЙ…
6. определим состав и последовательность смены состояний ЛДДС в замкнутом цикле длины T = = 7 , порожденного фактом принадлежности матрицы A показателю = 7 . В качестве стартового состояния примем состояние, характеризующееся минимальным кодовым расстоянием с нулевым состоя-
нием ЛДДС, не входящим в состав цикла x k = 0 0 1T . Если воспользоваться (10), то получим
замкнутый цикл, характеризующийся составом и последовательностью
0 0 1 0 1 1 1
10,
1, 0
0, 1
1, 1
1, 1
1, 0
00;
7. получим полную структуру замкнутых циклов и неподвижных состояний при u k 0 (рис. 1);
001
0
000
0
0
010
0
100
0
110
101
0
0
111
011
0
Рис. 1. Структура замкнутых циклов и неподвижных состояний ЛДДС при u k 0
8. для рассмотрения ЛДДС вида (14) для матрицы B входа положим B = 0 0 1T ;
9. для поиска неподвижного состояния x k: x k +1= x k используем соотношение (6) и получим
0 1 1 0 1
x k = I + A1B = 1 1 1 0 1 ;
1 0 1 1 1 10. определим состав и последовательность смены состояний ЛДДС в замкнутом цикле длины T = = 7 ,
порожденной фактом принадлежности матрицы A показателю = 7 . В качестве стартового состояния одного из циклов примем состояние, отличное от состояния п. 9 примера, например, нулевое со-
стояние ЛДДС x k= 0 0 0T . Если воспользоваться (11), то получим замкнутый цикл, характе-
ризующийся составом и последовательностью
0 0 0 1 1 0 1
00,
0, 1
1, 1
1, 0
0, 1
1, 0
00;
11. получим полную структуру замкнутых циклов и неподвижных состояний при u k =1 (рис. 2).
000
1
111
1
1
001
1
011
1
100
1
010
1
101
110
1
Рис. 2. Структура циклов и неподвижных состояний ЛДДС с парой матриц A, B при u k = 1
Воспользуемся алгоритмом А.1 для всех пар матриц A, B , оговоренных в преамбуле примера.
Полученные результаты сведены в таблицу. Для компактности записи в таблице использованы представления матриц, циклов, последовательностей в виде их десятичных эквивалентов, причем величина периодичности представлена скобочной записью с указанием длительности периода в виде нижнего индекса у правой скобки.
48 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 4 (74)
А.В. Ушаков, Е.С. Яицкая
Матрица AT
Показатель
u k 0
0
1
u k 1 , Матрица BT
2 3 4 567
[2, 1, 6]
7
(0,5,6,1, 7,3,2)7, (4)1 (0,6,2,3, 1,4,7)7, (5)1 (0,7,1,5, 4,6,3)7, (2)1
(0,4,5,7, 2,1,6)7, (3)1
(0,3,4,2, 6,7,5)7, (1)1
(0,2,7,4, 3,5,1)7, (6)1
(0,1,3,6, 5,4,2)7, (7)1
(1, 3, 7, 6, 5, 2, 4)7, (0)1 (1, 2, 5, 3, 7, 6, 4)7, (0)1
(0,5,7,3, 2,1,6)7, (4)1 (0,6,3,1, 5,4,7)7, (2)1 (0,7,1,4, 6,2,3)7, (5)1
(0,4,5,6, 1,7,2)7, (3)1
(0,3,4,2, 7,5,1)7, (6)1
(0,3,4,2, 7,5,1)7, (1)1
(0,1,2,5, 3,6,4)7, (7)1
[2, 1, 5]
7
Таблица. Структура циклов и неподвижных состояний всех возможных вариантов реализаций
пар A, B матриц, задающих соответствующие ЛДДС при размерности вектора состояния dim x 3
Анализ структуры состояний ЛДДС, из которых под действием u k =1 возможен переход
в нулевое состояние
Проблема вычисления состояний, из которых ЛДДС переходит в нулевое состояние x k +1 0 , сводится к решению уравнения (14) при нулевой левой части. Тогда искомый x k при x k +1 0 и u k =1 определяется выражением
x k= A1B .
(16)
Если рассмотреть ЛДДС с парой матриц A, B, где матрица A задается в форме п. 1 примера, а
матрица B – в форме п. 8 примера, то состояние x k , удовлетворяющее условию (16), получает пред-
ставление
x k= 1 0 0T .
Заключение
Предложенная в работе алгоритмическая среда анализа структуры пространства состояний ЛДДС делает алгебраически прозрачным процесс преобразования двоичных кодов [1–3], что особенно важно при решении задач помехозащитного преобразования этих кодов. Становится наглядной необходимость выбора неприводимых многочленов в качестве образующих многочленов помехозащищенного кода с максимальным значением их принадлежности.
Литература
1. Фараджев Р.Г. Линейные последовательностные машины. – М.: Советское радио, 1975. – 248 с. 2. Гилл А. Линейные последовательностные машины. – М.: Наука, 1974. – 288 с. 3. Мельников А.А., Ушаков А.В. Двоичные динамические системы дискретной автоматики / Под ред.
А.В. Ушакова. – СПб: СПбГУ ИТМО, 2005. – 214 с. 4. Ушаков А.В., Яицкая Е.С. Рекуррентное систематическое помехозащитное преобразование кодов:
возможности аппарата линейных двоичных динамических систем // Изв. вузов. Приборостроение. – 2011. – № 3. – С. 17–25. 5. Ушаков А.В., Яицкая Е.С. Динамическое наблюдение нелинейных двоичных динамических систем // Научно-технический вестник СПбГУ ИТМО. – 2010. – № 4. – С. 38–44. 6. Гантмахер Ф.Р. Теория матриц. – 5-е изд. – М.: Физматлит, 2004. – 560 с.
Ушаков Анатолий Владимирович – Санкт-Петербургский государственный университет информационных технологий, механики и оптики, доктор технических наук, профессор,
Яицкая Елена Сергеевна
ushakov-AVG@yandex.ru – Санкт-Петербургский государственный университет информационных
технологий, механики и оптики, аспирант, yaitskayaes@mail.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
49
4 АНАЛИЗ И СИНТЕЗ СЛОЖНЫХ СИСТЕМ
УДК [517.938 + 519.713/.718]: 621.398
АНАЛИЗ СТРУКТУРЫ ПРОСТРАНСТВА СОСТОЯНИЙ ЛИНЕЙНЫХ ДВОИЧНЫХ ДИНАМИЧЕСКИХ СИСТЕМ НА ОСНОВЕ
ИХ РЕКУРРЕНТНОГО МОДЕЛЬНОГО ПРЕДСТАВЛЕНИЯ
А.В. Ушаков, Е.С. Яицкая
Рассматриваются проблемы, связанные со спецификой структуры пространства состояний линейных двоичных динамических систем (ЛДДС), характеризующихся наличием неподвижных состояний и замкнутых циклов при отсутствии и наличии экзогенной задающей последовательности на входе ЛДДС. Показывается, что решаемая задача связана с особенностью структуры алгебраического спектра собственных значений матрицы состояния ЛДДС, особенностями структуры геометрического спектра собственных векторов той же матрицы и в значительной степени зави-
сит от показателя , которому принадлежит эта матрица. Предлагается алгоритм анализа структуры пространства
состояний ЛДДС. Приводится пример. Ключевые слова: двоичная динамическая система, структура пространства состояния, собственный вектор, принадлежность показателю, неподвижные состояния, замкнутые циклы.
Введение
Класс линейных динамических систем как объект научных исследований появился в последней четверти прошлого века благодаря работам [1, 2]. Авторы указанных работ называли линейные динамические системы линейными последовательностными машинами (ЛПМ), потому что они возникли из задач преобразования временных последовательностей с дискретным временем над конечными полями
Галуа GFp 0,1,...p 1 с произвольной характеристикой (модулем) p и модулярной арифметикой
по mod p . Достаточно быстро в силу наибольшей практической применимости выделился класс ЛПМ с
характеристикой p 2 , который стал именоваться линейными двоичными динамическими системами
(ЛДДС).
В это же время завершалось формирование такой системной парадигмы, как аппарат пространства
состояний (АПС), опирающийся на возможности векторно-матричного формализма линейной алгебры,
который разрабатывался в основном для систем над бесконечным полем с непрерывным и дискретным
временем. Возможности указанного формализма АПС не могли быть не замечены специалистами по
ЛДДС. Без сомнения, перенос положений АПС на класс ЛДДС имеет свою специфику, которая опреде-
ляется в основном конечностью числа возможных состояний.
В этой связи становится достаточно логичной постановка задачи анализа структуры пространства
состояний ЛДДС на основе их рекуррентного модельного представления [1–5]
x k +1= A x k+B u k , x 0 ,
(1)
где x, u – соответственно вектор состояния и вектор входной последовательности размерности
dim x m, dimu r с элементами; A – m m матрица состояния; B – m r матрица входа. Эле-
менты векторов и матриц принадлежат двоичному полю Галуа GFp 0,1. Исследования, результаты
которых приводятся ниже, выполнены для случая r = 1, т.е. матрица B представляет собой m -мерный
вектор-столбец. Следует ожидать, что структура пространства состояний автономной ЛДДС, т.е. ЛДДС (1) при
u k= 0 , определяется свойствами матрицы A состояния системы, а структура ЛДДС при u k 0
определяется свойствами пары матриц A,B.
Предпринятые исследования начнем с рассмотрения базовых свойств квадратных матриц над двоичным полем Галуа.
Базовые свойства квадратных m m матриц над двоичным полем Галуа
Свойство 1 (С.1). (Теорема Гамильтона–Кэли). Произвольная квадратная m m – матрица A
над простым полем Галуа GF p при p = 2 обладает тем свойством, что обнуляет свой характеристи-
ческий модулярный многочлен (ХММ) так, что выполняется равенство
det I + A |=A= a0Am + a1Am1 ++ am1A+ amI = O .
□
Доказательство утверждения строится по той же схеме, что и теорема Гамильтона–Кэли над бес-
конечным полем [3].
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
43
АНАЛИЗ СТРУКТУРЫ ПРОСТРАНСТВА СОСТОЯНИЙ…
Свойство 2 (С.2). Будем говорить, что квадратная m m– матрица A с элементами из GF 2
обладает свойством нильпотентности индекса , если она удовлетворяет условию
A = O ,
□
при этом 1 m .
Свойство 3 (С.3). Будем говорить, что квадратная m m– матрица A с элементами из GF 2
обладает свойством принадлежности показателю , если она удовлетворяет условию
Aμ = I .
□ (2)
Примечание 1 (П.1). Нетрудно видеть, что в силу правил модулярной двоичной арифметики со-
отношение (4) имеет эквивалентное представление
Aμ +I = O .
(3)
Для целей дальнейших исследований сформулируем следующее утверждение.
Утверждение 1 (У.1). Для того чтобы матрица A обладала свойством принадлежности показате-
лю достаточно, чтобы ее ХММ D = det I+A входил в разложение двучлена +1 .
□
Доказательство. Предположим, что D входит в разложение двучлена +1 , тогда становится
справедливым представление
+1= Q D .
(4)
Построим на скалярном соотношении (4) матричное соотношение, заменив скаляр матрицей
A . Тогда будем иметь
A +I = Q A D A.
Нетрудно видеть, что в соответствии с теоремой Гамильтона–Кэли D(A) = 0 , а, следовательно,
выполняется соотношение (3).
■
Примечание 2 (П.2). Из доказанного утверждения следует, что является наименьшей степенью
двучлена вида +1 , который характеризуется делимостью без остатка
= min j : j
rest
j
+1
D
=
0
,
при
этом
показатель
удовлетворяет
неравенству
m .
на
ХММ
Постановка задачи анализа структуры пространства состояния ЛДДС с различными показателями принадлежности их матриц состояния
Структура пространства состояний ЛДДС определяется наличием неподвижных состояний, замкнутых циклов, возвратных состояний и состояний, из которых под действием входной последовательности ЛДДС переходит в нулевое состояние.
Неподвижные состояния линейных ДДС
Определение 1 (О.1). Состояние x k автономной ЛДДС (АЛДДС), т.е. ЛДДС (1) при u k= 0 ,
называется неподвижным, если оно удовлетворяет равенству
x k +1= A x k= x k , k .
□ (5)
Примечание 3 (П.3). АЛДДС при любой m m реализации матрицы A имеет в качестве непо-
движного состояния нулевое
x k0 .
Примечание 4 (П.4). Все ненулевые состояния АЛДДС оказываются неподвижными, если ее мат-
рица состояния является единичной A = I .
Утверждение 2 (У.2). Неподвижным состоянием АЛДДС является собственный вектор матри-
цы A , соответствующий собственному значению = 1.
□
Доказательство утверждения строится на определении понятия собственного вектора [6], в силу
которого выполняется соотношение
A = |=1 = .
Если x k выбран в форме x k= , тогда для АЛДДС получим цепочку равенств
x k +1= A x k|xk== A = = x k.
□
Рассмотрим теперь структуру неподвижных состояний ЛДДС (1) для случая u k 0 ( u k= 1).
44 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 4 (74)
А.В. Ушаков, Е.С. Яицкая
Определение 2 (О.2). Состояние x k ЛДДС (1) для случая u k=1 называется неподвижным,
если оно удовлетворяет равенству
x k +1= A x k+B = x k, k .
□
Примечание 5 (П.5). Нулевое состояние x k 0 не принадлежит множеству неподвижных со-
стояний ЛДДС при u k=1, так как система (1) при x k 0 и u k=1 переходит в состояние
x k +1= B, k.
Утверждение 3 (У.3). Неподвижное состояние ЛДДС (1) при u k =1 задается выражением
x k= I+ A1B ,
(6)
если матрица I + A обратима.
□
Доказательство утверждения строится на подстановке x k +1= x k и u k=1 в (1), в резуль-
тате чего получаем
I+A x k= B .
(7)
Если матрица I + A обратима, то выполняется (6).
■
Примечание 6 (П.6). При обратимости матрицы I + A неподвижное состояние, определенное
соотношением (6), представляет собой линейную комбинацию столбцов матрицы I + A1 . Матрица I + A есть матричная функция f A от матрицы A , по свойству которой [6] ее спектр I+ A соб-
ственных значений равен I+ A = λi =1+λi ; i =1, m , а потому ее обратимость возможна при
условии
λ i
=
1+
λ i
0,
i =1,
m
.
(8)
Условие (8) выполняется тогда, когда матрица A является нильпотентной с любым индексом
нильпотентности или обладает неприводимым характеристическим многочленом [1–3]. При этом в слу-
чае, когда матрица A ЛДДС (1) такова, что ее характеристический полином имеет четное число ненуле-
вых элементов, включая единичный свободный член, то такая система при u k =1 не имеет ненулевого
неподвижного состояния.
Определим теперь состояния x k , из которых возможен переход в нулевое состояние
x k +1= 0 . При u k= 0 нулевое состояние x k= 0 является неподвижным, поэтому переход в него
возможен только из него. При u k=1 состояние x k , из которого возможен переход в нулевое состо-
яние x k +1= 0 , в силу (1) определяется выражением x k = A1B .
Замкнутые циклы линейных ДДС
Вынесенную в название данного параграфа проблему, как и при исследовании неподвижных со-
стояний, будем решать с использованием модельных представлений ЛДДС отдельно для каждого из слу-
чаев: u k= 0 и u k=1.
Введем понятие замкнутый цикл в структуре пространства состояний линейной ДДС с помощью
следующего определения.
Определение 3 (О.3). Пусть множество X~ мощности X~ = N~ = 2m состояний линейной ДДС (5),
тогда подмножество X~~ множества X~ , содержащее T состояний, на котором выполняется соотношение
x k= x k +T ,
(9)
называется замкнутым циклом длиной T .
□
Примечание 7 (П.7). Нетрудно видеть, что условие (9), по существу, содержит определение поня-
тия возвратных состояний, множество которых мощности T образует замкнутый цикл той же длины.
Рассмотрим структуру возвратных состояний, образующих цикл некоторой длины T = T u , при
двух возможных значениях u k . Нетрудно видеть, что при u k= 0 множество возвратных состояний
замкнутого цикла длиной T (9) состоит из состояний, определяемых в силу соотношений
x k ; x k +1= Ax k ; x k +2= Ax k +1= A2x k ,
, x k +T 1= AT 1x k .
(10)
При u k= 1 возвратные состояния задаются системой соотношений
x k; x k 1 Ax k B; x k 2 Ax k 1 B A2x k AB B, , x k T 1 AT 1x k AT 2B AB B .
□ (11)
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
45
АНАЛИЗ СТРУКТУРЫ ПРОСТРАНСТВА СОСТОЯНИЙ…
Рассмотрим факторы, определяющие длину T замкнутых циклов на множестве состояний ЛДДС
при u k= 0 . С этой целью соотношение (9) запишем в форме
x k= AT x k .
(12)
Сформулируем следующее утверждение.
Утверждение 4 (У.4). При x k 0 соотношение (12) выполняется в случаях, когда матрица A
принадлежит показателю = T .
□
Доказательство справедливости первой части утверждения строится на определении показателя
, которому принадлежит матрица A , в соответствии с которым выполняется матричное равенство (2),
подстановка = T делает справедливым (12). Доказательство справедливости второй части утверждения
строится на определении собственного вектора с учетом специфики простого поля Галуа GF p при
p=2.
■
Очевидно, что длина T замкнутых циклов при u k= 0 и u k=1 удовлетворяет неравенствам
1 T 2m 1.
(13)
Очевидно, что в структуре пространства m m матрицы A состояний ЛДДС (5) имеется цикл
длины T =1 , когда x k является собственным вектором матрицы A . Иначе говоря, ненулевое непо-
движное состояние образует цикл длиной T =1 . Максимальная длина T = 2m 1 имеет место, когда
m m матрица A и ее характеристический многочлен D = det I+A принадлежат показателю
= 2m 1.
Наложим на неравенства (13), определяющие возможные по длине T циклы на множестве ненуле-
вых состояний ~x мощности ~x = N~ = 2m 1, неравенства, оценивающие возможные показатели , которым могут принадлежать m m матрица состояний ЛДДС и ее характеристический многочлен D
m 2m 1 .
Рассмотрим теперь структуру замкнутых циклов линейной ДДС при u k =1 . Описание ЛДДС
для этого случая задается представлениями (1), в которых следует положить u k =1 так, что получим:
x k +1= Ax k+B ; x 0.
(14)
Следует заметить, что введенное с помощью О.3 определение замкнутого цикла длиной T сохраняется, однако структура этих циклов не только зависит от показателя , которому принадлежит матри-
ца A , структуры собственных векторов f степенных матричных функций f A= AT от m m
матрицы A состояний ЛДДС, но и от матрицы B . Последняя может принадлежать пространству столбцов матрицы A , т.е. ее образу
B Jm A ,
тогда пара матриц A, B оказывается неполностью управляемой, простейшим случаем такой ситуации
является случай, когда матрица B является собственным вектором матрицы A . В этой связи сформулируем утверждение.
Утверждение 5 (У.5). Если матрица B векторно-матричного описания ЛДДС является собствен-
ным вектором матрицы A , то ЛДДС с такой парой матриц A, B не является полностью управляемой,
при этом размерность подпространства управляемости равна единице.
□
Доказательство. Тот факт, что матрица B есть собственный вектор матрицы A состояний ЛДДС
над простым полем Галуа GF 2 , позволяет записать A B = B .
Составим матрицу управляемости пары A, B
Wy A, B = B A B A2 B Am1 B . Для элементов Wу A, B можно записать
A B = B ; A2 B = A B = B, , Am1 B = A Am2 B = = B .
(15)
Подстановка полученных матричных равенств в (15) дает для матрицы управляемости
rank Wу A, B= rank B B B B= rank B =1< m .
■
Составим следующий алгоритм анализа структуры замкнутых циклов линейных ДДС с системной
матрицей A , имеющей своим характеристическим модулярным многочленом D = det I+A не-
приводимый многочлен степени m .
46 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 4 (74)
А.В. Ушаков, Е.С. Яицкая
Алгоритм 1 (А.1) 1. Построить векторно-матричное представление линейной двоичной динамической системы в рекур-
рентной форме (1).
2. Перейти от представления ЛДДС (1) к ее представлению в форме (5), положив в (1) u k = 0 .
3. Вычислить характеристический многочлен D матрицы A состояний ЛДДС в силу соотношения
D = det I+A .
4. Определить показатель , которому принадлежит характеристический многочлен D и матрица
A состояний ЛДДС, с использованием таблиц многочленов, принадлежащих конкретному , или
возведением матрицы A в степень над полем Галуа GF 2 до момента выполнения равенства (2).
5. Проанализировать полученное значение по соотношению
2m 1= m+ r ,
из которого определить m – число циклов длины T = и r – суммарную длину циклов, длительности 1 Tr r . 6. Определить состав и последовательность изменения состояний в замкнутых циклах длиной T = ,
порожденных фактом принадлежности матрицы A состояний ЛДДС показателю , используя
представление циклов в форме (10), в котором за исходное состояние x k цикла взять любое со-
стояние множества X~ . 7. Сформировать структуру замкнутых циклов и неподвижных состояний линейной ДДС (5) (при
u k = 0 ) п.п. 5, 6, дополнив их нулевым неподвижным состоянием.
8. Перейти от представления ЛДДС (1) к ее представлению в форме (14), положив в (1) u k =1 .
9. Определить неподвижное состояние x k: x k +1= x k , используя соотношение (6) или (7).
10. Определить состав и последовательность изменения состояний в замкнутых циклах длиной T = ,
порожденных фактом принадлежности матрицы A состояний ЛДДС показателю , используя
представление циклов в форме (11), в котором за исходное состояние x k цикла взять любое со-
стояние множества X~ .
11. Сформировать структуру замкнутых циклов и неподвижных состояний линейной ДДС (14) (при
u k =1 ) п. 10, дополнив их неподвижным состоянием п. 9.
■
Пример анализа структуры пространства состояний ЛДДС, представленной ее неподвижными состояниями и замкнутыми циклами
В качестве примера рассматриваются ЛДДС с матрицами A состояний размерности
m m= 33. Структура пространства изучается на реализациях пар матриц A, B, в которых матрицы A обладают характеристическими многочленами D , принадлежащими классу неприводимых
степени degD = m , а множество ненулевых матриц B характеризуется мощностью B= 2m 1.
Исследования начнем со случая, когда ХММ матрицы A имеет вид D = 3 ++1. Тогда, следуя ал-
горитму А.1: 1. выполним п.п. 1–2, в результате чего ЛДДС будет иметь матрицу A состояний, заданной во фробе-
ниусовой форме так, что она получает представление
0 1 0 A = 0 0 1 ;
1 1 0
4. путем вычисления степенной матричной функции f A= Al установим, что при l = 7 выполняется
равенство Al = I , на основании чего становится справедливым соотношение = 7 , где – показа-
тель, которому принадлежит матрица A ; 5. анализируя значение , обнаружим справедливость разложения мощности 2m 1 множества нену-
левых состояний в форме 2m 1= 7 =1 7+0 , что свидетельствует о наличии в структуре пространства матрицы A состояний ЛДДС одного замкнутого цикла длиной T = = 7 ;
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
47
АНАЛИЗ СТРУКТУРЫ ПРОСТРАНСТВА СОСТОЯНИЙ…
6. определим состав и последовательность смены состояний ЛДДС в замкнутом цикле длины T = = 7 , порожденного фактом принадлежности матрицы A показателю = 7 . В качестве стартового состояния примем состояние, характеризующееся минимальным кодовым расстоянием с нулевым состоя-
нием ЛДДС, не входящим в состав цикла x k = 0 0 1T . Если воспользоваться (10), то получим
замкнутый цикл, характеризующийся составом и последовательностью
0 0 1 0 1 1 1
10,
1, 0
0, 1
1, 1
1, 1
1, 0
00;
7. получим полную структуру замкнутых циклов и неподвижных состояний при u k 0 (рис. 1);
001
0
000
0
0
010
0
100
0
110
101
0
0
111
011
0
Рис. 1. Структура замкнутых циклов и неподвижных состояний ЛДДС при u k 0
8. для рассмотрения ЛДДС вида (14) для матрицы B входа положим B = 0 0 1T ;
9. для поиска неподвижного состояния x k: x k +1= x k используем соотношение (6) и получим
0 1 1 0 1
x k = I + A1B = 1 1 1 0 1 ;
1 0 1 1 1 10. определим состав и последовательность смены состояний ЛДДС в замкнутом цикле длины T = = 7 ,
порожденной фактом принадлежности матрицы A показателю = 7 . В качестве стартового состояния одного из циклов примем состояние, отличное от состояния п. 9 примера, например, нулевое со-
стояние ЛДДС x k= 0 0 0T . Если воспользоваться (11), то получим замкнутый цикл, характе-
ризующийся составом и последовательностью
0 0 0 1 1 0 1
00,
0, 1
1, 1
1, 0
0, 1
1, 0
00;
11. получим полную структуру замкнутых циклов и неподвижных состояний при u k =1 (рис. 2).
000
1
111
1
1
001
1
011
1
100
1
010
1
101
110
1
Рис. 2. Структура циклов и неподвижных состояний ЛДДС с парой матриц A, B при u k = 1
Воспользуемся алгоритмом А.1 для всех пар матриц A, B , оговоренных в преамбуле примера.
Полученные результаты сведены в таблицу. Для компактности записи в таблице использованы представления матриц, циклов, последовательностей в виде их десятичных эквивалентов, причем величина периодичности представлена скобочной записью с указанием длительности периода в виде нижнего индекса у правой скобки.
48 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2011, № 4 (74)
А.В. Ушаков, Е.С. Яицкая
Матрица AT
Показатель
u k 0
0
1
u k 1 , Матрица BT
2 3 4 567
[2, 1, 6]
7
(0,5,6,1, 7,3,2)7, (4)1 (0,6,2,3, 1,4,7)7, (5)1 (0,7,1,5, 4,6,3)7, (2)1
(0,4,5,7, 2,1,6)7, (3)1
(0,3,4,2, 6,7,5)7, (1)1
(0,2,7,4, 3,5,1)7, (6)1
(0,1,3,6, 5,4,2)7, (7)1
(1, 3, 7, 6, 5, 2, 4)7, (0)1 (1, 2, 5, 3, 7, 6, 4)7, (0)1
(0,5,7,3, 2,1,6)7, (4)1 (0,6,3,1, 5,4,7)7, (2)1 (0,7,1,4, 6,2,3)7, (5)1
(0,4,5,6, 1,7,2)7, (3)1
(0,3,4,2, 7,5,1)7, (6)1
(0,3,4,2, 7,5,1)7, (1)1
(0,1,2,5, 3,6,4)7, (7)1
[2, 1, 5]
7
Таблица. Структура циклов и неподвижных состояний всех возможных вариантов реализаций
пар A, B матриц, задающих соответствующие ЛДДС при размерности вектора состояния dim x 3
Анализ структуры состояний ЛДДС, из которых под действием u k =1 возможен переход
в нулевое состояние
Проблема вычисления состояний, из которых ЛДДС переходит в нулевое состояние x k +1 0 , сводится к решению уравнения (14) при нулевой левой части. Тогда искомый x k при x k +1 0 и u k =1 определяется выражением
x k= A1B .
(16)
Если рассмотреть ЛДДС с парой матриц A, B, где матрица A задается в форме п. 1 примера, а
матрица B – в форме п. 8 примера, то состояние x k , удовлетворяющее условию (16), получает пред-
ставление
x k= 1 0 0T .
Заключение
Предложенная в работе алгоритмическая среда анализа структуры пространства состояний ЛДДС делает алгебраически прозрачным процесс преобразования двоичных кодов [1–3], что особенно важно при решении задач помехозащитного преобразования этих кодов. Становится наглядной необходимость выбора неприводимых многочленов в качестве образующих многочленов помехозащищенного кода с максимальным значением их принадлежности.
Литература
1. Фараджев Р.Г. Линейные последовательностные машины. – М.: Советское радио, 1975. – 248 с. 2. Гилл А. Линейные последовательностные машины. – М.: Наука, 1974. – 288 с. 3. Мельников А.А., Ушаков А.В. Двоичные динамические системы дискретной автоматики / Под ред.
А.В. Ушакова. – СПб: СПбГУ ИТМО, 2005. – 214 с. 4. Ушаков А.В., Яицкая Е.С. Рекуррентное систематическое помехозащитное преобразование кодов:
возможности аппарата линейных двоичных динамических систем // Изв. вузов. Приборостроение. – 2011. – № 3. – С. 17–25. 5. Ушаков А.В., Яицкая Е.С. Динамическое наблюдение нелинейных двоичных динамических систем // Научно-технический вестник СПбГУ ИТМО. – 2010. – № 4. – С. 38–44. 6. Гантмахер Ф.Р. Теория матриц. – 5-е изд. – М.: Физматлит, 2004. – 560 с.
Ушаков Анатолий Владимирович – Санкт-Петербургский государственный университет информационных технологий, механики и оптики, доктор технических наук, профессор,
Яицкая Елена Сергеевна
ushakov-AVG@yandex.ru – Санкт-Петербургский государственный университет информационных
технологий, механики и оптики, аспирант, yaitskayaes@mail.ru
Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2011, № 4 (74)
49