Устройство для моделирования конечных автоматов Советский патент 1989 года по МПК G06N7/06 

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

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

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

Устройство содержит блок 1 памяти (БП) тестов, блок 2 памяти (ВП) описания функций, блок 3 памяти (БП). промежуточных результатов, блок 4 памяти (БП) результатов моделирования, блок 5 управления, первый 6 и второй.7 бло ки постоянной памяти, первый 8 и второй 9 мультиплексоры, вход 10 констант устройства, буферньй регистр 11, .триггер 12, элементы 13-16 сравнения,

регистры 17-19, счетчики 20-22, элементы ИЛИ 23-25.

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

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

Таблица 1

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

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

Таблица 2

Пара расстояний (переход)

Кодирующий их символ

О О О 1 1

О 1 1

() Е Н J

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

25

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

Q Е Е Н

J Е НН

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

Т а б л и ц а 4

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

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

50

А ВС

1

SE РН

Символ S кодирует пару Q,J, символ Р - Е,Н, такое кубическое покрытие в двухкратном алфавите занимает в памяти шесть ячеек, по одной на каждую букву, что в 2,5 раза меньше, чем для системы булевых функций.

5

15

5

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

БП 1 содержит Т моделируемых векторов. Каждой переменной КА в БП 1 соответствует один символ из алфавита 0,1,Х,Ф. Для хранения одного символа требуется два разряда, поэтому объем БП 1 (2 X К), где К - число переменных КА (входных, внутренних и выходных) .

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

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

20

35

крытия прекращается, начинается пере- дд тор результата моделирования, который

затем переписывается в БП 1 на месПеред насечение со следующей строкой покрытия с первого символа. При-этом рето моделируемого вектора,

зультаты пересечения,находящиеся в БП 3, теряются. Объем БП 3-(2 х К),

чалом моделирования в БП 1 заносятся

моделируемые векторы, состоящие из

так как он содержит символы из алфави-д входных наборов и символов ф на места О, 1 , X, Ф .

те внутренних и выходных переменных. Перед началом моделирования очередного входного набора в БП 4 заносятся символы 0 по всем координатам, которые поступают на вход БП 4 с входа 10 через мультиплексор 9.

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

Счетчики 20-22 содержат текущие значения адресов переменной, строки покрытия и набора теста соответственно.

Регистры 17-19 содержат верхние пределы циклов по переменным, стро

5

15

25

30

05346

кам покрытия и наборам теста соответственно .

Буферный регистр 11 служит для временного хранения результата объединения символа из БП 4 с символом из БП 3 перед его записью снова в БП 4 (в следующем такте),

Блок 5 управления может быть реализован как автомат с ествественной адресацией микрокоманд.

Моделирование по кубическому покрытию происходит следующим образом. Моделируемый вектор из БП 1 посимвольно пересекается с очередной строкой кубического покрытия из БП 2, результат посимвольно заносится в БП 3. С помощью блока 6 постоянной памяти каждой паре символа из БП 1 и 2 ставится в соответствие один символ - результат пересечения. Если в БП 3 хотя бы один символ вектора результата пересечения равен 0 (пусто), то пустым считается весь вектор пересечения данной строки покрытия и моде лируемого вектора. Затем вектор результата пересечения из БП 3 посимвольно объединяется с вектором результата моделирования из БП 4 и записывается снова в БП 4 . Если в БП 3 - пустой вектор пересечения, то с входа 10 через мультиплексор 8 на первый адресный вход блока 7 Подается код символа 0 . Блок 7 ставит в соответствие паре символов из БП 3 и 4 один символ на сво.ем выходе. Затем берется следующая строка покрытия и процесс повторяется. Когда покрытие исчерпано, в БП 4 находится век20

35

Перед нато моделируемого вектора,

чалом моделирования в БП 1 заносятся

моделируемые векторы, состоящие из

входных наборов и символов ф на мес

