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

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

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


Pages:     | 1 || 3 | 4 |   ...   | 6 |

«МИНИСТЕРСТВО ПРОСВЕЩЕНИЯ И НАУКИ УКРАИНЫ КИЕВСКИЙ НАЦИОНАЛЬНЫЙ ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ Л.Ф. МАРАХОВСКИЙ, Н.Л. МИХНО ОСНОВЫ ...»

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

Y Х е А Рис. 2.5. Обобщенная структура автомата А В реальных устройствах на входные узлы поступает по следовательная пара входных сигналов х(t) и е(), которые оп ределяют элементарное входное слово р(Т) = х(t), е(). При использовании в качестве схем памяти триггеров, все состоя ния элементов памяти которых сохраняются только при одном сохраняющем е() входном сигнале. Этот сохраняющий е() входной сигнал не в состоянии изменить состояние автомата.

Это и объясняет то, что в автоматах, в которых используются в качестве памяти триггеры, входной сигнал е() опускается, а функционирование самого абстрактного автомата может рас сматривается в автоматное дискретное время Однако, на уровне абстрактной теории автоматов Мара ховского, которые в дальнейшем будем просто называть авто матом М, с многофункциональной системой организации па мяти, которые могут использовать переходы по двум пере менным х(t) и е() в схемах автоматной памяти [55], значение сохраняющего е() входного сигнала необходимо учитывать и использовать для рассмотрения функционирования автоматов автоматное непрерывное время.

Схему автоматной памяти условно можно представить в виде матрицы, в которой столбики представляют собою под множества µi( ( i Q) ) состояний автомата, а строки – под j i множества j ( j Q) состояний автомата (табл.. 2.1) j Таблица 2. Матрица состояний схемы автоматной памяти µ1 µ2 ….. µn 0 ai ai … ai 1 ai ai … ai 2 ai ai … ai ………… … m ai ai … ai Триггеры и многостабильные схемы памяти (МСП) можно представить как строку 0 автоматной матрицы (табл. 2.1) в связи с тем, что все его ai состояния сохраняются при одном сохраняющем е() входном сигнале в одном множестве всех его состояний. Эти схемы обладают полнотой функций пере ходов, когда из каждого ai состояния можно под воздействием определенного входного х(t) сигнала перейти в любое, напе ред заданное, ai состояние схемы памяти;

а также полнотой системы выходов, когда каждое ai состояние отождествляется с выходным уi сигналом, который отличный от всех других.

В схемах автоматной памяти [14] переходы в момент t под воздействием входных х(t) сигналов могут происходить из од ного состояния в другое в определенном подмножестве i, а в моменты автоматного непрерывного времени Т под воздей ствием входного е() сигнала могут происходить переходы из одного состояния в другое в определенном подмножестве µi состояний автомата. Таким образом, в матричной схеме авто матной памяти возможны переходы по двум переменным х(t) и е() в автоматном непрерывном времени Т.

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

А = (Х, Е, YI, YII, YIII, Q,, e0, a0, o, e, y, 1, 2, 3), (2.14) у которого:

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

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

YI = { Y01, Y11,...,YK1 1 } – множество выходных сигналов типа 1( выходной алфавит типа 1):

YII = { Y02, Y12,...,YK2 1 } – множество выходных сигналов типа 2 ( выходной алфавит типа 2);

YIII = { Y03, Y13,...,YK3 1 } – множество выходных сигналов типа 3 ( выходной алфавит типа 3);

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

Абстрактный М-автомат А, который описывается векто ром (2.14), имеет два входа Х и Е та три виходи Y1, Y2, Y (рис. 2.6). Функционирование автомата исследуется в авто матном непрерывном времени Т [11–12].

