«ДВОИЧНЫЕ ДИНАМИЧЕСКИЕ СИСТЕМЫ ДИСКРЕТНОЙ АВТОМАТИКИ x( k + 1) = [ x( k ), u ( k ) ], y ( k ) = [ x( k ), u ( k ) ] Санкт - Петербург 2005 Редакционно-издательский отдел Санкт-Петербургского государственного университета ...»

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

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

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

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

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

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

2005

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

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

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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

САНКТ - ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

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

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

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

Санкт - Петербург УДК [517.938 + 519.713 /.718]: 621. Мельников А.А., Ушаков А.В. Двоичные динамические системы дискретной автоматики / Под ред. А. В. Ушакова. СПб.: СПбГУ ИТМО, 2005. 220с., ил. 40.

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

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

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

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

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

197101, Санкт-Петербург, Кронверкский пр. 49, Санкт-Петербургский государственный университет информационных технологий, механики и оптики, e-mail: [email protected], [email protected]

СОДЕРЖАНИЕ

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)

1.1. Transfer Function (Matrix) Approach in Problem of LBDS 1.2. Vector-Matrix LBDS Model Representation Parameterized by 1.3. The Problem of Dimension Reduction of LBDS Model Representation……………………………………………………...... 1.3.1. Reduction of Dimension of LBDS by Means of Numerator and Denominator Modular Polynomials of Transfer 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 1.4.1. The Similarity Conception in Systematic Noise-Immune 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 NoiseImmunity 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 1.5.3. Design of Noise-Immune Codes 1.6. The Analysis of Structure of LBDS Motionless States and 1.7. LBDS in Tasks of Dividing Noise-Immunity Code Transformation…………………………………………………………..

2. NONLINEAR BINARY DYNAMIC SYSTEMS (NBDS)

2.1. The Construction of NBDS Model Representation by Means of 2.2. The Construction of Dividing Devices Noise-Immunity Code Transformation by Means of NBDS in the Arbitrary Flip-Flops 2.3. NBDS in Tasks of Noise-Immunity Codes 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)

3.1. The Problem of Code Space infilling with a Hybrid Binary 3.2. The Request Factor of Boolean Variables of Binary Dynamic 3.3. The Use of the Request Factor of State Codes’ Boolean Variables of NBDS for EFFICIENT Employment of Noise Immunity Resource………………………………………………….. 3.4. The Design of Equivalent Linear Vector-Matrix Model Representation of NBDS Based on Boolean Description Variables 3.5. The Problem of “Apparatus Space – Time Expense” Exchange in Tasks of Noise-Immunity Code Transformation…………… CONCLUSION…………………………………………………….. APPLICATION D – Transformation and its Properties…………… 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;

электронная почта – [email protected] и [email protected].

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 являются и модулярных многочленов (см. Приложение).

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

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

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

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

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

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

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

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

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

Утверждение 1.1 (У1.1). Передаточная матрица ( d ) (1.4) линейной ДДС, осуществляющей преобразование r -мерной кодовой последовательности u ( k ) в m -мерную кодовую последовательность y ( k ), имеющих представление представляет собой ( m r ) -матрицу, составленную из передаточных функций ij ( d ) (1.5) всех ( m r ) ее ( i, j ) -х сепаратных каналов так, что становится справедливым представление Если ЛДДС преобразует скалярную входную кодовую последовательность u ( k ) в скалярную кодовую последовательность y ( k ) так, что r = m = 1, то передаточная матрица (1.4) ЛДДС вырождается в передаточную функцию, задаваемую дивидендным выражением где M ( d ), N ( d ) — модулярные многочлены (ММ) относительно переменной d, соответственно степеней и m.

Выделим теперь случай, когда входной и выходной коды задаются в форме модулярных многочленов где и 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 ( d ) = D{ f ( x )} при его передаче младшим разрядом вперед задается выражением Доказательство утверждения состоит в формировании последовательности с последующим применением к (1.13) прямого D-преобразования.

Утверждение 1.3 (У1.3). D-образ модулярного многочлена F ( d ) = D{ f ( x )} при его передаче старшим разрядом вперед задается выражением Доказательство утверждения строится на формировании последовательности с последующим применением к (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 ), будет определяться в силу правила В случае, когда ставится задача конструирования ДДС, осуществляющей деление модулярного многочлена a ( x ) и ММ b ( x ) в форме a ( x), то передаточная функция ( d ) ДДС будет иметь вид b ( x) Представленные положения своей целью имеют получение структурного представления ЛДДС для последующей ее технической реализации или структурно-функционального анализа. Получить структурное представление ЛДДС с использованием понятия передаточной функции (матрицы) позволяют положения следующего утверждения.

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

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

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

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

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

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

откуда для ЭП ( d ) будем иметь:

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

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

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

2. Задать выходной двоичный код в форме ДКП y ( k ) или ММ 3. Вычислить U ( d ) 5. Сконструировать передаточную функцию ( d ) синтезируемой ЛДДС в форме (1.8) и перейти к выполнению п.7 алгоритма.

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

В случае конструирования ЛДДС, осуществляющую деление ММ, то вычислить ее передаточную функцию ( d ) в силу 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 ) :

2. В соответствии с расположением информационных разрядов в кодах Хэмминга (7,4) зададим выходной двоичный код в U ( d ) D-образ преобразуемой (входной) кодовой последовательности u ( k ) в результате чего получим:

4. Аналогично п.3 вычислим Y ( d ) D-образ выходной ДКП 5. Сконструируем передаточную функцию синтезируемой ЛДДС в форме (1.8) и перейдем к выполнению п.7 алгоритма.

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

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

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

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

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

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

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

