Оптимальная синхронизация линейных дискретных систем

• Автор: Богомолов, Алексей Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Саратов
• Количество страниц: 101 с. : ил

ОГЛАВЛЕНИЕ
Введение

Глава 1. Оптимальная синхронизация линейных автоматов

1.1. Определение основных понятий и постановка задачи

1.2. Определение множества синхросостояний

линейного автомата

1.3. Графы переходов обобщенно синхронизируемых

линейных автоматов

1.4. Построение оптимальной обобщенно синхронизирующей последовательности

1.5. Метод ветвей и границ

1.6. Об одной оптимальной синхронизации
линейного автомата
Глава 2. Стабилизация интервальных линейных систем
2.1 .Определение основных понятий и постановка задачи
2.2.Метод решения задачи
2.3. Операции над интервальными матрицами
2.4. Линейное выражение для вычисления
конечного интервального состояния ИЛС
2.5. Условие существования
и оценка длины СтП
2.6. Нахождение СтП фиксированной длины
2.7. Нахождение СтП фиксированной длины
интервальными методами
Заключение
Библиографический список

ВВЕДЕНИЕ
В основе многих современных средств и методов технической диагностики дискретных устройств лежит теория экспериментов с автоматами. Одной из причин, затрудняющих решение задач этой теории, во многих случаях является неопределенность начального, текущего или конечного состояния автомата. Для решения этой проблемы служат синхронизирующие, установочные и диагностические эксперименты с автоматами, построение которых является одним из важнейших направлений теории автоматов. Общая теория экспериментов с автоматами развита в работах Мура Э. [35], Трахтенброта Б.А. [58], Гилла А. [15], Глушкова В.М. [18], Мучника A.A. [36], Яблонского С.В. [65], Богомолова А.М. [5-8], Твердохлебова В.А. [57], Грунского И.С. [5-7], Кудрявцева В.Б. [28], Скобелева В.Г. [47], Спивака М.А. [56] и других авторов.
Первая глава данной диссертационной работы посвящена синхронизации устройств, математической моделью которых служит линейный автомат [12, 14, 16, 59, 60]. Функционирование стационарного линейного автомата над полем GF(р) = {0, 1, .. р-l] (р - простое число), задается уравнением состояний:
s(H-l) = Яв(/)+
где А, В - матрицы над полем GF(p), вектора u(f), s(/) над полем GF(/?) обозначают входной сигнал и состояние JIA в моменты времени / = 0, 1, ... Данное уравнение позволяет вычислить следующее состояние линейного автомата по его текущему состоянию и входному сигналу.
Дискретные устройства, моделируемые линейными и билинейными автоматами, находят широкое применение при создании сигнатурных

анализаторов, при сжатии и кодировании информации, синтезе схем автоматического управления [4, 19, 31, 41]. При этом имеется сравнительно небольшое количество работ по экспериментам с линейными автоматами.
В основном они изучались Сперанским Д.В. [50 - 55], в работах которого было введено понятие обобщенного состояния линейного автомата. Пусть у - некоторое натуральное число, не превосходящее п - размерности векторов состояний линейного автомата. Множество всех векторов размерности п над полем ОБ(р), первые V координат которых совпадают с некоторыми фиксированными значениями из этого поля, называется обобщенным состоянием линейного автомата. Обобщением известного понятия синхронизирующей последовательности послужило понятие обобщенно синхронизирующей последовательности. Входная последовательность автомата называется обобщенно синхронизирующей последовательностью, если после её подачи на вход автомат переходит в одно и то же заключительное обобщенное состояние независимо от своего начального состояния. Каждое из финальных состояний, в которые линейный автомат может быть переведен подачей обобщенно синхронизирующей последовательности, называется обобщенным синхросостоянием. Д.В. Сперанским был получен критерий существования обобщенно синхронизирующей последовательности длины к, заключающийся в выполнении условия
[Л = (о),
где через [А% обозначается матрица, составленная из V первых строк матрицы Ак. Было показано, что при выполнении данного условия все входные последовательности длины к и более являются обобщенно синхронизирующими.

Теорема 1.8. Если для любого входного сигнала и 1Т(и)>0, то для любой ОСП С длины к>кым существует ОСП ит|„ длины переводящая ЛА В ТО Же обобщенное СИНХрОСОСТОЯНИе, ЧТО И С, Причем ЩС'шо) < Щи).
Доказательство. Предположим, что ОСП и(0), ..., и(£-1), где к>ктпереводит ЛА в обобщенное синхросостояние Согласно формуле (1.2) это означает, что
[А к-'В]уи(0) + ... + [й],.и(Ы) = И„.
Учитывая, что в силу условия обобщенной синхронизируемости [А% = [0] для всех к>ктполучаем
[0]+...+ [0] + [Ак^'В]Мк-кть)+ ... +[В]„ч(Ы) = [?]„,
где слагаемые, содержащие А' при Р-кщ-1, равны [0]. Из полученного равенства следует, что ОСП и(£-£тш), ..., и(£-1) длины ктщ переводит ЛА в обобщенное синхросостояние *. При этом, поскольку веса входных сигналов неотрицательны, вес подпоследовательности не превосходит веса содержащей ее последовательности. Что и требовалось доказать.
Таким образом, при условии неотрицательности весовой функции оптимальную ОСП следует искать среди ОСП минимальной длины. В случае же, когда функция отрицательна на некотором входном сигнале п0, поставленная выше задача имеет решение лишь тогда, когда длина искомой ОСП задана заранее, т.е. нужно найти ОСП минимального веса при заданной длине последовательности. Такая задача решается с помощью излагаемых в работе методов как частный случай. В случае же, когда длина входной последовательности не фиксирована, вес ОСП при условии отрицательности весовой функции на некотором входном сигнале является неограниченным.