Х Y А Y Y Е Рис. 2.6. Структурная схема абстрактного М-автомата А Для правильной (функционально надежной) работы авто мата А нельзя позволять, чтобы на входные узлы САП сигналы брали участие в создании в выходных сигналах, которые по цепи обратной связи подавались бы в тот же самый момент 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.7. Понятие об абстрактных автоматах М, с пере страиваемой структурой запоминания состояний Многофункциональные автоматы на схемах автоматной памяти (САП) имеют возможность с помощью автомата настройки U выполнять комутацию функций возбуждения и выходов САП, как это осуществлялось при реализации в автоматах с памятью на тригерах (рис. 2.4), а с помощью (g-1) ступенчатого (g 1) автомата стратегии АМ, который гене рирует входные е() сохраняющие сигналы для абстрактного М-автомата А, выполняется перестройка (регенерация) функ ций сохранения состояний памяти автомата, что является но вым в теории иерархических, параллельных многофункцио нальных автоматов.

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

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

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

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

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

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

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

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

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

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

ху уу Ау Х Ey уМ Y хМ АМ уH EH Рис. 2.9. Открытая многоуровневая структура Определение 2.2. Закрытою многоуровневою структурою устройства памяти МУСП с многофункциональною системою организации назовем автомат, который состоит из двух устройств: управляемой МСП Ау и многофункционального автомата стратегии АМ, которые имеют объединенные множества состояний, входные Х и выходные Y алфавиты.

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

ху уу Ау Y Х Ey уМ хМ АМ Рис. 2.10. Закрытая многоуровневая структура Триггеры и регистры на триггерах представляют собою закрытые структуры памяти. САП вместе с автоматом стра тегии может создавать закрытые или открытые многоуров невые структуры устройств памяти с многофункциональною системою организации.

Иерархический абстрактный автомат А с памятью на САП рассматривается как g-ступенчатое (g 1) устройство, состоящее из регистров Rj(j = 1, 2, …, g), которые взаемодействуют одновременно, і двух комбинационных схем КС1і, КС2і (і = 1, 2,..., g) на каждой ступени. На уровне g (верхнему) иерархический g-ступенчатый автомат А способен функционировать как многофункциональный автомат 1-го, 2 го, а так же 3-го рода, который имеет (g – 1)-ступенчатый автомат стратегии, использующийся для сохранения определенного блока і состояний соответствующего автомата на уровне g.

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

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

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

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

Показано, что автоматы М g–уровневой ступени на САП имеют качественно новые (по сравнению с автоматами на тригге рах) переходы из одного состояния в другое под воздействием входных сигналов еj(): укрупненные, вероятностные и нечеткие.

§ 2.8. Понятие об абстрактных вероятностных автома тах 3-го рода Различия между дискретными автоматами, которые опи сывают функционирование устройств ЭВМ и даже самих ЭВМ, и моделями, которые использует человеческий мозг, со стоит в той способности, которая позволяет человеку думать и делать заключения в неточных, неколичественных, нечетких, расплывчатых терминах [40], принимая в расчет параллельные соображения как общего, так и сопутствующего, частного ха рактера [49].

Основным элементом человеческого мозга является ней рон, важнейшую роль в котором играют перестройки надмо лекулярных структур в различных частях нервной клетки, а также волны структурных перестроек, сопровождающие пере дачу информации в пределах данного нейрона и от нейрона к другому нейрону [15–16;

49]. Нейронную память представля ют в матричном виде, управляемую по двум координатам воз буждающими и тормозящими входными сигналами и способ ную выполнять структурную перестройку передачи информа ции в иерархических ансамблях нейронов [29].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

yB1 : ар E j – функция вероятностного укрупненного перехода, реализующая отображение D a p e j в j.

y Другими словами, функция yB1 некоторым парам „не сохраняемое состояние – сохраняющий входной сигнал” (ар(t), е()) ставит в соответствие состояние автомата а()= yB1 (ар(t), е()), где ар(t) j, а() j, ар(t) а();

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

B 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 ));

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

(2.22) 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 определяемый как одиннадцатикомпонентный кортеж или вектор [9]:

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

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

