УСТРОЙСТВО для МОДЕЛИРОВАНИЯ КОНЕЧНЫХ АВТОМАТОВ Советский патент 1972 года по МПК G06F15/173 

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

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

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

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

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

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

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

вверх.

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

мента 5 подключен к выходной схеме 6 совпадения, а выход последней соединен со входом 9 одноразрядного регпстра.

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

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

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

Одновременно с продвижением результатов f по матрице производится запись в й-разрядный регистр 4 каждого элемента 2 значений тех функций /, которые, согласно заданному графу, должны поступить на вход данного элемента автомата с выходов смежных элементов автомата. Например, элемент 9 на фиг. 2 реализует функцию переменных, являющихся результатами функций /127, /13, /689, /256, реализованных смежными элементами автомата в предшествующем цикле. Для этого в тот момент времени, когда какая-либо из этих функций появляется на входе 7 элемента 2, на вход 10 схемы 3 совпадения из блока 11 унравления поступает сигнал. Б результате значения функций /127, /13, /S89, /258 записываются в й-разрядный регистр 4 элемента 9 автомата.

Аналогично за пу(т тактов значения всех переменных / будут переписаны в -разрядные регистры 4 соответствующих элементов автомата и произойдет отработка заданных функций. На ()-омтакте из блока //управления на входы 12 всех элементов 2 подается сигнал, вследст зие чего полученные в рассматриваемом цикле новые значения функций / переписываются в одноразрядные регистры / матрицы. Затем производится следующий цикл моделирования и т. д. В каждом цикле значения внешних переменных задаются на входах 13 многофункционального перестраиваемого

элемента 5.

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

автомата, заданного произвольным графом с числом вершин «Х Х Предмет изобретения

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

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

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

с третьим входом одноразрядного регистра.

Фиг 2

2 J