Абстрактная теория автоматов

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

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

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

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

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

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



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



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

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



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

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

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

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

8. Понятие об абстрактных вероятностных автоматах 3-го рода

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

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

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

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

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

р_в1(Т) = х_р(t), e_j(?),(18)

где х_р(t) -информационный входной сигнал (х_рХ), который однозначно устанавливает состояние памяти автомата, не сохраняемое ни при одном сохраняющем e_j(?) входом сигнале;

р_в2(Т) = х_і(t), (?),(19)

где (?) - вероятностный сохраняющий входной сигнал (Е).

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

Вероятностное слово первого типа (18) позволяет осуществлять вероятностный переход в тактовый внутренний момент ? из а_р(t) состояния, которое не запоминается, в неопределенное состояние вполне определенного р_j блока состояний автомата, под воздействием сохраняющего e_j(?) входного сигнала.

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

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

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

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

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

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

Усилиями Рамсея, Эрдёша, Ван дер Вардена и многих других были заложены основы теории, носящей имя Рамсея. Для нас очень важен сам результат теории Рамсея, утверждающий, что каждое достаточно большое множество чисел, точек или объектов обязательно содержит высоко упорядоченную структуру [133; 144]. С этой точки зрения мы и подходим к созданию вероятностных и нечетких автоматов 3-го рода.

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

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

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

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

А_В1 = (х_р, Е, , Q, р, e₀, a₀, a_р, д_o, , , Р_е), (20)

у которого:

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

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

· = {} - множество вероятностных выходных сигналов типа 3 (выходной вероятностный алфавит типа 3);

· Q = {a₀, a₁,…, a_m1} - произвольное множество запоминаемых состояний автомата (алфавит состояний);

· р = {р₀, р₁,…, р_R-1} -множество блоков р_j состояний (алфавит блоков состояний);

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

· a₀ р₀ - начальное состояние автомата;

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

· : а_р E> р_j - функция вероятностного укрупненного перехода, реализующая отображение в р_j. Другими словами, функция некоторым парам „несохраняемое состояние - сохраняющий входной сигнал” (а_р(t), е(?)) ставит в соответствие состояние автомата а(?)=(а_р(t), е(?)), где а_р(t) р_j, а(?) р_j, а_р(t) а(?);

· : Q E> -вероятностная функция выходов типа 3, реализующая отображение в . Другими словами, функция : некоторым парам „несохраняемое состояние - сохраняющий входной сигнал” (а_р(t), е(?)) ставит в соответствие выходной сигнал автомата у^в1(?)=(а_р(t), е(?)), где у ;

· Р_е(а_ре_j) - система условных вероятностей.

Система условных вероятностей Р_е, заданных для каждой пары (а_р(t), е(?)) на множестве р_j ( р_j Q; Y_III, где Y_III выходные сигналы автомата 3-го рода) характеризует вероятность перехода автомата в состояние а_s(?) с выдачей сигнала у_k(?), который отображает состояние а_s(?) автомата, при условии, что автомат предварительно был установленный в состояние а_р(t), которое не запоминается, и на его входы подан сохраняющий е_j(?) входной сигнал, способный сохранять все множество состояний блока р_j состояний (а_s р_j).

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

(21)

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

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

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

А_В2 = (Х, Е_в2, , Q, р, e₀, a₀, д_o, , , Р⁽⁰⁾, Р_е), (22)

у которого:

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

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

· = {} - множество вероятностных выходных сигналов типа 2 (выходной вероятностный алфавит типа 2);

· Q = {a₀, a₁,…, a_m1} - произвольное множество запоминпемых состояний (алфавит состояний);

· р = {р₀, р₁,…, р_R-1} -множество блоков р_j состояний (алфавит блоков состояний);

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

· a₀ р₀ - начальное состояние автомата;

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

· : Q Е_в2> р_j - функция вероятностного укрупненного перехода, реализующая отображение в р_j. Другими словами, функция некоторым парам „состояние - вероятностный сохраняющий входной сигнал” (а (t), е^В2(?)) ставит в соответствие состояние автомата а(?)= (а(t), е^В2(?)), где а(t) р_і, а(?) р_j, а(t) ? а(?) (а (t), а(?)Q);

