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

 

О П И С А Н И Е 3544II

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советския

Социалистических

Республик

Зависимое от авт. свидетельства №

М. Кл. С 06f 7/ 38

Заявлено 27.Х.1970 (№ 1486609f18-24) с присоединением заявки №

Приоритет

Опубликовано 09.Х.1972. Бюллетень № 30

Дата опубликования описания ЗО.Х.1972

Комитет по делам изобретений и открытий при Совете Министров

СССР

УДК 681.332:371.69 (088.8) Автор изобретения

И. П. Егоров

Ордена Ленина Институт проблем управления (автоматики и телемеханики) Заявитель

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

КОНЕЧНЫХ АВТОМАТОВ

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

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

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

На фиг. 1 приведена схема предлагаемого устройства; на фнг. 2 — пример структурного графа моделируемого автомата; на фиг. 3— элемент схемы устройства.

Устройство содержит одноразрядные регистры 1 и элементы 2 (см. фиг. 3), содержащие схему 8 совпадения, k-разрядный регистр 4; многофункциональный перестраиваемый элемент 5 и схему б совпадения.

Одноразрядные регистры 1 образуют матрицу размером nX т. Выход каждого одноразрядного регистра 1 соединен со входами двух смежных одноразрядных регистров 1, выходы

10 крайних верхних одноразрядных регистров 1— со входами крайних нижних одноразрядных регистров 1, а выходы крайних правых одноразрядных регистров 1 — со входамн крайних левых одноразрядных регистров 1. Таким об15 разом, матрица представляет собой совокупность регистров, которые могут работать как кольцевые т-разрядные регистры сдвига в направлении слева направо или как кольцевые и-разрядные регистры — в направлении снизу

20 вверх.

Третий вход 7 каждого одноразрядного регистра l соединен со входом элемента 2. Элемент 2 содержит входную схему 3 совпадения, выход которой соединен с /г-разрядным регист25 ром 4. Последний своими выходами соединен со входами многофункционального перестранваемого элемента 5, который, с помощью сигналов, подаваемых на входы 8, настраивается на реализацию требуемой функции. Выход

30 многофункционального перестраиваемого эле354411

50 мента 5 подключен к выходной схеме б совпадения, а выход последней соединен со входом

9 одноразрядного регистра.

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

Моделирование автомата производится циклически следующим образом.

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

В последующем цикле моделирования в течение и тактов матрица работает как регистр сдвига в направлении снизу вверх; затем на (п+1)-ом такте производится сдвиг содержимого всех одноразрядных регистров 1 на один разряд вправо. На следующих п тактах матрица снова работает как регистр сдвига в направлении снизу вверх, после чего производится сдвиг содержимого на один разряд вправо, и т. д, Таким образом, за n)(m тактов значение каждой функции j, выработанной моделируемым автоматом в предшествующем цикле, появится на входе 7 каждого одноразрядного регистра 1 устройства.

Одновременно с продвижением результатов

f по матрице производится запись в k-разрядный регистр 4 каждого элемента 2 значений тех функций f, которые, согласно заданному графу, должны поступить на вход данного элемента автомата с выходов смежных элементов автомата. Например, элемент 9 на фиг. 2 реализует функцию переменных, являющихся результатами функций f -„ f<3, f6, f»6, реализованных смежными элементами автомата в предшествующем цикле. Для этого в тот момент времени, когда какая-либо из этих функций появляется на входе 7 элемента 2, на вход 10 схемы 8 совпадения из блока 11 управления поступает сигнал. В результате значения функций f<>-„ f<3, f„., !»6 записываются в !г-разрядный регистр 4 элемента 9 автомата.

Аналогично за num тактов значения всех переменных f будут переписаны в k-разрядные регистры 4 соответствующих элементов автомата и произойдет отработка заданных функ4 ций. На (п)(т+1)-ом такте из блока ll óïðàâления на входы 12 всех элементов 2 подается сигнал, вследствие чего полученные в рассматриваемом цикле новые значения функций переписываются в одноразрядные регистры 1 матрицы. Затем производится следующий цикл моделирования и т. д, В каждом цикле значения внешних переменных задаются на входах

И многофункционального перестраиваемого элемента 5.

Аналогично строится устройство для моделирования конечного автомата в виде пространственной матрицы одноразрядных регистров 1 размером nQmQl. В этом случае каждый одноразрядный регистр 1 матрицы будет соединен со входами трех смежных одноразрядных регистров 1, а время прохождения всех результатов по входам 7 всех элементов

2 составит и, (т (1 тактов, Из того, что в предлагаемом устройстве за время одного цикла все результаты f поочередно появляются на входах 7 всех элементов, следует, что это устройство может моделировать без избыточности (по числу элементов 2) логическую структуру автомата, заданного произвольным графом с числом вершин n+m)(l.

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

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

354411

Фиг.т

I 1O

Ôèã. 2

Фиг 3

Составитель Г. Сорокин

Техред Е. Борисова

Редактор А. Батыгин

Корректор Т. Гревцова

Типография, пр. Сапунова, 2

Заказ 3576/16 Изд. № 1475 Тираж 406 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

Москва, Я-35, Раушская наб., д. 4/5