Использование свойств матриц над конечными полями для обнаружения неустойчивых циклов и неподвижных состояний двоичных динамических систем

ИСПОЛЬЗОВАНИЕ СВОЙСТВ МАТРИЦ НАД КОНЕЧНЫМИ ПОЛЯМИ ДЛЯ ОБНАРУЖЕНИЯ НЕУСТОЙЧИВЫХ ЦИКЛОВ И НЕПОДВИЖНЫХ СОСТОЯНИЙ ДВОИЧНЫХ ДИНАМИЧЕСКИХ СИСТЕМ А. А. Мельников, Е. В. Рукуйжа, А. В. Ушаков

На основе анализа свойств матриц состояния и входа линейной двоичной динамической системы (ЛДДС) над конечным полем вР(2) решается задача обнаружения неустойчивых циклов и неподвижных состояний ЛДДС. Результаты иллюстрируются примерами.

Введение. Постановка задачи.

Рассматривается линейная двоичная динамическая система [1-3], векторно-матричное описание которой задается в формах рекуррентной

х

у

и суммарной

к-1

х

1=0

у

моделей. В (1) - (3) х - п мерный вектор состояния ЛДДС, и - г мерная входная последовательность, У - т мерная выходная последовательность, А - (пхп) матрица состояния, В - (пхг) матрица входа, С - (тхп) матрица выхода, Н - (тхг) матрица "вход-выход", V- (к) вектор стратегии управления состоянием ЛДДС, задаваемый на первых к - тактах в форме

V

Щ (к) - матрица управляемости двоичной системы на первых к тактах, определяемая матричной структурой

Щ

В дальнейшем используется для оценки свойств пары матриц (А,В) матрица управляемости (5) для случая к = п, в силу чего она представляется выражением

Щ =Щ

Ставится задача обнаружения неустойчивых циклов и неподвижных состояний двоичных динамичных систем вида (1) - (3) на основе анализа свойств пары матриц (АВ). Анализ опирается на то обстоятельство, что часть свойств матриц над конечными полями идентичны свойствам матриц над бесконечными [4], а другая часть свойств порождена модулярной природой конечных полей.

Свойства матриц состояния и входа над конечными полями

Анализ свойств матрицы состояния проведем опираясь на понятие матричной функции от матрицы с учетом модулярной специфики конечного поля, а анализ свойств матрицы В, в котором в основном ограничимся случаем г = 1, будем проводить на предмет установления факта принадлежности матрицы В геометрическому спектру собственных векторов матрицы А, а также установления свойства управляемости пары (А, В).

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

Определение 1 (О.1) Матричной функцией f(A), представляющей собой (nxn) матрицу от (nxn) матрицы А, заданных над конечным полем GF(2) называется матричный ряд, порождаемый рядом от скалярной переменной а вида

f

путем замены а на А, так что f (A) принимает вид:

f

В (7), (8) at eGF(2);/ =1,p....; так, что суммирование и приведение подобных

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

Утверждение 1(У.1) Матричная функция от матрицы, порожденная модулярным характеристическим полиномом матрицы A

D

обнуляется этой матрицей, так что

D

Доказательство утверждения опирается на положение теоремы Гамильтона-Кэли [4], сформулированное для случая характеристического полинома матриц над бесконечным полем [1].

Определение 2 (О.2) Квадратная (nxn) матрица A обладает свойством принадлежности показателю ¿и, где ¿и - целое положительное, если выполняется условие

Au= I

Утверждение 2 (У.2) Для того чтобы матрица A принадлежала показателю и достаточно чтобы характеристический полином D(X) этой матрицы входил в разложение двучлена Ли +1 в форме

Ли+1=Q

где Q

Доказательство (У.2) Сконструируем на модулярном многочлене (12) матричную функцию от матрицы

Au +1 = Q

В силу положения утверждения

D

тогда подстановка (14) в (13) дает

Au +1 = 0 или Au = I

Определение 3

Утверждение 3 (У.3) Достаточным условием наличия у матрицы A свойства нильпотентности (15) с индексом v является представимость ее характеристического полинома в виде