Ев2 = { e1B 2, e2B 2,... eR 21 } – множество вероятностных сохра 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;

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

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

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

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

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

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

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

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

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

a() B 2 (a(t ), e j (), P0, Pe );

B B (2.24) 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.9. Понятие об абстрактных нечетких автоматах 3-го рода Абстрактные нечеткие автоматы 3-го рода рассматрива ются при поступлении на их входные узлы элементарных не четких рн(Т) входных слов (рн(Т) = хр(t), ев()) в автоматном непрерывном времени Т.

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

Ан = (хр, Е, Ев, YIII, Q, Qн,, e0, a0, o, yH, 3, Р(0), Ре), (2.25) H H у которого:

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

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

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

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

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

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

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

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

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

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

yН : Q ЕН j – функция нечеткого укрупненного пе рехода, реализующая отображение D Q E Н в j.

y Другими словами, функция Н некоторым парам „ не y сохраняемое состояние – нечеткий сохраняющий вход ной сигнал” (ар(t), еН()) ставит в соответствие состоя ние автомата а()= yН (ар(t), еН()), где ар(t)і, а()j, ар(t) а();

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

н н (2.26) y L () н (a(), e н ()), a (t ) j, a() j ;

р i 0, 1, 2,...;

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

0 Pн 1.

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

§ 2.10. Классификация детерминированных абстрактных автоматов Рассмотрим классификацию детерминированных абст рактных автоматов по использованию типов их выходных сигналов, как это осуществлено в классических абстрактных автоматах Мили, генерирующих выходные у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.

Отметим, что абстрактные монофункциональные автома ты Мили (1-го рода), Мура (2-го рода) и С-автомат являются частным случаем абстрактных многофункциональных автома тов 1-го, 2-го рода и С-автомата.

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

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

Вероятностные абстрактные автоматы 3-го рода описыва ют вероятностные переходы из вполне определенного а(-1) состояния в состояние а() целого подмножества состояний вполне определенного блока j состояний в соответствии с оп ределенной вероятностью Ре. Такие переходы могут быть кон структивными, если учесть, что они выполняются в аппарату ре устройств ЭВМ и могут быть определяемыми при испыта ниях аппаратуры. Такие переходы могут быть очень полезны при использовании их в алгоритмах программ в связи с тем, что отсев ненужных вариантов повышает «машинный» интел лект программы.

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

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

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

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

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

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

26;

110;

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

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

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

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

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

§ 3.2. Табличные и графические способы задания клас сических автоматов Мили и Мура Задание классического монофункционального абстрактно го автомата А сводится к заданию функций переходов и функций выходов. Из соображений практики остановимся более подробно на способах задания автоматов с помощью таблиц и графов. Обычно для автоматов Мили функции пере ходов и выходов (2.3) задаются соответствующими таблицами с двумя входами. Столбик таблицы переходов 3.1 и таблицы выходов 3.2 обозначает состояние автомата аi (аi Q), а стро ка – входной сигнал хk (хk Х).

Таблица переходов 3.1 Таблица выходов 3. а(t) = (а(t – 1), х(t)) у(t) = (а(t – 1), х(t)) а1 а2 а3 а4 а1 а2 а3 а х1 а2 а3 а4 а1 х1 у2 у3 у4 у х2 а4 а1 а2 а3 х2 у4 у1 у2 у На пересечении столбиков и строк таблицы переходов 3. ставится новое состояние автомата аs(t), в которое автомат пе реходит под воздействием входного сигнала хk(t) из преды дущего состояния аi(t – 1), то есть аs(t) = (аi(t – 1), хk(t)).

