УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ КОНЕЧНЫХ АВТОМАТОВ Советский патент 1973 года по МПК G01N1/00 G06F17/10 

;1

Изобретение относится к области вычислительной техяики.

Известны устройства для моделирования конечных автоматов, содержащие сумматор по модулю два и блок управления, соединенный двусторонними СВЯЗЯМИ с блоком памяти, входы которого подключены ко входам устройства, выходы блока памяти через элементы «И, вторые входы которых подключены к соответствующим выходам триггера, подключенного входами к выходу дешифратора служебных символов, соединены со входами регистра функций и регистра аргументов, выходы первого из которых через дешифратор функций выхода и дешифратор функций возбуждения и соответствующие им третий и четвертый элементы «И соединены со входами регистра состояний, выходы регистра аргументов через дешифратор аргументов соединены со входами коммутатора, вторые входы которого подлючены к выходам регистра состояний, а третьи входы через регистр Hai6opa аргументов соединены со входами устройства, к выходам которого подключены выходы регистров функций выхода и состояний.

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

Предлагаемое устройство с целью его

|2

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

На чертел е приведена блок-схема устройства. Устройство содержит блок памяти /,

блок управления 2, дешифратор сл жебных символов 3, элементы «И 4 и 5, триггер 6. регистр аргументов 7, регистр функций 8, дешифратор аргументов 9, дешифратор функций возбуждения 10, дешифратор функций

выхода //, элемент «И 12, регистр функций выхода 13, блок вычисления булевых функций 14 с выходами 15 и 16, элемент «И 17, регистр . состояний 18, сумматор по модулю два 19, коммутатор 20, регистр набора аргументов 21.

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

формах, по которым составляется програмMai. Для этого каждая булевая функция записывается в виде одного слова. Например, функция yi XiX2- -XiX2 будбт запивана следующим образом: а t/i А JCi.Cj Лл:1 , где а - служебный символ, за которым следует сИ)Мвол функции r/i; А - служебный символ раздела между дизъюнкТИвными членами, служащий также вместо знака: равенства; - служебный символ конца программы, который ставится в конце последнего выражения функции; аргументы. Подобным образом записываются все подряд выражения булевых функций (функций возбуждения и выходов), образующих одно слово, в конце которого стоит знак со. В полученном слове каждой букве присваивается определенное двоичное число - двоичный код. Полученный ряд кодов записывается в блок памяти 1. Кроме кода каждому аргументу присваивается еще определенное значение «О или «1, которые вместе с кодом аргумента вносятся в каждую ячейку блока памяти- }. Это значение а1ргумента вносится в специальный разряд ячейки блока памяти. Если аргумент входит в формулу без знака отрицания, то в специальный разряд заносится «1, если со знаком отрицания, то «О. Служебным символам «А, «а и «со, а также символам функций присваивается «I в специальном разряде. Для получения значений булевых функций производится вывод из блока памяти всех символов (т. е. их кодов и значений в специальном разряде) в порядке их записи. Первый выведенный из блока памяти символ «а дешифрируется с помощью дешифратора служебных символов 3 и устанавливает триггер 6 в состояние, при котором на элемент «И 4 подается разрешающий потенциал. Следующий символ г/i проходит через элемент «И 4, попадает на регистр функций и дешифрируется дешифратором с|)ункций возбуждения 10 или дешис|)ратором функций выхода //, в зависимости от того, является ли этот символ функцией возбуждения или выходов. В результате этого на одном из выходов дешифратора функций возбуждения 10 или дешифратора функций выхода // появляется разрешающий потенциал, подаваемый на элементы «И 12 и 17. Следующий за «t/г символ «А, дешифрируясь с помощью дешифратора служебных символов сЗ, перебросит триггер 6. При этом будет подан разрещающий потенциал на элемент «И 5. Код аргумента, следующего за «А, будет подан на регистр аргументов 7 и дешифрирован с помощью дещифратора аргументов 9. В результате на одном из выходов дещифратора аргументов 9 появляется разрешающий потенциал, который, воздействуя на коммутатор 20, произведет выбор аргумента на1 регистре набора аргументов 21 или регистра состояний 18. Это значение аргумента подается на один из входов сумматора по модулю два 19, на второй вход которого подается значение аргумента из специального разряда блока памяти. Если окажется, что значение аргумента в специальном разряде блока иа1мяти 1 и его значение на выходе коммутатора 20 будут одинаковы, то будет выдана «1 на выходе а сумматора по модулю два 19. Если же значения аргументО|В на входе сумматора по модулю два 19 не совпадают, то «1 появится на выходе Ь. После этого поступает следующий аргумент Hai регистр аргументов 7 и с ним производится такая же операция. Поступление сигнала иа любой из входов а, Ь, а, и А блока вычисления булевых функций 14 означает появление на его обобщенном входе любой из перечисленных букв а, Ь, а или Д. Эти буквы составляют входной алфавит этого блока. Сигнал на выходе /5 блока вычисления булевых функций 14 появляется в том случае, если входное слово будет содержать такую его часть, в которой между буквами А будут только буквы а. Сигнал на выходе 16 блока вычисления булевых функций 14 появляется в том случае, если входное слово будет содержать всеми парами букв А хотя бы одну букву Ь. При этом имеется в виду, что входное слово образуется в результате обработки алгебраического выражения одной из булевых функций. Если условия появления сигналов на выходах 15 и 16 выразить Hai языке регулярных выражений н обозначить как события 5 и Sz, то последние будут иметь следующие выраS, ir: а.А (и {а + 61 А + а «) Ь а + + 6} Д1а}а}Д |а + о + Л|а, Sj : аД (Ь {а+Ь} Д+а а+6|Д) Ь la+b Д + + а а Ь а- -blA} у.. Приведенные выражения представляют собой алгоритм функционирования блока вычисления булевых функций 14. Сигнал на выходе 15 появляется в том случае, когда булевая функция равна «1, а сигнал на выходе 16, если она равна «О. Любое из значений функций выходов будет зафиксировано на регистре функций выхода 13 с помощью элемента «И 12 и дешифратора функций выхода 11 и сохранено до последующего цикла работы блока паадятк 1. При обработке функций возбуждения будет произведена установка каждого разряда регистра состояний 18 в соответствии со значени-ем футакции возбуждения, полученной

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

В конце цикла работы блока памяти 1 с выхода дешифратора служебных символов 3 Быдается сигнаш в результате дешифрирования си-мвола «ю. Этот сигнал может быть использован для формирования следуюшего набора аргументов на регистре набора аргументов 21.

Таким образом, с каждым циклом работы блока памяти / на регистрах состояний 18 и регистре функций выхода 13 будут цоявляться новые кодируемые состояния и выходы, т. е. последовательности состояний и выходов, которые можио рассматривать как реакци.и на входную последовательность, подаваемую на регистр набора аргументов 21. В этом случае каждому циклу работы соответствует один переход из одного состояния в другое.

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

Последовательности состояний и выходов снимаются с регистра функций выхода 13 и регистра состояний 18 и наносятся в процессе моделирования на носитель. В результате будет получена временная диаграмма последовательностей состояний и выходов. Используя предлагаемое устройство, можно легко получать таблицы переходов и выходов моделируемого автомата, заданного Hai языке функций возбуждения и выходов. Это дает возможность производить минимизацию данного автомата и синтеза другого автомата,

эквивалентного заданному и построенному с минимальными аппаратурными затратами.

Предмет изобретения

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

iflii