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

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

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


Pages:     | 1 || 3 | 4 |   ...   | 5 |

«Государственный экономико-технологический университет транспорта Кафедра «Автоматизация и компьютерно-интегрованные технологий ...»

-- [ Страница 2 ] --

2: Q YII – функция выходов типа 2, реализующая отобра жение D Q в YII. Другими словами, функция 2: некото рым парам „состояние – состояние” (а(t), а()), которые равны друг другу а(t)= а(), ставит в соответствие выходной сигнал автомата у(Т)= 2(а(t), а()), где у YII;

3: Q E YIII – функция выходов типа 3, реализующая ото бражение D Q Е в YIII. Другими словами, функция 3:

некоторым парам „состояние – сохраняющий входной сиг нал” (а(), е()) ставит в соответствие выходной сигнал ав томата у()= 3(а(), е()), где у YIII;

Абстрактные автоматы М представляют собою объединение ав томатов 1-го, 2-го и 3-го рода, функционируют в автоматное непре рывное время Тi, которое состоит из двух отрезков ti и i (Тi= ti+i), описанных ранее.

В каждый момент i автомат способен воспринимать входной е() сохраняющий сигнал – произвольную букву входного сохраняющего алфавита Е и находится в определенном состоянии а() подмножест ва j из множества Q (j Q) состояний автомата, причем в начальный момент времени =0 инициальный автомат всегда находится в своем начальном состоянии а0, то есть а(0)=а0.

В каждый момент ti автомат 1-го рода способен воспринимать входной х(t) информационный сигнал – произвольную букву входного информационного алфавита Х и осуществлять переход в новое со стояние а(t), которое принадлежит определенному подмножеству со стояний j, сохраняющегося при входном сигнале еj() и входящего во множество состояний Q (j Q), а также выдавать соответствующий выходной сигнал у1(t) – некоторую букву выходного алфавита YI.

Закон функционирования абстрактного автомата в автоматном непрерывном времени в случае автомата 1-го рода задается уравне ниями:

a(t ) (a( 1), x(t ));

a() e (a(t ), e());

(2.15) y1 (t ) 1 (a( 1), x(t )), L a(t ), a() ;

i 0, 1, 2,...;

0, 1, 2,....

j В каждый момент ti автомат 2-го рода способен воспринимать входной х(t) информационный сигнал – произвольную букву входного информационного алфавита Х и осуществлять переход в новое со стояние а(t), которое принадлежит определенному подмножеству со стояний j, сохраняющегося при входном сигнале еj() и входящего во множество состояний Q (j Q), а также выдавать соответствующий выходной сигнал у2(Т) – некоторую букву выходного алфавита YII.

Закон функционирования абстрактного автомата в автоматном непрерывном времени в случае автомата 2-го рода задается уравне ниями:

a(t ) (a( 1), x(t ));

a() e (a(t ), e());

(2.16) y L (T ) 2 (a(t ), a()), a(t ), a() ;

i 0, 1, 2,...;

0, 1, 2,....

j В каждый момент ti автомат 3-го рода способен воспринимать входной х(t) информационный сигнал – произвольную букву входного информационного алфавита Х и осуществлять переход в новое со стояние а(t), а также способен воспринимать сохраняющийся входной сигнал еj()– произвольную букву входного сохраняющего алфавита Е и осуществлять в каждый момент i переход в новое состояние а() входящего в подмножество µi множество состояний Q (µi Q), а так же выдавать соответствующий выходной сигнал у3() – некоторую бу кву выходного алфавита YIII.

Закон функционирования абстрактного автомата в автоматном непрерывном времени в случае автомата 3-го рода задается уравне ниями:

a(t ) (a( 1), x(t ));

a() y (a(t ), e());

(2.17) y L () 3 (a(), e()), a(t ), a() ;

i 0, 1, 2,...;

0, 1, 2,....

j j Установлением законов функционирования абстрактных автома тов 1-го, 2-го и 3-го рода обобщенного абстрактного автомата М за канчивается определение абстрактного автомата.

Смысл понятия абстрактного автомата 1-го рода состоит в реали зации некоторого отображения 1 последовательного множества эле ментарных р слов, состоящих из букв входного информационного ал фавита Х и букв входного сохраняющего алфавита Е, в множество слов выходного алфавита YI.

Каждое элементарное входное слово р (р=х, е), последовательно подается на вход данного абстрактного автомата М, установленного предварительно в начальное состояние. В момент такта t под воздей ствием входной х(t) буквы входного информационного алфавита Х ав томат М способен перейти в новое состояние подмножества состоя ний j, сохраняющегося при входной букве еj() входного сохраняю щего алфавита Е автомат М, и входящего в множество состояний Q (j Q), а также выдавать соответствующий выходной сигнал у (t) – не которую букву выходного алфавита YI.

Смысл понятия абстрактного автомата 2-го рода состоит в реали зации некоторого отображения 2 последовательного множества эле ментарных р слов, состоящих из букв входного информационного ал фавита Х и букв входного сохраняющего алфавита Е, а также выда вать соответствующий выходной сигнал у2(Т) – некоторую букву вы ходного алфавита YII.

Смысл понятия абстрактного автомата 3-го рода состоит в реали зации некоторого отображения 3 последовательного множества эле ментарных р слов, состоящих из букв входного информационного ал фавита Х и букв входного сохраняющего алфавита Е, в множество слов выходного алфавита YIII.

В момент такта t под воздействием входной х(t) буквы входного информационного алфавита Х автомат М способен перейти в новое состояние аi подмножества состояний i, а потом перейти в новое со стояние аk подмножества состояний j при входной букве еj() входно го сохраняющего алфавита Е автомат М, и входящего во множество состояний Q (i Q), а также выдавать соответствующий выходной сигнал у3() – некоторую букву выходного алфавита YIII.

Возникающие таким образом конечные последовательности входных элементарных слов р(Т) = х(t), е() на основании законов функционирования автомата в автоматном непрерывном времени Т вызывают соответственно определенные конечные последовательно сти qi= i(p) выходных букв из соответствующих входных алфавитов YI, YII, YIII. Эту последовательность qi называют выходным словом ав томата 1-го, 2-го или 3-го рода обобщенного автомата М.

Таким образом, отнесся каждой последовательности входных элементарных слов р соответствующую ему последовательность вы ходного слова qi, получаем искомое отображение i, которое называ ют отображением, индуцированным абстрактным автоматом М, кото рый в состоянии работать как автомат 1-го, 2-го и 3-го рода.

Х Y А Y Y Е Рис. 2.6. Структурная схема абстрактного М-автомата А Абстрактный М-автомат А, который описывается вектором (2.14), имеет два входа Х и Е и три выхода Y1, Y2, Y3 (рис. 2.6). Функциониро вание автомата исследуется в автоматном непрерывном времени Т [64;

70].

Абстрактный автомат, описывающий реальное компьютерное устройство, должен удовлетворять элементарным требованиям на дежности, устойчивости состояний и выходных символов (слов).

Здесь следует отступить от сугубо абстрактного понятия символов входного алфавита и учитывать, что на входные каналы (узлы) реаль ного устройства поступают устанавливающие и сохраняющие сигна лы вполне определенной длительности. Под действием какого-либо устанавливающего входного сигнала x(t) устройство переходит во вполне определенное состояние а(t) и должно оставаться в нем, пока не закончится действие этого входного сигнала. На уровне абстракт ной модели это означает, что если при поступлении входного сигнала x(t) автомат перешел в состояние а(t), то он должен оставаться в нем, пока сохраняется длительность входного сигнала x(t) (многократное воздействие символа x за период времени t в состоянии а). В период воздействия сохраняющего входного сигнала e() состояние а(t) со храняется (а(t) = а()) в автоматах 1-го и 2-го рода или осуществляет ся укрупненный переход в новое состояние а(), то есть состояние а(t) а(), в автоматах 3-го рода. Выполнение этого условия необходимо также для ориентации на определенную реализацию автомата в зада ваемом элементном базисе [64].

Для правильной (функционально надежной) работы автомата А нельзя позволять, чтобы на входные узлы схемы памяти поступали сигналы, которые брали участие в создании выходных сигналов и по цепи обратной связи подавались бы в тот же самый момент t на вход ные узлы тех же самых схем памяти. В связи с этим в памяти автомата целесообразно использовать задержки для появления входных сигна лов обратной связи в следующий момент времени t+1. Примером ис пользования линии задержки в схемах памяти могут быть двухсту пенчатые регистры, использующие в качестве задержки вторую сту пень памяти. Каждая ступень в регистре тактируются синхроимпуль сами i (i=1, 2) только одной серии, или отдельные группы схем памя ти, каждая из которых имеет устанавливающие х(t) входные сигналы, которые тактируются синхроимпульсами i (i=1, 2) только одной се рии. При использовании нескольких групп схем памяти для создания обратных связей можно использовать выходные сигналы других групп, которые в данный момент t имеют устойчивые выходные сиг налы.

Таким образом, структурная схема многофункционального автомата М состоит из схемы автоматной памяти (регистра) и пяти комбинационных схем. Она представлена комбинационной схемой функций возбуждения памяти первой ступени регистра, сохраняющей комбинационной схемой памяти первой ступени регистра, комбина ционной схемой выходов типа 1, символизирующие автомат 1-го ро да, комбинационной схемой выходов типа 2, символизирующие авто мат 2-го рода, и комбинационной схемой выходов типа 3, символизи рующие автомат 3-го рода. Структурная схема многофункционально го автомата М представлена на рис. 2.7.

у1(t) у2(Т) у3() комбинацион- комбинацион- комбинацион ная схема ная схема ная схема выходов выходов выходов типа 1 типа 2 типа РЕГИСТР комбинационная схема функций возбуждения комбинационная схема сохране ния состояний х(t) е() Рис. 2.7. Состав структурной схемы абстрактного многофункцио нального М-автомата 2.5. Понятие об абстрактных автоматах, с перестраиваемой структурой запоминания состояний Многофункциональные автоматы на схемах автоматной памяти имеют возможность с помощью автомата настройки U выполнять комутацию функций возбуждения и выходов, как это осуществлялось при реализации в автоматах с памятью на триггерах, а также с помощью g-ступенчатого автомата А, имеющего (g-1) автомат стратегии АМ, который генерирует сохраняющие е() входные сигна лы для абстрактного М-автомата А и выполняет перестройку (регене рацию) функций сохранения состояний многофункциональной памяти автомата Ау, что является новым в теории иерархических, многофунк циональных автоматов.

