авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 | 5 |
-- [ Страница 1 ] --

А.А. Мельников, А.В. Ушаков

ДВОИЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ

ДИСКРЕТНОЙ АВТОМАТИКИ

x( k + 1) = [ x( k ), u ( k ) ],

y ( k ) = [ x( k ), u ( k ) ]

Санкт - Петербург

2005

Редакционно-издательский отдел

Санкт-Петербургского государственного

университета информационных технологий,

механики и оптики

197101, Санкт-Петербург, Кронверкский пр., 49

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ САНКТ - ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ А.А. Мельников, А.В. Ушаков ДВОИЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ ДИСКРЕТНОЙ АВТОМАТИКИ Санкт - Петербург 2005 УДК [517.938 + 519.713 /.718]: 621.398 Мельников А.А., Ушаков А.В. Двоичные динамические системы дискретной авто матики / Под ред. А. В. Ушакова. СПб.: СПбГУ ИТМО, 2005. 220с., ил. 40.

В монографии освещены вопросы анализа и синтеза двоичных динамических систем, используемых в современной дискретной автоматике «четкой логики».

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

Монография рассчитана на широкий круг специалистов в области дискретной автоматики, отраслевой телемеханики, аспирантов специальности 05.13.05. «элементы и устройства вычислительной техники и систем управления», а также студентов старших курсов, обучающихся по направлению 6519.00- «автоматизация и управление» бакалаврской и магистерской подготовки и специальности 2101.00 «управление и информатика в технических системах» подготовки специалиста инженера.

ISBN © Санкт-Петербургский государственный университет информационных технологий, механики и оптики, 2005.

© А. А. Мельников, А. В. Ушаков, 2005.

197101, Санкт-Петербург, Кронверкский пр. 49, Санкт-Петербургский госу дарственный университет информационных технологий, механики и оптики, e-mail: ushakov_AV@mail.ru, amndrey@newmail.ru СОДЕРЖАНИЕ CONTENTS……………………………………………………... Принятые сокращения и обозначения………………………… ВВЕДЕНИЕ…………………………………………………….. 1. ЛИНЕЙНЫЕ ДВОИЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ (ЛДДС) ДИСКРЕТНОЙ АВТОМАТИКИ…………………… 1.1. Аппарат передаточных функций (матриц) в задаче модельного представления ЛДДС………………………….. 1.2. Векторно-матричное модельное представление ЛДДС, параметризованное дискретным временем……………….. 1.3. Проблема редуцирования размерности модельных представлений ЛДДС……………………………………..... 1.3.1. Редуцирование линейных двоичных динамических систем на основе делимости модулярных многочлена числителя и знаменателя передаточной функции…… 1.3.2. Редуцирование линейных двоичных динамических систем на основе анализа структуры пространств управляемости и наблюдаемости ЛДДС……………... 1.4. Концепции подобия в теории линейных ДДС…………….. 1.4.1. Концепция подобия в задаче декодирования систематических помехозащищенных кодов………… 1.4.2. Концепция подобия в задаче синтеза двоичных динамических систем в логике произвольных линейных триггеров………… 1.5. Векторно-матричное представление линейного помехозащитного кодопреобразования, не параметризованное дискретным временем…………….. 1.5.1. Формирование матриц ПЗК с помощью проверочных равенств при декодировании и кодировании…………………… 1.5.2. Формирование матриц ПЗК с использованием матричного уравнения Сильвестра 1.5.3. Формирование матриц ПЗК с полной блоковой систематикой…………………….. 1.6. Анализ структуры неподвижных состояний и замкнутых циклов ЛДДС………………………………………………... 1.6.1. Неподвижные состояния линейной двоичной динамической системы…………. 1.6.2. Замкнутые циклы линейных ДДС…………………….. 1.7. ЛДДС в задачах дивидендного помехозащитного кодопреобразования………………………………………… 2. НЕЛИНЕЙНЫЕ ДВОИЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ (НДДС) ДИСКРЕТНОЙ АВТОМАТИКИ…….. 2.1. Построение модельного представления НДДС с использованием средств автоматной логики…..……….. 2.2. Построение дивидендных устройств помехозащитного кодопреобразования с помощью НДДС в логике произвольных триггеров………………………….. 2.3. НДДС в задачах коррекции искажений помехозащищенных кодов…………………………………. 2.4. Дивидендные кодирующие и декодирующие устройства укороченных циклических кодов с коммутируемой структурой………………………………. 2.5. Аппарат селлерсовского дифференцирования в задачах анализа булевых описаний НДДС дискретной автоматики 3. ГИБРИДНЫЕ ДВОИЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ (ГДДС) ДИСКРЕТНОЙ АВТОМАТИКИ…….. 3.1. Проблема заполнения кодового пространства классом гибридных ДДС……………………………………………... 3.2. Фактор востребованности переменных булевых описаний двоичных динамических систем…………………………… 3.3. Использование фактора востребованности булевых переменных кодов состояний НДДС для рационального использования ресурса помехозащиты 3.4. Построение эквивалентного линейного векторно матричного представления НДДС на основе принципа агрегирования переменных булевых описаний…………… 3.5. Проблема обмена на паре «аппаратурное пространство – временные затраты» в задачах помехозащитного кодо преобразования……………………………………………… ЗАКЛЮЧЕНИЕ….………………………………………………. ПРИЛОЖЕНИЕ D-преобразование и его свойства…………...

ЛИТЕРАТУРА…………………………………………………… Предметный указатель………………………………………….. Из истории лаборатории телемеханики………………………… BINARY DYNAMIC SYSTEMS OF DISCRET AUTOMATION Editor Doctor of Technical Sciences Professor A. V. Ushakov CONTENTS………………………………………………………. Table of Abbreviations and Symbols……………………………... INTRODUCTION………………………………………………... 1. LINEAR BINARY DYNAMIC SYSTEMS (LBDS) OF DISCRETE AUTOMATION……………………………...... 1.1. Transfer Function (Matrix) Approach in Problem of LBDS Model Representation…………………………………………. 1.2. Vector-Matrix LBDS Model Representation Parameterized by Discrete Time………………………………………………..... 1.3. The Problem of Dimension Reduction of LBDS Model Repre sentation……………………………………………………...... 1.3.1. Reduction of Dimension of LBDS by Means of Numera tor and Denominator Modular Polynomials of Transfer Function Divisibility……………………………………… 1.3.2. Reduction of Dimension of LBDS by Means of Analysis of Controllability and Observability Space of LBDS…….. 1.4. The Similarity Conception in Theory of Linear Binary Dynamic Systems……………………………………………… 1.4.1. The Similarity Conception in Systematic Noise-Immune Codes Decode Task………………………………………. 1.4.2. The Similarity Conception in Task of Binary Dynamic Systems Synthesis Within Arbitrary Flip-Flop Logic……. 1.5. Vector-Matrix Model Representation of Linear Noise Immunity Encoding not parameterized by Discrete Time…….. 1.5.1. Design of Noise-Immune Codes Matrices by Means of Check Equations Within Coding and Decoding Processes 1.5.2. Design of Noise-Immune Codes Matrices by Means of Sylvester Matrix Equation……………………………….. 1.5.3. Design of Noise-Immune Codes of Full-Block Systematization……………………………. 1.6. The Analysis of Structure of LBDS Motionless States and Closed Loops………………………………………………….. 1.6.1. Motionless States of LBDS………………………………. 1.6.2. Closed Loops of LBDS…………………………………… 1.7. LBDS in Tasks of Dividing Noise-Immunity Code Transfor mation………………………………………………………….. 2. NONLINEAR BINARY DYNAMIC SYSTEMS (NBDS) OF DISCRETE AUTOMATION……………………………...... 2.1. The Construction of NBDS Model Representation by Means of Finite-State Machine Logic……………………………………. 2.2. The Construction of Dividing Devices Noise-Immunity Code Transformation by Means of NBDS in the Arbitrary Flip-Flops Logic…………………………………………………………... 2.3. NBDS in Tasks of Noise-Immunity Codes Errors Correction………………………………………………. 2.4. The Dividing Encoding and Decoding Devices of Shortened Cyclical Codes with Switching Structure…………………….. 2.5. Sellers’ Differentiation Approach in Boolean Description Analysis Tasks of NBDS of Discrete Automation ……………. 3. THE HYBRID BINARY DYNAMIC SYSTEMS (HBDS) OF DISCRETE AUTOMATION……………………………...... 3.1. The Problem of Code Space infilling with a Hybrid Binary Dynamic Systems Set………………………………………….. 3.2. The Request Factor of Boolean Variables of Binary Dynamic Systems Description…………………………………………… 3.3. The Use of the Request Factor of State Codes’ Boolean Vari ables of NBDS for EFFICIENT Employment of Noise Immu nity Resource………………………………………………….. 3.4. The Design of Equivalent Linear Vector-Matrix Model Repre sentation of NBDS Based on Boolean Description Variables Aggregation Approach………………………………………… 3.5. The Problem of “Apparatus Space – Time Expense” Exchange in Tasks of Noise-Immunity Code Transformation…………… CONCLUSION…………………………………………………….. APPLICATION D – Transformation and its Properties…………… REFERENCES…………………………………………………….. Subject index………………………………………………………. Remote Control Laboratory. Brief Historical Review……………... ПРИНЯТЫЕ СОКРАЩЕНИЯ И ОБОЗНАЧЕНИЯ АА – абстрактный автомат БП – блок памяти БФ – булева функция ВА – время «аппаратурное»

ВВ – модель «вход-выход»

ВК – время «канальное»

ВМП – векторно-матричное представление ВНН – вектор невязки наблюдения ВПС – векторный показатель сложности ВС – модель «вход-состояние»

ВСВ – векторно-матричное линейное описание «вход состояние-выход»

