Например, Бобцов

ДИНАМИЧЕСКОЕ НАБЛЮДЕНИЕ НЕЛИНЕЙНЫХ ДВОИЧНЫХ ДИНАМИЧЕСКИХ СИСТЕМ

ДИНАМИЧЕСКОЕ НАБЛЮДЕНИЕ НЕЛИНЕЙНЫХ ДВОИЧНЫХ...
УДК 519.713
ДИНАМИЧЕСКОЕ НАБЛЮДЕНИЕ НЕЛИНЕЙНЫХ ДВОИЧНЫХ ДИНАМИЧЕСКИХ СИСТЕМ
А.В. Ушаков, Е.С. Яицкая
Ставится и решается задача использования возможностей динамического наблюдения, разработанного в основном применительно к дискретным системам над бесконечными полями, на случай систем над конечными двоичными полями Галуа. Основное внимание сосредоточено на реализации динамического наблюдения (ДН) за состоянием нелинейных двоичных динамических систем (ДДС) с учетом практики решения этой проблемы для случая линейных ДДС. Поставленная задача решается в три этапа: линеаризация нелинейной ДДС, формирование процесса ДН линеаризованной ДДС и вычленение наблюдений за состоянием исходной нелинейной ДДС. Приводится пример. Ключевые слова: двоичная динамическая система, линейная, нелинейная, линеаризация, динамическое наблюдение, матричное уравнение Сильвестра, темп сходимости, индекс нильпотентности.
Введение Концепция динамического наблюдения появилась и разрабатывалась в основном применительно к непрерывным и дискретным системам над бесконечными полями [1–3]. Интенсивное развитие телекоммуникационных сетей как в направлении их технологического совершенствования, так и в направлении усложнения модельного описания обнаружило, что канальная среда (КС) модельно представляет собой двоичную динамическую систему [4]. Если КС дополнить терминальными устройствами (ТУ) приема, обработки, хранения и преобразования двоичной информации, то их агрегатное объединение получает описание в одной из возможных форм – линейной двоичной динамической системы (ЛДДС) или нелинейной двоичной динамической системы (НДДС). Естественным образом встает задача формирования алгоритмической среды, средствами которой для целей задач диагностики и обеспечения помехозащиты можно было бы наблюдать состояние таких систем. Этой проблеме применительно к классу НДДС посвящается предлагаемая вниманию читателя статья.
Постановка задачи Как и в случае динамических систем над бесконечными полями, алгоритмическое обеспечение формирования динамического наблюдающего устройства (ДНУ) над двоичным полем Галуа получило достаточно глубокую разработку только для класса ЛДДС [4]. В этой связи для того, чтобы перенести
38 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 4(68)

А.В. Ушаков, Е.С. Яицкая

имеющиеся результаты по построению двоичного динамического наблюдающего устройства ЛДДС на класс НДДС, предлагается решение задачи в три этапа. На первом этапе путем агрегирования переменных на основе расширения булева базиса компонентами базиса Жегалкина [5] строится расширенное эквивалентное линейное представление НДДС. На втором этапе строится ДНУ расширенной размерности применительно к эквивалентному линейному представлению НДДС с использованием информации о входной и выходной кодовых последовательностей наблюдаемой НДДС. На третьем этапе из вектора наблюдающего устройства, являющегося оценкой состояния эквивалентного линейного представления НДДС, вычленяется с помощью матрицы-проектора составляющее состояние исходной двоичной нелинейной динамической системы.
К сказанному следует добавить, что поставленная и решаемая задача может найти неожиданное направление использования. Это связано с тем, что задача помехозащитного декодирования может быть сформулирована как задача наблюдения состояния регистра сдвига [6], начальное состояние которого представляет собой двоичную кодовую последовательность, искажающую передаваемую информацию в двоичном канале связи. Если источник искажений в двоичной канальной среде моделируется в форме НДДС, то положения динамического наблюдения, развиваемые в статье, оказываются применимы для решения задач помехозащитного декодирования и для данного случая.

Базовые концепции динамического наблюдения линейных двоичных систем

Базовые концепции динамического наблюдения ЛДДС представим в виде алгоритма синтеза дво-

ичного ДНУ.

Алгоритм 1 (А.1) синтеза устройства двоичного динамического наблюдения ЛДДС