Обобщенную структурную схему многофункционального автомата А на схемах автоматной памяти, которые составляют регистр Rg на схемах автоматной памяти, комбинованные схемы (КС), автомата настройки U и (g-1)-ступенчатого автомата стратегии АМ иллюстририрует рис. 2.8.

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

БА (базовые автоматы типа И-НЕ, ИЛИ-НЕ или И-ИЛИ-НЕ) і-й группы управляемой МФСП Аі, количество Ri которых больше единицы (Ri1), через сохраняющую входную шину, соединены с выходными шинами одной или нескольких МФСП Аk (k=1, 2,..., і-1), которые составляют (g-1) ступенчатый автомат стратегии АМ для МФСП Аі;

устанавливающие входные и выходные шины многоуровневой схемы памяти (МУСП) Аі (і=1, 2,..., g) соответственно соединены с общими входными и выходными шинами МУСП.

Суть принципа запоминания состояний в МУСП с много функциональной системой организации между МФСП состоит в том, xi(t) что устанавливающими входными сигналами состояния управляемых МФСП аі запоминаются только в том случае, если они принадлежат блокам і состояний, которые запоминаются под ej(), влиянием сохраняющегося входного сигнала который генерируется управляющей МФСП Аk.

Входные сигналы автомата А Комбинационные схемы Регистр Rg Выходные сигналы U U автомата А (g-1)-ступенчатого Автомат настройки U автомата стратегии АМ Входные сигналы автомата настройки U Входные сигналы (g-1)-ступенчатого автомата стратегии Рис. 2.8. Обобщенная структурная схема многофункционального автомата А на схемах автоматной памяти xi(t) Под воздействием входного сигнала устанавивается состояние aі(t) управляемой МФСП, которое, при последующем ej(), воздействии сохраняющего входного сигнала переводит состояние aі(t) в новое состояние ak() в блоке і. При этом происходит укрупненный переход в новый блок j состояний схемы памяти (см. табл. 2.1). При запоминании в МУСП возникает качественно новая вертикальная иерархическая взаимосвязь состояний, которая определяет блоки j состояний аі управляемых МФСП зависимо от запоминающих состояний ak управляющих МФСП.

МУСП с многофункциональной системой организации определяет такую структуру, в которой многофункциональный режим работы одного устройства определяется другим устройством, так называемым автоматом стратегии АМ. Автомат стратегии АМ в МУСП может быть моно- и многофункциональным устройством памяти. В зависимости от возможностей автомата стратегии АМ МУСП с многофункциональной системой организации можно определить как открытою, полуоткрытою или закрытою структурою.

Рассмотрим открытые и полузакрытые структуры устройств памяти.

Определение 2.5. Открытою многоуровневою структурою устройства памяти МУСП с многофункциональною системою организации назовем автомат, который состоит из двух устройств:

управляемой МФСП Ау и многофункционального автомата стратегии АМ, которые имеют объединенные множества состояний, входные Х и выходные Y алфавиты и сохраняющий входной алфавит ЕН автомата стратегии АМ.

Открытую многоуровневую структуру устройства памяти МУСП с многофункциональною системою организации иллюстрирует рис.

2.9. Такая структура позволяет расширить многофункциональность, используя дополнительный автомат стратегии.

Определение 2.6. Полузакрытою многоуровневою структурою устройства памяти МУСП с многофункциональною системою организации назовем автомат, который состоит из двух устройств:

Ау управляемой МСП и многофункционального (или монофункционального) автомата стратегии АМ, которые имеют объединенные множества состояний, входные Х и выходные Y алфавиты.

Полузакрытую многоуровневую структуру устройства памяти МУСП с многофункциональною системою организации иллюстрирует рис. 2.10. Триггеры и регистры на триггерах представляют собою закрытые структуры памяти, в связи с тем, что они не способны изменять структуру запоминаемых состояний.

МФСП вместе с автоматом стратегии может создавать полуза крытые или открытые многоуровневые структуры устройств памяти с многофункциональною системою организации.

ху уу Ау Х Ey уМ Y хМ АМ уH EH Рис. 2.9. Открытая многоуровневая структура ху уу Ау Y Х Ey уМ хМ АМ Рис. 2.10. Полузакрытая многоуровневая структура Иерархический абстрактный автомат А с памятью на МФСП рассматривается как g-ступенчатое (g 1) устройство, состоящее из Входные сигналы g-уровня Комбинационная Комбинационная схема 1g (КС1) Регистр Rg схема 2g (КС2) вы входных сигналов ходных сигналов Выходные сиг налы g-уровня Еg Входные сигналы (g-1)уровня Комбинационная Комбинационная схема 1 g-1 (КС1) Регистр Rg-1 схема 2g-1 (КС2) входных сигналов выходных сигна лов Выходные сигна лы (g-1)-уровня Е g- (g – 1)-уровневый автомат стратегии АМ Рис. 2.11. Структурная схема автомата 1-го рода (открытая g-уровневая структура) регистров Rj(j = 1, 2, …, g), которые взаемодействуют одновременно, и двух комбинационных схем КС1і, КС2і (і = 1, 2,..., g) на каждой ступени. На уровне g (верхнему) иерархический g-ступенчатый автомат А способен функционировать как многофункциональный автомат 1-го, 2-го, а также 3-го рода, который имеет (g–1) ступенчатый автомат стратегии АМ, использующийся для сохранения определенного блока і состояний соответствующего автомата на уровне g.

Каноническую структуру g-ступенчатого абстрактного автомата 1-го, 2-го и 3-го рода на МФСП одновременно с (g – 1)-ступенчатым автоматом стратегии изображено на рис. 2.11 —2.13.

В отличии от автоматов Мили (1-го рода) и Мура (2-го рода) с памятью на триггерах, функционирование которых рассматривается в автоматном дискретном времени, автоматы Мараховского на МФСП, функционирование которых рассматривается в автоматном непрерывном времени [64], способны при различных входных еj() сигналах запоминать состояния определенных блоков (подмножеств) j(j Q). В соответствии с этой способностью можно в j(j Q) каждом из блоков реализовать различные монофункциональные автоматы Мили и Мура, а также, воспользовавшися разными блоками j(j Q) памяти МФСП g-уровня и реализовать многофункциональные автоматы 1-го и 2-го рода (рис.

2.11–2.12).

Регистр Rg на МФСП и комбинационные схемы (КС) – это устройства, которые используются для обработки частной информации верхнего g-уровня. Каждое такое устройство можно описать как абстрактный автомат, который обрабатывает входную информацию и сохраняющие еj() входные сигналы которого, принадлежащие множеству Еg (еj() Еg), поступают из (g–1) уровневого автомата стратегии (рис. 2.11).

Таким образом, приходим к выводам, что автоматы Мили и Мура, которые используют память на триггерах, являются частным случаем автоматов М, которые реализуют свою память на МФСП.

Показано, что, автоматы М g–уровневой ступени на МФСП одновременно с (g–1)-уровневым автоматами стратегии АМ имеют уникальную способность обрабатывать частную и общую информа цию за один такт машинного времени.

Входные сигналы g-уровня Комбинационная Комбинационная схема 1g (КС1) Регистр Rg схема 2g (КС2) вы входных сигналов ходных сигналов Выходные сиг налы g-уровня Еg Входные сигналы (g-1)уровня Комбинационная Комбинационная схема 1 g-1 (КС1) Регистр Rg-1 схема 2g-1 (КС2) входных сигналов выходных сигна лов Выходные сигна лы (g-1)-уровня Е g- (g – 1)-уровневый автомат стратегии АМ Рис. 2.12. Структурная схема автомата 2-го рода (открытая g-уровневая структура) Показано, что автоматы М g–уровневой ступени на МФСП имеют качественно новые (по сравнению с автоматами на триггерах) переходы из одного состояния в другое под воздействием еj() вход ных сигналов: укрупненные, вероятностные и нечеткие.

Входные сигналы g-уровня Комбинационная Комбинационная схема 1g (КС1) Регистр Rg схема 2g (КС2) вы входных сигналов ходных сигналов Выходные сиг налы g-уровня Еg Входные сигналы (g-1)уровня Комбинационная Комбинационная схема 1 g-1 (КС1) Регистр Rg-1 схема 2g-1 (КС2) входных сигналов выходных сигна лов Выходные сигна лы (g-1)-уровня Е g- (g – 1)-уровневый автомат стратегии АМ Рис. 2.13. Структурная схема автомата 3-го рода (открытая g-уровневая структура) 2.6. Понятие об абстрактных вероятностных автоматах 3-го рода Различия между дискретными автоматами, которые описывают функционирование устройств компьютера и даже самого компьютера, и моделями, которые использует человеческий мозг, состоит в той способности, которая позволяет человеку думать и делать заключения в неточных, неколичественных, нечетких, расплывчатых терминах, принимая в расчет параллельные соображения как общего, так и со путствующего, частного характера [49].

Талантливый математик Фрэнк Пламптон Рамсей доказал, что полная неупорядоченность невозможна. Каждое достаточно большое множество чисел, точек или объектов обязательно содержит высоко упорядоченную структуру [144].

Основным элементом человеческого мозга является нейрон, важ нейшую роль в котором играют перестройки надмолекулярных струк тур в различных частях нервной клетки, а также волны структурных перестроек, сопровождающие передачу информации в пределах дан ного нейрона и от нейрона к другому нейрону [101]. Нейронную па мять представляют в матричном виде, управляемую по двум коорди натам возбуждающими и тормозящими входными сигналами и спо собную выполнять структурную перестройку передачи информации в иерархических ансамблях нейронов [37–38].