ГДДС – гибридная двоичная динамическая система ГСА – граф-схема алгоритма ДА – дискретная автоматика ДДС – двоичная динамическая система ДКП – двоичная кодовая последовательность ДКУ – декодирующее устройство ДНУ – двоичное динамическое наблюдающее устройство ДПВ – диаграмма переходов и выхода ДСНФ – дизъюнктивная совершенная нормальная форма ДУПК – дивидендное устройство помехозащитного кодопреоб разования ИВП – источник входной последовательности ИЧК – информационная часть кода КА – конечный автомат КПР – кодовое пространство КС – канал связи КУ – кодирующее устройство ЛДДС – линейная двоичная динамическая система ЛУ – линейное устройство ММ – модулярный многочлен МС – модельная среда НДДС – нелинейная двоичная динамическая система ОПВ – относительная оценка приведенной востребованности ОСВ – оценка степени востребованности ПЗК – помехозащищенный код ПЗКА – помехозащищенный конечный автомат ПНЗК – помехонезащищенный код РКС – регистр канала связи СД – «синдромный» дешифратор СДБФ – аппарат селлерсовского дифференцирования булевых функций УДA – устройство дискретной автоматики УДММ – устройство деления модулярных многочленов УК – устройство коммутации УКК – устройство коррекции кода УПЗК – укороченный помехозащищенный код УС – уравнение Сильвестра УФСК – устройство формирования сигнала коррекции ХММ – характеристический модулярный многочлен ХП – характеристический полином ЦДУ – циклическое декодирующее устройство ЦКУ – циклическое кодирующее устройство ЦПЗК – циклический помехозащищенный код ЧПС – частная производная Селлерса ЭЗ – элемент задержки ЭП – элемент памяти Г – гипотеза;

К – концепция;

ПМ – примечание;

Пр. – пример;

ПС – постулат;

С – следствие;

СВ – свойство;

Т – теорема;

У – утверждение;

– знак завершения доказательства утверждения, решения примера, завершения алгоритма;

– знак завершения формулировки утверждения, определения, приме чания, следствия, свойства, постулата, гипотезы;

A, A i, A j – матрица, i -я строка, j -й столбец матрицы A ;

{ } col i, i = 1, n – столбцовая матричная структура с элементами i в столбце;

D {( • )( k ) } – прямое D-преобразование кодовой последовательности ( • ) над простым полем Галуа;

E{ ( • )} – оператор округления величины ( • ) до ближайшего большего целого;

F ( d ) =D { f ( k ) } – D-образ последовательности f ( k ) ;

f ( k ) =D 1{ f ( d ) } – оригинал D-образа последовательности f ( k ) ;

GF ( p ) = { 0,1, 2,..., p 1}, p N – простое поле Галуа;

() GF p n, p, n N – расширенное поле Галуа;

k – дискретное время ( k = 0,1, 2, ), выраженное в числе тактов дли тельностью t процессов кодопреобразования;

{ } row i, i = 1, n – строчная матричная структура с элементами i в стро ке;

u ( k ) – входная кодовая последовательность ДДС;

x( k ) – вектор исходного состояния ДДС;

x( k + 1) – вектор состояния перехода ДДС;

y ( k ) – выходная кодовая последовательность ДДС;

& – союз «И» предикатов;

– союз «ИЛИ» предикатов.

ВВЕДЕНИЕ Вниманию проблемно ориентированного читателя предлагается монография «Двоичные динамические системы дискретной автомати ки», которая содержит три тематически замкнутых раздела.

Первый раздел, посвященный проблемам анализа и синтеза ли нейных двоичных динамических систем (ЛДДС) дискретной автомати ки (ДА), инструментально строится на результатах процесса алгебраи зации общей теории систем. Алгебраизация методов исследования уст ройств дискретной автоматики (УДА), которые составляют обширный класс динамических систем над конечными простым и расширенным полями Галуа, стала проникать в практику разработчиков этих уст ройств в последней трети XX в. На первом этапе она проявилась в ис пользовании векторно-матричных модельных представлений линейных УДА над конечными полями с основанием (характеристикой) два.

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

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

Возможности автоматных представлений УДА распространяются на реализацию циклических дивидендных кодирующих и декодирую щих устройств в произвольной триггерной логике, а также устройств коррекции искаженных при передаче по двоичным каналам связи ко довых комбинаций с использованием синдромов и квазисиндромов ис кажений. Автоматные представления ДДС обнаруживают свои воз можности и при построении циклических кодирующих и декодирую щих дивидендных устройств укороченных кодов с управляемым цик лом деления путем коммутации структуры устройств оптимальных ко дов. Богатые возможности в теории и практике автоматных описаний обнаруживает аппарат Селлерса дифференцирования булевых функ ций. Эти возможности в монографии используются для контроля кор ректности выбора булевых переменных, оценки их востребованности в процессе функционирования УДА, а также сравнительной оценки «степени нелинейности» и сложности альтернативных реализаций комбинационных схем по числу членов разложения булевых функций в ряд по селлерсовским производным.

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

В монографии указанные проблемы решаются путем редуцирования линейных ДДС и введением избыточности при кодировании состоянии ДДС, синтезируемых в автоматной логике, с целью приданию им по мехозащищенности. Причем последняя задача решается в постановке рационального использования ресурсов помехозащиты, в качестве кри терия которого используется фактор востребованности булевых пере менных кодов состояний на всех наборах переменных. Еще одним эф фективным способом решения проблемы «кодового пространства» на паре НДДС-ЛДДС является обмен аппаратурного пространства на вре менные затраты. Гибридные ДДС образуют достаточно новый класс двоичных динамических систем, разработка теории которых является весьма актуальной.

Авторы отдают себе отчет в том, что предлагаемая вниманию чи тателей монография является скромным вкладом в теорию двоичных динамических систем устройств дискретной автоматики, основы кото рой заложены фундаментальными работами Буля Дж. (Boole G.), К. Шеннона (C.Shannon), Э. Мура (E. Moore), А. Гилла (A. Gill), М. Арбиба (M. Arbib), У. Питерсона (W. Peterson), Ф. Селлерса (F. Sellers), Д. Бохманна (D. Bochmann), Х. Постхофа (C. Posthoff), Р. Хэмминга (R.Hamming), В. М. Глушкова, Ю. Т. Медведева, Р. Г. Фа раджева, С. И. Баранова, В. В. Сапожникова, Вл. В. Сапожникова, В. А. Горбатова, Ю. Л. Сагаловича, А. А. Шалыто, Н. С. Щербакова и многих других зарубежных и отечественных ученых.

Основу монографии составили результаты научных исследований в лаборатории телемеханики кафедры систем управления и информа тики (бывшей кафедры автоматики и телемеханики) университета, проводившихся под руководством доктора технических наук, профес сора А. В. Ушакова. Результаты последних лет авторами получены при разработке теоретических проблем, к решению которых во исполнение региональной комплексной целевой программы «ТЕЛЕМЕХАНИКА – 2000» в инициативном порядке подключилась лаборатория телемеха ники. Монография в предложенном виде содержит в основном резуль таты последних лет, имеющие как научный, так и методико познавательный характер. Последнее позволяет рекомендовать ее спе циалистам в области дискретной автоматики, а также аспирантам спе циальности 05.13.05.- «элементы и устройства вычислительной техни ки и систем управления», студентам старших курсов направления 6519.00- «автоматизация и управление» и специальности 2101.00 «управление и информатика в технических системах».

Замысел монографии возник у авторов в результате постоянных научных контактов и обмена научными идеями, в результате чего ос новной текст монографии авторы написали совместно. В написании параграфов 1.6, 1.7 и 2.4 приняла участие Е.В. Рукуйжа.

Конструктивную критику по существу структуры и содержания монографии просим направлять авторам:

почтовый адрес – 197101, Санкт-Петербург, Кронверкский пр., 49, Санкт-Петербургский государственный уни верситет информационных технологий, меха ника и оптики (СПбГУ ИТМО);

телефон 595-41-28;

электронная почта – amndrey@newmail.ru и ushakov_AV@mail.ru.

1 ЛИНЕЙНЫЕ ДВОИЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ ДИСКРЕТНОЙ АВТОМАТИКИ 1.2. Аппарат передаточных функций в задаче модельного представления линейных двоичных динамических систем Двоичные динамические системы (ДДС), интегрированные в неко торую техническую среду приема, хранения, обработки и передачи двоичной информации, при выполнении конкретных функций решают в основном задачи преобразования кодов, элементы которых принад лежат простому полю Галуа GF ( p ) = {0,1,2,, p 1 }, которое при p = 2 принимает вид GF ( 2 ) = { 0,1} [15, 29, 42, 55]. Преобразуемые ко ды могут быть представлены тремя основными способами: в виде век тора, не параметризованного дискретным временем;

в виде кодовой последовательности (скалярной или векторной), параметризованной дискретным временем, и в виде модулярных многочленов (ММ) [15, 55]. Если процесс преобразования кода, поданного на вход ДДС, в код, наблюдаемый на ее выходе, осуществляется с помощью линейной композиции результатов линейных операций умножения и суммирова ния по модулю два, то такая двоичная динамическая система является линейной (ЛДДС). Если при этом основной результат преобразования кодов с помощью ЛДДС фиксируется на ее выходе и входе, то описа ние функционирования такой ЛДДС может быть задано в классе мо дельных представлений «вход – выход».

Одним из конструктивных средств задания модельного представ ления «вход – выход» над бесконечными и конечными полями являет ся аппарат передаточных функций (матриц). В основе методологии ап парата передаточных функций (матриц) лежит алгебраизация отноше ния «вход – выход», которое для непрерывных систем над бесконеч ным полем осуществляется с помощью преобразования Лапласа, для дискретных систем над бесконечным полем – с помощью Z преобразования, а для дискретных систем над конечным простым по лем Галуа GF ( p ), частным случаем которых при p = 2 являются D-преобразования ЛДДС, – с помощью кодовых последовательностей и модулярных многочленов (см. Приложение).

Передаточная функция, записанная в виде отношения двух поли номов, представляет собой решение графа [46], к которому может быть применено правило Мейсона некасающихся контуров в инверсной по становке. Суть инверсного использования правила Мейсона [25, 46] состоит в воссоздании класса графов с вложенными (касающимися) контурами минимальной размерности, эквивалентных в смысле реше ний этих графов в форме передаточной функции отношения «вход – выход». Построенный класс графов образует множество возможных структурных представлений ЛДДС, которые могут быть положены в основу схемотехнических реализаций двоичных динамических систем, решающих заданную задачу преобразования кодов.

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

Определение 1.1 (О1.1). -мерной двоичной кодовой после довательностью f ( k ) : f ( 0 ), f ( 1), f ( 2 ),, f ( k ), (1.1) будем называть параметризованный дискретным временем k, выра женным в числе k тактов длительностью t, векторный кортеж [29], компоненты которого f ( k ) для k представляют собой мерные векторы, элементы которых принадлежат простому полю Галуа GF ( p ) p =2 = {0,1 }.

Если в (1.1) размерность компонентов равна единице, то последова тельность f ( k ) является скалярной или одномерной.

Кодовая последовательность (1.1) может быть конечной по време ни и периодической, если выполняется равенство f ( k ) = f ( k + T ), (1.2) где T – период периодической последовательности.

D-образом F ( d ) двоичной кодовой по Определение 1.2 (О1.2).