1.3. Векторно-матричное модельное представление линейных двоичных динамических систем, параметризованное дискретным временем Общесистемные тенденции к расширению банка модельных представлений динамических систем над бесконечными и конечными полями [3, 9, 15, 29] привели разработчиков теории систем к достаточно универсальной модельной среде (МС), которая опирается на триаду «вход–состояние–выход» (ВСВ). Применительно к двоичным динамическим системам модель ВСВ последних имеет вид где 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) называется ее представление в виде двух векторных выражений Векторное модельное описание ВСВ (1.21), (1.22) произвольной ДДС имеет структурное представление, приведенное на рисунке 1.7.

Рисунок 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) принимают вид то такая ДДС называется линейной. В (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 образуют комбинационную схему линейной ДДС.

векторно-матричной модели (1.23), (1.24) ЛДДС Векторно-матричное представление (ВМП) (1.23), (1.24) линейной ДДС называется рекуррентным, наряду с которым существует и суммарное ВМП ЛДДС. Суммарное векторно-матричное представление линейной ДДС введем с помощью утверждения.

Утверждение 1.6 (У1.6). Суммарное векторно-матричное представление ЛДДС (1.23), (1.24) задается соотношениями Доказательство утверждения строится с использованием рекуррентного соотношения (1.23), которое для первых трех тактов позволяет записать Полученная база индукции для любого момента k делает справедливым представление Второе соотношение суммарной ВМП ЛДДС в форме (1.26) получается подстановкой (1.27) в (1.24).

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

Утверждение 1.7 (У1.7). Суммарная модель (1.27) процессов по вектору состояния линейной ДДС допускает представление где при этом U ( k ) именуется «вектором стратегии» перевода ЛДДС из начального состояния x ( 0 ) в желаемое состояние x ( k ) за k -тактов, а матрица W y ( k ) (1.30) именуется матрицей управляемости линейной двоичной динамической системы за k -тактов.

Доказательство утверждения строится на представления выражения (1.27) в форме Выражение (1.31) путем введения агрегированных матрицы и вектора в правой части позволяет записать Введение обозначений (1.29), (1.30) приводит (1.32) к виду (1.28).

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

Утверждение 1.8 (У1.8). Для того чтобы линейная ДДС (1.23), (1.24) была полностью управляемой с индексом управляемости [29] равным k, то есть за k тактов линейная двоичная система могла быть переведена из любого начального состояния x ( 0 ) в любое конечное состояние необходимо и достаточно, чтобы выполнялось условие Доказательство утверждения строится на том, что выполнение равенства (1.33) является необходимым условием обратимости матрицы W y ( k ), то есть существование W y1 ( k ). Но если это так, то это условие становится достаточным для вычисления «вектора стратегии» управления U ( k ) на основе (1.28), записываемого в форме Условие полной управляемости с индексом k < n = dim x является достаточно жестким, более мягкой формой является условие полной управляемости с индексом n = dim x, которое принимает вид Соотношение (1.35) является условием полной управляемости, то есть управляемости за n тактов, при этом используется обозначение W y ( n ) = W y, где матрица именуется матрицей управляемости ЛДДС (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, иначе чтобы выполнялось условие Доказательство утверждения строится на формировании измерений на первых k тактах в силу (1.24) и (1.27) Сформируем на основе (1.38) вектор измерения z ( k ) с компонентами Совместное использование представлений (1.38) и (1.39) позволяет записать Выполнение условия (1.37) является необходимым для обратимости матрицы наблюдаемости с индексом k W н ( k ), а существование матрицы W н1 ( k ) является достаточным для вычисления вектора начального состояния ЛДДС x( 0 ) в силу (1.40) в форме Нетрудно видеть, что условие (1.37) для матрицы наблюдаемости с индексом k является сильным, более слабым является выполнение этого условия для k = n = dim x, тогда матрица наблюдаемости с индексом n W н ( n ) называется просто матрицей наблюдаемости ЛДДС (1.23), (1.24) или пары матриц ( A,C ) и обозначается следующим образом Векторно-матричная модель ВСВ линейной ДДС (1.23), (1.24) позволяет сконструировать модель «вход-выход» (ВВ) в форме передаточной функции (матрицы), а также в форме рекуррентного уравнения ВВ с матричными коэффициентами.

Утверждение 1.10 (У1.10). Линейная ДДС (1.23), (1.24) может быть описана передаточной функцией (матрицей) ( d ), связывающей D-образ Y ( d ) выходной последовательности y ( k ) и D-образ U ( d ) входной последовательности u ( k ) в мультипликативной форме где ( d ) задается в виде Доказательство утверждения строится на применении к (1.23), (1.24) прямого D-преобразования, которое дает выражения Если исключить из (1.44) и (1.45) x( d ) и разрешить их с использованием модальной арифметики относительно D-образа Y ( d ), то получим Положив в (1.46) нулевое начальное состояние ЛДДС в форме x( 0 ) 0, запишем для D-образа Y ( d ) выходной последовательности Сравнение (1.47) с (1.42) позволяет записать (1.43).

Из выражения (1.43) становится корректным вычисление ij ( d ) – передаточной функции ( i, j ) –сепаратного канала ЛДДС, связывающего i -й выход yi ( k ) с j -м входом u j ( k ) в виде где 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) может быть представлена в форме где матричные компоненты L = 1,n 1 определяются в силу рекуррентной процедуры Д. К. Фаддеева [25] где элементы a, = 1,n суть коэффициенты характеристического полинома Доказательство утверждения строится на последовательном умножении слева выражения (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) может быть модельно представлена рекуррентным уравнением ВВ с матричными коэффициентами, которое имеет вид Доказательство утверждения строится на подстановке резольвенты d 1 I + A 1, записанной в форме (1.49), с характеристическим полиномом вида (1.50) в выражение (1.47), что позволяет записать Если теперь к левой и правой частям (1.53) применить обратное Dпреобразование, памятуя о том, что при нулевых начальных условиях в силу свойств прямого D-преобразования выполняется соотношение то становится понятным переход от (1.53) к (1.52).

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

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

конструирования ( A, B,C, H ) представления ЛДДС 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 дает для последних представления 1) в каноническом управляемом базисе (рисунок 1.9) 2) в каноническом наблюдаемом базисе (рисунок 1.10) Пример 1.3 (Пр1.3) Сконструировать ( A, B,C, H ) -представление ЛДДС по ее передаточной функции ( d ), обеспечивающую размещение в регистре хранения информационных разрядов кода Хэмминга (7,4).