D

Доказательство утверждения строится на свойстве (10) матрицы обнулять свой характеристический полином.

Утверждение 4 (У.4) Индекс нильпотентности v (nxn)-нильпотентной матрицы A удовлетворяет неравенству

2 <v< n

Доказательство утверждения строится на канонической форме нильпотентной матрицы. Если каноническая форма матрицы A представляет собой (nxn) клетку Жордана [4] с нулевыми диагональными элементами, то индекс нильпотентности v ее равен значению n и является максимальным, что доказывает справедливость правой части неравенства (17). Если отсечением согласованных по размеру левых нулевых столбцов и нижних нулевых строк получается Жорданова клетка размера v<n, при этом индекс нильпотентности v такой матрицы устанавливается прямым возведением в степень v матрицы A, то очевидно, что минимальный размер Жордановой клетки с нулевыми диагональными элементами будет равен двум, что доказывает

справедливость левой части неравенства (17).

Утверждение 5 (У.5) Если матрица входа B имеет размерность (nxl) и при этом она является собственным вектором матрицы состояния A ЛДДС (1), то пространство управляемости ЛДДС имеет размерность равную единице.

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

Воспользуемся свойством собственного вектора матрицы A. Если некоторый вектор % является собственным вектором матрицы A, то над конечным полем GF (2) это обстоятельство может быть представлено в форме

A%=%

Подставим в (19) вместо % матрицу-столбец B , тогда на основе (19) получим матричные равенства AB = B;

A2 B = A

ApB = Ap-2(A2B) = Ap-2 • B = B

Если

Матрица управляемости вида (21) обладает тем свойством, что ранг ее равен единице.

Утверждение 6(У.6) Пусть ЛДДС (1) характеризуется передаточной функцией

) = Ж=Md)

U

где Y

последовательностей ЛДДС (1); M (d ), D(d ) - модулярные многочлены относительно переменной d с коэффициентом из GF(2); тогда характеристический полином

матрицы A ЛДДС (1) и знаменатель D(d ) передаточной функции (22) этой системы связаны соотношением

D

причем D(d-1) задается соотношением

D

Доказательство утверждения строится на применении к векторно-матричному описанию (1) ЛДДС прямого й - преобразования [1,2] при нулевом начальном ее состоянии, тогда с использованием свойств й - преобразования получим

й-1 X

У

где X (й) - Д образы состояния х(к) входной последовательности и (к) и выходной У (к) соответственно.

Разрешим соотношение (25),(26) относительно У(й), исключив из них X(й). Тогда получим

У

Нетрудно видеть, что (27) представляет собой передаточную функцию ЛДДС, записанную в мультипликативной форме так, что

1

Ф

ёе1;

Из(28)следует

ёе^й-1!+А)=Б

Основной результат

Для решения задачи, вынесенной в название статьи, введем и сформулируем дополнительные определения и утверждения.

Определение 4(О.4) ЛДДС (1) называется асимптотически устойчивой при и (к) = 0, если существует значение к * такое, что выполняется соотношение

х

Утверждение 7 (У.7) Если матрица А состояния ЛДДС (1) обладает индексом нильпотентности V, то эта двоичная динамическая система будет асимптотически устойчива в смысле определения О.4 в форме (29), при этом к * определяется равенством

к * =v

Доказательство утверждения строится на использовании суммарной модели (3) представления процессов ЛДДС по вектору состояния х(к). Если в (3) положить условие и (к) = 0 для любого к, то

х

По условию утверждения матрица А является нильпотентной с индексом нильпотентности V, в силу чего для к >v, выполняется равенство

Ак = 0

Соотношения (31)-(32) делают справедливым положение (29), где к * =v, а х(0) любое.

Доказанное утверждение сформулированное в негативной логике приводит к тому, что если матрица состояния не является нильпотентной, то такая ЛДДС не обладает свойством асимптотической устойчивости, в ней возможны неподвижные состояния, замкнутые неустойчивые циклы и особые режимы поведения в случае, если матрица В оказывается собственным вектором матрицы А.