следовательности (1.1) в силу прямого D-преобразования (см. Прило жение) называется сходящаяся бесконечная сумма F ( d ) = D{ f ( k )} = f ( k ) d k. (1.3) k = Введем теперь в рассмотрение передаточные матрицы и функции линейной ДДС.

Определение 1.3 (О1.3). Пусть ЛДДС преобразует r -мерную входную двоичную кодовую последовательность (ДКП) u ( k ) в m мерную выходную ДКП y ( k ), тогда передаточной матрицей ( d ) D-образ Y ( d ) вы этой ЛДДС называется матрица, связывающая ходной ДКП y ( k ) с D-образом U ( d ) входной ДКП u ( k ) при нулевом начальном состоянии ЛДДС в силу соотношения ( d ) = arg {Y ( d ) = ( d ) U ( d ), Y ( d ),U ( d ) fix } (1.4) Введем в рассмотрение ( i, j ) -й сепаратный канал ДДС, который ( ) связывает ее i-й выход Yi ( k ) с j-м входом U j ( k ) i = 1,m;

j = 1,r. То гда ( i, j ) -й сепаратный канал ЛДДС может быть описан передаточной функцией ij ( d ), задаваемой определением.

( i, j ) -го сепа Определение 1.4 (О1.4). Передаточной функцией ратного канала ij ( d ) ЛДДС называется отношение Yi ( d ) – D образа выходной ДКП yi ( k ), наблюдаемой на i-м выходе системы и U j (d) – D-образа входной двоичной кодовой последовательности u j ( k ), поданной на j-й вход линейной ДДС, полученное при нулевом на чальном состоянии ЛДДС:

( d ) = Yi ( d ).

ij (1.5) U j (d) Нетрудно видеть, что ij ( d ) является ( i, j ) -м компонентом пере даточной матрицы ( d ) (1.4). Таким образом становится справедли вым положение следующего утверждения.

Утверждение 1.1 (У1.1). Передаточная матрица ( d ) (1.4) ли нейной ДДС, осуществляющей преобразование r -мерной кодовой по следовательности u ( k ) в m -мерную кодовую последовательность y ( k ), имеющих представление { } { } u ( k ) = col u j ( k ), j = 1,r ;

y ( k ) = col yi ( k ),i = 1,m, (1.6) представляет собой ( m r ) -матрицу, составленную из передаточ ных функций ij ( d ) (1.5) всех ( m r ) ее ( i, j ) -х сепаратных каналов так, что становится справедливым представление [ ] ( d ) = row {col ij ( d );

i = 1,m ;

j = 1,r }. (1.7) Если ЛДДС преобразует скалярную входную кодовую последова тельность u ( k ) в скалярную кодовую последовательность y ( k ) так, что r = m = 1, то передаточная матрица (1.4) ЛДДС вырождается в пе редаточную функцию, задаваемую дивидендным выражением i d i Y ( d ) M ( d ) i = (d)=, 0 = 1, = = (1.8) U (d) N (d) m d j j j = где M ( d ), N ( d ) — модулярные многочлены (ММ) относительно пе ременной d, соответственно степеней и m.

Выделим теперь случай, когда входной и выходной коды задаются в форме модулярных многочленов u ( x ) = u x + u 1 x 1 + + u1 x + u 0, (1.9) y ( x ) = y m x m + y m 1 x m 1 + + y1 x + y0, (1.10) ( ) где и m именуются степенями ММ u ( x ) и y ( x ) ;

u = 1,, ( ) y µ µ = 1, m принадлежат простому полю Галуа GF ( p ) p =2 = {0,1 }, при этом приведение подобных при сложении и умножении модуляр ных многочленов производится по правилам сложения и умножения по модулю p = 2 ( mod p = mod 2 ).

Процесс преобразования входного кода u, задаваемый ММ u ( x ) (1.9) в выходной вектор y, задаваемый модулярным многочленом y ( x ) (1.10), может быть так же описан с помощью передаточной функ ции ( d ) вида (1.8), если будут сконструированы D-образы U ( d ) и Y ( d ) модулярных многочленов u ( x ) и y ( x ) соответственно. D-образ модулярного многочлена зависит от того, каким разрядом вперед орга низована в среде линейных ДДС передача (преобразование) модуляр ных многочленов.

Утверждение 1.2 (У1.2). D-образ модулярного многочлена f ( x ) = f k x k = f n x n + f n1 x n1 + + f1 x + f 0, (1.11) k =n F ( d ) = D{ f ( x )} при его передаче младшим разрядом вперед задается выражением F ( d ) = D{ f ( x )} = f ( x ) x=d = f 0 + f 1 x + + f n1 d n1 + f n d n (1.12) Доказательство утверждения состоит в формировании последова тельности f ( k ) : f 0, f 1,, f n1, f n, (1.13) с последующим применением к (1.13) прямого D-преобразования.

Утверждение 1.3 (У1.3). D-образ модулярного многочлена n f ( x) = fk xk (1.14) k = F ( d ) = D{ f ( x )} при его передаче старшим разрядом вперед задается выражением F ( d ) = D{ f ( x )} = f ( x 1 ) ~ = x 1 = d = f n + f n1d + + f1d n1 + f 0 d n ;

f ( x 1 ) = x n f ( x ) (1.15) ~ Доказательство утверждения строится на формировании последо вательности ~ f ( k ) : f n, f n1,, f 1, f 0, (1.16) с последующим применением к (1.16) прямого D-преобразования.

Заметим, что в современных устройствах дискретной автоматики (УДА) преобразование кодов, заданных с помощью модулярных мно гочленов, осуществляется старшим разрядом вперед.

Отмеченное выше позволяет ввести следующее определение.

Определение 1.5 (О1.5). ЛДДС, осуществляющая преобразование входного кода, заданного с помощью модулярного многочлена u ( x ) (1.9), в выходной код, заданного с помощью модулярного многочлена y ( x ) (1.10), может быть описана передаточной функцией вида (1.8), в которой D-образы Y ( d ) и U ( d ) вычисляются в силу (1.15).

Отдельного рассмотрения требует вопрос конструирования переда точной функции ДДС в случае, если ставится задача синтеза устройст ва умножения или деления модулярных многочленов. В данной поста новке передаточная функция ( d ) ДДС, осуществляющей умножение ММ a ( x ) и b ( x ), будет определяться в силу правила ( d ) = arg { ( a( d ) b( d ) ) & deg ( d ) = = min { deg a( d ),deg b ( d ) }} (1.17) В случае, когда ставится задача конструирования ДДС, осуществ ляющей деление модулярного многочлена a ( x ) и ММ b ( x ) в форме a ( x), то передаточная функция ( d ) ДДС будет иметь вид b ( x) (d)=. (1.18) b( d ) Представленные положения своей целью имеют получение струк турного представления ЛДДС для последующей ее технической реали зации или структурно-функционального анализа. Получить структур ное представление ЛДДС с использованием понятия передаточной функции (матрицы) позволяют положения следующего утверждения.

Утверждение 1.4 (У1.4). Структура модельного представления ЛДДС, описываемой передаточной функцией вида (1.8) с единичным свободным членом знаменателя, может быть построена с использо ванием правила некасающихся контуров метода Мейсона, в соответ ствии с которым она выразится в форме касающихся (вложенных друг в друга) контуров, передаточные функции которых заданы муль типликативной структурой из постоянного коэффициента i и со ответствующей степени i переменной d знаменателя передаточной функции так, что их число не превышает m, а число прямых ветвей от входа к выходу этой реализации определяется числом ненулевых элементов числителя передаточной функции с передаточными функ циями ветвей i d i, число которых не превышает m + 1.

Доказательство утверждения можно найти в литературе по теории графов, например, в [25].

Рисунок 1.1. Представление ЛДДС в каноническом управляемом базисе Рисунок 1.2. Представление ЛДДС в каноническом наблюдаемом базисе Таким образом, положения У1.4 дают два канонически сложившихся модельных представления [25] ЛДДС, описываемых передаточной функцией вида (1.8), приведенных на рисунках 1.1 и 1.2.

Элементы d модельных представлений, показанных на рисунке 1. и 1.2, имеют смысл, который раскрывают положения следующего ут верждения.

Утверждение 1.5 (У1.5). Элемент памяти, передаточная функция ЭП ( d ) которого имеет представление ЭП ( d ) = d, (1.19) является D–триггером.

Доказательство утверждения строится на понятии D–триггера и D-преобразования свойстве для сдвинутой ДКП (см. Приложение). Из теории элементов дискретной автоматики известно, что D–триггер представляет собой элемент памяти (ЭП), реализующий задержку вы ходной y ( k ) ДКП на один такт относительно входной u ( k ) ДКП так, что u ( k ) = y ( k + 1). Если теперь воспользоваться свойством D преобразования для сдвинутой ДКП, то получим:

d 1Y ( d ) = U ( d ), откуда для ЭП ( d ) будем иметь:

Y (d) Y (d) ( d ) = = 1 =d.

U (d) d Y (d) Положения раздела позволяют сформировать следующий алгоритм конструирования передаточной функции и построения структурного представления соответствующей ЛДДС.

Алгоритм 1.1 (А1.1) 0. Классифицировать задачу кодопреобразования: в форме ЛДДС, преобразующей входную последовательность в выходную, или в форме ЛДДС, осуществляющей умножение/деление ММ. Если рассматриваемая задача соответствует первому случаю, то про должить выполнение алгоритма с п.1, если второму – с п.6 алго ритма.

1. Задать преобразуемый (входной) двоичный код в форме двоич ной кодовой последовательности u ( k ) или модулярного много члена u ( x ).

2. Задать выходной двоичный код в форме ДКП y ( k ) или ММ y( x ).

D-образ u( k ) или u( x ).

3. Вычислить U ( d ) Вычислить Y ( d ) D-образ y ( k ) или y ( x ).

4.

5. Сконструировать передаточную функцию ( d ) синтезируемой ЛДДС в форме (1.8) и перейти к выполнению п.7 алгоритма.

6. В случае конструирования ЛДДС, осуществляющую умножение ММ, вычислить ее передаточную функцию ( d ) в силу (1.17).

В случае конструирования ЛДДС, осуществляющую деление ММ, то вычислить ее передаточную функцию ( d ) в силу (1.18).

7. С помощью правила Мейсона некасающихся контуров постро ить структурные представления передаточной функции ( d ) в канонических структурных формах [25].

8. Сравнить реализации по векторному показателю сложности (ВПС) с компонентами, учитывающими число элементов памяти с передаточной функцией ЭП ( d ) = d, число элементов двух входового суммирования по mod 2, число точек ветвления рас пространения сигналов, число ветвей.