Рассматриваемые многофункциональные автоматы 3-го рода спо собны переходить в новое состояние по двум координатам (перемен ным) информационных (устанавливающих) и сохраняющих входных сигналов и осуществлять структурную перестройку подмножеств за поминаемых состояний, которую можно сравнить с работой нейрона [37–38]. В связи с этим представляет интерес исследование функцио нирования многофункциональных автоматов 3-го рода при поступле нии на них вероятностных или нечетких входных слов.

Вероятностные переходы в автоматах 3-го рода происходят под воздействием вероятностных элементарных рв1(Т) входных слов авто матного непрерывного времени двух типов:

рв1(Т) = хр(t), ej(), (2.18) где хр(t) –информационный входной сигнал (хр Х), который одно значно устанавливает состояние памяти автомата, не сохраняемое ни при одном сохраняющем ej() входом сигнале;

и рв2(Т) = хі(t), e вj (), (2.19) где e вj () – вероятностный сохраняющий входной сигнал ( e вj Е).

Информационный хр(t) входной сигнал (хрХ) в детерминиро ванных автоматах является запрещенным, так как устанавливает на выходных узлах схем памяти выходной сигнал, который не сохраня ется ни при одном сохраняющем ej() входом сигнале и ведет к веро ятностным переходам, что не разрешено (просто запрещено).

Вероятностное слово первого типа (2.18) позволяет осуществ лять вероятностный переход в тактовый внутренний момент из ар(t) состояния, которое не запоминается, в неопределенное состояние вполне определенного j блока состояний автомата, под воздействием сохраняющего ej() входного сигнала.

Вероятностное слово второго типа (2.19) позволяет осуществ лять вероятностный переход в тактовый внутренний момент из оп ределенного аі(t) состояния в неопределенное состояние вполне опре деленного і блока состояний под воздействием вероятностного со храняющего eвj () входного сигнала.

Таким образом, вероятностные переходы в автоматах 3-го рода способны осуществлять переходы из одного состояния в состояние определенного блока состояний с определенной мерой вероятности.

Специалисты по теории Рамсея стараются вычислить, сколь велико должно быть множество звёзд, чисел или каких-либо объектов, чтобы можно было гарантировать существование определённой же лаемой подструктуры. На решение таких задач часто требуются деся тилетия, и поддаются они только при самом изобретательном и тон ком рассуждении. Пытаясь найти решения поставленной задачи, спе циалисты по теории Рамсея помогают тем самым инженерам в по строении более совершенных сетей коммуникации и систем передачи и поиска информации. Они также открыли некоторые математические методы, которые пригодятся учёным в будущем. Возможно, самое важное заключается в том, что теория Рамсея исследует основопола гающую структуру математики, т.е. структуру, пронизывающую всю Вселенную.

В отличие от многих разделов современной математики тео рию Рамсея можно изложить на интуитивном уровне. В самом деле, привлекательность этой теории отчасти обусловлена той простотой, с которой можно сформулировать её задачи.

Теорию Рамсея можно сформулировать в ещё более общем ви де. Если число объектов в совокупности достаточно велико и каждые два объекта связывает одно из набора отношений, то всегда существу ет подмножество данной совокупности, содержащее заданное число объектов, и при этом такое, что в нём все объекты связаны отношени ем одного типа.

Есть некая ирония в том, каким образом за два года до смерти Рамсей вывел теорию, ныне называемую его именем. Он пришёл к ос новной идее, пытаясь доказать тезис, выдвинутый Расселом и Альф редом Нортом Уайтхедом в их основополагающем труде «Principia Mathematica» (Основы математики). Они предположили, что все ма тематические истины могут быть выведены из ограниченного набора аксиом. Развивая эту идею, немецкий математик Давид Гильберт предположил, что должна существовать процедура, позволяющая ре шить, следует ли то или иное утверждение из данного набора аксиом или нет. Рамсей показал, что в некотором частном случае такая про цедура принятия решения существует. (Спустя несколько лет Курт Гёдель и его последователи, англичанин Алан Тьюринг и другие, ис черпывающим образом доказали, что в общем случае такой процеду ры не существует.) Усилиями Рамсея, Эрдёша, Ван дер Вардена и многих других были заложены основы теории, носящей имя Рамсея. Для нас очень важен сам результат теории Рамсея, утверждающий, что каждое дос таточно большое множество чисел, точек или объектов обязательно содержит высоко упорядоченную структуру [133;

144]. С этой точки зрения мы и подходим к созданию вероятностных и нечетких автома тов 3-го рода.

Рассмотрим два типа вероятностных абстрактных автомата 3 го рода в зависимости от типов элементарных входных слов (2.18 – 2.19).

Вероятностное слово первого типа (2.18) определяет функцио нирование вероятностного абстрактного автомата 3-го рода первого типа.

Вероятностный абстрактный автомат 3-го рода первого типа задается следующим определением.

Определение 2.7. Математическою моделью вероятностного уст ройства с многофункциональной системой организации памяти на схемах автоматной памяти является абстрактный вероятностный ав томат АВ1 определяемый как десятикомпонентный кортеж или вектор [64]:

yB, 3, Ре), АВ1 = (хр, Е, YIII, Q,, e0, a0, aр, o, B B (2.20) у которого:

хр, – информационный входной сигнал (входной информа ционный алфавит);

Е = {е0, е1,…, еR-1} – множество сохраняющих входных сиг налов (входной сохраняющий алфавит);

YIII B = { Y0B1, Y1B1,...,YKB11 } – множество вероятностных выход ных сигналов типа 3 (выходной вероятностный алфавит ти па 3);

Q = {a0, a1,…, am1} – произвольное множество запоминае мых состояний автомата (алфавит состояний);

= {0, 1,…, R-1} –множество блоков j состояний (алфа вит блоков состояний);

е0 Е – начальный сохраняющий входной сигнал;

Q) a0 0 ( j – начальное состояние автомата;

j o: Q хр ар, – однозначная функция перехода, реали зующая отображение D Q x p в ар,. Другими словами, функция o: некоторым парам „состояние – информацион ный входной сигнал” (а(-1), хр,(t)) ставит однозначно в со ответствие несохраняемое состояние автомата ар(t) = o(а( 1), хр(t)), где ар Q;

B1 : ар E j – функция вероятностного укрупненного пе y рехода, реализующая отображение D a e в j. Други p j y ми словами, функция B1 некоторым парам „несохраняемое y состояние – сохраняющий входной сигнал” (ар(t), е()) ста вит в соответствие состояние автомата а()= B1 (ар(t), е()), y где ар(t) j, а() j, ар(t) а();

3 1 : Q E YIII1 –вероятностная функция выходов типа 3, B B реализующая отображение D a Е в YIII1. Другими сло B p вами, функция B1 : некоторым парам „несохраняемое со стояние – сохраняющий входной сигнал” (ар(t), е()) ставит в соответствие выходной сигнал автомата ув1()= B1 (ар(t), е()), где у YIII1 ;

B Ре(ареj) – система условных вероятностей.

Система условных вероятностей Ре, заданных для каждой пары (ар(t), е()) на множестве j YIII1 ( j Q;

YIII1 YIII, где YIII выходные B B сигналы автомата 3-го рода) характеризует вероятность перехода ав томата в состояние аs() с выдачей сигнала уk(), который отображает состояние аs() автомата, при условии, что автомат предварительно был установленный в состояние ар(t), которое не запоминается, и на его входы подан сохраняющий еj() входной сигнал, способный со хранять все множество состояний блока j состояний (аs j).

Закон функционирования вероятностного абстрактного автомата 3-го рода первого типа задается уравнениями:

а (t ) (a( 1), x (t ));

р р (2.21) a() B1 (a p (t ), e(), Pe );

y B1 () (a(), e()), L a(t ) j, a() j ;

i 0, 1, 2,...;

0, 1, 2,..., 0 Pe 1.

Вероятностное слово второго типа (2.19) определяет вероятно стный абстрактный автомат 3-го рода второго типа.

Вероятностный абстрактный автомат 3-го рода второго типа задается следующим определением.

Определение 2.8. Математическою моделью вероятностного уст ройства с многофункциональной системой организации памяти на схемах автоматной памяти является абстрактный вероятностный ав томат АВ2 определяемый как одиннадцатикомпонентный кортеж или вектор [64]:

АВ2 = (Х, Ев2, YIII2, Q,, e0, a0, o, y 2, 3 2, Р(0), Ре), (2.22) B B B у которого:

Х= {х1, х2,…, хN-1} –информационный входной сигнал (входной информационный алфавит);

Ев2 = { e1B 2, e2B 2,... e R 1 } – множество вероятностных сохра B няющих входных сигналов (входной вероятностный сохра няющий алфавит);

YIII2 = { Y0B 2, Y1B 2,...,YKB 21 } – множество вероятностных выход B ных сигналов типа 2 (выходной вероятностный алфавит ти па 2);

Q = {a0, a1,…, am1} – произвольное множество запоминпе мых состояний (алфавит состояний);

= {0, 1,…, R-1} –множество блоков j состояний (алфа вит блоков состояний);

е0 Е –начальный сохраняющий входной сигнал;

a0 0 ( j Q) – начальное состояние автомата;

j o: Q Х Q, – однозначная функция перехода, реализую щая отображение D Q Х в Q,. Другими словами, функ ция o: некоторым парам „состояние – информационный входной сигнал” (а(-1), х(t)) ставит в соответствие состоя ние автомата а(t)= o(а(-1), х(t)), где а Q;

B2 : Q Ев2 j – функция вероятностного укрупненного y перехода, реализующая отображение D Q E в j. Дру B2 y гими словами, функция B 2 некоторым парам „состояние – y вероятностный сохраняющий входной сигнал” (а (t), еВ2()) ставит в соответствие состояние автомата а()= B 2 (а(t), y еВ2()), где а(t) і, а() j, а(t) а() (а (t), а()Q);

B 2 : Q Ев2 YIII2 –вероятностная функция выходов типа 3, B в YIII2. Другими реализующая отображение D Q Е B B2 словами, функция B2 : некоторым парам „состояние – веро ятностный сохраняющий входной сигнал” (а (t), еВ2()) ста вит в соответствие выходной сигнал автомата ув2()= B 2 (а (t), еВ2()), где у YIII2 ;

B Р(0)={P0, P1, P2, …, Pk-1,} –начальное распределение вероят ностей блока j состояний автомата;

Ре(а еВ2j) – система условных вероятностей.

Система условных вероятностей Ре, заданных для каждой пары (а(t), еВ2j ()) на множестве j YIII2 ( j Q;

YIII2 YIII, где YIII выходные B B сигналы автомата 3-го рода) характеризует вероятность перехода ав томата в состояние аs() с выдачей сигнала ув2(), который отобража ет состояние аs() автомата, при условии, что автомат предварительно был установленный в состояние а(t) и на его входы подан вероятност ный сохраняющий еВ2j () входной сигнал, способный сохранять все множество состояний блока j состояний (аs j).

Закон функционирования вероятностного абстрактного автомата 3-го рода второго типа задается уравнениями:

a(t ) (a( 1), x(t ));

(2.23) a() B 2 (a(t ), e j (), P, P );

B 0e B y L () в 2 (a(), e()), a(t ) j, a() j ;

i 0, 1, 2,...;

0, 1, 2,..., 0 P 1;

0 Pe 1.

Смысл понятия абстрактного вероятностного автомата 3-го рода состоит в реализации некоторого вероятностного отображения в множества вероятностных слов рв(Т) входных алфавитов в множество слов ув() выходного алфавита, символы которых принадлежат вполне определенным подмножествам YIII. Появление каждого символа вы ходной последовательности зависит и определяется системой услов ных вероятностей в соответствии с типом абстрактного вероятностно го автомата 3-го рода.

2.7. Понятие об абстрактных нечетких автоматах 3-го рода Абстрактные нечеткие автоматы 3-го рода рассматриваются при поступлении на их входные узлы элементарных нечетких рн(Т) вход ных слов (рн(Т) = хр(t), ев()) в автоматном непрерывном времени Т.

Определение 2.9. Математическою моделью нечеткого устройства с многофункциональной системой организации памяти на схемах ав томатной памяти является абстрактный нечеткий автомат М опреде ляемый как четырнадцатикомпонентный кортеж или вектор [64]:

Ан = (хр, Е, Ев, Y H, Q, Qн,, e0, a0, o, H, 3, Р(0), Ре), H (2.24) III y у которого:

хр – информационный входной сигнал (входной информа ционный алфавит);

Е = множество сохраняющих входных сигналов (входной сохраняющий алфавит);

ЕН = { e1Н, e2Н,... e R 1 } – множество нечетких сохраняющих Н входных сигналов (входной нечеткий сохраняющий алфа вит, где ( Е Е ) );

H j Y H = { Y0Н, Y1Н,...,YKН 1 } – множество нечетких выходных сиг III налов автомата 3-го рода (выходной нечеткий алфавит);

Q – произвольное множество запоминаемых состояний ав томата (алфавит состояний);

QН = {a0, a1,…, am1} – произвольное нечеткое подмножество состояний (алфавит нечетких подмножеств состояний, где Q) );