· : Q Е_в2> -вероятностная функция выходов типа 3, реализующая отображение в . Другими словами, функция : некоторым парам „состояние - вероятностный сохраняющий входной сигнал” (а (t), е^В2(?)) ставит в соответствие выходной сигнал автомата у^в2(?)=(а (t), е^В2(?)), где у ;

· Р⁽⁰⁾={P₀, P₁, P₂, …, P_k-1,} -начальное распределение вероятностей блока р_j состояний автомата;

· Р_е(а е^В2_j) - система условных вероятностей.

Система условных вероятностей Р_е, заданных для каждой пары (а(t), е^В2_j (?)) на множестве р_j ( р_j Q; Y_III, где Y_III выходные сигналы автомата 3-го рода) характеризует вероятность перехода автомата в состояние а_s(?) с выдачей сигнала у^в2(?), который отображает состояние а_s(?) автомата, при условии, что автомат предварительно был установленный в состояние а(t) и на его входы подан вероятностный сохраняющий е^В2_j (?) входной сигнал, способный сохранять все множество состояний блока р_j состояний (а_s р_j).

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

(23)

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

9. Понятие об абстрактных нечетких автоматах 3-го рода

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

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

А_н = (х_р, Е, Е_в, , Q, Q_н, р, e₀, a₀, д_o, , , Р⁽⁰⁾, Р_е), (24)

у которого:

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

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

· Е_Н = {} - множество нечетких сохраняющих входных сигналов (входной нечеткий сохраняющий алфавит, где );

· = {} - множество нечетких выходных сигналов автомата 3-го рода (выходной нечеткий алфавит);

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

· Q_Н = {a₀, a₁,…, a_m1} - произвольное нечеткое подмножество состояний (алфавит нечетких подмножеств состояний, где );

· р = {р₀, р₁,…, р_R-1} -множество блоков р_j состояний (алфавит блоков состояний);

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

· a₀ р₀ - начальное состояние автомата;

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

· : Q Е_Н> р_j - функция нечеткого укрупненного перехода, реализующая отображение в р_j. Другими словами, функция некоторым парам „ несохраняемое состояние - нечеткий сохраняющий входной сигнал” (а_р(t), е^Н(?)) ставит в соответствие состояние автомата а(?)= (а_р(t), е^Н(?)), где а_р(t)р_і, а(?)р_j, а_р(t) ? а(?);

· : Q_Н Е_Н> - нечеткая функция выходов, реализующая отображение в . Другими словами, функция : некоторым парам „несохраняемое состояние - нечеткий сохраняющий входной сигнал” (а_р(t), е^Н(?)) ставит в соответствие выходной сигнал автомата у^Н(?)=(а_р(t), е^Н(?)), где у^Н ;

· Р⁽⁰⁾={P₀, P₁, P₂, …, P_k-1,} -начальное распределение нечеткого подмножества Q_Н состояний автомата;

· Р_Н(а_р е^Н_j) - система условных вероятностей.

Система условных вероятностей Р_Н, заданных для каждой пары (а_р(t), е^Н(?)) на множестве Q_Н ( Q_Н Q; Y_iii, где Y_III выходные сигналы автомата 3-го рода) характеризует вероятность перехода автомата в состояние а_s(?) с выдачей сигнала у_k(?), который отображает состояние а_s(?) автомата, при условии, что автомат предварительно был установленный в состояние а_р(t) и на его входы подан нечеткий сохраняющий е^Н_j(?) входной сигнал, способный переводить автомат из а_р(t) состояния в а(?) состояние блока р_j состояний, который принадлежит нечеткому подмножеству Q_Н состояний (р_j Q_Н).

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

(25)

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

10. Классификация детерминированных абстрактных автоматов

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

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

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

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

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

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

11.Классификация недетерминированных абстрактных автоматов

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

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

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

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

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

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

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