9. Принять к реализации одну из структур (с меньшей нормой ВПС). Осуществить схемотехническую реализацию принятой версии ЛДДС.

Пример 1.1 (Пр1.1) В качестве примера рассматривается линейная ДДС, преобразую щая входную единичную последовательность u ( k ) = 1 ( k ) в периодиче скую периода T = 7, обеспечивающую размещение в регистре хране ния информационных разрядов кода Хэмминга (7,4).

0. Выполним п.0 алгоритма 1.1, в соответствии с которым про должим выполнение алгоритма с п.1.

1. Зададим преобразуемый (входной) двоичный код в форме двоичной кодовой последовательности u ( k ) :

u ( k ) = 1( k ) = 1111111 2. В соответствии с расположением информационных разрядов в кодах Хэмминга (7,4) зададим выходной двоичный код в форме ДКП y ( k ) :

y ( k ) = 1110100 1110100 1110100.

D-преобразование 3. Используя прямое (П1.1), вычислим U ( d ) D-образ преобразуемой (входной) кодовой последо вательности u ( k ) в результате чего получим:

U ( d ) =D {u ( k ) } =.

1+ d 4. Аналогично п.3 вычислим Y ( d ) D-образ выходной ДКП y( k ) :

1+ d + d2 + d Y ( d ) =D { y ( k ) } =.

1 + d 5. Сконструируем передаточную функцию синтезируемой ЛДДС в форме (1.8) и перейдем к выполнению п.7 алгорит ма.

Y ( d ) ( 1 + d + d 2 + d 4 )( 1 + d ) 1 + d 3 + d 4 + d (d)= = =.

U(d) 1 + d7 1 + d 7. С помощью правила Мейсона некасающихся контуров по строим структурные представления передаточной функции ( d ) в канонических структурных формах (рисунок 1.3, ри сунок 1.4).

Рисунок 1. Рисунок 1. 8. В соответствии с п.7 алгоритма при выбранной элементной базе технической реализации ДДС выполним сравнение по лученных в п.7 модельных представлений ЛДДС по вектор ному показателю сложности, которое обнаруживает их иден тичность.

Пример 1.2 (Пр1.2) Рассматривается задача конструирования линейной ДДС, осущест вляющей деление произвольной входной ДКП (задаваемой в виде ММ u ( x ) ) на неприводимый многочлен ( x ) = x 3 + x + 1 с учетом передачи ДКП старшим разрядом вперед.

0. Выполним п.0 алгоритма 1.1, в соответствии с которым про должим выполнение алгоритма с п.6.

6. Сконструируем передаточную функцию синтезируемой ЛДДС в форме (1.17) с учетом передачи ДКП старшим раз рядом вперед:

() ( ) ~ f x = x 3 1 + x 2 + x 3 ;

() ~ ( d ) = D{ ( x )} = x 1 1 = 1 + d 2 + d 3 ;

=d x 1 (d)= =.

(d) 1+ d2 + d 7. С помощью правила Мейсона некасающихся контуров по строим структурные представления полученной передаточ ной функции ( d ) в канонических структурных формах (см.

рисунок 1.5, рисунок 1.6):

Рисунок 1. Рисунок 1. 1.3. Векторно-матричное модельное представление линейных двоичных динамических систем, параметризованное дискретным временем Общесистемные тенденции к расширению банка модельных пред ставлений динамических систем над бесконечными и конечными по лями [3, 9, 15, 29] привели разработчиков теории систем к достаточно универсальной модельной среде (МС), которая опирается на триаду «вход–состояние–выход» (ВСВ). Применительно к двоичным динами ческим системам модель ВСВ последних имеет вид ДДС : { u, x, y, k,, } (1.20) где u – r -мерный вектор входной последовательности;

x – n -мерный вектор состояния ДДС;

y – m -мерный вектор выходной последова тельности;

k – счетное множество моментов кодопреобразования, осуществляемого ДДС;

– правило перехода ДДС из исходного со стояния x( k ) в состояние перехода x( k + 1) под действием вектора входной последовательности u ( k ) ;

– правило выхода, описывающее процесс формирования элементов выходной последовательности y ( k ) на переходе из состояния x( k ) под действием u ( k ) или как функции только состояния x( k ).

Введем в рассмотрение следующее определение.

Определение 1.6 (О1.6). Каноническим представлением «вход– со стояние–выход» произвольной двоичной динамической системы (1.20) называется ее представление в виде двух векторных выражений x( k + 1) = [ x( k ), u ( k ) ], (1.21) y ( k ) = [ x( k ), u ( k ) ]. (1.22) Векторное модельное описание ВСВ (1.21), (1.22) произвольной ДДС имеет структурное представление, приведенное на рисунке 1.7.

y( k ) x( k + 1) x( k ) ( x, u ) ( x, u ) Рисунок 1.7. Структурное представление произвольной ДДС На рисунке 1.7 ЭЗ – элемент задержки на один такт кодопреобра зования образует блок памяти (БП);

блоки ( x, u ), ( x, u ) образуют комбинационную схему (КСХ) произвольной ДДС.

Определение 1.7 (О1.7). Если правило перехода ( x, u ) и правило выхода ( x, u ) ДДС (1.21), (1.22) допускают представление в виде композиции линейных операций умножения матрицы на вектор и сум мирования в рамках правил модулярной арифметики по модулю p = так, что (1.21) и (1.22) принимают вид x ( k + 1) = A x ( k ) + B u ( k ), x ( 0 ) ;

(1.23) y ( k ) = C x ( k ) + H u ( k ), (1.24) то такая ДДС называется линейной. В (1.21), (1.22) A – ( n n ) – матрица состояния, B – ( n r ) –матрица входа, C – ( n m ) – матрица выхода, H – ( m r ) –матрица вход-выход ДДС, x ( 0 ) – на чальное состояние ДДС.

Краткости ради представление (1.23), (1.24) ЛДДС будем называть ее ( A, B,C, H ) –матричным представлением.

Линейное векторно-матричное представление (1.23), (1.24) двоич ной динамической системы имеет структурный графический аналог, приведенный на рисунке 1.8. На рисунке 1.8 ЭЗ – элемент задержки, который образует БП ЛДДС, а блоки с матричными коэффициентами передачи B, A,C, H и сумматоры по модулю p = 2 образуют комбина ционную схему линейной ДДС.

x( 0 ) x( k + 1) y( k ) x( k ) u(k) ЭЗ B C A H Рисунок 1.8. Структурное представление векторно-матричной модели (1.23), (1.24) ЛДДС Векторно-матричное представление (ВМП) (1.23), (1.24) линейной ДДС называется рекуррентным, наряду с которым существует и сум марное ВМП ЛДДС. Суммарное векторно-матричное представление линейной ДДС введем с помощью утверждения.

Утверждение 1.6 (У1.6). Суммарное векторно-матричное пред ставление ЛДДС (1.23), (1.24) задается соотношениями k x ( k ) = A k x ( 0 ) + A k 1i B u ( i ), (1.25) i = k y ( k ) = C A x ( 0 ) + CA k 1i B u (i ) + u ( k ) k (1.26) i = Доказательство утверждения строится с использованием рекур рентного соотношения (1.23), которое для первых трех тактов позволя ет записать x ( 1) = A x ( 0 ) + B u ( 0 ) ;

x ( 2 ) = A x ( 1) + B u ( 1) = A 2 x ( 0 ) + AB u ( 0 ) + B u ( 1) ;

x ( 3) = A x ( 2 ) + B u ( 2 ) = A 3 x ( 0 ) + A 2 B u ( 0 ) + AB u ( 1) + B u ( 2 ) ;

Полученная база индукции для любого момента k делает справед ливым представление k x ( k ) = A k x ( 0 ) + A k 1i B u ( i ), (1.27) i = Второе соотношение суммарной ВМП ЛДДС в форме (1.26) получает ся подстановкой (1.27) в (1.24).

Соотношение (1.27) допускает модификацию, обнаруживающую динамическое преимущество моделей ВСВ над моделями «вход выход», коими являются передаточные функции двоичных динамиче ских систем. Модифицированное представление суммарной ДДС зада дим с помощью утверждения.

Утверждение 1.7 (У1.7). Суммарная модель (1.27) процессов по вектору состояния линейной ДДС допускает представление x ( k ) = Ak x ( 0 ) = W y ( k ) U ( k ), (1.28) где [ ] U ( k ) = u T ( k 1),u T ( k 2 ),,u T ( 1),u T ( 0 ) T (1.29) [ ] W y ( k ) = B AB A k 1 B, (1.30) при этом U ( k ) именуется «вектором стратегии» перевода ЛДДС из начального состояния x ( 0 ) в желаемое состояние x ( k ) за k -тактов, а матрица W y ( k ) (1.30) именуется матрицей управляемости линей ной двоичной динамической системы за k -тактов.

Доказательство утверждения строится на представления выраже ния (1.27) в форме x ( k ) + A k x ( 0 ) = B u ( k 1) + AB u ( k 2 ) + A 3 B u ( k 3) + + A k 2 B u ( 1) + A k 1 B u ( 0 ) (1.31) Выражение (1.31) путем введения агрегированных матрицы и вектора в правой части позволяет записать x ( k ) + Ak x ( 0 ) = = [ B AB A k 1 B ] [ u T ( k 1),u T ( k 2 ),,u T ( 1),u T ( 0 ) ] (1.32) T Введение обозначений (1.29), (1.30) приводит (1.32) к виду (1.28).

Представление (1.28) позволяет сформулировать критерий управ ляемости линейной ДДС с индексом управляемости, равным k.

Утверждение 1.8 (У1.8). Для того чтобы линейная ДДС (1.23), (1.24) была полностью управляемой с индексом управляемости [29] равным k, то есть за k тактов линейная двоичная система могла быть переведена из любого начального состояния x ( 0 ) в любое конеч ное состояние необходимо и достаточно, чтобы выполнялось условие rank W y ( k ) = n = dim x. (1.33) Доказательство утверждения строится на том, что выполнение ра венства (1.33) является необходимым условием обратимости матрицы W y ( k ), то есть существование W y1 ( k ). Но если это так, то это условие становится достаточным для вычисления «вектора стратегии» управ ления U ( k ) на основе (1.28), записываемого в форме U ( k ) = W y1 ( k ) ( x ( k ) + A k x ( 0 ) ) (1.34) для любых x ( k ) и x ( 0 ).