1. Выполним алгоритм 1.1, в результате чего получим передаточную функцию ЛДДС и структурные представления, приведенные на рисунке 1.3 и 2. Разметим соответствующим образом структурные реализации (см. рисунок 1.11, рисунок 1.12).

x1 (k + 1) x7 (k + 1) 3. По размеченной структурной реализации передаточной функции ( d ) сконструируем матрицы A, B,C и H векторно-матричного представления линейной ДДС в форме (1.23), (1.24) 1) в каноническом управляемом базисе (рисунок 1.11) 2) в каноническом наблюдаемом базисе (рисунок 1.12) 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 обнуляет свой характеристический модулярный многочлен (ХММ) так, что выполняется равенство Доказательство утверждения строится по той же схеме, что и над бесконечным полем F = R действительных чисел [12, 13].

Утверждение 1.15 (У1.15). Если характеристический полином матрицы A D( ) = det ( I + A) степени n входит в разложение двуj + принадлежит показателю µ в том смысле, что Доказательство утверждения строится на факте делимости без остатка двучлена µ + 1 на ХММ D( ) = det ( I + A), который позволяет записать Выражение (1.64) делает справедливым соотношение в котором в силу У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 ( x ).

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

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

Утверждение 1.18 (У1.18). Если степень µ бинома x µ + 1 представима в форме где µ и 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 может быть записан в форме Доказательство утверждения сводится к непосредственному вычислению правой части (1.69) с учетом специфики модулярной арифметики по mod p = mod 2.

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

Утверждение 1.20 (У1.20). Если степень µ бинома x µ + 1 представима в форме µ = 2, где – целое положительное число, то этот бином над простым полем Галуа GF ( 2 ) при p = 2 может быть записан в виде Доказательство утверждения строится на использовании У1.19, позволяющее записать Пример 1.4 (Пр1.4) В качестве примера рассматривается линейная ДДС, преобразующая входную импульсивную последовательность u ( k ) = ( k ) в периодическую последовательность y ( k ) : 11110000 11110000 периода T = 8.

Следуя А1.4 получим передаточную функцию проектируемой ЛДДС в силу определения Задачу редуцирования размерности ( d ) решим с использованием делимости модулярных многочленов, то есть полинома наибольшего С этой целью проверим: не принадлежит ли M ( d ) показателю µ = 4.

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

d 4 + 1 = ( d + 1) M ( d ) и осуществим редуцирование передаточной функции ( d ) с помощью цепочки равенств Сконструируем структурное представление редуцированной версии проектируемой ЛДДС, которое приведено на рисунке 1.13.

1.4.2 Редуцирование линейных двоичных динамических систем на основе анализа структуры пространств управляемости и наблюдаемости ЛДДС Рассмотрим векторно-матричное ВСВ представление ЛДДС В предыдущем разделе исследованы вопросы управляемости и наблюдаемости ЛДДС, записанной в форме (1.23), (1.24) или (1.72) за n тактов ее функционирования, где n = dim x. В случае неполной управляемости и наблюдаемости структура пространства ЛДДС (1.72) разбивается на четыре части, так что вектор состояния линейной ДДС представим в форме где x ун – управляемая и наблюдаемая часть вектора состояния x ;

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

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

5. Составить матрицу W H наблюдаемости пары матриц ( A,C ) модели ЛДДС (1.72) 7. Вычислить размерность n уН объединения L {W y } L W H пространств управляемости и наблюдаемости ЛДДС в силу выражения n = rank W W.

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

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

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

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

5. Оценить порядок n p = n уН редуцированной модели ЛДДС и 6. На множестве ММ степени n p найти такой, который входит в разложение полинома числителя M ( d ) и знаменателя D ( d ) передаточной функции ( d ) синтезируемой ЛДДС, с целью конструирования p ( d ) передаточной функции ЛДДС размерности 7. Построить структурное представление передаточной функции p ( d ) в одном из канонических базисов и разметить его переменными xi ( k ) и xi ( k + 1).

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

Имеем передаточную функцию устройства Выполняем А1.4 с пункта 2.

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

По отмеченной схеме рисунок 1.15 конструируем матрицы 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, что приводит к редуцированной передаточной функции ЛДДС вида 6. Строим структурную схему полученной передаточной функции и осуществляем ее разметку (рисунок 1.13).

7. Строим по размеченной структурной схеме (рисунок 1.13) векторно-матричное ВСВ-представление (1.79) редуцированной ЛДДС, матрицы которой принимают вид 1.5. Концепция подобия в теории линейных двоичных динамических систем Концепция подобия в теории динамических систем над бесконечными полями получила в последнее время заметное распространение при решении широкого круга задач управления [5, 35, 40, 48, 53].

