Устройство для моделирования конечных автоматов

1 елплтг- библи 54 оюа Советски ациалистических РеспубликИДЕТЕЛЬСТВ ВТОР СКОМ ависимое от авт. свидетельствааявлепо 27.Х,1970 ( 1486609/18-24присоединением заявкиПриоритет М, Кл. С 0617/3 Комитет по деламобретений и открытийри Совете МинистровСССР К 681.332:371,6 (088.8) бликовано 09.Х.1972. Бюллетень30 Дата опубликования описания ЗО.Х.1972 Автор зобретения. Егоров рдеиа Ленина Институт проблем управлениаявитель ОЙСТВО ДЛЯ МОДЕЛИРОВАН КОНЕЧНЫХ АВТОМАТОВобласти вычисли Изобретение относится гтельной техники.Известные устройства для моделирования конечных автоматов, содержащие блок управления, матрицу одноразрядных регистров, логические схемы, многофункциональные перестраиваемые элементы и Й-разрядные регистры, требуют для моделирования работы конечного автомата большой объем оборудования.В предлагаемом устройстве, с целью его упрощения, первый и второй выходы каждого из одноразрядных регистров матрицы соединены соответственно со входами соседних одноразрядных регистров, расположенных в строке и столбце матрицы, а третий выход каждого одноразрядного регистра через схему совпадения, подключенную вторым входом к блоку управления, соединен со входом /г-разрядного регистра, выходы которого соединены со входами многофункционального перестраиваемого элемента, вторые входы которого подключены к блоку управления, причем выход многофункционального перестраиваемого элемента через схему совпадения, подключенную вторым входом к блоку управления, соединен с третьим входом одноразрядного регистра.На фиг, 1 приведена схема предлагаемого устройства; на фнг. 2 - пример структурного графа моделируемого автомата; на фиг, 3 - элемент схемы устройства. Устройство содержит одноразрядные регистры 1 и элементы 2 (см. фиг. 3), содержащие схему 3 совпадения, Й-разрядный регистр 4; многофункциональный перестраиваемый эле мент 5 и схему б совпадения.Одноразрядные регистры 1 образуют матрицу размером ггХт. Выход каждого одноразрядного регистра 1 соединен со входами двух смежных одноразрядных регистров 1, выходы 10 крайних верхних одноразрядных регистров 1 -со входами крайних нижних одноразрядных регистров 1, а выходы крайних правых одноразрядных регистров 1 - со входамн крайних левых одноразрядных регистров 1. Таким об разом, матрица представляет собой совокупность регистров, которые могут работать как кольцевые т-разрядные регистры сдвига в направлении слева направо или как кольцевые и-разрядные регистры - в направлении снизу 20 вверх.Третий вход 7 каждого одноразрядного регистра 1 соединен со входом элемента 2, Элемент 2 содержит входную схему 3 совпадения, выход которой соединен с /г-разрядным регист ром 4. Последний своими выходами соединенсо входами многофункционального перестранваемого элемента 5, который, с помощью сигналов, подаваемых на воды 8, настраивается на реализацию требуемой функции, Выход 30 многофункционального перестраиваемого эле 3544115 10 15 20 25 30 35 40 45 50 мента 5 подключен к выходной схеме б совпадения, а выход последней соединен со входом 9 одноразрядного регистра.Подлежащий моделированию автомат задается в виде структурного графа с числом вершин, не более и)(т; при этом каждая вершина изображает элемент автомата, а дуги - связи между элементами (см, фггг, 2), В процессе работы каждый элемент автомата отрабатывает некоторую функцию.Моделирование автомата производится циклически следующим образом.Пусть значения функции , отработанные устройством в предшествуюшем цикле, записаны в одноразрядных регистрах 1 матрицы. В последующем цикле моделирования в течение п тактов матрица работает как регистр сдвига в направлении снизу вверх; затем на (п+1)-ом такте производится сдвиг содержимого всех одноразрядных регистров 1 на один разряд вправо. На следующих п тактах матрица снова работает как регистр сдвига в направлении снизу вверх, после чего производится сдвиг содержимого на один разряд вправо, гг т. д, Таким образом, за п(т тактов значение каждой функции г, выработанной моделируемым автоматом в предшествующем цикле, появится на входе 7 каждого одноразрядного регистра 1 устройства.Одновременно с продвижением результатовпо матрице производится запись в Й-разрядный регистр 4 каждого элеъгента 2 значений тех функций , которые, согласно заданному графу, должны поступить на вход данного элемента автомата с выходов смежных элементов автомата. Например, элемент 9 на фиг. 2 реализует функцию переменных, являгощихся результатами функций гзг, ггз, еез, Ье, реализованных смежными элементами автомата в предшествующем цикле, Для этого в тот момент времени, когда какая-либо из этих функций появляется на входе 7 элемента 2, на вход 10 схемы 3 совпадения из блока 11 управления поступает сигнал. В результате значения функций гз-Ггз, Реее, зее записываются в е-разрядный регистр 4 элемента 9 автомата.Аналогично за п(т тактов значения всех переменныхбудут переписаны в е-разрядньге регистры 4 соответствующих элементов автомата и произойдет отработка заданных функ 4ций, На (и)(т+1)-ом такте из блока 11 управления на входы 12 всех элементов 2 подается сигнал, вследствие чего полученные в рассматриваемом цикле новые значения функций переписываются в одноразрядные регистры 1 матрицы. Затем производится следующий цикл моделирования и т. д, В каждом цикле значения внешних переменных задаются на входах И многофункционального перестраиваемого элемента 5,Аналогично строится устройство для моделирования конечного автомата в виде пространственной матрицы одноразрядных регистров 1 размером п)(тЯ. В этом случае каждый одноразрядный регистр 1 матрицы будет соединен со входами трех смежных одноразрядных регистров 1, а время прохождения всех результатов по входам 7 всех элементов 2 составит и,(т(1 тактов, Из того, что в предлагаемом устройстве за время одного цикла все результатыпоочередно появляются на входах 7 всех элементов, следует, что это устройство может моделировать без избыточности аппо числу элементов 2) логическую структуру автомата, заданного произвольным графом с числом вершин и(т)(1,Предмет изобретен и яУстройство для моделирования конечных автоматов, содержащее блок управления, матрицу одноразрядных регистров, логические схемы, многофункциональные перестраиваемые элементы и г-разрядньге регистры, отличаюглееся тем, что, с целью упрощения устройства, в нем первый и второй выходы каждого из одноразрядных регистров матрицы соединены соответственно со входами соседних одноразрядных регистров, расположенных в строке и столбце матрицы, а третий выход каждого одноразрядного регистра через схему совпадения, подключенную вторым входом к блоку управления, соединен со входом Й-разрядного регистра, выходы которого соединены со входами многофункционального перестраиваемого элемента, вторые входы которого подключены к блоку управления, причем выход многофункционального перестраиваемого элемента через схему совпадения, подключенную вторым входом к блоку управления, соединен с третьим входом одноразрядного регистра..г фиг Составитель Г. Сорокинактор А. Батыгин Техред Е, Борисова Корректор Т. Гревцова ипография, пр. Сапунова, 2 11 О аказ 3576/16 Изд. Уо 1475 Тираж 4НИИПИ Комитета по делам изобретений и открытий приМосква, Ж, Раушская наб д. 4/5 Подписноете Министров СССР