Условие полной управляемости с индексом k n = dim x является достаточно жестким, более мягкой формой является условие полной управляемости с индексом n = dim x, которое принимает вид [ ] rank W y ( n ) = rank B AB A n 1 B = n = dim x. (1.35) Соотношение (1.35) является условием полной управляемости, то есть управляемости за n тактов, при этом используется обозначение W y ( n ) = W y, где матрица [ ](1.36) W y = B AB A n1 B именуется матрицей управляемости ЛДДС (1.23), (1.24).

По аналогии с (1.32) может быть сконструировано векторно матричное соотношение, позволяющее по результатам измерений на первых k тактах выходной последовательности y ( k ) и входной после довательности u ( k ) восстановить начальное состояние x( 0 ) линейной ДДС.

Утверждение 1.9 (У1.9). Для того чтобы линейная ДДС (1.23), (1.24) была бы полностью наблюдаемой с индексом наблюдаемости k, то есть чтобы имелась возможность восстановить начальное со стояние x( 0 ) за первые k тактов, необходимо и достаточно, чтобы матрица наблюдаемости W н ( k ) с индексом наблюдаемости k обла дала рангом, равным n = dim x, иначе чтобы выполнялось условие [ ] { rank W н ( n ) = col CA i ;

i = 0,k 1 = [ ] (C A ) ( C A k 1 ) = n = dim x.

TT = C ( C A) 2T (1.37) T Доказательство утверждения строится на формировании измере ний на первых k тактах в силу (1.24) и (1.27) y ( 0) = C x ( 0) + H u ( 0) y ( 1) = C x ( 1) + H u ( 1) = CAx ( 0 ) + CB u ( 0 ) + H u ( 1) y ( 2 ) = C x ( 2 ) + H u ( 2 ) = CA x ( 0 ) + CAB u ( 0 ) + CB u ( 1) + H u ( 2 ) (1.38) y ( k 1) = C x ( k 1) + H u ( k 1) = CA x ( 0 ) + CA B u ( 0 ) + k 1 k + CA k 3 B u ( 1) + + H u ( k 1) Сформируем на основе (1.38) вектор измерения z ( k ) с компонен тами y ( 0) + H u ( 0) y ( 1) + CB u ( 0 ) + H u ( 1) z(k)= y ( 2 ) + CAB u ( 0 ) + CB u ( 1) + H u ( 2 ) (1.39) y ( k 1) + CA B u ( 0 ) + CA B u ( 1) + + H u ( k 1) k 2 k Совместное использование представлений (1.38) и (1.39) позволяет за писать [ ] z ( k ) = col CA i ;

i = 0,k 1 x( 0 ) = W ( k ) x( 0 ). (1.40) н Выполнение условия (1.37) является необходимым для обратимо сти матрицы наблюдаемости с индексом k W н ( k ), а существование матрицы W н1 ( k ) является достаточным для вычисления вектора на чального состояния ЛДДС x( 0 ) в силу (1.40) в форме x( 0 ) = W н1 ( k ) z ( k ).

Нетрудно видеть, что условие (1.37) для матрицы наблюдаемости с индексом k является сильным, более слабым является выполнение этого условия для k = n = dim x, тогда матрица наблюдаемости с индек сом n W н ( n ) называется просто матрицей наблюдаемости ЛДДС (1.23), (1.24) или пары матриц ( A,C ) и обозначается следующим обра зом { } W н =W н ( n ) = col C A i : i = 0,n 1. (1.41) Векторно-матричная модель ВСВ линейной ДДС (1.23), (1.24) позволя ет сконструировать модель «вход-выход» (ВВ) в форме передаточной функции (матрицы), а также в форме рекуррентного уравнения ВВ с матричными коэффициентами.

Утверждение 1.10 (У1.10). Линейная ДДС (1.23), (1.24) может быть описана передаточной функцией (матрицей) ( d ), связываю щей D-образ Y ( d ) выходной последовательности y ( k ) и D-образ U ( d ) входной последовательности u ( k ) в мультипликативной форме Y( d ) =( d )U ( d ) (1.42) где ( d ) задается в виде ( d ) = C ( d 1 I + A) 1 B + H.

(1.43) Доказательство утверждения строится на применении к (1.23), (1.24) прямого D-преобразования, которое дает выражения d 1 x( d ) + d 1 x( 0 ) = Ax( d ) + BU ( d ) (1.44) Y ( d ) = Cx( d ) + HU ( d ) (1.45) Если исключить из (1.44) и (1.45) x( d ) и разрешить их с использовани ем модальной арифметики относительно D-образа Y ( d ), то получим Y ( d ) = {C ( d 1 I + A) 1 B + H }U ( d ) + C ( d 1 I + A) 1d 1 x( 0 ). (1.46) Положив в (1.46) нулевое начальное состояние ЛДДС в форме x( 0 ) 0, запишем для D-образа Y ( d ) выходной последовательности Y ( d ) = {C ( d 1 I + A) 1 B + H }U ( d ). (1.47) Сравнение (1.47) с (1.42) позволяет записать (1.43).

Из выражения (1.43) становится корректным вычисление ij ( d ) – передаточной функции ( i, j ) –сепаратного канала ЛДДС, связывающе го i -й выход yi ( k ) с j -м входом u j ( k ) в виде ij ( d ) = C i ( d 1 I + A) 1 B j + H ij, (1.48) где C i – i -я строка матрицы C, B j – j -й столбец матрицы B и H ij – ( i, j ) -й элемент матрицы H.

С целью дальнейших исследований воспользуемся разложением ( ) Д. К. Фаддеева [25] резольвенты d 1 I + A 1 ЛДДС (1.23), (1.24). Раз ложение построим в силу положений следующего утверждения.

( ) Утверждение 1.11 (У1.11). Резольвента d 1 I + A 1 ЛДДС (1.23), (1.24) может быть представлена в форме [ ( d 1 I + A)1 = ( 1 L0 (d 1 ) + L1 (d 1 ) + L2 (d 1 ) + n 1 n2 n det d I + A) ] + Ln2 (d 1 ) + Ln1, (1.49) ( ) где матричные компоненты L = 1,n 1 определяются в силу ре куррентной процедуры Д. К. Фаддеева [25] L = a I + AL1, = 1,n 1;

L0 = I (1.50) где элементы a, = 1,n суть коэффициенты характеристического полинома ( )( ) () () () n 1 n n det d 1 I + A = d 1 + a1 d 1 + a2 d 1 + + an1 d 1 + an (1.51) Доказательство утверждения строится на последовательном ум ножении слева выражения (1.49) на характеристическую матрицу ( ) d 1 I + A ЛДДС (1.23), (1.24), затем на характеристический полином ( ) det d 1 I + A, записанный в форме (1.51), и приравнивании матрич () ных коэффициентов при скалярных степенях d 1, = 0,n 1 слева и справа. Выполнение указанных действий приводит к (1.49) с матрич ными коэффициентами (1.50).

Утверждение 1.12 (У1.12). Линейная двоичная динамическая сис тема (1.23), (1.24) может быть модельно представлена рекуррент ным уравнением ВВ с матричными коэффициентами, которое имеет вид y(k + n ) + a1 y(k + n 1) + a2 y(k + n 2 ) + + an1 y(k + 1) + an y(k ) = = H u( k + n ) + ( CL0 B + a1 H ) u( k + n 1) + + ( CLn 2 B + an1 H )u ( k + 1) + ( CLn1 B + an H )u ( k ) (1.52) Доказательство утверждения строится на подстановке резольвен ( ) ты d 1 I + A 1, записанной в форме (1.49), с характеристическим по линомом вида (1.50) в выражение (1.47), что позволяет записать d n y(d ) + a1d ( n1 ) y(d ) + a2 d ( n2 ) y(d ) + + an1d 1 y(d ) + an y(d ) = = Hd n u ( d ) + ( CL0 B + a1 H ) d ( n1 )u ( d ) + + ( CLn 2 B + a n 1 H ) d 1 u ( d ) + ( CLn 1 B + a n H ) u ( d ) (1.53) Если теперь к левой и правой частям (1.53) применить обратное D преобразование, памятуя о том, что при нулевых начальных условиях в силу свойств прямого D-преобразования выполняется соотношение D 1 {D [ f ( k + p ) ]} = D 1 {d p F ( d ) }= f ( k + p ) (1.54) то становится понятным переход от (1.53) к (1.52).

Нетрудно видеть, что в структуре доказательств утверждений У1.11 и У1.12 содержится доказательство следующего утверждения.

Утверждение 1.13 (У1.13). Если передаточная функция ( d ) ли нейной ДДС (1.23), (1.24) задана в форме отношения модулярных мно гочленов по положительным степеням переменной d M (d) (d)=. (1.55) D( d) где M ( d ) и D( d ) соответственно степеней deg M ( d ) = m и ( ) deg D( d ) = n, то характеристический полином det d 1 I + A матрицы состояния A ЛДДС с передаточной функцией (1.55) определится вы ражением ( )() ~ det d 1 I + A = D d 1, (1.56) () ~ где D d 1 – модулярный полином по отрицательным степеням пере менной d, вычисляется в силу соотношения () ~ D( d ) = d n D d 1. (1.57) Теперь поставим обратную задачу конструирования ( A, B,C, H ) представления линейной ДДС в форме (1.23), (1.24) по ее передаточной функции ( d ) отношения «вход-выход». Возможности решения по ставленной задачи заложены в параграфе 1.1 структурными представ лениями в виде рисунков 1.1 и 1.2 передаточных функций, а также тем обстоятельством, что элемент памяти с передаточной функцией ЭП ( d ) = d реализует задержку на один такт двоичного кодового пре образования произвольной переменной ( k + 1), наблюдаемой на его входе, в переменную ( k ), наблюдаемую на его выходе. Решение по ставленной задачи представим в виде алгоритма.


Алгоритм 1.2 (А1.2) конструирования ( A, B,C, H ) представления ЛДДС по ее передаточной функции ( d ) 1. Выполнить алгоритм 1.1.

2. Разметить выбранную структурную реализацию передаточной функции ( d ), для чего выходам элементов памяти с переда точной функцией ЭП ( d ) = d в определенном порядке присво ить переменную xi ( k ), а их непосредственным входам – пере менную xi ( k + 1).

3. Из размеченной структурной реализации передаточной функции ( d ) сконструировать матрицы A, B,C и H векторно матричного представления линейной ДДС в форме (1.23), (1.24).

Для приведенных на рисунке 1.1 и рисунке 1.2 структурных реали заций ( d ), заданной в форме отношения двух модулярных много членов (1.55), размеченных переменными состояния xi ( k ) и xi ( k + 1) слева направо (рисунок 1.9) и справа налево (рисунок 1.10) конст руирование матриц A, B,C и H дает для последних представления ~ ~ ~ n n Рисунок 1.9. Представление ЛДДС в каноническом управляемом базисе n 1 2 n Рисунок 1.10. Представление ЛДДС в каноническом наблюдаемом базисе 1) в каноническом управляемом базисе (рисунок 1.9) ~ 0 0 0 n ~ 1 0 0 0 n ~ T ~ = O( n1 ) A = 0 n1, 1 0 0 n2 (1.58) I ( n1 )( n1 ) ~ 0 1 ~ n1 = col { i : i = 1,n}, ~ где ~ n + 0 n [ ] ~ + 0 n1,C = O T B = n1 ( n 1 ) 1, H = [ 0 ], (1.59) + 0 ~ 1 2) в каноническом наблюдаемом базисе (рисунок 1.10) 0 1 0 0 O( n1 ) I ( n1 )( n1 ) 0 0 A=0 0 0 0 =, (1.60) 0 0 0 1 n1 1 2 3 n { } n где = col : i = 1,n, i O B = ( n1 ),C = [ n + 0 n n1 + 0 n1 1 + 0 1 ], H = [ 0 ] (1.61) Пример 1.3 (Пр1.3) Сконструировать ( A, B,C, H ) -представление ЛДДС по ее переда точной функции ( d ), обеспечивающую размещение в регистре хра нения информационных разрядов кода Хэмминга (7,4).