( Q H j = {0, 1,…, R-1} –множество блоков j состояний (алфа вит блоков состояний);

е0 Е –начальный сохраняющий входной сигнал;

a0 0 ( j Q) – начальное состояние автомата;

j o: Q хр ар, – однозначная функция перехода в незапо ар минаемое состояние, реализующая отображение D Q х р в ар. Другими словами, функция o: некоторым парам „состояние – информационный входной сигнал” (а( 1), хр(t)) ставит в соответствие несохраняемое состояние ав томата ар(t)= o(а(-1), хр(t)), где ар Q;

H: Q ЕН j – функция нечеткого укрупненного перехо y да, реализующая отображение D Q E в j. Другими Н y словами, функция H некоторым парам „несохраняемое со y стояние – нечеткий сохраняющий входной сигнал” (ар(t), еН()) ставит в соответствие состояние автомата а()= H y (ар(t), еН()), где ар(t)і, а()j, ар(t) а();

Н 3 : QН ЕН YIII – нечеткая функция выходов, реализую Н щая отображение D Q Е в YIII. Другими словами, Н Н Н Н функция 3 : некоторым парам „несохраняемое состояние – нечеткий сохраняющий входной сигнал” (ар(t), еН()) ставит в соответствие выходной сигнал автомата уН()= Н (ар(t), еН()), где уН YIII ;

Н Р(0)={P0, P1, P2, …, Pk-1,} –начальное распределение нечетко го подмножества QН состояний автомата;

РН(ар еНj) – система условных вероятностей.

Система условных вероятностей РН, заданных для каждой пары (ар(t), еН()) на множестве QН YIII ( QН Q;

YIII Yiii, где YIII выход Н Н ные сигналы автомата 3-го рода) характеризует вероятность перехода автомата в состояние аs() с выдачей сигнала уk(), который отобра жает состояние аs() автомата, при условии, что автомат предвари тельно был установленный в состояние ар(t) и на его входы подан не четкий сохраняющий еНj() входной сигнал, способный переводить автомат из ар(t) состояния в а() состояние блока j состояний, кото рый принадлежит нечеткому подмножеству QН состояний (j QН).

Закон функционирования нечеткого абстрактного автомата 3-го рода задается уравнениями:

a (t ) (a( 1), x (t ));

р р a( ) н (a р (t ), e j (), P, Pн );

н (2.25) н y L () (a (), e ()), н н a р (t ) j, a( ) j ;

i 0, 1, 2,...;

0, 1, 2,..., 0 P0 1;

0 Pн 1.

Смысл понятия абстрактного нечеткого автомата 3-го рода состо ит в реализации некоторого нечеткого отображения н множества элементарных нечетких слов рв(Т) входных алфавитов в множество слов уН() выходного алфавита, символы которых принадлежат впол не определенным подмножествам YIII. Появление каждого символа Н выходной последовательности зависит и определяется системой ус ловных вероятностей в соответствии с системой условных вероятно стей РН абстрактного нечеткого автомата 3-го рода.

2.8. Классификация детерминированных абстрактных автоматов Рассмотрим классификацию детерминированных абстрактных ав томатов по использованию типов их выходных сигналов, как это осу ществлено в классических абстрактных автоматах Мили, генерирую щих выходные у1(t) сигналы типа 1, и Мура, генерирующих выходные у2(Т) сигналы типа 2. Объединенный абстрактный С-автомат характе ризуется генерацией двух типов (типа 1 и типа 2) выходных сигналов у1(t) и у2(Т). Схемы памяти этих автоматов используют триггеры, ко торые своими ограничениями определяют монофункциональный ха рактер их работы.

Функционирование многофункциональных автоматов Марахов ского исследуется в автоматном непрерывном времени, а сами абст рактные автоматы, память которых реализованы на МФСП, опреде ляют многофункциональный характер их работы и могут также клас сифицироваться по их типам выходных сигналов, как это осуществле но в классических автоматах Мили и Мура. Так, объединенный абст рактный многофункциональный М-автомат имеет возможность гене рировать три типа (тип 1, тип 2 и тип 3) выходных сигналов у1(t), у2(Т) и у3(). Сочетание в абстрактном многофункциональном автомате только двух типов (тип 1 и тип 2) выходных сигналов у1(t) и у2(Т) можно по аналогии с объединенным автоматом Мили и Мура также назвать многофункциональным С-автоматом.

Сочетание в абстрактном многофункциональном автомате только двух типов (тип 1 и тип 3) выходных сигналов у1(t) и у3() назовем многофункциональным R1-автоматом, а сочетание в абстрактном многофункциональном автомате только двух типов (тип 2 и тип 3) выходных сигналов у2(Т) и у3() назовем многофункциональным R2 автоматом. Абстрактные многофункциональные автоматы, исполь зующие только один тип выходных сигналов у1(t), у2(Т) или у3() на зовем соответственно абстрактными многофункциональными автома тами 1-го, 2-го или 3-го рода.

Классификация абстрактных многофункциональных автоматов с памятью на МФСП представлена на рис. 2.14.

Абстрактный многофункциональный М-автомат Абстрактный Абстрактный Абстрактный многофункциональный многофункциональный многофункциональный С-автомат R1-автомат R2-автомат Абстрактный Абстрактный Абстрактный многофункциональный многофункциональный многофункциональный автомат 2-рода автомат 1-рода автомат 3-рода Рис. 2.14. Классификация абстрактных многофункциональных ав томатов на схемах автоматной памяти Отметим, что абстрактные монофункциональные автоматы Мили (1-го рода), Мура (2-го рода) и С-автомат являются частным случаем абстрактных многофункциональных автоматов 1-го, 2-го рода и С автомата.

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

2.9. Классификация недетерминированных абстрактных автоматов Рассматриваемые недетерминированные (вероятностные и нечет кие) абстрактные автоматы 3-го рода характеризуются осуществлени ем переходов по двум переменным за один такт Т автоматного непре рывного времени под влиянием элементарных вероятностных и не четких входных слов.

Вероятностные абстрактные автоматы 3-го рода описывают веро ятностные переходы из вполне определенного а(-1) состояния в со стояние а() целого подмножества состояний вполне определенного блока j состояний в соответствии с определенной вероятностью Ре.

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

Нечеткие абстрактные автоматы 3-го рода описывают нечеткие переходы из вполне определенного а(-1) состояния в состояние а() целого нечеткого Qн подмножества состояний, которое состоит из вполне определенных подмножеств блоков j состояний в соответст вии с определенной вероятностью Рн.

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

Классификация абстрактных вероятностных и нечетких автома тов третьего рода представлена на рис. 2.15.

Абстрактный многофункциональный недетерминированный автомат 3-рода Абстрактный Абстрактный Абстрактный вероятностный вероятностный нечеткий автомат 3-рода автомат 3-рода автомат 3-рода первого типа второго типа Рис. 2.15. Классификация абстрактных недетерминированных автоматов 3-го рода Абстрактный недетерминированный автомат 3-го рода может быть общим, когда в нем используются элементарные вероятностные входные слова первого и второго типа, а также элементарные нечет кие входные слова.

Объединенный абстрактный недетерминированный автомат мож но рассматривать совместно с детерминированным абстрактным ав томатом 3-го рода. При этом происходит использование соответст вующих элементарных входных слов: однозначных, вероятностных первого и второго типа или нечетких.

2.10. Понятие об автоматах четвертого рода, контролирую щих работоспособность базовых схем памяти Все абстрактные автоматы с 1-го по 3-й род рассматривают толь ко область их функционирования в автоматном дискретном времени, или в автоматном непрерывного времени. В своем описания они не рассматривают возможность проверки схем памяти на работоспособ ность [13-14;

24–26;

32;

35;

64;

90;

119;

140].

Вопросы проверки работоспособности схем памяти автоматов в общем осуществляется схемотехническими средствами при наличии трех одинаковых устройств, которые через схему сравнения выдают сигнал, что схема работает верно или не верно [44-45].

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

При катастрофических отказах базовых схем является возмож ным построение нового автомата четвертого рода, который бы выда вал сигнал проверки катастрофических отказов в базовых схемах па мяти.

В настоящее время большие интегральные схемы (БИС) строятся с расчетом на 100% работоспособность всех компонентов схемы. Уве личение числа компонентов и уменьшения их размеров увеличивает вероятность выхода из области работоспособности компонентов и по явление обрывов в их связях. Это приводит к значительному брака кристаллов при построении БИС и к катастрофическому отказу их в процессе эксплуатации.

С целью увеличения надежности работы системы из ненадежных электронных элементов делается многократное резервирование, рас пределение сетевых систем и т.п., в которых отказ целого блока или устройства из строя определяется выходным сигналом схем сравнения нескольких блоков [5-7].

К сожалению, определение катастрофических отказов в схемах памяти в известных работах не рассматривается, а тем более их обна ружение.

Катастрофических отказов в базовых схемах памяти существует два типа. Первый тип в базовых схемах памяти на логических элемен тах ИЛИ-НЕ (И-НЕ) осуществляется при появлении неизменного ак тивного выходного сигнала хотя бы на одном из выходных узлов ло гических элементов, значение которых равно логической 1(0). Второй тип в базовых схемах памяти на логических элементах ИЛИ-НЕ (И НЕ) осуществляется при появлении неизменных пассивных сигналов одновременно на всех выходных узлах логических элементах ИЛИ НЕ (И-НЕ), значение которых равны логическому 0(1). Первый тип катастрофических отказов представляет собой активный постоянный выходной сигнал на выходном узле логического элемента, который по цепям к входам логических элементов других групп базовой схеме памяти делает схему памяти полностью не работоспособной. Такой же не работоспособной становится схема памяти при втором типе катаст рофических отказов, когда на всех ее выходных узлах базовой схемы памяти значения пассивны. Такое состояние схемы памяти не запоми нается ни при одном сохраняющем е() входном сигнале. При ответ ственных устройствах управления в таких областях как: атомная элек тростанция, любой вид транспорта и т.д. катастрофические неконтро лируемые отказы недопустимы, так как компоненты устройств и БИС должны работать надежно. Иначе, это приводит к большим катастро фам [8].

Поэтому, появление методов обнаружения катастрофических от казов в базовых схемах памяти на уровне теории автоматов, автору кажется актуальной темою.

Все известные абстрактные и структурные автоматы с системных позиций, которые рассматривают законы работы каких-либо уст ройств с памятью, классифицируются по типу выходного сигнала [24;

64]. Для всех из них, работающих в детерминированном режиме, есть один устанавливающий хр(t) входной сигнал, осуществляющий веро ятностный переход (3.5) под действием сохраняющего е() входного сигнала в определенный блок j состояний,, который имеет для базо вой схемы на всех ее входящих узлах активное значение, равное логи ческой 1(0). Этот хр(t) входной сигнал устанавливает на выходных уз лах логических элементов ИЛИ-НЕ (И-НЕ) значение, равное логиче скому 0 (1). Такое состояние ар(t) выходных сигналов не сохраняется при окончании устанавливающего сигнал хр(t) и делает вероятный пе реход в состояние а(), которое затем запоминается в определенном множества j состояний схемы памяти. Поэтому, устанавливающий хр(t) входной сигнал не используется в детерминированных автоматах и является запрещенным [64;

125].

Но, этот устанавливающий хр(t) входной сигнал можно во всех рассмотренных автоматах 1-го, 2-го и 3-го рода использовать для оп ределения выходных сигналов катастрофических отказов первого ти па, когда у4(t) = 4(хр(t), aр(t)), и использовать для определения выход ных сигналов катастрофических отказов второго типа выходной сиг нал вероятностного автомата 3-го рода ув1() = 3(aр(), е()). Выход ной сигнал у4(t) автомата 4-го рода отличается от выходного сигнала у1(t) автомата 1-го рода тем, что использует в функции выходов не со стояние a(-1), а состояние aр(t), которое установлено устанавливаю щим хр(t) входным сигналом. Таким образом, автомат, использующий выходной сигнал у4(t) можно назвать автоматом четвертого рода в свя зи с тем, что все автоматы определяются по своим выходным сигна лам. На самом деле, выходной сигнал у4(t) может дополнительно до бавляться в выходных сигналов любых автоматов с памятью на базо вых схемах памяти. Выходной сигнал ув3() автомата 3-го рода появ ляется после вероятностного перехода схемы памяти в одно из запо минаемых состояний базовой схемы памяти при воздействии сохра няющего е() входного сигнала.

Эти выходные сигналы у4(t) и ув1() можно использовать для про верки работоспособности элементов памяти в любых устройствах при выявлении их катастрофических отказов. Объясняется это тем, что при катастрофических отказах первого типа в схеме памяти автомата, когда хотя бы один логический элемент в памяти ИЛИ-НЕ (И-НЕ) имеет постоянный выходной сигнал, равный логическому 0 (1), то вы ходной сигнал у4(t) меняет свое значение, которое определяет отказ работоспособности памяти на противоположное значение 1 (0). Ката строфические отказы второго типа образуются и при отсутствии на всех выходных узлах схемы логической 1 и при поступлении на вход ные узлы сохраняющего е() входного сигнала. Структурная схема автомата четвертого рода изображена на рис. 2.16.

xP е y4 yв АВТОМАТ ЧЕТВЕРТОГО РОДА Рис. 2.16. Структурная схема автомата 4-го рода Таким образом, кратко рассмотрены монофункциональные 1-го и 2-го рода и многофункциональные абстрактные автоматы 1-го, 2-го и 3-го рода и предложен для использования в каждом из этих автоматов устанавливающий хр(t) входной сигнал для определения катастрофи ческих отказов в схемах памяти этих автоматов. Конечно, выявление катастрофического отказа в схемах памяти не решает всех проблем по проверке работоспособности схем памяти, но помогает выявлению наиболее существенных отказов - катастрофических, при которых схема памяти работать как запоминающее устройство уже не в со стоянии.

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

Отмечено, что автоматы Мили и Мура являются частным случаем детерминированных автоматов Мараховского.

В данном разделе также рассмотрены основные понятия абст рактных недетерминированных автоматов (вероятностных и нечет ких) 3-го рода, реализуемых на схемах автоматной памяти.

Впервые представлен автомат 4-го рода, предназначенный для выявления катастрофических отказов в базовых схемах памяти любо го автомата, что в устройствах с памятью является актуальной про блемой.

Подводя итог этого раздела, можно констатировать, что предло женные многофункциональные автоматы 1-го, 2-го и 3-го рода рас ширили теорию монофункциональных и многофункциональных авто матов Мили и Мура с памятью на триггерах до многофункциональных автоматов Мараховского с памятью на схемах автоматной памяти, в которых возможны изменения структуры запоминаемых состояний.

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

3. СПОСОБЫ ЗАДАНИЯ АВТОМАТОВ 3.1. Некоторые понятия в теории абстрактных автоматов В литературе по классическим автоматам [12–14;

18–19;

21;

24;

26;

32;

90;

125;

140] даны некоторые важные понятия о взаимоотно шениях между автоматами, такие, как: эквивалентность между авто матами, изоморфизм абстрактных автоматов, взаимоотношения между автоматами первого и второго рода.

Рассмотрим эти понятия.

Определение 3.1. Два абстрактных автомата с общим входным и выходным алфавитом называются эквивалентными между собой, если они индуцируют одно и то же отображение множества слов во вход ном алфавите в множество слов в выходном алфавите.

Изоморфизм между абстрактными автоматами сводится к про блеме перекодировки множества входных и выходных сигналов, а также к перекодировке множества их состояний. По сути дела изо морфные автоматы с абстрактной точки зрения одинаковы.


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

Автомат называется конечным, если множество его состояний ко нечно, и бесконечным, если множество его состояний бесконечно. Ав томат называется инициальным, если функционирование его всегда начинается с одного и того же начального состояния.

3.2. Табличные способы задания многофункциональных абстрактных детерминированных автоматов Задание многофункциональных абстрактных автоматов 1-го, 2-го и 3-го рода сводится к заданию соответствующих однозначной функ ций переходов o, функций выходов 1, 2, 3, функцией сохранения состояний e и функции укрупненных переходов y. Остановимся бо лее подробно на способах задания автоматов с помощью таблиц и графов.

Описание работы многофункционального автомата первого рода задается множествами (не менее двух) таблиц переходов, множества ми таблиц выходов и таблицей сохранения состояний. Проиллюстри руем задание многофункционального автомата А1 первого рода в таб лицах 3.4 – 3.8.

Строки в таблицах 3.4 – 3.8 соответствуют входным сигналам хi, а столбцы – блокам 1 состояний, сохраняющих еj входных сигналов.

Обычно крайний столбец в таблицах обозначен начальным состояни ем а0. На пересечении строк и столбцов таблиц однозначных перехо дов 0і ставится состояние а(t)= 0і (а(-1), х(t)), в котором автомат 1 го рода переходить из состояния а(-1) под воздействием информа ционного х(t) входного сигнала в состояние а(t) в тактовый момент t автоматного непрерывного времени Т. В таблицах выходов автомата 1-го рода – соответствующий переходу выходной сигнал у(t)= 1(а( 1), х(t)) типа 1.

Таблица переходов 3.4 Таблица переходов 3. 02 : Q(-1) X(t) Q(t) 0 : Q(-1) X(t) Q(t) 1 а0 а1 а2 а3 а0 а4 а5 а хi хi х1 а1 а2 а1 а0 х1 a4 a0 a6 a х2 а2 а3 а0 а2 х2 a5 a6 a4 a Таблица выходов 3.6 Таблица выходов 3. 1 : Q(-1) X(t) YI(t) 1 : Q(-1) X(t)YI(t) 1 а0 а4 а5 а а0 а1 а2 а3 хi хi х1 у5 у5 у6 у х1 у1 у2 у3 у х2 у6 у7 у5 у х2 у2 у1 у4 у Строки таблицы сохранения состояний (табл. 3.8) соответствуют сохраняющим е() входным сигналам, а столбцы – а() состояниям автомата. В каждой строке на пересечении со столбцами в таблице сохранения состояний ставится соответствующее состояние а()= е(а(t), е()), где а j, а(t) = =а() (j Q), сохраняемое под воздей ствием сохраняющего е() входного сигнала во время внутреннего такта автоматного непрерывного времени Т, а в остальных случаях ставятся прочерки.

При описании работы многофункционального автомата А 2-го рода выходной сигнал зависит только от запоминаемых состояний блока j автомата, которые устанавливаются в тактовый момент t и сохраняются во время реализации функций сохранения состояний во время внутреннего такта автоматного непрерывного времени Т.

Таблица сохранения состояний 3.8.

Q e j e : j Q a0 a1 a2 a3 a4 a5 a ej e1 a0 a1 a2 a3 – – – e2 a0 - a4 a5 a – – Автоматы 1-го и 2-го рода способны осуществлять функции пе реходов в тактовый момент t автоматного непрерывного времени Т под воздействием информационных х(t) входных сигналов.

Работа автомата 2-го рода может быть задана с помощью отме ченных таблиц функций o однозначных переходов вместе с функци ей 2 таблицы выходов типа 2 и таблицы сохранения состояний (табл.

3.8). Пример табличного описания автомата 2-го рода А3 приведен в таблицах 3.8 –3.10.

Автоматы 3-го рода качественно отличаются от автоматов 1-го и 2-го рода тем, что они способны осуществлять переходы из одного состояния в другое не только в тактовый момент t под воздействием информационных х(t) входных сигналов, но и во время внутреннего такта под воздействием сохраняющих е() входных сигналов авто матного непрерывного времени Т. Это принципиальное отличие ав томатов 3-го рода позволяет им осуществлять переходы в матричной структуре схем автоматной памяти (МФСП), которые происходят не только в блоках j состояний в тактовый момент t, представляющих строку состояний МФСП, но и в блоках i во время внутреннего так та, представляющих столбец состояний МФСП, за один внешний такт Т автоматного непрерывного времени.

Отмеченная Отмеченная таблица переходов 3.9 таблица переходов 3. 02 : Q(-1) X(t) Q(T) 0 : Q(-1) X(t) Q(T) уі у0 у1 у2 у3 уі у0 у4 у5 у 1 а0 а1 а2 а3 а0 а4 а5 а xi xi x1 а1 а2 а1 а0 x1 a4 a0 a6 a x2 а2 а3 а0 а2 x2 a5 a6 a4 a Автоматы 1-го, 2-го и 3-го рода также отличаются своими функ циями 1, 2 и 3 выходных сигналов, рассматриваемых в автоматном непрерывном времени Т.

Функция выходов 1 автоматов 1-го рода реализуется только в тактовый момент t под воздействием информационных х(t) входных сигналов и состояний автомата а(-1), то есть у(t)= 1(а(-1), х(t)), где у YI.

Функция выходов 2 автоматов 2-го рода реализуется в тактовый момент t после перехода автомата в новое состояний под воздействи ем информационных х(t) входных сигналов и предыдущего во време ни состояния автомата а(-1). Функция выходов 2, во первых, явля ется по этому сдвинутой по сравнения с началом тактового момента t, а также зависит только от вновь установленного состояния а(t) и со храняемого состояния а(), где а(t) = а() и у(Т) = 2(а(t), а()), где у YII.

Функция выходов 3 автоматов 3-го рода реализуется во время внутреннего тактового момент в новое состояний под воздействием сохраняющих е() входных сигналов и состояний автомата а().

Функция выходов 3, во первых, является сдвинутой по сравнения с началом внутреннего тактового момента, а также зависит только от вновь установленного состояния а() и от сохраняющего е() вход ного сигнала, то есть у()= 3(а(), е()), где у YIII.

Работа автомата 3-го рода может быть задана с помощью таблиц функций o однозначных и отмеченных таблиц функций y укрупнен ных переходов вместе с функцией 3 таблицы выходов типа 3. При мер табличного описания автомата 3-го рода А3 приведен в таблицах 3.11–3.14 и таблицы сохранения состояний (табл. 3.8).

Таблица переходов 3.11 Таблица переходов 3. 02 : Q(-1) X(t) Q(t) 0 : Q(-1) X(t) Q(t) а0 а1 а2 а а0 а4 а5 а хi хi х1 а1 а2 а1 а х1 a4 a0 a6 a х2 а2 а3 а0 а х2 a5 a6 a4 a Отмеченная Отмеченная таблица переходов 3.13 таблица переходов 3. 02 : Q(t) E() Q() 0 : Q(t) E() Q() уі у0 у1 у2 у3 уі у0 у4 у5 у 1 а0 а1 а2 а3 а0 а4 а5 а еi еi е1 а1 а2 а1 а0 е1 a4 a0 a6 a е2 а2 а3 а0 а2 е2 a5 a6 a4 a 3.3. Табличные способы задания абстрактных вероятностных автоматов 3-го рода В отличие от детерминированных автоматов, в которых возмо жен только однозначный переход от одного состояния в другое под воздействием элементарных однозначных р0(T) и укрупненных ру(T) входных слов, в вероятностных автоматах осуществляется переход в состояние определенного блока j состояний автомата с определен ной вероятностью Ре перехода под воздействием элементарных веро ятностных рв(T) входных слов.

Вероятностный абстрактный автомат 3-го рода первого типа за дается с помощью таблицы сохранения состояний, как и в детерми нированных автоматах (табл. 3.8), таблицы однозначного перехода в ар(t) состояние (табл. 3.15–3.16), отмеченной таблицы переходов в а() состояние блока j состояний (табл. 3.17) с определенной вероят ностью Ре перехода.

Таблица переходов 3.15 Таблица переходов 3. 02 : Q(-1) хр(t) ар(t) 0 : Q(-1) хр(t) ар(t) 1 а0 а1 а2 а3 а0 а4 а5 а хi хi хр ар ар ар ар хр ар ар ар ар Отмеченная таблица вероятностных переходов 3. B1 : ар(t) еj() j(аB()) 3 1 : ар(t) еj() YIII1 (ув1()) B B ув ej у0(Pe1) у1(Pe1) … уk(Pe1) ej ap j e0 а0(Pe1) а1(Pe1) … аk1(Pe1) … … … em а0(Pe1) а1(Pe1) … аkm(Pe1) m Вероятностный абстрактный автомат 3-го рода второго типа за дается с помощью таблицы сохранения состояний, как и в детерми нированных автоматах (табл. 3.8), таблицы однозначного перехода в а(t) состояние (табл. 3.18–3.19), отмеченной таблицы переходов в а() состояние блока j состояний (табл. 3.20) с определенной вероят ностью Ре перехода.

Таблица переходов 3.18 Таблица переходов 3. 02 : Q(-1) X(t) Q(t) 0 : Q(-1) X(t) Q(t) 1 а0 а1 а2 а3 а0 а4 а5 а хi хi х1 а1 а2 а1 а0 х1 a4 a0 a6 a х2 а2 а3 а0 а2 х2 a5 a6 a a Отмеченная Отмеченная таблица переходов 3.9 таблица переходов 3. 02 : Q(-1) X(t) Q(T) 0 : Q(-1) X(t) Q(T) уі у0 у1 у2 у3 уі у0 у4 у5 у 1 а0 а1 а2 а3 а0 а4 а5 а xi xi x1 а1 а2 а1 а0 x1 a4 a0 a6 a x2 а2 а3 а0 а2 x2 a5 a6 a4 a Вероятностные переходы в автомате 3-го рода первого типа про исходят в определенном блоке j состояний, а в автомате 3-го рода второго типа происходят в определенном блоке µі состояний. Таким образом, вероятностные автоматы 3-го рода первого типа и вероятно стные автоматы 3-го рода второго типа осуществляют вероятностные переходы в состояния вполне определенных подмножеств соответст вующих блоков j и µі состояний с определенной мерой вероятности.

Автоматы 4-го рода задаются таблицами переходов (3.15) – (3.16), а выходной сигнал у4(t) = 4(xp(t), ap(t)) зависит от входного сигнала xp(t) и установленного однозначного состояния базовой схе мы памяти ap(t), которое не сохраняется ни при каких сохраняющих e() входных сигналов. После окончания этого сигнала детерминиро ванные автоматы должны устанавливаться в начальное состояние а0.

3.4. Табличный способ задания абстрактных нечетких автоматов 3-го рода Абстрактный нечеткий автомат 3-го рода задается с помощью таблиц сохранения состояний, как в многофункциональных детерми нированных автоматах (табл. 3.8), таблицы однозначного перехода в ар(t) состояние, как в вероятностных автоматах 3-го рода первого ти па (табл. 3.15–3.16), и отмеченной таблицы переходов в а() состоя ние блока j состояний (табл. 3.21) с определенной вероятностью Рн перехода.

Отмеченная таблица нечетких переходов 3. yН : ар(t) еН()j(ан()) 3 : ар(t) еН() YIII (уН()) Н Н ун ej у0(Pн) у1(Pн) … уk(Pн) ej ap j e0 а0(Pн) а1(Pн) … аk1(Pн) … … … em а0(Pн) а1(Pн) … аkm(Pн) m 3.5. Графические способы задания переходов в многофункциональных абстрактных автоматах Абстрактные автоматы с памятью используются для реализации функций однозначного перехода в новое состояние аі(t) при соответ ствующем входном сигнале х(t) при условии сохранения этого со стояния после окончания сигнала х(t), то есть во времени внутреннего такта автоматного непрерывного времени Т.


Однозначные переходы в абстрактных детерминированных авто матах 1-го и 2-го роду изображает рис. 3.3.

хі(t) хі(t) ej() аk( – 1) аі(Т) Рис. 3.3. Однозначный переход Выходные сигналы абстрактных автоматов 1-го и 2-го рода соот ветственно изображаются в графе либо на дуге перехода из одного со стояния в другое в автоматах 1-го рода, либо возле вершины графа в автоматах 2-го рода.

Многофункциональные детерминированные абстрактные авто маты 3-го рода используются не только для реализации функций од нозначного перехода в новое состояние а(t) при соответствующем ус танавливающем х(t) входном сигнале при условии сохранения этого состояния после окончания сигнала х(t), но и при использовании пе реходов во время внутреннего такта для реализации укрупненного перехода в новое состояние а () при соответствующем е() входном сигнале, как это изображено на рис. 3.4.

хі(t) ej() ej() ak( – 1) aі(t) аj() Рис. 3.4. Укрупненный переход Выходные сигналы абстрактных автоматов 3-го рода соответст венно изображаются, как и в автоматах 2-го рода, возле вершины гра фа.

Блок j ej() а j1 () хр (t) e j() а k( – 1) a і(t) ej() а jN () ej() Рис. 3.5. Вероятностный переход первого типа Блок µі ej() аj1() e вj () хi(t) аk( – 1) aі(t) ej() в e j () аjM() Рис. 3.6. Вероятностный переход второго типа Вероятностные абстрактные автоматы первого и второго типа 3 го рода используются для реализации функций вероятностного пере хода в новое состояние а() при соответствующих входных элемен тарных словах рв1(T)) или рв2(T) с определенной вероятностью Ре во время внутреннего такта, как это изображено на рис. 3.5 (для веро ятностного автомата 3-го рода первого типа и автомата 4-го рода) и на рис. 3.6 (для вероятностного автомата 3-го рода второго типа).