1. Представить ЛДДС, состояние которой подлежит динамическому наблюдению, с помощью векторно-

матричного описания

x  k 1  A x  k   B u  k , x  0  x0 , y  k   C x  k   N u(k) ,

(1)

де x, u, y – соответственно n - мерный вектор состояния, r -мерный вектор входной последовательности

и l -мерный вектор выходной последовательности; матрицы A, B, C, N согласованы по размерности с векторами x, u и y ; элементы векторов и матриц принадлежат двоичному простому полю Галуа

GF  2 .
2. Представить двоичное ДНУ, использующее всю доступную для непосредственного измерения инфор-
мацию об ЛДДС (1), в виде входной последовательности u  k  и выходной y  k  в форме

z  k 1  Γ z  k   L y  k   G u  k , z  0  z0 ,

(2)

где z – n - мерный вектор состояния ДНУ, матрица Γ имеет заданный индекс нильпотентности  , ко-

торый определяет динамику процесса наблюдения, а пара матриц  L,G  обладает свойствами

L  arg  contr  Γ, L , G  arg  contr  Γ,G  , где contr  ,  – предикат наличия полной управ-

ляемости пары матриц   ,  .

3. Поставить задачу наблюдения вектора x состояния системы (1) в среде ДНУ (2) в виде
z k  Tx k k, k ,

(3)

где T – n  n -матрица преобразования подобия;  k  – вектор невязки наблюдения (ВНН).

4. Описать согласно утверждению, представленному в [6], процесс по ВНН  k  рекуррентным вектор-

но-матричным уравнением

 k 1  Γ  k ,  0  Tx  0  z  0 .

(4)

5. Представить задачу наблюдения вектора x  k  текущего состояния ЛДДС (1), воспользовавшись яв-

ным (степенным) решением (4) и условием обнуления состояния ДНУ при запуске ( z  0  0 ):

 k  Γk T x 0 ,

(5)

z k  T x k  Γk  0 .

(6)

6. Решить матричное уравнение Сильвестра относительно матрицы подобия Т : ΓTTA LC, G TB.

(7)

При этом решение уравнения Сильвестра (7) гарантируется перечисленными в п. 2 условиями и непересекаемостью алгебраических спектров собственных значений матриц Γ и A для случая, когда последняя не имеет нулевых собственных значений.

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)

39

ДИНАМИЧЕСКОЕ НАБЛЮДЕНИЕ НЕЛИНЕЙНЫХ ДВОИЧНЫХ...

7. Оценить правильность назначения матрице Γ свойства нильпотентности с индексом  [7] путем кон-

троля при k   выполнения соотношений Γk  0 и z  k   T x  k  . 8. Сформировать оценку x k  вектора состояния x k  ЛДДС в форме

x  k   T1 z  k  , которая при k   удовлетворяет соотношению x  k   x  k  .

(8)

Постановка задачи наблюдения нелинейной двоичной динамической системы

Каноническое представление «вход–состояние–выход» произвольной двоичной динамической системы задается в виде двух векторных выражений:

xн  k 1    xн  k , u  k   ,  

(9)

y  k     xн  k   ,

(10)

в которых   xн  k , u  k   ,   xн  k  именуются соответственно функциями перехода и выхода. Если
функции перехода и выхода допускают представление в виде линейных операций умножения матрицы на вектор и суммирования, то они получают представление вида (1), если такой возможности нет, то со-

отношения (9)–(10) задают НДДС с вектором состояния xн размерности dim xн  nн  log2n .

Если поставить задачу динамического наблюдения вектора состояния xн НДДС (9)–(10), т.е. его восстановления в среде динамического наблюдающего устройства на основе непосредственного измере-

ния входной последовательности u k  и выходной последовательности y k  , то следует признать, что в

классе нелинейных представлений в силу отсутствия на настоящий момент опыта решения такого рода

задач она может не получить решения с гарантированным качеством. Тем не менее, решение таких задач

с гарантированным качеством в классе линейных представлений имеет хорошую прикладную практику.

Таким образом, встает задача построения эквивалентного линейного представления НДДС (9)–(10)

в предположении, что правила  и  заданы аналитически в виде булевых функций в булевом базисе, в

виде ЛДДС

x  k 1  A x  k   B u  k , x  0  x0 , y  k   C x  k   N u(k) ,