1. Выполним алгоритм 1.1, в результате чего получим переда точную функцию ЛДДС 1+ d3 + d4 + d (d)=.

1 + d и структурные представления, приведенные на рисунке 1.3 и рисунке 1.4.

2. Разметим соответствующим образом структурные реализа ции (см. рисунок 1.11, рисунок 1.12).

x2 (k ) x4 (k ) x7 (k ) x6 (k ) x5 (k ) x3 (k ) x1 (k ) x6 (k + 1) x5 (k + 1) x2 (k + 1) x3 (k + 1) x4 (k + 1) x7 (k + 1) x1 (k + 1) Рисунок 1. x7 (k ) x4 (k ) x2 (k ) x6 (k ) x5 (k ) x3 (k ) x1 (k ) x6 (k + 1) x5 (k + 1) x7 (k + 1) x4 (k + 1) x3 (k + 1) x2 (k + 1) x1 (k + 1) Рисунок 1. 3. По размеченной структурной реализации передаточной функции ( d ) сконструируем матрицы A, B,C и H вектор но-матричного представления линейной ДДС в форме (1.23), (1.24) 1) в каноническом управляемом базисе (рисунок 1.11) O [ ] O6 T, B = I 3,C = O6 1, H = [ 1 ] T A= O6 I 66 O 2) в каноническом наблюдаемом базисе (рисунок 1.12) [ ] O I A = 6 66, B = O6,C = O2 I 3 O2, H = [ 1 ] 1 O 1.4. Проблема редуцирования размерности модельных представлений линейных двоичных динамических систем В параграфах 1.1 и 1.2 рассмотрены возможности модельных пред ставлений линейных двоичных динамических систем в классе отноше ний «вход-выход» в форме передаточных функций (матриц) и рекур рентного уравнения ВВ n -го порядка, а также в классе отношений «вход-состояние-выход» в форме векторно-матричных представлений правил перехода и выхода рекуррентной и суммарной версий. Однако в одном из вариантов модельных представлений ЛДДС пока не затрону та проблема их минимального модельного представления. Тем не ме нее, проблема построения минимальной схемотехнической реализации линейных ДДС ставит задачу редуцирования их первичных модельных представлений. Очевидно, эта задача может быть решена двумя спосо бами. Первый способ опирается на формализм модулярных многочле нов, использующий фактор делимости модулярных многочленов чис лителя и знаменателя передаточной функции [15, 38, 55]. Второй спо соб использует свойства пространств управляемости и наблюдаемости, конструируемых на матричных компонентах модельного ВСВ представления линейных двоичных динамических систем [38].

1.4.1 Редуцирование линейных двоичных динамических систем на основе делимости модулярных многочлена числителя и знаменателя передаточной функции Рассмотрение данного способа редуцирования начнем с исследова ния некоторых основных свойств квадратных ( n n ) -матриц, часть из которых носит общесистемный характер, то есть выполняется для мат рицы над любым полем, а часть имеет силу над простым полем Галуа GF ( p ) при p = 2. Заявленные свойства зададим с помощью утвержде ний.

Утверждение 1.14 (У1.14). (Теорема Гамильтона-Кэли). Произ вольная квадратная ( n n ) -матрица A над простым полем Галуа GF ( p ) при p = 2 обнуляет свой характеристический модулярный мно гочлен (ХММ) так, что выполняется равенство det ( I + A) = a0 A m + a1 A m1 + + am1 A + am I = O (1.62) =A Доказательство утверждения строится по той же схеме, что и над бесконечным полем F = R действительных чисел [12, 13].

Утверждение 1.15 (У1.15). Если характеристический полином матрицы A D( ) = det ( I + A) степени n входит в разложение дву µ j + члена µ + 1, где µ = min µ j : rest = 0, то матрица A det ( I + A) j принадлежит показателю µ в том смысле, что Aµ = I. (1.63) Доказательство утверждения строится на факте делимости без ос татка двучлена µ + 1 на ХММ D( ) = det ( I + A), который позволяет записать µ + 1 = Q( ) det ( I + A) = Q( ) D( ) (1.64) Выражение (1.64) делает справедливым соотношение A µ + I = Q( A) D( A) = Q( A)det ( I + A) = A, (1.65) в котором в силу У1.14 член det ( I + A) = A оказывается равным ну лю, что доказывает справедливость У1.15.

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

Утверждение 1.16 (У1.16). Любой модулярный многочлен f ( x ) над простым полем Галуа GF ( p ) при p = 2 с ненулевым свободным членом, то есть неделящийся без остатка на x, является при некото ром целом числе µ делителем двучлена 1 + x µ, при этом минимальное значение µ называется показателем, которому принадлежит f ( x ).

Доказательство утверждения можно найти в [15].

Нетрудно видеть, что объединение положений У1.15 и У1.16 по зволяет сформулировать утверждение, использование которого дает возможность сформировать простую технологию оценки показателя µ, которому принадлежит ММ f ( x ).

Утверждение 1.17 (У1.17). Если сконструировать некоторую квадратную ( n n ) матрицу P, где n = deg f ( x ) в сопровождающей f ( x ) форме так, что f ( ) = det ( I + P ) = D ( ), (1.66) то оценка { } µ = arg P µ = I (1.67) для случая минимального значения µ представляет собой показатель, которому принадлежит ММ f ( x ).

Доказательство утверждения строится на непосредственном вы числении µ, при котором выполняется равенство P µ = I.

Вернемся к решению проблемы редуцируемости передаточной функции ( d ) = M ( d ) / D( d ) на основе сокращаемости ММ числителя M ( d ) и знаменателя D( d ). Математической основой возможной со кращаемости модулярных многочленов над простым полем Галуа яв ляется основная теорема арифметики [30] о представлении отличного от нуля целого числа произведением степеней простых чисел. Над ко нечным полем GF ( p ) при p = 2 свойствами простого числа обладают неприводимые многочлены. В этой связи весьма важным является сле дующее утверждение.

Утверждение 1.18 (У1.18). Если степень µ бинома x µ + 1 пред ставима в форме µ = 2 n 1, (1.68) где µ и n положительные целые числа, то в разложении бинома x µ + 1 входят все без исключения неприводимые ММ, степени кото рых, начиная с единицы, являются делителями числа n.

Доказательство утверждения можно найти в [15].

Утверждение 1.18 является эффективным инструментом при реду цировании передаточных функций ( d ) линейных ДДС, решающих задачи кодопреобразования, в результате которого на выходе ДДС формируется периодическая последовательность y ( k ) с периодом T. В этом случае в знаменателе передаточной функции ( d ) появляется бином d T + 1, который в силу У1.18 представим произведением не приводимых ММ, что порождает возможность редуцирования ( d ).

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

Утверждение 1.19 (У1.19). Если степень µ бинома x µ + 1 пред ставима в форме µ = 2, где – целое положительное число, то би ном x µ + 1 над простым полем Галуа GF ( 2 ) при p = 2 может быть записан в форме ( ) x µ + 1 = x 2 + 1 = x v + 1. (1.69) Доказательство утверждения сводится к непосредственному вы числению правой части (1.69) с учетом специфики модулярной ариф метики по mod p = mod 2.

Как следствие из У1.19 становится справедливым положение сле дующего утверждения.