Нечеткие абстрактные автоматы 3-го рода используются для реа лизации функций нечеткого перехода в новое состояние а() при со ответствующем входном элементарном слове рн(T) с определенной вероятностью Рн во время внутреннего такта, как это изображено на рис. 3.7.

Блок аj1() ej() в ej () аjN() ej() ejв() Блок аj1() ej() в ej () хр(t) ak( – 1) aі(t) ejв() ejв() аjN() ej() Блок k аj1() ej() ejв() аjN() ej() Нечітка підмножина Qн Рис. 3.7. Нечеткий переход в автомате 3-го рода Таким образом, многофункциональные абстрактные автоматы увеличивают типы переходов, используемых в классических абст рактных автоматах Мили и Мура, расширяют понятие функциониро вания автомата с дискретного автоматного времени t до непрерывно го автоматного времени T, что дает возможность более глубоко ис следовать их работу.

3.6. Математическая модель иерархического абстрактного автомата с многофункциональной системой организации памяти Последовательные многофункциональные автоматы Мараховско го 1-го, 2-го и 3-го рода, имеющие два множества входных алфавитов:

Х – информационный входной алфавит и Е – сохраняющий входной алфавит, способен настраиваться другим многофункциональным ав томатом через множество букв еj (еj Е) сохраняющего входного ал фавита на функционирование в определенном блоке j (подмножест ве) своих состояний.