(11)

где x – вектор состояния эквивалентного линейного представления НДДС размерности n ; y(k) –

вектор выходной последовательности той же размерности l , что в (1) и (10); u(k) – вектор входной по-

следовательности той же размерности r , что в (1) и (10); A , B ,C – матрицы, согласованные по размер-

ности с переменными так, что dim A  n  n;dim B  n  r;dim C  l  n . Задача формирования эквивалент-

ного линейного представления НДДС вида (11) решается в предположении, что достижимо представле-

 ние

вектора x ~x  col

xвнф,о~~xрм. е

(12)

Процедура построения эквивалентного линейного представления НДДС реализуется в виде сле-

дующего алгоритма.

Алгоритм 2 (А.2) построения эквивалентного линейного представления НДДС

1. Составить аналитические представления булевых функций, построенных в булевом базисе, на основа-

нии таблиц переходов и выходов НДДС как таблиц истинности функций (9) и (10) относительно булевых

переменных u  k  , xн  k  , xн  k 1 , y k  .
2. Модифицировать аналитические выражения п.1, используя арифметику базиса Жегалкина путем замены всех инверсий переменных суммированием по модулю два инвертируемой переменной с единицей,

осуществляемой в форме xi k   xi k  1 [8].
3. Ввести в рассмотрение двухкомпонентный расширенный вектор x состояния системы, полученной в

п. 2, первый компонент которого совпадает с вектором xн состояния линеаризируемой НДДС, а второй
имеет своими элементами все возможные конъюнкции переменных аддитивных композиций, связанных операцией суммирования по модулю два. 4. Сформировать линеаризованное представление НДДС с вектором состояния x , записанное в поком-
понентной форме. 5. Составить предварительную линеаризованную модель НДДС в канонической векторно–матричной форме (11), списав матрицы A , B , C , N с покомпонентного представления п. 4.

40 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 4(68)

А.В. Ушаков, Е.С. Яицкая

   6. Вычислить ранг матрицы управляемости пары A , B и матрицы наблюдаемости пары A ,C .

7. В случае отличия вычисленных в п. 6 рангов от величины n  dim x осуществить минимизацию
размерности вектора состояния эквивалентного линейного представления НДДС с использованием аппарата булевых (селлерсовских) производных [9]. 8. Построить минимизированное эквивалентное линейное представление НДДС с вектором состояния xm и матрицами A m , B m , C m , N .
Очевидно, что ДНУ вектора x состояния эквивалентного линейного представления НДДС (11)

строится по той же схеме, что и ДНУ вектора x состояния ЛДДС (1), так что для него можно записать

z  k 1  Γ z  k   L y  k   G u  k , z  0  z0 ,

(13)

где z – вектор состояния ДНУ размерности n ; Г , L ,G – матрицы, согласованные по размерности с

переменными ДНУ, так что dim Г  n  n;dim L  n  r;dim G  l  n . Наделение матрицы Γ свойством

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

соотношения, аналогичного (8), записываемого при k   в форме

z  k   T x  k  ,

(14)

где матрица подобия Т находится решением матричного уравнения Сильвестра Γ T  T A  L C , G  T B .

(15)

В силу равенства размерностей векторов состояния эквивалентного линейного представления НДДС и

сеогоотндоишнеанмииечделсякоогцоенкниабxл(юk )давюекщтеогроа

устройства состояния x(k

оказывается справедливым ) , эквивалентное (8),

x(k)  T 1z(k) ,

которая при k   удовлетворяет соотношению x  k   x  k  .

векторно-матричное (16)

В случае выполнимости представления вектора состояния эквивалентного линейного

представления НДДС в форме (12) для вектора xн состояния исходной НДДС получим оценку xˆн (k)  C н xˆ(k)  C нT z(k) ,
где

(17)

C н  Ilnн

0l  n  nн



 

.

(18)

Выражение (17) в случае справедливости (18) представляет собой решение задачи динамического

наблюдения вектора xн состояния исходной НДДС вида (9)–(10). Таким образом, задача динамического

наблюдения НДДС будет успешно решена, если удастся решить задачу построения ее эквивалентного линейного представления (11).

Основной результат. Построение устройства двоичного динамического наблюдения за состоянием НДДС на основе линеаризованного представления

