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

 

Изобретение относится к области вычислительной техники и может быть использовано для моделирования исправной работы цифровых устройств при их проектировании, в том числе при построении тестов. Цель изобретения - расширение функциональных возможностей устройства за счет моделирования в многозначном алфавите. Цель достигается тем, что устройство содержит блок 1 памяти тестов, блок 2 памяти описания функций, блок 3 памяти промежуточных результатов, блок 4 памяти результатов моделирования, блок 5 управления, первый 6 и второй 7 блоки постоянной памяти, первый 8 и второй 9 мультиплексоры, вход 10 констант устройства, буферный регистр 11, триггер 12, четыре элемента 13-16 сравнения, и три регистра 17-19, три счетчика 20-22, три элемента ИЛИ 23-25. 4 ил., 4 табл.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТ ИЧЕСНИХ

РЕСПУБЛИК (594 С 06 F 15 20 "» «» " ". . »

»

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

C»»»»»»»"»» II»Je

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

IlO ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГННТ СССР

1 (21) 4402822/24-24 (22) 04.04.88 (46) 07.11.89. Вюл.М 41 (72) В.А.Кизуб, Г.Ф.Кривуля, В.И.Хаханов и В.П.Тыдыков (53) 681.325 (088.8) (56) Миллер Р. Теория переключательных схем. - М.: Наука, 1970, т.1, 416 с.

Майоров С.А. и Новиков Г.И. Структура электронных вычислительных машин. — Л.: Машиностроение, 1979, 384 с.

Авторское свидетельство СССР

717775, кл. G 06 F 15/20, 1977. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

КОНЕЧНЫХ АВТОМАТОВ (») Изобретение относится к области вычислительной техники и может, быть

„„30„„1520534 А1

2 использовано для моделирования исправной работы цифровых устройств. при их. проектировании, в том числе при построении тестов. Цель изобретения — расширение функциональных возможностей устройства за счет моделирования в многозначном алфавите. Цель достигается тем, что устройство содержит блок 1 памяти тестов, блок 2 па« мяти описания функций, блок 3 памяти промежуточных результатов, блок 4 памяти результатов моделирования, блок 5 управления, первый 6 и второй

7 блоки постоянной памяти, первый 8 и второй 9 мультиплексоры, вход 10 констант устройства, буферный регистр

11, триггер 12, четыре элемента .13-16 сравнения, три регистра 17-. 19, три счетчика 20-22, три элемента ИЛИ 2325. 4 ил., 4 табл. С." l520534

Пара расстояний (переход) Кодирующий их символ

0

1

0

1<2

Таблица 3

Переход

ВС

А Переход в двухтактном алфавите ВС

0 О.

0 1

1 0

1 0

1 1

Е Н

1 1

0 0

НН

Состояние Старое

В, С Йовое

Входной сигнал

0

Т а блица 4

50

1 SE

1 PH

0 l

Изобретение относится к вычислительной технике и может быть использовано для моделирования цифровых систем, при разработке БИС и цифровых

5 устройств, при их диагностике.

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

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

Устройство содержит блок 1 памяти (БП) тестов, блок 2 памяти (БП) описания функций, блок 3 памяти (БП). про" межуточных результатов, блок 4 памяти (БП) результатов моделирования, блок

5 управления, первый 6 и второй .7 бло-щ0 ки постоянной памяти, первый 8 и второй 9 мультиплексоры, вход 10 констант устройства, буферный регистр 11, .триггер 12, элементы 13-16 сравнения, регистры 17-19, счетчики 20-22, эле- 25 менты ИЛИ 23-25.

Блок 5 управления содержит дешифраторы 26-30, первый элемент HE 31, элемент И-ИЛИ 32, регистр 33 микрокоманд, узел 34 памяти микрокоманд, счетчик 35 адреса, второй элемент

HE 36.

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

его таблица переходов имеет следую- 40 щий вид (табл.1)

Таблица 1

Система булевых функций для задания поведения счетчика имеет внд:

В = А (ВС V ВС), С = А (ВС ч ВС).

Для уменьшения объема модели применим кодирование двух соседних состояний таблицы переходов-выходов одним символом (табл.2).

Таблица 2

Тогда из табл. 1 получаем табл.3.

По правилам минимизации кубов, если существуют два куба, отличающиеся по одной переменной, они подлежат склеиванию (объединению) по этой переменной. Получаем всего два куба (табл.4).

Символ S кодирует- пару Q,J, символ

P — - E,Н, такое кубическое покрытие в двухкратном алфавите занимает в памяти шесть ячеек, по одной íà каждую букву, что в 2,5 раза меньше, чем для системы булевых функций.!

520534

БП 1 тестов используется для хране — . ния моделируемых наборов (по входным, внутренним и выходным переменным), БП 2 описания функций используется для хранения кубического покрытия в двухтактном алфавите, Б|1 3 промежуточных результатов используется для хранения результатов пересечения, а БП 4 результатов моделирования — для хранения результатов моделирования одного набора.

БП 1 содержит Т моделируемых векторов. Каждой переменной КА в БП 1 соответствует один символ из алфавита 15

0 1 Х, Ф. Для хранения одного символа требуется два разряда, поэтому объем

БП 1 (2 х К), где К вЂ” число переменных КА (входных, внутренних и выходных). 20

БП 2 содержит описание функций КА (его модель) в форме кубического покрытия. Каждое слово БП 2 содержит символ двухкратного алфавита, всего таких символов в алфавите 22, поэтому 25 слово состоит из четырех разрядов, объем bII 2 (4 х К х N), где N — число строк кубического покрытия.

БП 3 содержит промежуточные результаты после операции пересечения стро- 30 ки кубического покрытия и моделируемого вектора. Наличие БП 3 обусловлено необходимостью хранить получаемые символы вектора пересечения, пока он не ,будет получен полностью (пересечение

35 производится посимвольно) . Символы вектора пересечения анализируются, и если хотя бы один из них равен Ф, то пересечение с данной строкой покрытия прекращается, начинается пере- 40 сечение со следующей строкой покрытия с первого символа. При этом результаты пересечения, находящиеся в

БП 3, теряются. Объем БП 3-(2 х К), так как он содержит символы из алфави-45 та О, 1, Х, 4 .

БП 4 содержит промежуточные результаты моделирования одного входного набора, полученные после объединения результатов пересечений иэ БП 3 с промежуточными результатами из БП 4.

Объем БП 4-(2 х К) разрядов, Счетчики 20-22 содержат текущие значения адресов переменной; строки покрытия и набора теста соответственно.

Регистры 17-19 содержат верхние пределы циклов по переменным, строкам покрытия и наборам теста cooòâåтственно. .Буферный регистр 11 служит для временного хранения результата объединения символа из bII 4 с символом иэ БП 3 перед его записью снова в

БП 4 (в следующем такте), Блок 5 управления может быть реализован как автомат с ествественной адресацией микрокоманд.

Моделирование по кубическому покрытию происходит следующим образом, Моделируемый вектор из bII 1 посимвольно пересекается с очередной строкой кубического покрытия из bII 2, результат посимвольно заносится в БП 3. С помощью блока 6 постоянной памяти каждой паре символа иэ БП 1 и 2 ставится в соответствие один символ — результат пересечения. Если в БП 3 хотя бы один символ вектора результата пересечения равен Ф (пусто), то пустым считается весь вектор пересечения данной строки покрытия и моде лируемого вектора. Затем вектор результата пересечения иэ БП 3 посимвольно объединяется с вектором результата моделирования из БП 4 и записывается снова в БП 4. Если в БП 3 пустой вектор пересечения, то с входа

10 через мультиплексор 8 на первый адресный вход блока 7 подается код символа . Блок 7 ставит в соответствие паре символов из bII 3 и 4 один символ на своем выходе. Затем берется следующая строка покрытия и процесс повторяется. Когда покрытие исчерпано, в blE 4 нахоцится вектор результата моделирования, который затем переписывается в БП на место моделируемого вектора. Перед началом моделирования в БП 1 заносятся моделируемые векторы, состоящие из входных наборов и символов ф на месте внутренних и выходных переменных.

Перед началом моделирования очередно»

ro входного набора в БП 4 заносятся символы ф по всем координатам, которые поступают на вход БП 4 с входа

10 через мультиплексор 9.

Устройство работает следующим образом.

Сигнал "Пуск" обнуляет счетчик 35 адреса в блоке 5 управления. По синхроимпульсу, поступающему на вход синхронизации устройства, в блоке 5 управления из узла 34 памяти микрокоманд по адресу, указываемому счетчиком 35

7 1520534 8 адреса, выбирается очередная микрокоманда. Она поступает в регистр 33 микрокоманд, В зависимо ти от значения нулевого разряда микрокоманды разрешающий сигнал подается либо на дешифратор 30, либо через элемент

НЕ 31 на дешифраторы 26-29.

В первом случае микрокоманда явля" ется условной, тогда дешифратор 30 дешифрирует разряды 1-5 микрокоманды, которые определяют проверяемое условие из множества Х1-Х5. В зависимости от равенства 0 (1) условия на выходе элемента И-ИЛИ 32 появляется

0 (1). При 0 разрешающий сигнал подается через элемент НЕ 36 на вход счетчика 35 адреса, управляющий приращением, поэтому переходим к следующей микрокоманде, rIPH 1 разрешающий 20 сигнал подается на вход разрешения записи, в счетчик 35 адреса записываются разряды 6-10 регистра 32 микрокоманд и происходит переход к микрокоманде, заданной адресом в разрядах 6-10.

Во втором случае микрокоманда является операционной, тогда дешифраторы 26-29 дешифрируют группы разрядов микрокоманды 1-2, 3-5, 6"8, 9-10 соответственно и на некоторых иэ выхо" дов У1-У18 появляются сигналы, активизирующие заданные микрооперации.

При этом на управляющих входах счетчика 35 адреса присутствует сигнал, вызывающий приращение его содержимо35 го на

Если в регистр 33 микрокоманд попадает микрокоманда -"Конец", то на выходе дешифратора 27 появляется сигнал

"Стоп", Работа остальных частей устройства активизируется управляющими сигналами: У1- I18 в соответствии с микропрограммой (фиг ° 3 и 4) По сигналам 45

У1-У4 происходит обнуление счетчика

21 и занесение с шины данных (ШД1) в регистры 17-19 значений К (где К вЂ” число переменных моделируемого КА),N (где.N — число строк кубического покрытия KA), Т (где Т - число модели50 руемых наборов теста). Затем по сигналу У5 происходит обнуление счетчика 20 и по сигналу Уб приращение на содерясимого счетчика 21. По сигналу

У7 происходит приращение на 1 содержимого счетчика 20. По сигналу У8 с шины данных (ШД 2) в БП 2 описания функций заносится один символ кубического покрытия по адресу, указываемому счетчиками 20 и 21. Затем проверяется условие Х1 на выходе элемента

14 сравнения, являющееся результатом сравнения на равенство содержимого счетчика 20 и регистра 17. Если они не равны, то происходит. переход к микрооперации приращения содержимого счетчика 20. Иначе проверяется усло" вие Х2 на выходе элемента 15 сравнения, являющееся результатом сравне- ния на равенство содержимого счетчика 21 и регистра 18. Если они не равны, то происходит переход к микрооперации обнуления счетчика 20 и прира" щения счетчика 21. Иначе по сигналу

У9 обнуляется счетчик 22.

Затем по сигналу У5 обнуляется счетчик 20 и по сигналу У 10 производится приращение содержимого счетчика 22. По сигналу У7 производится приращение счетчика 20. По сигналу Yii поступающему на вход разрешения записи БП 1 тестов через элемент ИЛИ 23, с шины данных (ШД 3) в БП 1 тестов вводится очередной символ теста по адресу, задаваемому счетчиками 20 и

22. Производится анализ сигнала Х1, при его отсутствии происходит переход к микрооперации приращения содержимого счетчика 21. Иначе производится анализ сигнала ХЗ, являющегося выходом элемента 16 сравнения, Сигнал ХЗ вырабатывается в случае, если содержимые счетчика 22 и регистра 19 равны. При его отсутствии происходит переход на микрокоманду обнуления счетчика 21 и приращения счетчика 22.

Иначе по сигналу У9 обнуляется счетчик 22 ° По сигналу У1 обнуляется счетчик 21, по сигналу У12 устанавливается в "0" триггер 12 и по сигналу

У10 производится приращение содержимого счетчика 22. По сигналу У5 обнуляется счетчик 20 и производится прира" щение счетчика 2 l По сигналу У7 производится приращение счетчика 20.

Из блока 1 памяти тестов по адресу, задаваемому счетчиками 20 и 22, считывается символ теста и подается на одни адресные входы блока 6, на другие его адресные входы подаетея символ кубического покрытия из БП 2 описания функций. По сигналу У13 результат пересечения считывается из блока 6 и записывается в блок 3 памяти промежуточных результатов по адресу, задаваемому счетчиком 20. Анализиру1520534

10 ется сигнал Х4 на выходе элемента 13 сравнения, который появляется при равенстве кода символа на выходе БП 3 промежуточных результатов и кода 11 на входе 10.

При йаличии сигнала Х4 происходит переход на микрооперацию обнуления счетчика 20 и приращения счетчика 21.

Иначе анализируется сигнал Х1, при его отсутствии происходит переход на микрооперацию приращения счетчика 20.

Анализируется сигнал Х5, при наличии сигнала происходит переход на микрооперацию обнуления счетчика 20. Иначе по сигналу, У5 обнуляется счетчик

20 и по сигналу У14 устанавливается в "1" триггер 12. По сигналу У7 производится приращение счетчика 20; По сигналу У15, поступающему на вход 20 разрешения записи BII 4 результатов моделирования через элемент ИЛИ 25, в .БП 4 результатов моделирования с входа 10 через мультиплексор 9 заносится код -11 символа Ф по адресу, 25 задаваемому счетчиком 20. Анализируется условие Х1, при его выполнении происходит переход на микрооперацию приращения счетчика 20. Иначе по сигналу У5 обнуляется счетчик 20. 30

По сигналу YZ происходит его приращение, По сигналу У16, поступающему на вход разрешения чтения блока 7 через элемент ИЛИ 24, на входы блока 7- через мультиплексор 8 с . БП 3 промежу35 точных результатов подается один объединяемый символ, из БП 4 результатов моделирования на другие входы блока 7 — другой объединяемый символ, с выходом блока 7 результат объедине- 40 ния записывается в буферный регистр

11 по сигналу записи У16, По сигналу

У18, поступающему на вход разрешения записи блока 14 памяти результатов моделирования через элемент ИЛИ 25, 45 символ — результат пересечения из буферного регистра 11 через мультиплексор 9 записывается в БП 4 результатов моделирования по адресу, задаваемому счетчиком 20, Анализируется сигнал Х1, при его отсутствии производится переход на микрооперацию приращения счетчика 20. Иначе анализируется сигнал Х2, при его отсутствии производится переход на микрооперацию обнуления счетчика 21. . По сигналу У5 обнуляется счетчик

20, По сигналу У7 производится приращение счетчика 20. По сигналу У17 из

БП 4 результатов моделирования по адресу, заданному счетчиком 20, на входы блока 7 подается очередной символ результата моделирования, на другне входы блока 7 с входа 10 через мультиплексор 8 подается код 11 символа P . С выхода блока 7 по сигналу

У17 поступающему на вход разрешения чтения блока 7 через элемент ИЛИ 24, символ блока 4 записывается в БП тестов по адресу, заданному счетчиками 20 и 22, при этом обеспечивается пересылка результатов моделирования одного набора теста из Б|1 4 и БП 1.

Анализируется сигнал Х1, при его отсутствии производится переход на микрооперацию приращения счетчика 20.

Иначе анализируется сигнал ХЗ, при его отсутствии производится переход на микрооперацию обнуления счетчика

20, обнуления триггера 12 и приращения счетчика 22.

Формула изобретения.

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

12 ка постоянной памяти, выход третьего счетчика подключен к первому входу третьего элемента сравнения и к второму адресному входу блока памяти

5 тестов, выход которого подключен к второму адресному входу первого блока постоянной памяти, выход которого подключен к информационному входу блока памяти промежуточных результа- 1р тов, выход которого подключен к первому входу четвертого элемента сравне,ния и к первому информационному входу первого мультиплексора, выход которого подключен к первому адресному входу второго блока постоянной памяти, выход которого подключен к информационным входам блока памяти тестов и буферного регистра и объединен с входом символов теста устройства, 20 вход констант которого подключен к второму информационному входу первого мультиплексора, к второму входу четвертого элемента сравнения и к первому информационному входу второ- 25 го мультиплексора, выход которого подключен к информационному входу блока памяти результатов моделирования, выход которого подключен к второму адресному входу второго блока посто- 30 янной памяти, входы числа переменных, числа строк кубического покрытия и числа моделируемых наборов теста уст< ройства подключены соответственно к информационным входам первого, вто- 35 рого и третьего регистров, выходы которых подключены соответственно к вторым входам первого, второго и третьего элементов сравнения, выходы которых подключены к первому, второ- 40 му и третьему входам режима блока управления, четвертый и пятый входы режима которого подключены соответственно к выходам четвертого элемента сравнения и триггера, выход буферного регистра подключен к второму информационному входу второго мультиплексора, вход синхронизации и вход запуска устройства подключены соответственно к одноименным входам блока управления, первый выход которого подключен к выходу признака останова устройства, вход описания функций которого подключен к информационному входу блока памяти описания функций, выходы с второго по тринадцатый блока управления подключены соответственно к входу установки в "0" первого счетчика, к входам записи первого, второго и третьего регистров, к входу установки в "0" второго счетчика, к счетным входам первого и второго счетчиков, к входу записи блока памяти описания функций, к входу установки в "0" третьего счетчика, к счетному входу третьего счетчика, к первому входу первого элемента ИЛИ, к входу установки в "0" триггера, че ырнадцатый выход блока управления подключен к входу чтения первого блока постоянной памяти и к входу записи блока памяти. промежуточных результатов, пятнадцатый выход блока управления — к входу установки в "i" триггера, шестнадцатый выход — к первому управляющему входу второго мультиплексора и к первому входу второго элемента ИЛИ, семнадцатый выход — к первому управляющему входу первого мультиплексора, к первому входу третьего элемента ИЛИ и к входу записи буферного регистра, восемнадцатый выход — к второму управляющему входу первого мультиплексора,к вторым входам первого и третьего элементов ИЛИ,выход последнего подключен к.входу чтения второго блока постоянной памяти, девятнадцатый выход блока управления под" ключен к второму управляющему входу второго мультиплексора и к второму входУ второго элемента ИЛИ, выход которого подключен к входу записи блока памяти результатов моделирования, выход первого элемента ИЛИ подключен к входу записи блока памяти тестов.

1520534

Р раиелтро1 сси/И

ЮоР у ичес чага

spumus

РКИ

mecca

Пересечение

Фиг. 3

1520534

Занесение р лервд

Моделироданием очередново набора

Объединение

Пераснака результата о уединению о 41он лащю и

Рюш РР1 о о

Составитель В. Смирнов

Техред Л. Сердюкова Корректор Н. Король

Редактор В.Петраш

Заказ 6160/51 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ CCCE

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101