В рамках векторно-матричного формализма метода пространства состояний в непараметризованной временем форме концепция подобия сводится к выполнению соотношения В параметризованном временем виде соотношение (1.80) достигается в асимптотике так, что при этом В (1.80) – (1.82) – вектор состояния некоторого эталонного динамического процесса, – вектор состояния конструируемой динамической среды, dim = m, dim =, M – ( m ) – матрица в общем случае особого [12] преобразования подобия; – принимает смысл непрерывного времени t ( = t ) в непрерывных по времени процессах и смысл дискретного времени k ( = k ), выраженного в числе интервалов дискретности длительности t так, что t = k t, в дискретных по времени процессах, – вектор невязки выполнения векторно-матричного подобия, задаваемого в форме Если на асимптотически сходящемся процессе (1.82) можно указать такое, что при соотношение (1.83) выполняется «почти точно», то следует называть временем установления векторно-матричного подобия (1.83). В технической среде достижение векторно-матричного подобия (1.83), обеспечиваемого путем выполнения условия (1.82), реализуется в виде связей по вектору состояния и части компонентов вектора состояния так, что математическая модель по вектору невязки представляет собой автономную систему, которая для непрерывного времени имеет вид для дискретного времени. Указанные связи должны быть выбраны так, чтобы процессы в (1.84) и (1.85) сходились за назначенное время. Для процессов с непрерывным временем матрица 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 ) обладает свойством нильпотентности индекса, если выполняется условие Утверждение 1.21 (У1.21). Для того чтобы ( m m ) -матрица A с элементами из конечного поля Галуа GF ( 2 ) обладала свойством СВ1.1 достаточно, чтобы матрица A обладала нулевым корнем кратности, при этом ее каноническое представление имело вид Доказательство утверждения строится на свойстве матричной функции от матрицы сохранять отношение подобия. Действительно, если существует ( m m ) - неособая матрица М преобразования подобия такая, что выполняется матричное соотношение тогда по указанному свойству выполняется и соотношение Если в качестве f ( A) выбрана функция от матрицы f ( A) = A, то соотношение (1.90) примет вид но A при = в силу представления (1.88) обнуляется:

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

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

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

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

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

Рисунок 1.16. Модель процесса двоичного динамического наблюдения Сформулируем теперь утверждение.

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

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

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

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

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

Объединим системные компоненты – наблюдаемая ДДС (1.93), ДНУ (1.94) и ИВП (1.108), – процесса наблюдения, охарактеризовав его агрегированным вектором состояния = z T, T, T. Тогда динамика системы с агрегированным вектором описывается автономной ДДС где матрица A имеет представление Рисунок 1.17. Структурное представление модели (1.109) процесса двоичного динамического наблюдения Агрегированная модель (1.109) с матричным компонентом A (1.110) процесса двоичного динамического наблюдения представлена на рисунке 1.17.

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

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

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

Пример 1.5 (Пр1.5) Пусть требуется синтезировать ДНУ для наблюдения вектора состояния ДДС, A, B,C, H -описание которой имеют вид С целью решения поставленной задачи в соответствии с (1.103) и (1.104) выберем в качестве модели ДНУ регистр сдвига третьего порядка, матрица ВМ описания которого будет иметь следующий вид Решим поставленную задачу в форме z ( k ) = ( k ), k, для чего в силу (1.104) выберем матрицу T в форме T = I. Решение уравнения Сильвестра (1.98) относительно матрицы L и вычисление матрицы G дает В силу (1.104) и того, что матрица имеет индекс нильпотентности, равный трем, то, очевидно, что начиная с момента k 3 вектор состояния z ДНУ должен будет совпасть с вектором состояния исходной ДДС. Покажем это, полагая, что входная последовательность u ( k ) ДДС на первых семи тактах имеет вид u ( k ): 1001010, а начальное состояние ( 0 ) ДДС определяется вектором ( 0 ) = [0 1 1].

Рисунок 1.18. Структурное представление процесса Из таблицы 1.1 видно, что начиная с третьего такта, то есть с выполнением условия k = 3, вектор состояния z синтезированного ДНУ повторяет в форме z ( k ) = ( k ) состояние ( 0 ) наблюдаемой ДДС.С использованием полученных результатов структурно-функциональная схема процесса двоичного динамического наблюдения вектора состояния заданной ДДС примет вид, как показано на рисунке 1.18.

Из таблицы 1.1 видно, что начиная с третьего такта, то есть с выполнением условия k = 3, вектор состояния z синтезированного ДНУ повторяет в форме z ( k ) = ( k ) состояние ( 0 ) наблюдаемой ДДС.С использованием полученных результатов структурно-функциональная схема процесса двоичного динамического наблюдения вектора состояния заданной ДДС примет вид, как показано на рисунке 1.18.

1.5.2 Концепция подобия в задаче декодирования систематических помехозащищенных кодов Задачу декодирования систематических помехозащищенных кодов, подвергшихся воздействию на функциональном и модельном уровнях, зададим следующим образом. Кодирующее устройство (КУ) на выходе которого формируется ( n, k ) -помехозащищенный код y, выводимый в канал связи в виде двоичной кодовой последовательности y ( k ), старшим разрядом вперед, представляется n -разрядным регистром сдвига, начальное состояние которого ( 0 ) представляет собой передаваемую помехозащищенную кодовую посылку. Векторно-матричное модельное представление КУ имеет вид где F – матрица размерности ( n n ) является нильпотентной с индексом нильпотентности равным n так, что = n. Формирователь импульсной помехи, которая в канале связи (КС) искажает передаваемую кодовую посылку y, также представим n -разрядным регистром сдвига, который будем именовать регистром канала связи (РКС). РКС характеризуется нулевой входной последовательностью и вектором начального состояния ( 0 ), который представляет собой n -разрядный вектор помехи, выводимый в КС в виде последовательности ( k ) старшим разрядом вперед. Векторно-матричное описание РКС имеет вид Матрица A совпадает с матрицей F и так же является нильпотентной с индексом нильпотентности = n.