Решение проблемы, вынесенной в заголовок раздела, представим в виде алгоритма построения устройства двоичного динамического наблюдения за состоянием НДДС на основе линеаризованного представления.
Алгоритм 3 (А.3) построения устройства двоичного динамического наблюдения за состоянием НДДС на основе линеаризованного представления 1. Задать НДДС вида (9), (10) в форме совмещенной таблицы истинности. 2. Сформировать эквивалентное линеаризованное представление НДДС вида (11) на основе алгоритма А.2. 3. Построить в произвольном базисе устройство двоичного динамического наблюдения за состоянием НДДС с вектором состояния z и матрицей подобия Т на основе использования алгоритма А.1.
4. Сформировать оценку наблюдения xe k  вектора состояния x k  линеаризованной НДДС с
 помощью соотношения xe k   T 1 z k   Γ k  k  .
5. Сформировать оценку xнe k  вектора состояния xн k  исходной НДДС с помощью соотношения
xнe (k)  C н xe (k) , где C н определяется выражением (18).

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)

41

ДИНАМИЧЕСКОЕ НАБЛЮДЕНИЕ НЕЛИНЕЙНЫХ ДВОИЧНЫХ...

6. Проверить правильность функционирования двоичного динамического наблюдающего устройства НДДС, построенного на основе эквивалентного линейного представления НДДС, на примере тестовой входной последовательности.

Пример

Ключевым моментом формирования двоичного динамического наблюдающего устройства НДДС является процедура построения эквивалентного линейного представления НДДС. Проиллюстрируем ал-
горитм А.2 на примере НДДС, преобразующей унитарный код u k   1k  в периодическую тестовую

последовательность y k  :11010 11010 

1. Сформируем функции (9), (10), задав их в форме совмещенной таблицы истинности, на основании которых, а также процедуры минимизации булевых функций, получим:

xн1 k 1  u k  xн1 k  xн2 k  xн3 k   u k  xн1 k  xн2 k  xн3 k ,

  

xн2 xн3

k k

 1  1

 

xн1 k  xн2 k   u k  u k  xн1 k  xн3 k  

xн1 k  xн3 k   u k u k  xн1 k  xн2 k ,





2



k



xн3



k



,

 y k   xн1 k  xн2 k   xн1 k  xн3 k .

 

выход y k 

1

1

0

1

0

*

*

*

вход

исходные состояния xн k 

неиспользуемые состояния

u k  000 001 011 010 110 100 101 111

0 000 001 011 010

1 001 011 010 110

состояние перехода

xн k  1  xн1 k  1 xн2 k  1 xн3 k  1

* – пустой символ

110 000

Таблица 1. Совмещенная таблица истинности функций перехода и выхода
  2. Модифицируем аналитические выражения п.1, построенные с помощью элементов арифметики вида
xi k   xi k  1 базиса Жегалкина, в результате чего получим:

 

xн1

k

 1



xн1

k



xн2

k





xн1

k



xн2

k



xн3

k





u

k



 xн2

k





xн2

k



xн3

k



,

xн2 k 1  xн2 k   xн1 k  xн2 k  xн3 k  

   

xн3



k



1

 

u k  xн3 k xн3 k   xн1

 

 xн1  k  xн3

k  xн2 k  



k





xн1



k



xн3



k







2



k



xн3



k



,

 

 u k  1 xн1 k   xн2 k   xн3 k   xн1 k  xн2 k   xн1 k  xн3 k  ,

 

y



k





1



xн1



k







2



k



xн3



k





xн1



k





2



k



xн3



k



.

 3. Введем в рассмотрение двухкомпонентный расширенный вектор x  col xн , x состояния эквивалент-

ной двоичной системы (11) в силу соотношений
 x k   col xн , x  col{x1 k   xн1 k , x2 k   xн2 k , x3 k   xн3 k , x4 k   xн1 k  xн2 k ,

x5 k   xн2 k  xн3 k , x6 k   xн1 k  xн3 k , x7 k   xн1 k  xн2 k  xн3 k , x9 k   u k  xн2 k , x10 k   u k  xн3 k , x11 k   u k  xн1 k  xн2 k ,

 

x12 k   u k  xн1 k  xн3 k , x13 k   u k  xн2 k  xн3 k , x14 k   u k  xн1 k  xн2 k  xн3 k };