те внутренних и выходных переменных. Перед началом моделирования очередного входного набора в БП 4 заносятся символы 0 по всем координатам, которые поступают на вход БП 4 с входа 10 через мультиплексор 9.

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

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

адреса, выбирается очередная микрокоманда. Она поступает в регистр 33 микрокоманд, В зависимости от значения нулевого разряда микрокоманды разрешающий сигнал подается либо на дешифратор 30, либо через элемент НЕ 31 на дешифраторы 26-29.

В первом случае микрокоманда является условной, тогда дешифратор 30 дешифрирует разряды 1-5 микрокоманды, которые определяют проверяемое условие из множества XI-Х5. В зависимости от равенства О (1) условия на выходе элемента И-ИЛ1 32 появляется О (О. При О разрешающий сигнал подается через элемент НЕ 36 на вход счетчика 35 адреса, управляющий приращением, поэтому переходим к следующей микрокоманде. При 1 разрешающий сигнал подается на вход разрешения записи, в счетчик 35 адреса записываются разряды 6-10 регистра 32 микрокоманд и происходит переход к микрокоманде, заданной адресом в разря- дах 6-10.

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

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

Работа остальных частей устройства активизируется управляющими сигналами: У1-У18 в соответствии с микропрограммой (фиг.З и 4). По сигналам Y1-Y4 происходит обнуление счетчика 21 и занесение с тины данных (ШДО в регистры 17-19 значений К (где К - чсло переменных моделируемого KA),N (где N - число строк кубического покрытия КА), Т (где Т - число модели- руемых наборов теста). Затем по сигналу Y5 происходит обнуление счетчика 20 и по сигналу Y6 приращение на 1 содержимого счетчика 21, По сигнал Y7 происходит приращение на 1 содер- жимого счетчика 20, По сигналу Y8 с шины данных (ШД 2) в БП 2 описания функций заносится один символ кубич

с 0

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

Затем по сигналу Y5 обнуляется счетчик 20 и по сигналу Y 10 производится приращение содержимого счетчика 22, По сигналу Y7 производится приращение счетчика 20. По сигналу Y11, поступающему на вход разрешения записи БП 1 тестов через элемент ИЛИ 23, с шины данных (ШД 3) в 1зП 1 тестов вводится очередной символ теста по адресу, задаваемому счетчиками 20 и 22, Производится анализ сигнала XI, при его отсутствии происходит переход к микрооперации приращения содержимого счетчика 21, Иначе производится анализ сигнала ХЗ, являющегося выходом элемента 16 сравнения. Сигнал ХЗ вырабатывается в случае, если содержимые счетчика 22 и регистра 19 рйвны. При его отсутстаии происходит переход на микрокоманду обнуления счетчика 21 и приращения счетчика 22, Иначе по сигналу Y9 обнуляется счетчик 22, По сигналу Y1 обнуляется счетчик 21, по сигналу Y12 устанавливается в О триггер 12 и по сигналу Y10 производится приращение содержимого счетчика 22, По сигналу Y5 обнуляется счетчик 20 и производится приращение счетчика 21, По сигналу Y7 производится приращение счетчика 20, Из блока 1 памяти тестов по адресу, задаваемому счетчиками 20 и 22, считывается символ теста и подается на одни адресные входы блока 6, на другие его адресные входы подаетея символ кубического покрытия из БП 2 описания функций. По сигналу Y13 результат пересечения считывается из блока 6 и записывается в блок 3 памяти промежуточных результатов по адресу, задаваемому счетчиком 20, Анализируется сигнал Х4 на выходе элемента 13 сравнения, который появляется при равенстве Кода символа на выходе БП 3 промежуточных результатов и кода 11 на входе 10.

При Наличии сигнала Х4 происходит переход на микрооперацию обнуления счетчика 20 и приращения счетчика 21. Иначе анализируется сигнал XI, при его отсутствии происходит переход на микрооперацию приращения счетчика 20. Анализируется сигнал Х5, при наличии сигнала происходит переход на микрооперацию обнуления счетчика 20. Ина- че по сигналу.Y5 обнуляется счетчик 20 и по сигналу Y1A устанавливается в 1 триггер 12. По сигналу Y7 про

БП 4 результатов моделирования по адресу, заданному счетчиком 20, на входы блока 7 подается очередной символ результата моделирования, на другие входы блока 7 с входа 10 через мультиплексор 8 подается код 11 символа 0 . С выхода блока 7 по сигналу Y17, поступающему на вход разрешения чтения блока 7 через элемент ИЛИ 24, символ блока 4 записывается в БП 1 тестов по адресу, заданному счетчиками 20 и 22, при этом обеспечивается пересылка результатов моделирования одного набора теста из БП 4 и БП 1. Анализируется сигнал Х1, при его отсутствии производится переход на микрооперацию приращения счетчика 20. Иначе анализируется сигнал ХЗ, при его отсутствии производится переход на микрооперацию обнуления счетчика 20, обнуления триггера 12 и приращения счетчика 22.

20

30

35

изводится приращение счетчика 20. По сигналу Y15, поступающему на вход разрешения записи БП 4 результатов моделирования через элемент ИЛИ 25, в ;БП 4 результатов моделирования с входа 10 через мультиплексор 9 заносится код -11 символа 0 по адресу, 25ФоРмула изобретения- задаваемому счетчиком 20. Анализируется условие XI, при его вьтолне- нии происходит переход на микрооперацию приращения счетчика 20. Иначе по сигналу Y5 обнуляется счетчик 20. По сигналу Y7 происходит его приращение. По сигналу Y16, поступающему на вход разрешения чтения блока 7, через элемент ИЛИ 24, на входы блока 7 через мультиплексор 8 с :БП 3 промежуточных результатов подается один объединяемый символ, из БП 4 результатов моделирования на другие входы блока 7 - другой объединяемь1й символ, с выходом блока 7 результат объедине- Q ния записывается в буферньй регистр 11 по сигналу записи Y16, По сигналу Y18, поступающему на вход разрешения записи блока 14 памяти результатов моделирования через элемент ИЛИ 25, символ - результат пересечения из буферного регистра 11 через мультиплексор 9 записывается в БП 4 результатов моделирования по адресу, задаваемому счетчиком 20. Анализируется jQ сигнал XI, при его отсутствии производится переход на микрооперацию приращения счетчика 20, Иначе анализиру45

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

производится переход на микрооперацию ,j ка подключен к первому вх:оду второго

обнуления счетчика 21.элемента сравнения и к второму адрес По сигналу Y5 обнуляется счетчик 20, По сигналу Y7 производится приращение счетчика 20. По сигналу Y17 из

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

053А10

БП 4 результатов моделирования по адресу, заданному счетчиком 20, на входы блока 7 подается очередной символ результата моделирования, на другие входы блока 7 с входа 10 через мультиплексор 8 подается код 11 символа 0 . С выхода блока 7 по сигналу Y17, поступающему на вход разрешения чтения блока 7 через элемент ИЛИ 24, символ блока 4 записывается в БП 1 тестов по адресу, заданному счетчиками 20 и 22, при этом обеспечивается пересылка результатов моделирования одного набора теста из БП 4 и БП 1. Анализируется сигнал Х1, при его отсутствии производится переход на микрооперацию приращения счетчика 20. Иначе анализируется сигнал ХЗ, при его отсутствии производится переход на микрооперацию обнуления счетчика 20, обнуления триггера 12 и приращения счетчика 22.

20

25ФоРмула изобретения- Q jQ

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

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

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

к информационным входам первого, вто- г буферного регистра, восемнадцатый

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

40

45

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

0

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

5

0

0

5

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

3 By(p. uej

ГЖ йГ К} .Рг

Занесение перед Mode/iupoSaHUfff ovepeff/fogo ffafepa

OfbedtmeHue

Перлсиана pe) matrta одьединения S ( памяти tneff oe