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

 

297042

О П И

ИЗОБРЕТЕНИЯ

Сова Советских

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

Республин

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

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

Заявлено 01.VI I.1969 (№ 1341649/18-24) с присоединением заявки №

Приоритет

Опубликовано 02.lll.1971. Бюллетень ¹ 9

Дата опубликования описания 15,VI.1971

МПК С 06f 15/06

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

СССР

УДК 681.326.74(088.8) Авторы изобрстения

В. Г. Лазарев и И. Д. Сейфулла

Институт проблем передачи информации АН СССР

Заявитель

УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ КОНЕЧНЫХ АВТОМАТОВ

HA ВЫЧИСЛИТЕЛЬНОЙ СРЕДЕ

Предложенное устройство относится к области автоматики и вычислительной техники.

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

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

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

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

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

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

15 между автоматом настройки и двумя участками вычислительной среды, на которых попеременно и по частям реализуется заданный конечный автомат.

Контроль за работой участков вычислитель20 ной среды осуществляется автоматом настройки путем воздействия на ряд блоков, стоящих в цепях связи участков среды и автомата настройки.

Функциональная схема автомата показана

25 на чертеже.

В качестве участков вычислительной среды (блоки 1 и 2) используется универсальная шинная вычислительная среда.

Входные переменные реализуемого конечно30 го автомата Хь Ха, ...., Х„подаютси оДно297042

55

65

3 временно на оба участка. Настройка среды осуществляется по шинам 1, 2, .... t. Выходами блоков 1, 2 являются внутренние (Yl, У,..., Ys) и выходные (ZI, Zg, ..., Z„) переменные реализуемого конечного автомата. Выходы блока 1 связаны со входом блока 3, выходы блока 2 — со входами блока 4, Блоки 8 и 4 представляют собой наборы двухвходовых клапанов, управляемых выходами блока триггера 5. Число клапанов в блоках 8 и 4 равно 2 (з+/г). Выходы блоков 3 и 4, соответствующие внутренним переменным У1, У, ..., У; объединены и связаны со входами блока б — деши фр атор а.

Выходы блоков 8 и 4, соответствующие

Z 1, ...., Z„, объединены и являются выходами реализуемого конечного автомата. Выходы блока б, число которых s, связаны со входами блока 7, являющегося автоматом настройки.

Выход i —,1 блока 7 связан со входом блока 5, первый выход которого соединен со входом блока 8, второй выход — со входом блока 4.

Выход О блока 7 связан со входом блока триггера 8. Первый выход блока 8 связан со входом блока 9, второй выход — со .входом блока 10. Блоки 5 и 8 — триггеры со счетными входами. Выходы 1, 2, .... г блока 7 разветвлены и связаны со входами блоков 9 и 10, которые представляют собой наборы двухвходовых клапанов, число которых в каждом блоке равно t. Выходы 1, 2,, t блока 9 связаны с настроечными выходами блока 2. Выходы 1, 2, ..., t блока 10 связаны с настроечными выходами блока 1. Блок 6 имеет внешний вход L, блок 7 — внешний вход М.

Блок 7 построен и работает как оперативная память ЦВМ.

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

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

Рассмотрим реализацию в данном устройстве конечного автомата, который имеет s внутренних состояний и k выходов. Число строк в таблице переходов при этом будет равно s, число внутренних переменных — s (Yl, У,..., Y,)..

Функции выходов и переходов конечного автомата для каждой из строк таблицы переходов и выходов переводятся в программу настройки для среды и извне по входу N записываются массивами в блок 7.

В исходном положении блоки 5 и 8 находятся в таком состоянии, что открыты клапаны блоков 4 и 9. С выхода блока 4 на блок б поступает нулевой сигнал. После того, как в блок 7 записана исходная информация о реализуемом конечном автомате, извне на блок б по входу L подается код начального состояния конечного автомата. Этот код после де5

45 шифрования в блоке б поступает по одному из 1, 2, ..., s входов в блок % После этого по выходу О из блока 7 на блок 8 поступает сигнал «Начало настройки». Блок 8 переводит блок 10 в проводящее состояние и запирает клапаны блока 9. Затем с выходов 1, 2, ..., t блока 7 через блок 10 в соответствии с программой настройки поступают сигналы в блок 1, настраивая данный участок вычисли.тельной среды согласно выоранному начальному состоянию конечного автомата. На этом участке вычислительной среды реализуется начальная строка таблицы переходов и выходов. По окончании настройки сигнал с выхода

1+1 блока 7 приводит блок 5 в такое состояние, при котором открываются кл11ианы Олокг!

8 и закрываются клапаны блока 4.

При воздействии на блок 1 одного из состояний входа конечного автомата (одного из наборов значений входных сигналов Х1, ..., Х) этот блок вырабатывает сигналы на выходах Zl, ......, Л„(соответствующие этому состоянию входа при внутреннем состоянии конечного автомата, реализованном на участке вычислительной среды блока 1) и сигналы на выходах Уь ..., У„которые через клапаны блока 3 поступают на входы блока 6. Набор значений этих сигналов, определяющий внутреннее состояние конечного автомата в следующий момент времени, дешифрируется блоком б в один из сигналов на выходах 1,..., s, который поступает на вход блока 7.

В случае совпадения кода внутреннего состояния, дешифрированного в блоке б, с кодом предыдущего (в данном случае начального) внутреннего состояния устройство находится в устойчивом состоянии, в случае несовпадения — устройство находится в неустойчивом состоянии. При этом блок 7 вновь вырабатывает сигнал «Начало настройки» с выхода О, под воздействием которого блок 8 переводит блок 10 в непроводящее состояние, а блок 9— в проводящее, настраивая участок вычислительной среды (блок 2) в соответствии со строкой таблиц переходов и выходов, номер которой совпадет с номером поступившего в блок 7 сигнала из блока б.

После того, как будет настроен участок вычислительной среды (блок 2), входные сигналы Х1, ..., Х воздействуют уже на блок 2, и вместо клапанов блока 8 будут открыты клапаны блока 4.

При изменении состояния входа конечного автомата произойдет изменение выходов блоков 2 и 4. При этом если код внутреннего состояния не изменился, то устройство находится в устойчивом состоянии; если изменился, то появится единица на одном из выходов 1, ..., я блока 6.

Появление единицы на входе блока 7 приведет к тому, что на выходе О блока 7 появится сигнал, воздействующий на блок 8. Выходы блока 8 откроют клапаны блока 10 и закроют клапаны блока 9. Программа настрой-ки, соответствующая уже новой строке таб297О42

10

30 лиц переходов и выходов, через блок 10 поступит на блок 1 и произведет его настройку.

На участке среды блока 1 будет реализована новая строка таблиц переходов и выходов.

По окончании настройки сигнал с выхода t+1 блока 7 воздействует на блок 5. Выходы блока 5 запирают клапаны блока 4 и открывают клапаны блока 8, Теперь значения выхода и внутреннего состояния автомата снимаются с блока 1 и блока 8, При последующем изменении входа конечного автомата происходит настройка участка среды 2 и т. д. Таким образом, в процессе работы устройства попеременно на участках 1 и 2 вычислительной среды будут реализовываться строки таблицы переходов и выходов, соответствующие внутренним состояниям конечного автомата, появляющихся в процессе его функционирования, и конечный автомат реализуется по частям попеременно на двух участках вычислительной среды.

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

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

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

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

1, Редактор Ю. Полякова

Заказ 154272 Изд. № 654 Тираж 473 Подписное

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

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

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

Составитель Е. Иванеева

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

Корректоры: А. Николаева и Л. Корогод