4. Сформируем линеаризованное представление НДДС с вектором состояния x в форме (11), записанное

в покоординатном виде:

42 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2010, № 4(68)

А.В. Ушаков, Е.С. Яицкая

x1 k 1  x4 k   x7 k   x9 k   x13 k ,

 

x2



k

 1



x2

k





x7



k





x10



k





x11



k





x12



k





x13

k



,

  

x3 x4

k k

 1  1

 

x3 x4

k k

 

 

x6 x9

k k

 

 

x8 k   x13 k ,

x9



k





x10



k





x11



k





x12



k





u



k



,

  

x5 x6

 

k k

 

1 1

 

x5 0,



k





x7



k





x10



k





x12



k



,

  

x7 x8

k k

 1  1

 

0, x9



k





x11



k





x13



k





x14



k



,

 

x9



k



1



x9

k





x10



k





x11



k





x12



k





x13



k





x14



k



,

x10 k 1  x8 k   x9 k   x11 k   u k ,

 

x11

k

 1



x9

k





x11

k





x13

k

,

  

x12 x13

 

k k

 1  1

 

0, x10



k





x12



k





x13



k





x14



k



,

 

  

x14 k y k 

 

1
x1

 0,
k

x5



k





x7



k





u



k



.

5. Списываем с полученных в п. 4 соотношений матрицы A , B , C , N представления (11).

6. Пользуясь матричными компонентами эквивалентного представления (11), продолжаем его исследование в соответствии с пп. 6–8 алгоритма А. 2.

  Заключение

Завершая рассмотрение проблемы, вынесенной в заголовок статьи, авторы вынуждены констатировать на примере конкретной задачи преобразования кодов, что решение этой задачи средствами линейных ДДС размерности n и средствами линеаризованной нелинейной ДДС размерности nm обнару-
живает существенное различие этих величин, удовлетворяющих отношению порядка n  nm . Таким
образом, перед исследователями ставится задача анализа причин этого различия и выяснения класса ДДС, размерность nдс которых удовлетворяет неравенству n  nдс  nm .

Литература

1. Гудвин Г.К. Проектирование систем управления / Г.К. Гудвин, С.Ф. Гребе, М.Э. Сальгадо. – М.: БИНОМ. Лаборатория знаний, 2004. – 911 с.
2. Синтез дискретных регуляторов при помощи ЭВМ/ В.В. Григорьев, В.Н. Дроздов, В.В. Лаврентьев, А.В. Ушаков – Л.: Машиностроение, Ленингр. отд-ние, 1983. – 245 с.
3. Дударенко Н.А., Слита О.В., Ушаков А.В. Математические основы современной теории управления: аппарат метода пространства состояний: учебное пособие / Под ред. А.В. Ушакова – СПб: СПбГУ ИТМО, 2008. – 323 с.
4. Мельников А.А., Ушаков А.В. Двоичные динамические системы дискретной автоматики / Под ред. А.В. Ушакова. – СПб.: СПбГУ ИТМО, 2005. – 214 с.
5. Горбатов В.А. Фундаментальные основы дискретной автоматики. Информационная математика. – М.: Наука, Физматлит, 1999.
6. Ушаков А.В., Яицкая Е.С. Помехозащитное декодирование систематических кодов // Изв. вузов. Приборостроение. – 2009. – Т. 52. – № 11. – С.77–83.
7. Гантмахер Ф.Р. Теория матриц. – 5-е изд. – М.: ФИЗМАТЛИТ, 2004. – 560 с. 8. Глава 4. Метод приведения систем логического типа к форме линейной последовательностной ма-
шины // В кн.: Дубаренко В.В., Коновалов А.С., Кучмин А.Ю. Оптимизация динамики систем при управлении в нестационарных условиях. Учебное пособие. – СПб: СПбГУАП, 2008. – 77 с. 9. Селлерс Ф. Методы обнаружения ошибок в работе ЭЦВМ. – М.: Мир, 1972. – 310 с.

Ушаков Анатолий Владимирович Яицкая Елена Сергеевна

– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, доктор технических наук, профессор, ushakov-AVG@yandex.ru
– Санкт-Петербургский государственный университет информационных технологий, механики и оптики, аспирант, yaitskayaes@mail.ru

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2010, № 4(68)

43