Определение 5 (О.5) Пусть ЛДДС (1) характеризуется (пхп) матрицей состояния А, не обладающей свойством нильпотентности, тогда цикл длины Т при и (к) = 0,

сформированный на подмножестве X множеств состояний этой ЛДДС мощностью 2п, будет называться неустойчивым, если условие

х

выполняется для любого xi

Выделим на множестве X удовлетворяющем условию (33) частные случаи Т, удовлетворяющие неравенствам

1 < Т < 2п -1

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

Определение 6 (О.6) Состояние х(к) называется неподвижным, если оно удовлетворяет условию

х

Условие (35) может быть реализовано следующими двумя способами, которые определим утверждениями.

Утверждение 8(У.8) ЛДДС (1), с (пхп) матрицей состояния А, при любой ее реализации всегда имеет в качестве неподвижного состояния нулевое состояние х(к) = 0

Доказательство утверждения использует рекуррентную модель ЛДДС (1), в которой положено и (к) = 0, так, что она принимает вид

х

Подстановка в (36) условия х(к) = 0 дает при любой матрице А, для состояния перехода

х

что приводит к удовлетворению

Утверждение 9 (У.9) ЛДДС (1) с (пхп) матрицей состояния А произвольной реализации имеет в качестве неподвижного состояния состояние, которое является ее собственным вектором.

Доказательство утверждения опирается на определение собственного вектора который с учетом специфики конечного поля ОЕ (2), записывается в форме

Подстановка х(к)=% в (36) в силу (38) приводит к (35).

Необходимо сделать следующие примечания. Примечание 1

Нетрудно видеть, что условию утверждения У.9 удовлетворяет любой вектор если матрица состояния ЛДДС (1) является единичной.

Рассмотрим теперь ситуацию, в которой Т = / , где / - показатель, которому принадлежит матрица А.

Если характеристический полином Э

Таким образом, в случае удовлетворяющем (40) все множество мощностью 2п состояний ЛДДС (1), (36) разбивается на два подмножества, где одно представлено нулевым неподвижным состоянием, а второе образовано / состояниями, где / удовлетворяет (40), образующими замкнутый неустойчивый цикл.

Если характеристический полином Э (Я), является приводимым, то в зависимости от конкретной его реализации / принимает одно из значений удовлетворяющее неравенству

п </< 2п-1

В этом случае 2п возможных состояний ЛДДС (1), (36) образует сумму подмножеств. Первое из них образуется нулевым неподвижным состоянием. Второе-образуется р неустойчивыми циклами, каждое из которых содержит и состояний. Следующие подмножества образованы неподвижными состояниями

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

х = 2п -1 - и-[[4,)]

[(^ )]- мощность множества из элементов (£. ) (38).

В ключе поставленной проблемы обнаружения неподвижных состояний и замкнутых неустойчивых циклов, рассмотрим теперь поведение ЛДДС (1) для случая ненулевой входной последовательности. При этом выделим ситуацию, когда матрица В размерности (пх1) является собственным вектором матрицы А. Для этой ситуации сформулируем следующее утверждение.

Утверждение 10 (У.10) Пусть входная последовательность представляет собой унитарный код, так что

и

Пусть матрица входа В размерности (пх1) является собственным вектором матрицы А так, что выполняется соотношение

АВ = В

Тогда, под действием такой входной последовательности в пространстве состояний ЛДДС (1), возникает вынужденное движение, образующее неустойчивый замкнутый цикл {х(к) = 0; х(к +1) = В} с периодом Т = 2.

Доказательство утверждения строится на рекуррентной модели ЛДДС (1) в предположении, что х(к) = 0 и с учетом условий (42), (43), тогда рекуррентная модель для смежных к, (к +1), (к + 2) тактов приводит к результатам

х

х

Из

Примеры

В качестве примеров, иллюстрирующих основные положения работы, рассмотрим три версии ЛДДС третьего порядка (п =3) со следующими реализациями матриц состояния А:

А = со/{[010], [001], [101]}: Б

А = со/ {[010], [001], [111]}: Л) = ёе<Л I + А) = Л3 +Л2 +Л +1