На пересечении столбиков и строк таблицы выходов 3. ставится выходной сигнал автомата уs(t), которое автомат вы дает под воздействием входного сигнала хk(t) и предыдуще го состояния аi(t – 1), то есть уs(t) = (аi(t – 1), хk(t).

Для автоматов Мура функции переходов и выходов (2.4) задаются соответствующей одной отмеченной таблицей 3.3.

Столбик таблицы переходов в отмеченной таблице 3.3 задает ся аналогично, как это делается в таблице переходов 3.1 авто мата Мили. Это связано с тем, что функции переходов в авто матах Мили и Мура совпадают (см. формулы (2.3) и (2.4)).

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

Отмеченная таблица переходов 3. автомата Мура а(t) = (а(t – 1), х(t)), у(t) = (а(t)) у1 у2 у3 у а1 а2 а3 а х1 а2 а3 а4 а х2 а4 а1 а2 а Таким образом, с помощью таблиц 3.1 – 3.3 можно полно стью задать функционирование автомата Мили или Мура в ав томатном дискретном времени t.

Более наглядно задается функционирование автомата Ми ли с помощью направленных графов, у которых состояния аi автомата отображается в кружочках (вершинах графа), а пере ходы из одного состояния аi в другое аk отображается стрелоч кой, над которой устанавливается символ хk входного сигнала, способного перевести автомат в состояние аk. Выходные сиг налы уi автомата Мили отображаются рядом с хk входными сигналами, в связи с тем, что они зависят от тех же перемен ных и появляются в одно и тоже автоматное время t.

Функционирование автомата Мура с помощью направлен ных графов, у которых состояния аi автомата отображается в кружочках (вершинах графа), а переходы из одного состояния аi в другое аk отображается стрелочкой, над которой устанав ливается символ хk входного сигнала, способного перевести автомат в состояние аk. Выходные сигналы уk автомата Мура отображаются рядом с состояниями аk, в которые перешел ав томат. Это связано с тем, что уk выходной сигнал появляется на выходном узле после перехода автомата в новое аk состоя ние, о чем говорит сдвинутая функция выходов автомата Му ра.

Для наглядности представим таблицу переходов 3.1 и таб лицу выходов 3.2 автомата Мили в изображении направленно го графа (рис. 3.4), а отмеченную таблицу переходов 3.3 авто мата Мура в изображении направленного графа (рис. 3.5).

х2, у х1, у а1 а х2 х1 х у4 у1 у х х1, у4 у а а х2, у Рис. 3.4. Направленный граф автомата Мили х у у х а1 а х2 х1 х х х а а у у х Рис. 3.5. Направленный граф автомата Мура § 3.3. Табличные способы задания многофункциональ ных абстрактных детерминированных автоматов Задание многофункциональных абстрактных автоматов 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. 0 : Q(-1) X(t) Q(t) 02 : Q(-1) X(t) Q(t) 1 а 0 а 1 а 2 а 3 2 а 0 а 4 а 5 а хi хi а1 а2 а1 а х1 a4 a0 a6 a х а2 а3 а0 а х2 a5 a6 a4 a х Строки таблицы сохранения состояний (табл. 3.8) соот ветствуют сохраняющим е() входным сигналам, а столбцы – а() состояниям автомата. В каждой строке на пересечении со столбцами в таблице сохранения состояний ставится соот ветствующее состояние а()= е(а(t), е()), где а j, а(t) = а() (j Q), сохраняемое под воздействием сохраняющего е() входного сигнала во время внутреннего такта автомат ного непрерывного времени Т, а в остальных случаях ставятся прочерки.

Таблица выходов 3.6 Таблица выходов 3. 1 : Q(-1) X(t) YI(t) 1 : Q(-1) X(t)YI(t) 1 а 0 а 1 а 2 а 3 2 а 0 а 4 а 5 а хi хi у1 у2 у3 у х1 у5 у5 у6 у х у2 у1 у4 у х2 у6 у7 у5 у х Таблица сохранения состояний 3.8.

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

Автоматы 1-го и 2-го рода способны осуществлять функ ции переходов в тактовый момент t автоматного непрерывно го времени Т под воздействием информационных х(t) входных сигналов.

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

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


Автоматы 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-го рода реализуется во время внутреннего тактового момент в новое состояний под воздействием сохраняющих е() входных сигналов и состоя ний автомата а(t) Функция выходов 3, во первых, является сдвинутой по сравнения с началом внутреннего тактового момента, а также зависит только от вновь установленного состояния а() и от сохраняющего е() входного сигнала, то есть у()= 3(а(), е()), где у YIII.

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

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

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

Таблица переходов 3.15 Таблица переходов 3. 0 : Q(-1) хр(t) ар(t) 02 : Q(-1) хр(t) ар(t) 1 а 0 а 1 а 2 а 3 2 а 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. 0 : Q(-1) X(t) Q(t) 02 : Q(-1) X(t) Q(t) 1 а 0 а 1 а 2 а 3 2 а 0 а 4 а 5 а хi хi а1 а2 а1 а х1 a4 a0 a6 a х а2 а3 а0 а х2 a5 a6 a4 a х Отмеченная таблица вероятностных переходов 3. yB 2 : а(t)еВ2() µі(аB()) 3 2 : а(t)еВ2()YIII2 (ув2()) B B ув y1( P11 ) y2( P12 ) yn0( P1n0 ) µі … µі µ1 µ2 µn В еj e0 а1( P11 ) a2( P12 ) … an0( P1n0 ) …… … … em an1( P1n1 ) an2( P1n 2 ) … anm( P1mn ) Вероятностные переходы в автомате 3-го рода первого типа происходят в определенном блоке j состояний, а в авто мате 3-го рода второго типа происходят в определенном блоке µі состояний. Таким образом, вероятностные автоматы 3-го рода первого типа и вероятностные автоматы 3-го рода второ го типа осуществляют вероятностные переходы в состояния вполне определенных подмножеств соответствующих блоков j и µі состояний с определенной мерой вероятности.

§ 3.5. Табличный способ задания абстрактных нечет ких автоматов 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.6. Графические способы задания переходов в многофункциональных абстрактных автоматах Абстрактные автоматы с памятью используются для реа лизации функций однозначного перехода в новое состояние аі(t) при соответствующем входном сигнале х(t) при условии сохранения этого состояния после окончания сигнала х(t), то есть во времени внутреннего такта автоматного непрерыв ного времени Т.

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

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

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

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

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

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

Таким образом, многофункциональные абстрактные авто маты увеличивают типы переходов, используемых в класси ческих абстрактных автоматах Мили и Мура, расширяют по нятие функционирования автомата с дискретного автоматного времени t до непрерывного автоматного времени T, что дает возможность более глубоко исследовать их работу.

Блок а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.10. Нечеткий переход в автомате 3-го рода § 3.7. Математическая модель иерархического абстрактного автомата с многофункциональной системой организации памяти Последовательные многофункциональные автоматы Ма раховского 1-го, 2-го и 3-го рода, имеющие два множества входных алфавитов: Х – информационный входной алфавит и Е – сохраняющий входной алфавит, способен настраиваться другим многофункциональным автоматом через множество букв еj (еj Е) сохраняющего входного алфавита на функцио нирование в определенном блоке j (подмножестве) своих со стояний. В этом случае образуется многоуровневая (иерархи ческая) структура абстрактного Fи–автомата из последова тельных многофункциональных подавтоматов Si (i=1, 2, …, n).

Организация такой объединенной структуры иерархического автомата (ИА) представлена на рис. 3.11.

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

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

Определение 3.2. Математической моделью иерархическо го дискретного устройства с многофункциональной системой организации памяти является абстрактный иерархический Fи– автомат, определяемый как N-компонентный вектор Fи = (S1, S2, …, SN), (3.1) компоненты Si которого задаются шестнадцатикомпонентным вектором Yn Xn Sn En 1 Zn- Y Yn Х Y Y X S E 1 Z Y Yn Рис. 3.11. Иерархический абстрактный Fи–автомат Si = (Xi, Ei, Zi, Yi I,Yi II,Yi III, Qi, i, ei, ai, i, i, i, 0 0 o e y i, i, i (3.2) ) 1 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 – однозначная функция переходов;

o 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, 1, 2, 3 ) (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 i (t 0 ) X i. Во время последующего внут реннего такта 0 начальное состояние а0 сохраняется под воз действием начальных сохраняющих ei (0) входных сигналов.

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

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

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

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

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

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

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

Полиграмма описывает каждое состояние ИА А как объе динение состояний подавтоматов 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 Yk (t ) Yi1 (t );

1 (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 состояний, в которых работает подав j томат Si, а совокупность Е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 Y ji1 a j1e j1, j a2 e2. p j 2 Y ji2 a j 2 e j 2, (3.11) i aq eq. p jq Y jq a jq e jq, где q – число строк Sk(k= 1, 2, …,, m ), имеющихся в описании строки полиграммы j (j=1, 2, …, m);

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

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

i a j – состояние подавтомата 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 выходных сигналов, а третья часть определяет функцию F i однозначного сохранения вектора Kj состояний либо функцию F укрупненного перехода в состояние 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) называется С-вида ис пользуется при описании микропрограммы или автограммы [8] автоматов Мили, Мура и С-автомата, которые используют в качестве памяти триггеры в регистрах, состояния которых сохраняются при одном сохраняющем е() входном сигнале.

Такое описание микропрограммы лишний раз подчеркивает, что автоматы Мили, Мура и С-автомата являются подмноже ством автоматов Мараховского, на основе которых рассмат ривается полиграмма, описывающая ИА А, построенный на автоматах Мараховского.

Отметим одну важную особенность выходных векторов Y ji ИА А. Упомянутые выше компоненты Yki векторов Y ji (3.5)– i i i (3.8) одновременно во внешнем такте Тогут инициировать различные операции в управляемых объектах, а также функ циональное отключение одного из подавтоматов Si ИА А, при определении его ненадобности или ошибочности в работе.

Это свойство является важным при создании отказоустойчи вых цифровых устройств [93].

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

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

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

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

§ 3.8. Формулирование полиграммы Работать с полиграммой проще, если соблюдать следую щие правила.

1. Пункт полиграммы удобно обозначать двумя номе рами, отмеченными символами K и E. Например, 12K,2E.

2. Начальный пункт обычно имеет номер 1K,1E, а ос тальные пункты полиграммы нумеруются числами до максимального номера с символом K и до макси мального номера с символом E.

3. Пункты в полиграмме целесообразно располагать в порядке возрастания в начале номера с символом K, без изменения номеров возле символа E, а после из менения номера с символом E нумерацию с симво лом K можно начинать с начала, то есть с номера 1K.

4. Пункты, образующие в полиграмме непрерывную последовательность при одном номере с символом E, удобно нумеровать непрерывным рядом чисел.

5. Установочные пункты не имеют конкретных номе ров, так как при подсчете количества пунктов в поли грамме они не учитываются. Целесообразно место установочного пункта определять в начале нумера ции чмсел с символом K при определенном номере с символом E.

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

Задание автомата в табличном виде, в виде графа, в виде полиграммы или каким-то другим способом является творче ством проектировщика. Проектировщик перед заданием ав томата, с одной стороны, должен полностью разобраться в работе объекта и временных последовательностях управляю щих воздействий, необходимых при управлении объектом, а с другой стороны – владеть методами формального синтеза ав томатов по полиграмме на доступной ему элементной базе современных сверхбольших интегральных схем (СБИС). Про верка правильной (корректной) работы полиграммы или спроектированного управляющего устройства может быть выполнена средствами моделирования устройства на ЭВМ [45;

60].

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

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

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

1. Начинать описание полиграммы целесообразно с общей информации алгоритма, в рамках которого идет обработка всего процесса решения задачи.

2. Процесс расщепления общей информации алгоритма на уровни возможен при иерархическом характере обработки информации во время решении задачи.



Pages:     | 1 || 3 | 4 |   ...   | 6 |
 





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

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