Процесс искажения кодовой последовательности y ( k ), при передаче по КС представим суммированием в простом двоичном поле GF ( 2 ), в результате чего формируется искаженная кодовая комбинация f = y +, в виде кодовой последовательности Процесс декодирования реализуем в форме построения ДНУ, формирующего к моменту k = n состояние z ( n ), которое с точностью до матрицы преобразования подобия представляло бы собой вектор ( 0 ) начального состояния РКС. Векторно-матричное описание ДНУ – декодирующего устройства (ДКУ) принимает вид а структурное представление процесса декодирования – так, как показано на рисунке 1.19.

Рисунок 1.19. Структурное представление двоичного динамического наблюдения начального состояния регистра канала связи Поставленная задача опирается на следующее утверждение.

Утверждение 1.24 (У1.24). Вектор z ( k ) состояния ДКУ, построенного по структуре двоичного наблюдающего устройства для наблюдения векторов x( 0 ) и ( 0 ), задается соотношением где матричные компоненты T и Tx вычисляются как решение матричных уравнений Сильвестра Доказательство утверждения ведется по той же схеме, что и доказательство У1.23. В рассмотрение вводится агрегированный вектор Вектор (1.122) подчиняется рекуррентному векторно-матричному уравнению явное решение которого в показательной форме имеет вид В (1.123) и (1.124) матрицы и k имеют вид Подстановка из (1.125) в (1.124) и выделение из z ( k ) компоk нента z ( k ) приводит к (1.120).

В стандартной постановке задачи декодирования [51] сформированный ДКУ синдром ошибки представляет собой образ вектора начального состояния ( 0 ) РКС, формируемого с помощью матрицы преобразования подобия T. В этой связи выясним при каких условиях и свойствах матричных компонентов соотношения (1.120) последнее вырождается в соотношение вида (1.107), записываемое в форме Решение поставленной задачи получим с использованием положений следующего утверждения.

Утверждение 1.25 (У1.25). Если ДНУ начального состояния ( 0 ) функционирует так, что всегда z ( 0 ) = 0, то есть перед запуском его состояние обнуляется, матрица принадлежит показателю µ = n, матрицы A и F обладают индексом нильпотентности = n, матрица преобразования подобия Tx обладает свойством где G – образующая матрица систематического кода [51], то выполняется соотношение векторно-матричного подобия Доказательство утверждения строится на определениях свойств нильпотентности матрицы и принадлежности матрицы показателю, а так же на использовании условия z ( 0 ) = 0, что приводит (1.120) к виду Напомним, что вектор x( 0 ) формируется из информационной части xи ( 0 ) систематического помехозащищенного кода с помощью образующей матрицы G кода в силу соотношения Если (1.130) подставить в (1.129) и учесть (1.127), то получим (1.128).

Следует заметить, что в силу (1.127) матрица Tx как решение матричного уравнения Сильвестра (1.121) является проверочной матрицей [51] систематического кода.

Пример 1.6 (Пр1.6) В качестве примера рассмотрим аналитику решения в виде (1.130) задачи конструирования декодирующего устройства в форме ДНУ циклического кода с образующим многочленом g ( x ) = x 3 + x + 1.

Сконструируем ДКУ в форме ДНУ и кодирующее устройство в виде модельных представлений «вход-состояние-выход» с матричными компонентами соответственно.

Решение относительно матрицы T матричного уравнения (1.97) дает Следует заметить тождественность результата для вычисленной матрицы T каноническому [51] представлению проверочной матрицы H циклического кода, который в рассматриваемом примере соответствует образующему многочлену g ( x ) = x 3 + x + 1, которая имеет вид Заметим также, что процесс декодирования состоит в вычислении вектора ошибки (применительно к данному примеру – вектору состояния регистра канала связи см. рисунок 1.19) посредством умножения матрицы T T на вектор начального состояния ( 0 ) РКС. Нетрудно видеть, что в силу равенств матриц T и H T, процесс декодирования циклических кодов полностью совпадает с классическим его представлением. Структурная схема процесса декодирования циклического кода с образующим многочленом g ( x ) = x 3 + x + 1 представлена на рисунке 1.20.

xи (0) Рисунок 1.20. Структурное представление процесса декодирования 1.5.3 Концепция подобия в задаче синтеза Решая поставленную задачу, следует отметить, что банк линейных триггеров состоит из D- и T- триггеров при этом так, как передаточная функция элемента памяти (ЭП), выполненного в виде D- триггера, характеризуется передаточной функцией а в виде T- триггера – характеризуется передаточной функцией то векторы состояний ДДС, имеющих D- и T- триггерную реализацию, оказываются связанными отношениями подобия Пусть в результате синтеза ДДС, решающей задачу преобразования входной последовательности u ( k ) в выходную y ( k ), получена Dтриггерная реализация системы, имеющая векторно-матричное представление Требуется, опираясь на условие векторно-матричного подобия (1.133), построить T- триггерную реализацию системы решающую ту же задачу кодопреобразования. Поставленную задачу решим, опираясь на следующие утверждения.

Утверждение 1.26 (У1.26). Матричные компоненты векторноматричных представлений (1.134) и (1.135) ДДС, решающих одну и ту же задачу кодопреобразования входной последовательности u ( k ) в выходную y ( k ), связаны соотношениями Доказательство утверждения строится на использовании (1.133), которое должно выполняться для k, а потому оказывается справедливой запись Подстановка в (1.138) соотношений (1.134) и (1.135) приводит к справедливости (1.136) и первого соотношения в (1.137). Второе соотношение в (1.137) получается после подстановки (1.133) в выражение для выходной последовательности y ( k ) в (1.135).