Утверждение 1.20 (У1.20). Если степень µ бинома x µ + 1 пред ставима в форме µ = 2, где – целое положительное число, то этот бином над простым полем Галуа GF ( 2 ) при p = 2 может быть запи сан в виде )( ) ( ( ).

1 xµ + 1 = x2 + 1 = x2 + 1 x2 + 1 x2 + 1 (1.70) Доказательство утверждения строится на использовании У1.19, позволяющее записать ( ) ( )( ) 2 2 x µ + 1 = x 2 + 1 = x 2 + 1 x 2 + 1 = x 2 + 1 x 2 + 1. (1.71) 1 Пример 1.4 (Пр1.4) В качестве примера рассматривается линейная ДДС, преобразую щая входную импульсивную последовательность u ( k ) = ( k ) в перио дическую последовательность y ( k ) : 11110000 11110000 периода T = 8.


Следуя А1.4 получим передаточную функцию проектируемой ЛДДС в силу определения Y (d) 1+ d + d 2 + d3 M (d) (d)= = = U (d) D( d ) 1+ d Задачу редуцирования размерности ( d ) решим с использованием делимости модулярных многочленов, то есть полинома наибольшего ( ) общего делителя M ( d ) = 1 + d + d 2 + d 3 и D ( d ) = 1 + d 8 = 1 + d 4.

С этой целью проверим: не принадлежит ли M ( d ) показателю µ = 4.

Следуя У1.17, сформируем матрицу P сопровождающую моду лярный многочлен M ( d ) = 1 + d + d 2 + d 3 так, что 0 1 P = 0 0 1.

1 1 с целью решения задачи µ = arg { P µ = I }, которая в своем решении дает µ = 4.

dµ +1= d4 + Представим полином в форме d 4 + 1 = ( d + 1) M ( d ) и осуществим редуцирование передаточной функции ( d ) с помощью цепочки равенств M(d) M(d) M(d) (d)= = = =.

D( d ) (1 + d )(1 + d ) (1 + d ) M ( d )( 1 + d 4 ) 1+ d + d4 + d 4 Сконструируем структурное представление редуцированной вер сии проектируемой ЛДДС, которое приведено на рисунке 1.13.

Рисунок 1. 1.4.2 Редуцирование линейных двоичных динамических систем на основе анализа структуры пространств управляемости и наблюдаемости ЛДДС Рассмотрим векторно-матричное ВСВ представление ЛДДС x ( k + 1) = A x ( k ) + B u ( k ), x ( 0 );

y ( k ) = C x ( k ) + H u ( k ). (1.72) В предыдущем разделе исследованы вопросы управляемости и наблю даемости ЛДДС, записанной в форме (1.23), (1.24) или (1.72) за n так тов ее функционирования, где n = dim x. В случае неполной управляе мости и наблюдаемости структура пространства ЛДДС (1.72) разбива ется на четыре части, так что вектор состояния линейной ДДС предста вим в форме [ ]T x = xT xT xнун xнунн, T T (1.73) ун унн где x ун – управляемая и наблюдаемая часть вектора состояния x ;

x унн – управляемая, но ненаблюдаемая часть x ;

xнун – неуправляемая, но наблюдаемая часть x ;

xнунн – неуправляемая и ненаблюдаемая часть вектора x. ЛДДС (1.72) с вектором состояния (1.73) структурно пред ставим схемой (рисунок 1.14).

S ун S унн S нун S нунн Рисунок 1.14. Структурная схема ЛДДС (1.72) с вектором состояния (1.73) Структурное представление, приведенное на рисунке 1.14, систе мы, характеризующееся четырьмя перечисленными компонентами век тора состояния, справедливо для систем над бесконечными и конечны ми полями предложено Р. Калманом [29] и носит название «канониче ское представление Р. Калмана». Из приведенного представления вид но, что передаточная функция ( d ), как модель «вход-выход» описы вает только полностью управляемую и полностью наблюдаемую часть ЛДДС. При вычислении передаточной функции ЛДДС (1.72) в силу соотношения ( ) ( d ) = C d 1 I + A 1 B + H (1.74) должно происходить сокращение сомножителей числителя и знамена теля ММ, которые задействованы для описания неуправляемых и не наблюдаемых частей ЛДДС. Таким образом размерность передаточной функции ЛДДС в целом, которая совпадает с передаточной функцией ее полностью управляемой и полностью наблюдаемой части, в ее ми нимизированной после сокращения сомножителей форме определится размерностью пересечения пространства управляемости пары матриц ( A, B ) и пространства наблюдаемости пары матриц ( A,C ). Для вычис ления размерности этого пересечения может быть использован сле дующий алгоритм.

Алгоритм 1.3 (А1.3) ( A, B ) 4. Построить матрицу W y управляемости пары матриц мо дели ЛДДС (1.71) в форме [ ] W y = B A B A 2 B A n1 B. (1.75) 5. Составить матрицу W H наблюдаемости пары матриц ( A,C ) мо дели ЛДДС (1.72) [ ( CA ) ].

( CA ) T ( CA) T 2T n-1 T WH = C T (1.76) L {W y } управляемости 6. Вычислить размерности пространств и {W } с помощью соотношений наблюдаемости T L н = dim L {W }= rank W ;

n = dim L {W }= rank W T (1.77) nу y y Н н н { } 7. Вычислить размерность n уН объединения L {W y } L W H T пространств управляемости и наблюдаемости ЛДДС в силу вы [ ] ражения n = rank W W.

T уН y H 8. Вычислить размерность n уН пересечения пространств управ L { W y } L {WH T } ляемости и наблюдаемости = dim {L {W y } L {W H }}= n у + nН n уН T n уН (1.78) Практика построения редуцированных модельных представлений линейных ДДС показывает, что наилучший результат решения задачи редуцирования имеет место при комбинировании двух рассмотренных подходов. Это комбинирование позволило сконструировать следую щий алгоритм синтеза линейных ДДС редуцированной размерности.

Алгоритм 1.4 (А1.4) 1. Выполнить А1.1, получив передаточную функцию ЛДДС в фор M (d) ме ( d ) =.

D( d) 2. Выполнить А1.2, получив матричные компоненты ( A, B,C, H ) представления ВСВ (1.72).

3. Выполнить А1.3, получив оценку n уН размерности пересече ния пространств управляемости и наблюдаемости.

4. Проанализировать полученное значение n уН, при этом если n уН = n, то перейти к выполнению п.9 алгоритма, иначе – к выполнению п.5.

5. Оценить порядок n p = n уН редуцированной модели ЛДДС и ~ степень ее редуцируемости n = n n.

уН p ~ 6. На множестве ММ степени n p найти такой, который входит в разложение полинома числителя M ( d ) и знаменателя D ( d ) пе редаточной функции ( d ) синтезируемой ЛДДС, с целью кон струирования p ( d ) передаточной функции ЛДДС размерности np.

7. Построить структурное представление передаточной функции p ( d ) в одном из канонических базисов и разметить его пере менными xi ( k ) и xi ( k + 1).

8. Построить векторно-матричное ВСВ-представление редуциро ванной ЛДДС x p ( k + 1) = A p x p ( k ) + B p u ( k ), x p ( 0 );

y( k) = C p xp ( k) + H u( k) (1.79) 9. Построить техническую реализацию редуцированной ЛДДС в схемотехнической версии в соответствии со структурным пред ставлением p ( d ) или в программной версии в соответствии с (1.79).

Пример 1.4 (продолжение) В продолжение примера 1.4 решим задачу редуцирования с исполь зованием оценки n уН размерности пересечения пространств управ ляемости и наблюдаемости исходной ( A, B,C, H ) модели синтезируе мой ЛДДС.

Имеем передаточную функцию устройства Y (d) 1+ d + d2 + d3 M (d) (d)= = =.

U (d) D( d ) 1+ d Выполняем А1.4 с пункта 2.

2. Строим структурное представление передаточной функции уст ройства и размечаем ее. В результате указанных действий полу чаем структурную схему, представленную на рисунке 1.15.

Рисунок 1. По отмеченной схеме рисунок 1.15 конструируем матрицы A, B,C, H :

O71 I T [ ] B = O41, A=, C = O71 I 11, I77 O T I H = [ 1].

3. Выполняем А1.3 с использованием пакета Matlab 6.5. В резуль тате находим n p = n уН = 5.

4. Выполняем п.п.4,5 и находим, что величина уменьшения раз ~ мерности n p оказывается равной трем, то есть n p = 3.

5. Находим общий делитель M ( d ) = 1 + d + d 2 + d 3, что приводит к редуцированной передаточной функции ЛДДС вида p ( d ) = (1 + d + d 4 + d 5 ) 6. Строим структурную схему полученной передаточной функции и осуществляем ее разметку (рисунок 1.13).

7. Строим по размеченной структурной схеме (рисунок 1.13) век торно-матричное ВСВ-представление (1.79) редуцированной ЛДДС, матрицы которой принимают вид I T I [ ] O O21, Bp = O 21, C p = O41 I 11, H = [ I 11 ].

Ap = T I 55 I I 1.5. Концепция подобия в теории линейных двоичных динамических систем Концепция подобия в теории динамических систем над бесконеч ными полями получила в последнее время заметное распространение при решении широкого круга задач управления [5, 35, 40, 48, 53].

В рамках векторно-матричного формализма метода пространства состояний в непараметризованной временем форме концепция подобия сводится к выполнению соотношения = M. (1.80) В параметризованном временем виде соотношение (1.80) достига ется в асимптотике так, что ( ) = M ( ) ( ), (1.81) при этом lim ( ) = 0 ( 0 ), ( 0 ). (1.82) В (1.80) – (1.82) – вектор состояния некоторого эталонного динами ческого процесса, – вектор состояния конструируемой динамической среды, dim = m, dim =, M – ( m ) – матрица в общем случае особого [12] преобразования подобия;

– принимает смысл непрерыв ного времени t ( = t ) в непрерывных по времени процессах и смысл дискретного времени k ( = k ), выраженного в числе интервалов дис кретности длительности t так, что t = k t, в дискретных по времени процессах, – вектор невязки выполнения векторно-матричного подо бия, задаваемого в форме ( ) = M ( );

( 0 ), ( 0 ), (1.83) Если на асимптотически сходящемся процессе (1.82) можно указать такое, что при соотношение (1.83) выполняется «почти точно», то следует называть временем установления векторно-матричного подобия (1.83). В технической среде достижение векторно-матричного подобия (1.83), обеспечиваемого путем выполнения условия (1.82), реализуется в виде связей по вектору состояния и части компонентов вектора состояния так, что математическая модель по вектору не вязки представляет собой автономную систему, которая для непре рывного времени имеет вид &t ) = A ( t );