Yn Xn Sn En 1 Zn- Y Yn Х Y Y X S E 1 Z Y Yn Рис. 3.8. Иерархический абстрактный Fи–автомат В этом случае образуется многоуровневая (иерархическая) струк тура абстрактного Fи–автомата из последовательных многофункцио нальных подавтоматов Si (i=1, 2, …, n). Организация такой объеди ненной структуры иерархического автомата (ИА) представлена на рис. 3.8.

Каждый многофункциональный подавтомат Si (i=1, 2, …, n) ие рархического абстрактного Fи–автомата может переходить из одного состояния в другое параллельно с другими подавтоматами ИА (рис.

3.8). Функционирование подавтомата Si в определенном подмножест ве состояний j может быть изменено воздействиями входных букв информационного алфавита Х в тактовый момент t и воздействиями результатов работы других подавтоматов Si ИА буквами сохраняюще го входного алфавита Е в моменты внутреннего такта автоматного непрерывного времени Т.

Дадим определение абстрактного иерархического Fи–автомата.

Определение 3.2. Математической моделью иерархического дис кретного устройства с многофункциональной системой организации памяти является абстрактный иерархический Fи–автомат, определяе мый как N-компонентный вектор Fи = (S1, S2, …, SN), (3.1) компоненты Si которого задаются шестнадцатикомпонентным векто ром Si ( X i, Ei, Z i, Yi1,Yi II, Yi III, Qi, i, ei0, ai0, i0, ie, iy, i1, i2, i3 ) (3.2) у которого Xi – множество информационных входных сигналов;