Все абстрактные автоматы с 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-го рода использовать для определения выходных сигналов катастрофических отказов первого типа, когда у⁴(t) = л₄(х_р(t), a_р(t)), и использовать для определения выходных сигналов катастрофических отказов второго типа выходной сигнал вероятностного автомата 3-го рода у^в1(Д) = л₃(a_р(Д), е(Д)). Выходной сигнал у⁴(t) автомата 4-го рода отличается от выходного сигнала у¹(t) автомата 1-го рода тем, что использует в функции выходов не состояние a(Д-1), а состояние a_р(t), которое установлено устанавливающим х_р(t) входным сигналом. Таким образом, автомат, использующий выходной сигнал у⁴(t) можно назвать автоматом четвертого рода в связи с тем, что все автоматы определяются по своим выходным сигналам. На самом деле, выходной сигнал у⁴(t) может дополнительно добавляться в выходных сигналов любых автоматов с памятью на базовых схемах памяти. Выходной сигнал у^в3(Д) автомата 3-го рода появляется после вероятностного перехода схемы памяти в одно из запоминаемых состояний базовой схемы памяти при воздействии сохраняющего е(Д) входного сигнала.

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

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

Заключение

автомат триггер схема

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

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

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

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

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

Литература

1. Ricardo, Argenton Ramos AIRDoc - An Approach to Improve the Quality of Requirements Document / Ricardo Argenton Ramos. - М.: LAP Lambert Academic Publishing, 2017. - 128 c.

2. Администратор информационных технологий / IT Manager, №2, 2013. - М.: ИТ Медиа, 2017. - 970 c.

3. Администратор информационных технологий / IT Manager, №4, 2013. - М.: ИТ Медиа, 2016. - 312 c.

4. Алиев, В. С. Информационные технологии и системы финансового менеджмента / В.С. Алиев. - М.: ИНФРА-М, 2016. - 320 c.

5. Андерсон, Джордж У. Лучшие практики внедрения SAP / Андерсон Джордж У.. - М.: ЛОРИ, 2017. - 899 c.

6. Брусакова, И. А. Информационные системы и технологии в экономике / И.А. Брусакова, В.Д. Чертовской. - М.: Финансы и статистика, 2017. - 352 c.

7. Данелян, Т. Я. Экономические информационные системы (ЭИС) предприятий и организаций / Т.Я. Данелян. - М.: Юнити-Дана, 2015. - 284 c.

8. Демистификация ИТ. Что на самом деле информационные технологии дают бизнесу. - М.: Альпина Паблишер, 2015. - 296 c.

9. Журнал Windows IT Pro/RE, июнь 2013. - М.: Открытые Системы, 2016. - 244 c.

10. Затонский, А. В. Информационная поддержка принятия решений при управлении филиалом вуза / А.В. Затонский, С.А. Варламова, Е.В. Измайлова. - М.: РИОР, Инфра-М, 2016. - 334 c.

11. ИТ инфраструктура бизнеса / IT Expert, №3, 2013. - М.: ИТ Медиа, 2016. - 978 c.

12. ИТ инфраструктура бизнеса / IT Expert, №6, 2012. - М.: ИТ Медиа, 2015. - 593 c.

13. ИТ инфраструктура бизнеса / IT Expert, №7, 2012. - М.: ИТ Медиа, 2015. - 925 c.

14. Информационная Война Против Российской Федерации: Институализация Информационного Противоборства В Контексте Реализации Стратегии Национальной Безопасности Российской Федерации. Материалы Круглого Стола / Коллектив авторов. - Москва: Мир, 2016. - 113 c.

15. Информационные технологии в менеджменте (управлении). Учебник и практикум. - М.: Юрайт, 2015. - 480 c.

16. Информационные технологии для финансовых менеджеров. - М.: Издательский центр БГУ, 2017. - 480 c.

17. Компьютерное моделирование менеджмента / А.Ф. Горшков и др. - М.: Экзамен, 2016. - 528

Размещено на Allbest.ru