( 0 ) = M ( ) ( 0 ), ( (1.84) и ( k + 1) = A ( k );

( 0 ) = M ( ) ( 0 ), (1.85) для дискретного времени. Указанные связи должны быть выбраны так, чтобы процессы в (1.84) и (1.85) ( t ) = e A t ( 0 );

( k ) = A k ( 0 ), (1.86) сходились за назначенное время. Для процессов с непрерывным временем матрица A должна быть гурвицевой, для процессов с дис кретным временем матрица A должна иметь собственные значения в единичном круге [5, 48].

К схеме (1.81), (1.84), (1.85) сводится задача регулирования [31] в форме модального управления [48, 53], задача слежения за конечно мерным экзогенным воздействием [5, 48, 31, 52], задача динамического наблюдения [5, 35, 48]. К этой же схеме сводятся задачи адаптивного управления [40]. Для случая единичной матрицы преобразования по добия ( M = I ), когда отношение подобия превращается в отношение тождественного равенства, разработаны методы решения обратных за дач динамики [34].

Следует ожидать, что перенос концепции подобия на динамиче ские системы над конечными полями, частным случаем которых явля ются двоичные динамические системы, заметно обогатит алгоритмиче ское обеспечение синтеза как линейных, так и нелинейных ДДС (ко нечных автоматов). Следует заметить при этом, что обеспечение усло вия вида (1.82) опирается на особые свойства матриц над конечным полем Галуа GF ( p ) при p = 2 [37]. Часть этих свойств представлены в разделе 1.3.1. Этими свойствами являются: свойство обнуления произ вольной квадратной m m -матрицей с элементами из конечного поля Галуа GF ( p ) при p = 2 своего характеристического полинома (Теоре ма Гамильтона-Кэли над конечным полем Галуа GF ( p ) при p = 2 ) в форме (1.62);

свойство принадлежности квадратной m m -матрицы с элементами из конечного поля Галуа GF ( 2 ) показателю µ в форме (1.63).

Для целей дальнейших исследований введем в рассмотрение еще одно свойство матриц над конечным полем Галуа GF ( 2 ).

Свойство 1.1 (СВ1.1). (Нильпотентность индекса матрицы A).

Квадратная (m m ) -матрица A с элементами из GF ( 2 ) обладает свойством нильпотентности индекса, если выполняется условие A = O. (1.87) Утверждение 1.21 (У1.21). Для того чтобы ( m m ) -матрица A с элементами из конечного поля Галуа GF ( 2 ) обладала свойством СВ1.1 достаточно, чтобы матрица A обладала нулевым корнем кратности, при этом ее каноническое представление имело вид O I A = ( 1)(m +1) ( 1)( 1). (1.88) O(m +1)m Доказательство утверждения строится на свойстве матричной функции от матрицы сохранять отношение подобия. Действительно, если существует ( m m ) - неособая матрица М преобразования подо бия такая, что выполняется матричное соотношение A = MA M -1, (1.89) тогда по указанному свойству выполняется и соотношение f ( A) = M f ( A ) M -1. (1.90) Если в качестве f ( A) выбрана функция от матрицы f ( A) = A, то со отношение (1.90) примет вид A = MA M -1, (1.91) но A при = в силу представления (1.88) обнуляется:

A = O, (1.92) что приводит к выполнению (1.87) в силу (1.91).

1.5.1 Концепция подобия в задаче динамического наблюдения состояния произвольной линейной ДДС Пусть линейная ДДС, состояние которой подлежит наблюдению, имеет векторно-матричное описание ( k + 1) = A ( k ) + B u ( k ), ( 0 ) = 0, ( k ) = C ( k ), (1.93) где, u, – соответственно n –мерный вектор состояния, r –мерный вектор входной последовательности и –мерный вектор выходной по следовательности, матрицы A, B,C согласованы по размерности с век торами, u и. Элементы векторов и матриц принадлежат двоично му простому полю Галуа GF ( 2 ).

Двоичное динамическое наблюдающее устройство (ДНУ), исполь зующее всю доступную для непосредственного измерения информа цию об ДДС (1.93) в виде входной последовательности u ( k ) и выход ной – y ( k ), строится в форме z ( k + 1) = z ( k ) + L ( k ) + G u ( k ), z ( 0 ) = z 0, (1.94) где z – m -вектор состояния ДНУ, матрица определяет динамику процесса наблюдения в форме (1.82), а пара матриц ( L,G ) обладает свойствами L = arg { contr (, L ) }, G = arg { contr (,G ) }, (1.95) где contr { ( ),( • )} – предикат наличия полной управляемости пары матриц { ( ),( • )}.

Задачу наблюдения вектора состояния системы (1.93) в среде ДНУ (1.94) сформулируем в форме (1.81), записываемой в виде z ( k ) = T ( k ) + ( k ), k, (1.96) где T – матрица преобразования подобия (в общем случае – особого).

Уравнение (1.96) позволяет построить модель процесса наблюдения по вектору невязки наблюдения, которое принимает вид ( k + 1) = T ( k + 1) + z ( k + 1). (1.97) Структурная модель процесса двоичного динамического наблюде ния в форме (1.97) в соответствии с моделями (1.93) и (1.94) представ лена на рисунке 1.16.

( 0) u ( k) ( k) ( k + 1) = A ( k ) + B u ( k ), ( k ) = C ( k ), ( 0 ) = z ( k + 1) = z ( k ) + L ( k ) + G u ( k ), z ( 0) = z Рисунок 1.16. Модель процесса двоичного динамического наблюдения состояния произвольной ЛДДС Сформулируем теперь утверждение.

Утверждение 1.22 (У1.22). Если матрицы T, L, G удовлетворяют матричным соотношениям T +T A = LC, G =T B, (1.98) то процесс по вектору невязки наблюдения (ВНН) ( k ) описывается рекуррентным векторно-матричным уравнением ( k + 1) = ( k ), ( 0 ) = T ( 0 ) + z ( 0 ). (1.99) Доказательство утверждения строится на подстановке в (1.99) векторно-матричных соотношений (1.93) и (1.94), в результате чего по лучим ( k + 1) = ( k ) + (T A + T + L C ) ( k ) + (T B + G ) ( k ). (1.100) Если в (1.100) подставить (1.98), то приходим к (1.99).

Модель процесса двоичного динамического наблюдения в форме процесса по ВНН (1.99) позволяет сформулировать требования к мат ричным компонентам наблюдаемой ДДС (1.93) и ДНУ (1.94), которые позволят обеспечить все возможные задачи наблюдения.

Так если ставится задача наблюдения вектора ( k ) текущего состояния ДДС (1.93), то следует воспользоваться явным (показатель ным) решением (1.99), записываемым в форме ( k ) = k ( 0 ) ;

( 0 ) = T ( 0 ) + z ( 0 ). (1.101) Следует заметить, что при нормальном использовании ДНУ его со стояние при запуске обнуляется так, что z ( 0 ) = 0. С учетом этого об стоятельства (1.101) принимает вид ( k ) = k T ( 0 ). (1.102) В свою очередь подстановка (1.102) в (1.96) дает z ( k ) = T ( k ) + k ( 0 ). (1.103) Потребуем от матрицы состояния ДНУ обладания свойством нильпотентности с индексом, тогда при k устанавливается ра венство z ( k ) = T ( k ), k. (1.104) Таким образом, вектор z ( k ) состояния ДНУ с точностью до мат рицы преобразования подобия T задает текущее состояние вектора ( k ) наблюдаемой ДДС (1.93). Заметим, что подобие (1.104) можно преобразовать в тождество, если в матричное уравнение Сильвестра (1.98) положить T = I, где I – единичная матрица, и решить уравнение (1.100) относительно матрицы L.

Поставим теперь задачу наблюдения вектора ( 0 ) начального состояния наблюдаемой ДДС (1.93). Для этого потребуем, чтобы матрица принадлежала показателю µ так, что µ = I. В этом слу чае при k = µ соотношение (1.102) примет вид z ( µ ) = T ( µ ) + ( 0 ) = T ( µ ) + T ( 0 ). (1.105) Дополним ситуацию еще одним условием, для чего предположим, что наблюдаемая ДДС (1.93) представляет собой регистр сдвига, функ ционирующий при u ( k ) 0 и ( 0 ) 0. Если учесть, что показатель µ удовлетворяет неравенствам n µ 2n 1, (1.106) то к моменту k = µ (1.105) примет вид z ( µ ) = T ( 0). (1.107) Таким образом (1.107) обнаруживает результат, который не дости гается над бесконечными полями. Если наблюдаемая ДДС (1.93) пред ставляет собой регистр сдвига размерности n с нулевой входной по следовательностью u ( k ) 0 и ненулевым начальным состоянием ( 0 ), а двоичное наблюдающее устройство (1.94) таково, что его мат рица состояния принадлежит показателю µ, то в силу выполнения (1.107) состояние z ( k ) ДНУ при k = µ является синдромом состояния ( 0 ).

Выделим еще одну постановочную версию задачи наблюдения со стояния ДДС (1.93), предположив, что входная последовательность u ( k ) формируется с помощью конечномерной автономной ДДС.

( k + 1) = R ( k );

( 0 ) = 0 ;

( k ) = S ( k ). (1.108) Соотношения (1.108) задают источник входной последовательности (ИВП) u ( k ).

Объединим системные компоненты – наблюдаемая ДДС (1.93), ДНУ (1.94) и ИВП (1.108), – процесса наблюдения, охарактеризовав [ ]T его агрегированным вектором состояния = z T, T, T. Тогда дина мика системы с агрегированным вектором описывается автономной ДДС [ ] ( k + 1) = A ( k ), ( 0 ) = z T ( 0 ), T ( 0 ), T ( 0 ), T (1.109) где матрица A имеет представление LC G S A = 0 A B S. (1.110) 0 0 R ( 0) ( 0) ( k) u ( k) ( k + 1) = R ( k ), ( k + 1) = A ( k ) + B u ( k ), u ( k ) = S ( k ), ( 0) = 0 ( k ) = C ( k ), ( 0 ) = z ( k + 1) = z ( k ) + L ( k ) + G u ( k ), z ( 0) = z Рисунок 1.17. Структурное представление модели (1.109) процесса двоичного динамического наблюдения Агрегированная модель (1.109) с матричным компонентом A (1.110) процесса двоичного динамического наблюдения представлена на рисунке 1.17.

Для системы (1.109) явное решение ( k ) в показательной форме принимает вид ( k ) = A k ( 0). (1.111) С целью покомпонентного вычисления (1.111) сформулируем ут верждение.

Утверждение 1.23 (У1.23). Показательная матричная функция A k матрицы A вида (1.110) представима в форме ( ) k k T + T k T R k + k к = 0 R k +k k, k (1.112) 0 0 R где матрица удовлетворяет матричному уравнению Сильвестра (1.98), а матрица – матричному уравнению Сильвестра R + A = B S. (1.113) Доказательство утверждения осуществляется на замене матрич ных членов LC и B S в представлении (1.108) матрицы A, являю щихся правыми частями уравнений Сильвестра (1.98) и (1.113), на их левые части, а так же подстановке второго матричного соотношения (1.98) в (1.108) так, что становится справедливым матричное равенство G S = TB S. (1.114) После проведенной модернизации представления (1.108) матрицы A осуществляется конструирование базы индукции степеней матрицы A, что приводит к (1.112).

Если теперь в агрегированном векторе выделить векторный компонент z, представляющий собой вектор состояния ДНУ, то в силу (1.111) и (1.112) для него можно записать ( ) ( ) z ( k ) = k z ( 0 ) + k T + T A k ( 0 ) + T R k + A k ( 0 ). (1.115) Выражение (1.115) обнаруживает все богатство решений задач дво ичного динамического наблюдения, рассмотренных выше на основе частных композиций начальных состояний и свойств матричных ком понентов.

Пример 1.5 (Пр1.5) Пусть требуется синтезировать ДНУ для наблюдения вектора со стояния ДДС, A, B,C, H -описание которой имеют вид 0 1 0 H = [ 0].

C = [ 1 1 0 ], A = 0 0 1, B = 0, 1 1 0 С целью решения поставленной задачи в соответствии с (1.103) и (1.104) выберем в качестве модели ДНУ регистр сдвига третьего по рядка, матрица ВМ описания которого будет иметь следующий вид 0 1 = 0 0 1.



Pages:   || 2 | 3 | 4 | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.