Утверждение 1.27 (У1.27). Матричное условие подобия (1.136), записанное в форме представимо в виде неоднородного матричного уравнения Сильвестра где dim AD = dim AT, ( AD, LD ) – полностью наблюдаемая пара матриц [4], ( AT, BT ) – полностью управляемая пара матриц, алгебраические спектры собственных значений матриц AD и AT не пересекаются, то есть { AD } { AT } =, размерности матриц BT, LD согласованы в силу соотношения dim BT = dim LD.

Доказательство утверждения строится на представлении матрицы AT в форме где матрица N T допускает представление Выражение (1.142) допускает эквивалентное представление Подстановка (1.143) в (1.140) с учетом (1.141) приводит к (1.139).

Утверждение (У1.27) является основой следующего алгоритма синтеза ДДС в логике T- триггеров.

конструирования двоичных динамических систем 10. Выполнить А1.2, получив представление линейной ДДС в форме 11. Назначить произвольные матрицы AT, BT и LD, удовлетворяющие условиям У1.30.

12. Решить матричное уравнение Сильвестра (1.140) относительно матрицы подобия M и вычислить матрицу M 1.

13. Сконструировать матричные компоненты T-триггерной реализации линейной ДДС (1.138) с помощью соотношений (1.136) и Следует отметить, что так как нелинейные ДДС, именуемые конечными автоматами, имеют линейные аналоги, то, как представляется авторам, концепция подобия может быть распространена и на этот класс ДДС.

Пример 1.7 (Пр1.7) Построить для декодирующего устройства циклического кода с образующим многочленом g ( x ) = x 3 + x + 1 модельное представление ДДС в логике линейных T-триггеров.

1. Выполнение п.1 А1.5 формирует модельное «входсостояние-выход» представление декодирующего устройства с матричными компонентами 2. Назначение произвольных матриц AT, BT и LD, удовлетворяющих условиям У1.27, дает 3. Выполнение п.3 алгоритма, состоящее в решении матричного уравнения Сильвестра (1.138) относительно матрицы подобия M, приводит к матрице 4. С помощью соотношений (1.136) и (1.137) конструирование матричных компонентов T-триггерной реализации ДДС, описываемой матричными компонентами, полученными в п.1 алгоритма, дает матричные компоненты искомого векторно-матричного описания Структурное представление векторно-матричного описания искомой ДДС с полученными компонентами AT, BT,C T имеет вид, как показано на рисунке 1.21.

1.6. Векторно-матричное представление линейного помехозащитного кодопреобразования, непараметризованное дискретным временем.

Методы формирования матриц помехозащищенных кодов Процесс линейного помехозащитного кодопреобразования как в фазе кодирования, так и в фазе декодирования [15, 42, 55, 51] как частный случай линейного кодопреобразования имеет три модельных представления, приведенных в параграфе 1.1. В данном параграфе используется векторно-матричное представление линейного помехозащитного кодопреобразования, непараметризованное дискретным временем, при этом особое внимание обращается на методы формирования образующей и проверочной матриц помехозащищенного кода (ПЗК).

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

На рисунке 1.22: КУ – кодирующее устройство; КС – канал связи, искажение в котором моделируется сумматором по модулю два помехозащищенного кода и кода ошибки; ДКУ – декодирующее устройство, формирующее синдром ошибки; a – вектор-строка исходного помехонезащищенного кода, dim a = k ; y – вектор-строка помехозащищенного ( n, k ) -кода, наблюдаемого на выходе КУ, dim y = n, n > k, m = n k – число вводимых избыточных разрядов кода y ; – вектор-строка помехи, воздействующей на КС, dim = n ; f = y + – вектор-строка искаженного кода, принимаемого из КС; E – вектор-строка синдрома ошибки (искажения) в принятой из КС кодовой комбинации, dim E = m.

Процесс формирования вектор-строки помехозащищенного кода y из вектор-строки помехонезащищенного кода a, осуществляемый в КУ, может быть описан линейным векторно-матричным соотношением где G – ( k n ) -матрица, именуемая образующей матрицей [42, 51] помехозащищенного линейного кода y.

Процесс искажения передаваемой кодовой комбинации y в канале связи под действием помехи такой, что на выходе КС формируется вектор-строка искаженного кода f, может быть представлен операцией суммирования соответствующих вектор-строк.

И, наконец, процесс декодирования, состоящий в формировании вектор-строки синдрома (опознавателя) E из вектор-строки принятого из КС искаженного кода f может быть описан векторно-матричным соотношением где H – ( k n ) -матрица, именуемая проверочной [42, 51] матрицей помехозащищенного кода y.

Заметим, что все операции умножения и суммирования в соотношениях (1.144) – (1.146) и ниже осуществляются по правилам модулярной арифметики с модулем два ( mod 2 ).

Выясним: какими свойствами должна обладать пара матриц ( G, H ) с тем, чтобы она порождала помехозащищенный код?

С этой целью сформулируем утверждение.

Утверждение 1.28 (У1.28). Матрица G, принятая за образующую матрицу, и матрица H, принятая за проверочную матрицу, порождают помехозащищенный код, если они удовлетворяют матричному соотношению Доказательство утверждения строится [42] на использовании соотношений (1.146), (1.145) и (1.144). Если в (1.146) подставить (1.145), в котором учесть (1.144), то получим цепочку равенств Напомним, что декодирующие устройства помехозащищенных кодов, построенные в прямой логике, функционируют так, что при отсутствии ошибки в принятой кодовой комбинации декодирующее устройство формирует нулевой синдром, а в случае наличия ошибок, для обнаружения или исправления которых осуществлено помехозащитное кодирование, ДКУ формирует соответствующий ненулевой синдром.