А = со/ {[010], [001], [00]}: £

при этом все версии ЛДДС будут иметь матрицу входа В

В = [111 ]Т

Анализ информации, представленный (47) показывает, что матрица А (47) обладает неприводимым характеристическим полиномом ^(Л) поэтому она

принадлежит показателю и = 2п -1 = 7. Как следствие, структура состояний ЛДДС с такой матрицей при и (к) = 0 представлена двумя подмножествами. Первое подмножество состоит из нулевого состояния, являющегося неподвижным, второе подмножество образует неустойчивый цикл из оставшихся семи состояний. Матрица А

(47) с матрицей B (50) образует полностью управляемую пару, так что матрица управляемости

W = [в | AB | A2B]= row {lll]T,[ll0]T , [l0l]T } обладает рангом равным 3, что соответствует выполнению условия управляемости rangW = n . Установленное свойство полной управляемости ЛДДС гарантирует соответствующим выбором входной последовательности перевод системы из любого начального состояния в любое конечное за фиксированное число тактов.

Анализ информации представленный (48) обнаруживает, что матрица A принадлежит показателю / = 4. Структура пространства ЛДДС для этого случая при U(к) = 0 разбивается на 4 подмножества. Первое подмножество представлено неподвижным нулевым состоянием х = [000]T . Второе подмножество представлено состояниями образующими замкнутый неустойчивый цикл с периодом равным 4. Третье подмножество образовано неподвижным состоянием х = [lll]T, которое является собственным вектором матрицы A. Четвертое подмножество представлено состояниями, образующими замкнутый неустойчивый цикл с периодом Т = 2, каждое из которых х(к) = [0l0]T и х(к) = [l0l]T таково, что для них выполняются соотношения х(к + 2) = A2 х(к) = х(к) , является собственным вектором матрицы A 2 .

A2 = Co/{[00lJ [ill], [l00]} £ =[010]t ,£2 =[l0l]T

Матрица A (48) и матрица B (50) образуют не полностью управляемую пару, т.к. матрица B (50) является собственным вектором матрицы A, как следствие при входной последовательности в виде унитарного входа U (к) = Цк) в структуре состояний ЛДДС возникает неустойчивый вынужденный цикл периода 2, содержащий нулевое состояние х = [000]T и состояние х = B = [lll]T .

Анализ информации представленный соотношением (49) показывает, что матрица A ЛДДС принадлежит показателю / = 3. Как следствие, при U(к) = 0 структура пространства ЛДДС представлена четырьмя подмножествами. Первое подмножество образовано нулевым неподвижным состоянием. Второе и третье подмножества представлены неустойчивыми неподвижными циклами периода T = / = 3 . Четвертое

подмножество, представленное неподвижным состоянием х = [lll]T , которое является собственным вектором матрицы A. Пара матриц (49), (50) является не полностью управляемой, т.к. B-собственный вектор A. Как следствие, при входной последовательности в виде унитарного кода в поведении ЛДДС обнаруживается неустойчивый вынужденный цикл периода Т = 2 на состояниях х = [000]T и х = [lll]T .

В заключении необходимо отметить, что полученная на основе анализа свойств матриц A и B в рассматриваемых примерах структура неподвижных состояний и неустойчивых циклов также обнаруживается таблично-графическим способом с использованием таблиц и графов переходов ЛДДС [6].

Литература

1. Гилл А. Линейные последовательностью машины. М.: Наука, l974.

2. Фараджев Р. Г. Линейные последовательностью машины. М.: Сов. радио, l975.

3. Бохман Д., Постхофф Х. Двоичные динамические системы. М.: Энергоатомиздат, l986.

4. Гантмахер Ф. Д. Теория матриц. М.: Наука, l988.

5. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. / Пер. с англ.М.: Мир, l976.

6. Алгебраические методы в теории устройств дискретной автоматики и телемеханики // Труды лаборатории телемеханики СПб ГИТМО (ТУ) / под ред. А. В. Ушакова. СПб: СПбГИТМО (ТУ), 200l.