Ei – множество сохраняющих входных сигналов;

Zi – множество разрешающих входных сигналов;

Yi I – множество выходных сигналов типа 1;

Yi II – множество выходных сигналов типа 2;

Yi III – множество выходных сигналов типа 3;

Qi – произвольное множество состояний;

i – множество блоков i состояний подавтомата Si;

j ei – начальный сохраняющий входной сигнал;

ai – начальное состояние подавтомата Si;

i : Qi Xi Qi – однозначная функция переходов;

i : Qi ei i – функция сохранения блоков состояний;

e j j i : Qi Ei i – функция укрупненного перехода;

y j i : Qi Xi Yi I – функция выходов типа 1;

i : i Yi II – функция выходов типа 2;

2 j i : Qi Ei Yi III – функция выходов типа и определенный функционально, как и компоненты структуры Si, ше стнадцатикомпонентным вектором FA = (X, E, Z, Y I, Y II, Y III, Q,, E0, Q0, F1, F2, F3,,, ) (3.3) у которого X={X1, X2, …, XN} – множество информационных входных сиг налов;

E ={E1, E2, …, EN}– множество сохраняющих входных сигналов;

Zi ={Z1, Z2, …, ZN}– множество разрешающих входных сигна лов;

Y I ={ Y1I,Y2I,...,Y NI }– множество выходных сигналов типа 1;

Y II ={ Y1 II,Y2II,...,YNII }– множество выходных сигналов типа 2;

Y III ={ Y1 III,Y2III,...,YNIII }– множество выходных сигналов типа 3;

Q ={ Q1, Q2, …, QN}– произвольное множество состояний;

={ 1, 2,…, N }– множество блоков состояний подавто мата Si;

E0= {e1, e2,..., eN } – начальный сохраняющий входной сигнал;

0 0 a0 = {a1, a2,..., a N } – начальное состояние подавтомата Si;

0 0 F1: Q X Q – однозначная функция переходов, реализующая отображение DF1 Q X в Q;

F2: Q еj j – функция сохранения блоков состояний, реали зующая отображение DF2 Q еj в j;

F3: Q E j – функция укрупненного перехода, реализующая отображение DF3 Q E в j;

1: Q X Y I – функция выходов типа 1, реализующая ото бражение D1 Q X на Y I ;

2: j Y II – функция выходов типа 2, реализующая отображе D2 j на Y II ;

ние 3: Q E Y III – функция выходов типа 3, реализующая ото бражение D3 Q Е на Y III.

Подавтоматы Si, реализующие свою автоматную память на реги страх открытого типа, функционируют в автоматном непрерывном времени Т.

В начальный тактовый момент t0 все подавтоматы Si устанавли ваются в начальное состояние а0 соответствующим входным сигналом N i0 (t 0 ) X i. Во время последующего внутреннего такта 0 начальное состояние а0 сохраняется под воздействием начальных сохраняющих ei0 (0) входных сигналов. Объединение состояний ai подавтоматов j Si определяют состояния аi иерархичного автомата в данный тактовый момент ti или i автоматного непрерывного времени Тi. В иерархич ном автомате А во время тактового момента ti все или только некото рые подавтоматы Si могут осуществлять функции однозначных пере ходов i, реализуя общую функцию однозначных переходов F1 ие рархического автомата А в новое состояние a s (t ) ai (t ). Во время j i внутреннего такта i подавтоматы Si могут осуществлять укрупнен ные переходы i, реализуя общую функцию перехода F3 иерархиче y ского автомата А в новое состояние a k ( ) ai (). Если подавтоматы j i Si за время всего внешнего такта Т не совершают переходы в новое со стояние, то, следовательно, они реализуют функцию сохранения со стояний ie, реализуя в ИА А объединенную функцию сохранения со стояний F2.

Каждый из подавтоматов Si работает в определенном блоке i j состояний всего множества своих состояний Qi. Блоки i j состоя ний подавтоматов Si образуют в ИА А определенный блок множе i ства блоков i состояний, в котором ИА А функционирует в данный j момент времени.

Характерной особенностью ИА А является возможность взаимо действия подавтоматов Si не только во время такта ti, но и во время внутреннего такта i автоматного непрерывного времени Тi. Память подавтоматов Si представляет собою матричную структуру, в которой во время такта ti под воздействием информационных хі(t) входных сигналов подавтомат Si способен перейти из одного состояния в дру гое в одном блоке i состояний (строке матричной структуры схемы j автоматной памяти). А во время внутреннего такта i под воздействи ем сохраняющих еj() входных сигналов подавтомат Si способен пе рейти из одного состояния в другое в одном блоке µi (столбике мат ричной структуры схемы автоматной памяти), то есть из определенно го состояния одного блока i в определенное состояние другого блока j i j состояний.

Таким образом, математическая модель иерархического автомата А способна описывать функционирование не только параллельно ра ботающих подавтоматов Si, но и их межуровневое взаимодействие за счет использования букв входного сохраняющего Е алфавита подав томатов Si.