Таким образом ДКУ реализует соотношение Если теперь в (1.148) положить = 0, то в силу первого из соотношений (1.149) получим векторно-матричное равенство выполняемое при любых вектор-строках исходного кода a, что доказывает справедливость утверждения.

Примечание 1.1 (ПМ1.1). Следует заметить, что характеристическое свойство (1.147) матриц ПЗК не нарушается при перестановке строк образующей матрицы G и столбцов проверочной матрицы H.

При перестановке столбцов матрицы G для сохранения (1.147) необходима согласованная перестановка строк матрицы H.

Нетрудно видеть, что соотношения (1.147) – (1.149) содержат доказательство следующего утверждения.

Утверждение 1.29 (У1.29). Процедура формирования синдрома E имеет два эквивалентных представления (1.145) и Следует заметить, что векторно-матричные представления (1.146) и (1.149) имеют различную нагрузку и среду реализацию. Первое используется в аппаратурной среде, а второе – в аналитической при формировании проверочной матрицы H помехозащищенного кода.

Заметим так же, что доказательство У1.28 делает справедливым положения следующего утверждения.

Утверждение 1.30 (У1.30). Пара матриц ( G, H ) размерности dim G = k n и dim H = n m, удовлетворяющие матричному соотношению (1.147), принятые соответственно за образующую и проверочную матрицы кода, порождают помехозащищенный ( n, k ) -код, характеризующийся корректирующей способностью, определяемой мощностью [ { E} ] множества { E} ненулевых синдромов, задаваемой в силу (1.149) соотношением Поставим теперь задачу конструирования алгоритмов формирования образующей G и проверочной H матриц помехозащищенного кода. Эта задача не инвариантна относительно требований к блоковой систематике формируемого помехозащищенного кода. В связи с этим введем следующие определения.

Определение 1.8 (О1.8). Систематическим помехозащищенным кодом называется код, элементы которого представляют собой комбинации элементов исходного помехонезащищенного кода. При этом ПЗК называется линейным, если эти комбинации строятся на основе линейных бинарных операций модулярной арифметики, и нелинейным, если комбинации строятся на основе нелинейных бинарных операций модулярной арифметики.

Нетрудно видеть, что ПЗК, сформированные в силу правила (1.144), являются систематическими и линейными, при этом вся систематика помехозащищенного линейного кода y заложена в образующей матрице G.

Определение 1.9 (О1.9). Систематический ПЗК называется систематическим помехозащищенным кодом с полной блоковой систематикой, если проверочные разряды кода, вводимые в структуру ПЗК процедурой кодирования, и информационные разряды, образованные исходным помехонезащищенным кодом (ПНЗК) a, представляют собой отдельные монолитные блоки.

Следует заметить, что в современной телекоммуникационной технике, в которой преобладает передача кодов «старшим разрядом вперед», в ПЗК с полной блоковой систематикой исходный ПНЗК образует старшие разряды кода, а блок проверочных разрядов – младшие его разряды.

Определение 1.10 (О1.10). Систематический ПЗК называется кодом с неполной блоковой систематикой, если разряды исходного ПНЗК и проверочные разряды ПЗК перемежаются, не образуя монолитные блоки.

С целью конструирования алгоритмов формирования матриц G и H ПЗК сформулируем дополнительно следующее утверждение.

Утверждение 1.31 (У1.31). Если помехозащищенный код исправляет ошибки кратности = 1, s, то синдром E j ошибки j в разрядах для j -ой их комбинации j = 1,C n равен сумме по модулю два строк H i, i = 1,n проверочной матрицы H однократных ошибок, сумма которых образует данную ошибку j.

Доказательство утверждения строится на использовании соотношения (1.149), в котором вектор-строку синдрома E, вектор-строку ошибки следует писать в поэлементной форме а проверочную матрицу H записать в столбцовой форме где H i – i -я строка матрицы H. Подстановка компонентов соотношения (1.149), представленных в форме (1.153), (1.154), в соотношение (1.152) доказывает справедливость утверждения.

Примечание 1.2 (ПМ1.2). Нетрудно видеть, что если при кодировке векторов ошибок векторами-синдромами E при построении ПЗК, исправляющего ошибки кратности s > 1 или обнаруживающего ошибки кратности r > 2, учтены условия У1.31, то достаточно иметь таблицу кодировок ошибок только первой кратности. Ниже при построении алгоритмов формирования матриц G и H кода предполагается, что условия У1.31 выполняются.

Утверждение 1.32 (У1.32). Столбцы H, = 1,m матрицы H принадлежат ядру матрицы G так, что выполняются соотношения в свою очередь столбцы G T, j = 1,k транспонированной G T образуюj щей матрицы принадлежат ядру транспонированной H T проверочной матрицы кода так, что выполняются соотношения Доказательство утверждения строится на представлении матричного соотношения (1.147) в векторно-матричной форме с использованием правых вектор-столбцов что позволяет записать в свою очередь матричное соотношение (1.147) в транспонированной форме по аналогии с (1.157) может быть записано в виде что позволяет записать Утверждение 1.33 (У1.33). Матрицы G и H, сформированные в виде где I k – k k -единичная матрица, I m – m m -единичная матрица, G – k m -матрица синдромов однократных ошибок вида где – k -мерный вектор-строка, содержащий одну единицу, Om – m -мерная нулевая вектор-строка, порождают помехозащищенный код, обладающий полной блоковой систематикой.

Доказательство утверждения в первой части состоит в непосредственной подстановке матриц G и H вида (1.158) в (1.147), которая приводит к Доказательство второй части утверждения строится на подстановке матрицы G вида (1.158) в (1.144) что обнаруживает полную блоковую систематику ПЗК y.

