Эксперименты с линейными автоматами

• Автор: Огнева, Марина Валентиновна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Саратов
• Количество страниц: 92 с.

СОДЕРЖАНИЕ
Введение
1. Обобщенные эксперименты с линейными автоматами
1.1. Основные понятия и определения
1.2. Обобщенные установочные эксперименты с линейными
автоматами
1.3. Обобщенные диагностические эксперименты с линей- 38 ными автоматами
Заключение
2. Эксперименты с сетями из линейных автоматов
2.1. Основные понятия и определения
2.2. Синхронизирующие эксперименты с сетями линейных
автоматов.
2.3. Восстановление входных сигналов лийейного автомата 51 с номерами из заданного множества
2.4. Установочные и диагностические эксперименты с сетя- 53 ми из линейных автоматов
2.5. Распознавание входного слова для сети из линейных ав- 57 томатов
Заключение
3. Эксперименты с билинейными дискретными систе- 64 мами
3.1. Основные понятия и определения
3.2. Синхронизирующие последовательности для билиней- 67 ных систем
3.3. Установочные и диагностические последовательности 73 для билинейных систем

3.4. Билинейные дискретные системы с запаздыванием
Заключение
Список литературы
ВВЕДЕНИЕ
Теория экспериментов с автоматами представляет собой фундамент многих современных методов и средств технической диагностики цифровой аппаратуры. Одной из существенных причин, порождающих сложности при решении упомянутых проблем, является отсутствие, как правило, информации о начальном, промежуточном или конечном состоянии устройства. Для снятия указанной неопределенности и служат так называемые синхронизирующие, установочные и диагностические последовательности, подаваемые при проведении соответствующего эксперимента на входы устройства. В настоящее время теория экспериментов для автоматов общего вида достаточно хорошо развита, и ей посвящен ряд работ. Это работы Мура Э. [26], Гилла А. [11], Глушкова В.М. [14], Яблонского С.В. [46], Богомолова А.М. [2]-[5], Твердохлебова В.А. [40], Грунского И.С. [3]-[4], Кудрявцева В.Б. [23], Скобелева В.Г. [30], Спивака М.А. [39] и др. Полученные результаты позволяют сделать вывод о значительной трудоемкости методов синтеза упомянутых последовательностей. Кроме того, их длины для реальных устройств, описываемых автоматными моделями, очень велики. Вместе с тем, среди реальных устройств существуют такие классы, специфика которых позволяет существенно упростить процедуры синтеза упомянутых последовательностей, причем длины их оказываются значительно короче в сравнении с длинами экспериментов для автоматов общего вида. Так, например, такая ситуация имеет место для устройств, математическими моделями которых являются линейные и билинейные автоматы [8], [10], [12], [44], [45].
Линейные и билинейные автоматы являются математической моделью устройств, широко используемых для кодирования и сжатия информации, в качестве сигнатурных анализаторов, а также при синтезе схем встроенного контроля и систем автоматического управления [1], [15],

Проиллюстрируем теорему 1.2.3 на следующем примере. Рассмотрим ЛА над полем С/Д2), заданный следующими характеристическими матрицами:
‘1 0" 1 0" '0

1 1 0
Обозначим состояния этого ЛА через я, =[0 0]г, =[0 1]г, «3 =[1 0]г,
54 =[1 1]т, его выходные реакции через у, =[0 О]1-, у2 = [о 1]г, Уз =[1 0]г, >4=[1
Пусть /и=, тогда обобщенными состояниями будут являться 5* = [0 х] и У* = [1 х].
Рассмотрим входное слово длины один р = [0 О]7 . Для 2-ЛА это входное слово является обобщенным установочным словом. В самом деле, если наблюдаемая выходная реакция ЛА есть у,, то обобщенное конечное состояние Л А есть у,*, если наблюдаемая выходная реакция у2, то обобщенное конечное состояние - У*, если наблюдаемая выходная реакция у3,
то обобщенное конечное состояние - Уг 5 если наблюдаемая выходная реакция у4, то обобщенное конечное состояние У*. Другие входные слова единичной длины также являются обобщенными установочными словами, что видно из таблицы. В таблице на пересечении г-ой строки и у-го столбца указано состояние автомата, в которое он переходит при подаче соответствующего входного слова при наблюдаемой реакции.