3.7. Способ задания иерархического абстрактного автомата с многофункциональной системой организации памяти с помощью полиграммы Автомат удобно описывать алгоритмически, рассматривая его функционирование последовательно при каждом переходе из одного состояния в другое за время одного внешнего такта Тi автоматного не прерывного времени. Наглядным способом задания классических ав томатов с памятью на триггерах является задание их в виде микропро граммы [125] или в более обобщенном виде автограммы [26].

Для алгоритмического описания иерархических автоматов с ав томатной памятью с общим состоянием, состоящим из частичных со стояний подавтоматов Si, предложен термин «полиграмма» по сле дующим соображениям. Во-первых, термин «микропрограмма», «ав тограмма» и другие способы задания автоматов с памятью на тригге рах ориентированы вполне обоснованно на описания функций пере ходов в автоматах только во время тактового момента ti, имеют силь ное ограничение, не позволяющее описывать работу автомата во вре мя внутреннего такта i автоматного непрерывного времени Тi. Во вторых, понятия «микропрограмма», «автограмма» и другие способы задания классических автоматов ориентированы на реализацию запо минаемого состояния в регистре на триггерах. В связи с этим, терми ны «микропрограмма», «автограмма» не подходят при описании об щего состояния регистров на схемах автоматной памяти. Термин же «полиграмма» ассоциируется со схемной реализацией управления на многоуровневых регистрах с многофункциональной системой органи зации памяти, которую называют многоуровневой иерархической ав томатной реализацией [64]. В-третьих, полиграмма ориентирована не только на преобразование входной информации в выходную инфор мацию, но и на изменение области запоминаемых состояний автомата, которая определяется сохраняющим еj() входным сигналом. Эта осо бенность позволяет использовать полиграмму при описании иерархи ческой структуры автомата, способной преобразовывать входную ин формацию и изменять внутреннюю структуру преобразования инфор мации [64].

Полиграмма описывает каждое состояние иерархического авто мата (ИА) А как объединение состояний подавтоматов Si.

a k ai (3.3) i В каждом пункте полиграммы описываются режимы работы по давтоматов Si за один внешний такт Т автоматного непрерывного вре мени. За один внешний такт Т ИА А воспринимает входное слово Rk(T), состоящее из совокупности элементарных рi(T) входных слов подавтоматов Si Rk p i (T ). (3.4) i Под воздействием входного слова Rk ИА А способен перейти в новое состояние as и выдать выходные сигналы Yki (і=1, 2, 3), состоя щие из совокупности выходных сигналов Yki определенных типов по давтоматов Si Yk1 (t ) Yi1 (t );

(3.5) i Yk2 (T ) Yi 2 (T );

(3.6) i Yk3 () Yi 3 (), (3.7) i где выходные сигналы Yi1 (t ), Yi 2 (T ), Yi 3 () определяются соответст венно по функциям выхода, описываемые в уравнениях (2.15)–(2.17).

При неизменяемых сохраняющих еі() входных сигналах по давтоматы Si функционируют в определенных блоках своих со i j стояний, а, следовательно, и ИА А функционирует в те же периоды времени в определенных блоках k своих состояний k i (3.8) i Каждое состояние аі подавтомата Si сохраняет свое значение при соответствующих сохраняющих еj входных сигналах. Изменение со храняющего еj входного сигнала в подавтомате Si происходит в такто вый момент t в зависимости от выходных сигналов Yi 2 (T ), поступаю щих от других подавтоматов Si в соответствии с алгоритмом решения задачи, и во время внутреннего такта сохраняющий еі() входной сигнал определяет область запоминаемых состояний (блок i состоя- j ний) подавтомата Si. Сохраняющие еі() входные сигналы однозначно определяют блоки i состояний, в которых работает подавтомат Si, а j совокупность Еk сохраняющих еі() входных сигналов однозначно оп ределяет блок k состояний, в которых работает ИА А Ek e j (3.9) j Пункт полиграммы при детерминированном элементарном вход ном слове Rk записывается в следующем виде:

KE. R1 Y11 – K1E1, R2 Y21 – K2E2, (3.10) ------------------- Rm Y21 – KmEm, где K – состояние ИА А;

Е – сохраняющий входной сигнал ИА А;

Rj(j=1, 2, …, m) – элементарное входное слово ИА А;

Kj(j=1, 2, …, m) – состояние ИА А, к которому совершается переход от состояния K при выполнении строки j;

Еj(j=1, 2, …, m) – сохраняющий входной сигнал, при котором запоминается состояние Kj;

Y ji ( j 1, 2,..., m) – выходной сигнал типа і ИА А.

Каждая строка (Rj Y11 – KjEj) пункта KE полиграммы описывается в виде Sk строк a1e1 p j1 Y ji1 a j1e j1, a2e2. p j 2 Y ji2 a j 2e j 2, (3.11) i aqeq. p jq Y jq a jqe jq, q – число строк Sk(k= 1, 2, …,, m где ), имеющихся в описании строки полиграммы j (j=1, 2, …, m);

pj – элементарное входное слово строки Sk;

i Y ji – выходной вектор строки Sk;

i aj – состояние подавтомата Si, к которому совершается i переход от состояния аі в состояние аk при выполнении строки Sk;

еі – сохраняющий входной сигнал состояния аі.

Такое описание поведения ИА А в состоянии КЕ является пунк том иерархического алгоритма функционирования автомата А.

Пункт полиграммы КЕ, как видно из описания поведения ИА А, имеет иерархическую структуру, то есть вначале описываются обоб щенные состояния К0, К1, …, Кm, обобщенные элементарные входные слова Rj(j=1, 2, …, m), обобщенные входные сигналы Е0, Е1, …, Еm, а затем каждая строка пункта полиграммы разворачивается в Sk(k= 1, 2, …,, m ) строк, которые реализуются в подавтоматах Si ИА А, осуществляя переход из одного состояния аі в состояние аk при вы полнении строки Sk. Во время функционирования ИА А некоторые, а, возможно, и все подавтоматы Si могут не изменять своих состояний на каком-то отрезке автоматного времени. Тогда при описании поли граммы ИА А в конце строк будут обозначения состояний, которые совпадают с начальным обозначением пункта полиграммы или пунк та строки полиграммы.

Каждая j-я строка пункта полиграммы КЕ состоит из следую щих элементов, функционирование которых описывается в автомат ном непрерывном времени Т: обозначение самого пункта КЕ, ото бражающего состояние К(-1), сохраняемое при входном сигнале Е(-1);

элементарного входного слова Rj(Т), состоящего из последо вательных соответственно информационного Х j(t) входного сигнала и сохраняющего Еj() входного сигнала;

Y ji выходных сигналов, опи i сываемых уравнениями (3.5)–(3.7).

Содержательный смысл каждой j-й строки полиграммы заклю чается в установлении связи между состояниями К(-1) ИА А в пре дыдущем внешнем такте Тi-1 и реакцией ИА А в следующем внешнем такте Тi- при переходе в состояние Кj().

Каждая j–я строка полиграммы может быть представлена из трех частей. Первая часть задает вектор Rj, вторая – вектор Y ji выход i ных сигналов, а третья часть определяет функцию F2 однозначного сохранения вектора Kj состояний либо функцию F3 укрупненного пе рехода в состояние Ks при векторе Е j сохраняющего входного сигна ла.

Вектор Еj сохраняющего входного сигнала при реализации функции F2 однозначного сохранения вектора Kj состояний задает определенный блок j запоминаемых состояний ИА А, в котором он функционирует в данный момент автоматного непрерывного вре мени Т, а при реализации функции F3 осуществляет укрупненный пе реход в состояние Ks в момент внутреннего такта автоматного не прерывного времени Т. Входной сигнал Еj обеспечивает межуровне вую связь подавтоматов Si в ИА А в момент внутреннего такта ав томатного непрерывного времени Т.

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

Преобразование тем совершеннее, чем более сложную и лучше организованную структуру системы она сопровождает.

Изменение внутренней структуры запоминания состояний в по давтоматах Si и в целом в ИА А, а также преобразование поступаю щей внешней информации в ИА А – это лишь две взаимосвязанные части одного и того же процесса преобразования информации в ИА А.

Опишем некоторые основные типы строк полиграммы.

Строку полиграммы, имеющий вид KE. Rj Y j – KjEj, (3.12) назовем общей строкой, подчеркивая этим термином, что в данной строке представлены все три вектора упомянутой команды.

Кроме общих строк в полиграмме могут быть и строки, в кото рых в явном виде представлен только один из векторов, в то время как другие векторы команды пропущены. Пропуск вектора изобра жают символом. Если пропущены компоненты вектора, то изобра жают вместо вектора его присутствующий компонент.

Например, строку вида KE. Еi Y j – KjEj при Еi Ej (3.13) назовем строкой перехода третьего рода, поскольку в ней описан переход, осуществляемый под воздействием только компоненты век тора Еi сохраняемых входных сигналов. В этом случае Хi=, а Еi Ri.

Строку вида KE. Rj – KjEj, (3.14) назовем просто строкой перехода, поскольку в ней представлен только переход в следующее состояние KjEj без вектора Y j выходных сигналов.

Строку вида KE. Rj Y j –, (3.15) назовем строкой выхода, поскольку в ней не представлен переход в вектор состояний Kj и не представлен вектор Ej сохраняющий новое состояние.

При совпадении векторов Еi и Ej в строке их можно опустить.

Строка тогда (например, общая) принимает такой вид K. Rj Y j – Kj, (3.16) а векторы Еi и Ej (Еi = Ej) в данном случае подразумеваются и задают вполне определенный блок j (K, Kj j) запоминаемых состояний.

Такая строка (3.16) называется С-вида и используется при описании микропрограммы или автограммы [26] автоматов Мили, Мура и С автомата, которые используют в качестве памяти триггеры в регист рах, состояния которых сохраняются при одном сохраняющем е() входном сигнале. Такое описание микропрограммы лишний раз под черкивает, что автоматы Мили, Мура и С-автомата являются под множеством многофункциональных автоматов Мараховского, на ос нове которых рассматривается полиграмма, описывающая ИА А, по строенный на схемах автоматной памяти.



Pages:     | 1 || 3 | 4 |   ...   | 5 |
 





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

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