Алгоритмы формирования матриц G и H ПЗК различаются последовательностью этой процедуры. Сначала рассмотрим процедуры формирования матриц помехозащищенного кода, в которых сперва конструируется проверочная матрица H, а затем на основе сформулированных утверждений вычисляется образующая матрица G ПЗК.

Вторую группу алгоритмов составляют процедуры, в которые на первом этапе формируется матрица G кода, а затем формируется проверочная матрица H ПЗК.

1.6.1 Формирование матриц ПЗК с помощью проверочных равенств при декодировании и кодировании Процедура формирования матриц H и G ПЗК, основанная на использовании проверочных равенств при декодировании и кодировании, инвариантна относительно требований к блоковой систематике кода.

По существу уровень блоковой систематики в структуре проверочной матрицы H кода закладывается в силу (1.146) и У1.31 на первом шаге процедуры, состоящем в кодировке векторов-строк ошибок j векторами-строками синдромов E j. Следует заметить, что на этапе кодировок ошибок j синдромами E j может быть так же заложен [42, 51] способ технической реализации исправления ошибки(ок) в принятой кодовой комбинации. Так кодировкой ошибок j синдромами E j по схеме Р. Хэмминга [42, 51] закладывается возможность технической реализации исправления однократных ошибок с использованием стандартных дешифраторов [27, 51].

формирования матриц ПЗК с помощью проверочных равенств 14. Составить таблицу кодировок векторов-строк однократных ошибок j векторами-строками синдромов E j, начиная с ошибки в старшем разряде n = [ 1 On1 ] и заканчивая ошибкой в младшем разряде 1 = [ On1 1], где On1 – ( n 1) -мерная нулевая вектор-строка, так, что E j удовлетворяют условиям У1.31 и принятым техническим соображениям относительно процедуры коррекции искаженного кода.

15. Сформировать проверочную матрицу H на основании составленной таблицы кодировок и соотношения (1.151), которая построчно должна удовлетворять условию 16. На основании составленной проверочной матрицы H кода и соотношения (1.146), описывающего процесс формирования синдрома в аппаратурной среде ДКУ, составить аналитические выражения для каждого разряда E, = m, 1 синдрома как функции 17. Сформировать аналитические выражения для помехозащитного кодирования помехонезащищенного кода a = row ai, i = k,1, для чего записать соотношения (1.162) в предположении, что в КС отсутствует помеха ( = 0 ), положив, тем самым, справедливость выполнения условий порождающих систему равенств допускающих явное разрешение относительно разрядов y j ПЗК как функций разрядов ai помехонезащищенного кода в форме 18. Сформировать образующую матрицу G = row G j, j = 1,n на основании соотношения (1.144) в силу условия в котором известны вектор-строка помехонезащищенного кода a, а также линейная связь y j и ai в форме (1.165).

1.6.2 Формирование матриц ПЗК с использованием матричного уравнения Сильвестра На возможность использования матричного уравнения Сильвестра для формирования проверочной матрицы циклического помехозащищенного кода (ЦПЗК) указано в параграфе 1.4. Эти возможности в систематизированном виде являются основой алгоритма 1.7 формирования указанной матрицы ЦПЗК.

формирования проверочной матрицы ЦПЗК на основе использования матричного уравнения Сильвестра 1. Сформировать k -разрядный ПНЗК на основе мощности [ Q] = N и заданного массива Q передаваемой или хранимой информации так, что 2. Сформировать число m проверочных разрядов, удовлетворяющих требованием к достоверности передачи или хранения информации и к способу реализации корректирующей способности синтезируемого ПЗК.

3. Выбрать неприводимый модулярный многочлен g ( ) степени deg g ( ) = m, удовлетворяющий всем требованиям к корректирующей способности кода [28, 42, 51].

4. Задать m m -матрицу в произвольном базисе так, чтобы она обладала характеристическим полиномом g ( ).

5. Выбрать матрицу L размерности m 1, образующую с матрицей полностью управляемую пару (, L).

6. Задать матрицу A размерности n n, где n = k + m, с индексом нильпотентности равным = n в канонической Жордановой 7. Выбрать матрицу P размерности 1 n, образующую с матрицей A полностью наблюдаемую пару ( A, P ) матриц.

8. Найти решение матричного уравнения Сильвестра относительно матрицы T.

9. Сформировать проверочную матрицу H помехозащищенного Примечание 1.3 (ПМ.1.3). Множество формируемых матриц H с помощью приведенного алгоритма (А1.7) может быть существенно расширено, если в матрицах L и P допустить отличное от единицы соответственно число столбцов и строк, но при этом они всякий раз должны быть согласованы с тем, чтобы существовало их произведение L P.

1.6.3 Использование сингулярного разложения матриц Рассмотрим теперь алгоритм конструирования образующей матрицы G ПЗК по известной проверочной матрице H, который основан на положениях У1.32 и использующий возможности сингулярного разложения (SVD-процедуры) матриц [12, 16]. С этой целью сделаем некоторые пояснения.

Определение 1.11 (О1.11). Сингулярным разложением [12, 16] µ матрицы N над произвольным полем называется ее представление в форме где U – -матрица левого сингулярного базиса, V – µ µ -матрица правого сингулярного базиса, обладающие свойством над этим полем – µ -квазидиагональная матрица сингулярных чисел, размещаемых на главной диагонали, при этом их число равно min {, µ }.

Если с помощью (1.172) сконструировать матрицы NN T и N T N, то в силу (1.173 получим при этом оказывается, что сингулярные числа совпадают с арифметическими значениями корней из собственных значений матриц NN T и N T N. Элементы левого сингулярного базиса U являются нормированными собственными векторами матрицы NN T, а элементы правого сингулярного базиса V являются нормированными собственными векторами матрицы N T N.