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

1520534 Изобретение относится к вычислительной технике и может быть использовано для моделирования цифровыхсистем, при разработке БИС и цифровых5устройств, при их диагностике,Цель изобретения - расширение функциональных возможностей устройстваза счет моделирования в многозначномалфавите,ОНа Фиг. 1 представлена схема устройства; на фиг. 2 - схема блокауправления; на Фиг. 3 и 4 - блок-схема алгоритма работы блока управления.Устройство содержит блок 1 памяти(БП) результатов моделирования, блок5 управления, первый 6 и второй .7 бло ки постоянной памяти, первый 8 и второй 9 мультиплексоры, вход 10 констант устройства, буферный регистр 11,,триггер 12, элементы 13-16 сравнения,регистры 17-19, счетчики 20-22, элементы ИЛИ 23-25.Блок 5 управления содержит дешифраторы 26-30, первый элемент НЕ 31,элемент И-ИЛИ 32, регистр 33 микрокоманд, узел 34 памяти микрокоманд,счетчик 35 адреса, второй элементНЕ 36.Конечный автомат (КА) может бытьописан как моделью в формуле булевыхФункций, так и кубическими покрытиями. Сравним, например, модели счетчика в этих формах, Пусть счетчик -двухраэрядный, управляется логической единицей по счетному входу А, аего таблица переходов имеет следующий вид (табл.1)Т а а 1 1 Пара расстояний (переход) Кодирующий ихсимвол 0 0 0 1 0 1 Таблица 3 Переход ВСА Переход в двухтактном алфавите ВС 0 О,О0 11 О1 01 1 1 1 0 О По правилам минимизацили существуют два куба,ся по одной переменной,склеиванию (объединению)ременной. Получаем всего45 (табл,4),и кубов, есотличающиени подлежатпо этой педва куба блиц Входной стоя В, С е СтароеЙовое игнал А Та блиц 0 1 50 Н 0 Систеия пове булевых функций для задния счетчика имеет внд: В = А (ВС Ч ВС),С = А (ВС ч ВС).Для уменьшения объема модели применим кодирование двух соседних состояний таблицы переходов-выходов одним символом (табл.2),Таблица 2 Тогда из табл. 1 получаем табл.3. Символ Я кодирует. пару Я,Л, символ Р - Е,Н, такое кубическое покрытие в двухкратном алфавите занимает в памяти шесть ячеек, по одной на каждую букву, что в 2,5 раза меньше, чем для системы булевых функций.БП 1 тестов используется для хранения моделируемых наборов (по входным,внутренним и выходным переменным),БП 2 описания функций используетсядля хранения кубического покрытия вдвухтактном алфавите, Б 1 3 промежуточных результатов используется для хранения результатов пересечения, а БП 4результатов моделирования - для хранения результатов моделирования одного набора.БП 1 содержит Т моделируемых векторов, Каждой переменной КА в БП 1 соответствует один символ из алфавита 150,1,Х, Ф, Для хранения одного символатребуется два разряда, поэтому объемБП 1 (2 х К), где К - число переменных КА (входных, внутренних и выходных). 20БП 2 содержит описание Функций КА(его модель) в форме кубического покрытия. Каждое слово БП 2 содержитсимвол двухкратного алфавита, всеготаких символов в алфавите 22, поэтому 25слово состоит из четырех разрядов,объем БП 2 (4 х К х И), где Б - числострок кубического покрытия,БП 3 содержит промежуточные результаты после операции пересечения строки кубического покрытия и моделируемого вектора. Наличие БП 3 обусловленонеобходимостью хранить получаемые символы вектора пересечения, пока он не,будет получен полностью (пересечение35производится посимвольно) . Символывектора пересечения анализируются,и если хотя бы один из них равен ф ,то пересечение с данной строкой покрытия прекращается, начинается пере- Осечение со следующей строкой покрытия с первого символа. При этом результаты пересечения, находящиеся вБП 3, теряются. Объем БП 3-(2 х К),так как он содержит символы из алфави та О, 1, Х, 4 . БП 4 содержит промежуточные результаты моделирования одного входного набора, полученные после объединения результатов пересечений иэ БП 3 с промежуточными результатами из БП 4. Объем БП 4-(2 х К) разрядов,Счетчики 20-22 содержат текущие значения адресов переменной; строки покрытия и набора теста соответственно.Регистры 17-19 содержат верхние пределы циклов по переменным, строкам покрытия и наборам теста соответственно.Буферный регистр 11 служит длявременного хранения результата объединения символа из БП 4 с символомиэ БП 3 перед его записью снова вБП 4 (в следующем такте),Блок 5 управления может быть реализован как автомат с ествественнойадресацией микрокоманд.Моделирование по кубическому покрытию происходит следующим образом,Моделируемый вектор из Б 1 посимвольно пересекается с очередной строкойкубического покрытия из БП 2, результат посимвольно заносится в БП 3. Спомощью блока 6 постоянной памятикаждой паре символа иэ БП 1 и 2 ставится в соответствие один символ - результат пересечения. Если в БП 3хотя бы один символ вектора результата пересечения равен Ф (пусто), топустым считается весь вектор пересечения данной строки покрытия и моделируемого вектора. Затем вектор результата пересечения иэ БП 3 посимвольно объединяется с вектором результата моделирования из БП 4 и записывается снова в БП 4. Если в БП 3пустой вектор пересечения, то с входа10 через мультиплексор 8 на первыйадресный вход блока 7 подается кодсимвола Ф, Блок 7 ставит в соответствие паре символов из БП 3 и 4один символ на своем выходе. Затемберется следующая строка покрытияи процесс повторяется. Когда покрытие исчерпано, в БИ 4 нахоцится вектор результата моделирования, которыйзатем переписывается в БПна место моделируемого вектора, Перед началом моделирования в БП 1 заносятсямоделируемые векторы, состоящие извходных наборов и символов ф на месте внутренних и выходных переменных.Перед началом моделирования очередного входного набора в БП 4 заносятсясимволы ф по всем координатам, которые поступают на вход ЬП 4 с входа10 через мультиплексор 9,Устройство работает следующим образом,Сигнал "Пуск" обнуляет счетчик 35адреса в блоке 5 управления. По синхроимпульсу, поступающему на вход синхронизации устройства, в блоке 5 управления из узла 34 памяти микрокомандпо адресу, указываемому счетчиком 35адреса, выбирается очередная микрокоманда. Она поступает в регистр 33микрокоманд, В зависимости от значения нулевого разряда микрокомандыразрешающий сигнал подается либо надешифратор 30, либо через элементНЕ 31 ца дешифраторы 26-29,В первом случае микрокоманда явля"ется условной, тогда дешифратор 30дешифрирует разряды 1-5 микрокоманды,которые определяют проверяемое условие из множества Х 1-Х 5, В зависимости от равенства 0 (1) условия навыходе элемента И-ИЛИ 32 появляется0 (1), При 0 разрешающий сигнал подается через элемент НЕ 36 на входсчетчика 35 адреса, управляющий приращением, поэтому переходим к следующей микрокоманде Прй 1 разрешающ Й 20сигнал подается на вход разрешениязаписи, в счетчик 35 адреса записываются разряды 6-10 регистра 32 микрокоманд и происходит переход к микрокоманде, заданной адресом в раэрядах 6-10.Во втором случае микрокоманда является операционной, тогда дешифраторы 26"29 дешифрируют группы разрядовмикрокоманды 1-2, 3-5, 6"8, 9-10соответственно и на некоторых иэ выхо"дов У 1-718 появляются сигналы, активизирующие заданные микрооперации.При этом на управляющих входах счетчика 35 адреса присутствует сигнал,вызывающий приращение его содержимо 35го наЕсли в регистр 33 микрокоманд попадает микрокоманда "Конец", то на выходе дешифратора 27 появляется сигнал"Стоп",Работа остальных частей устройства активизируется управляющими сигналами: У 1-У 18 в соответствии с микропрограммой (фиг.3 и 4), По сигналам 4571-У 4 происходит обнуление счетчика21 и занесение с шины данных (ШД 1) врегистры 17-19 значений К (где К - число переменных моделируемого КА),И(где.И - число строк кубического по"крытия КА), Т (где Т - число модели 50руемых наборов теста). Затем по сигналу У 5 происходит обнуление счетчика 20 и по сигналу Уб приращение насодерясимого счетчика 21. По сигналуУ 7 происходит приращение на 1 содержимого счетчика 20, По сигналу 78 сшины данных (ШД 2) в БП 2 описанияфункций заносится один символ кубического покрытия по адресу, указываемому счетчиками 20 и 21. Затем проверяется условие Х 1 на выходе элемента 14 сравнения, являющееся результатом сравнения на равенство содержимого счетчика 20 и регистра 17. Если они не равны, то происходит переход к микрооперации приращения содержимого счетчика 20, Иначе проверяется усло" вие Х 2 на выходе элемента 15 сравнения, являющееся результатом сравне- ния на равенство содержимого счетчика 21 и регистра 18, Если они не равны, то происходит переход к микрооперации обнуления счетчика 20 и прира" щения счетчика 21. Иначе по сигналу 79 обнуляется счетчик 22.Затем по сигналу У 5 обнуляется счетчик 20 и по сигналу 7 10 производится приращение содержимого счетчика 22. По сигналу У 7 производится приращение счетчика 20, По сигналу 711, поступающему на вход разрешения записи БП 1 тестов через элемент ИЛИ 23, с шины данных (ШД 3) в БП 1 тестов вводится очередной символ теста по адресу, задаваемому счетчиками 20 и 22, Производится анализ сигнала Х 1, при его отсутствии происходит переход к микрооперации приращения содержимого счетчика 21, Иначе производится анализ сигнала ХЗ, являющегося выходом элемента 16 сравнения, Сигнал ХЗ вырабатывается в случае, если содержимые счетчика 22 и регистра 19 равны. При его отсутствии происходит переход на микрокоманду обнуления счетчика 21 и приращения счетчика 22.Иначе по сигналу 79 обнуляется счетчик 22По сигналу 71 обнуляется счетчик 21, по сигналу 712 устанавливается в "0" триггер 12 и по сигналу 710 производится приращение содержимого счетчика 22. По сигналу У 5 обнуляется счетчик 20 и производится прира" щение счетчика 21. По сигналу 77 производится приращение счетчика 20, Из блока 1 памяти тестов по адресу, задаваемому счетчиками 20 и 22, считывается символ теста и подается на одни адресные входы блока 6, на другие его адресные входы подаетея символ кубического покрытия из БП 2 описания функций. По сигналу 113 результат пересечения считывается из блока 6 и записывается в блок 3 памяти промежуточных результатов по адресу, задаваемому счетчиком 20. Анализируется сигнал Х 4 на выходе элемента 13сравнения, который появляется при равенстве йода символа на выходе БП 3промежуточных результатов и кода11 на входе 10.5При Наличии сигнала Х 4 происходитпереход на микрооперацию обнулениясчетчика 20 и приращения счетчика 21,Иначе анализируется сигнал Х 1, приего отсутствии происходит переход намикрооперацию приращения счетчика 20.Анализируется сигнал Х 5, при наличиисигнала происходит переход на микрооперацию обнуления счетчика 20, Иначе по сигналу, 75 обнуляется счетчик20 и по сигналу 14 устанавливаетсяв "1" триггер 12, По сигналу 7 производится приращение счетчика 20; Посигналу 715, поступающему на вход 20разрешения записи БП 4 результатовмоделирования через элемент ИЛИ 25,в .БП 4 результатов моделирования свхода 10 через мультиплексор 9 заносится код -11 символа Ф по адресу, 25задаваемому счетчиком 20. Анализируется условие Х 1, при его выполнении происходит переход на микрооперацию приращения счетчика 20. Иначепо сигналу У 5 обнуляется счетчик 20.По сигналу 7 происходит его приращение, По сигналу 716, поступающему навход разрешения чтения блока 7 черезэлемент ИЛИ 24, на входы блока 7 через мультиплексор 8 с .БП 3 промежу 35точных результатов подается одинобъединяемый символ, из БП 4 результатов моделирования на другие входыблока 7 - другой объединяемый символ,с выходом блока 7 результат объединения записывается в буферный регистр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 символа Ф . С выхода блока 7 по сигналу 117, поступающему на вход разрешения чтения блока 7 через элемент ИЛИ 24, символ блока 4 записывается в БПтестов по адресу, заданному счетчиками 20 и 22, при этом обеспечивается пересылка результатов моделирования одного набора теста из Б 1 4 и БП 1. Анализируется сигнал Х 1, при его отсутствии производится переход на микрооперацию приращения счетчика 20. Иначе анализируется сигнал ХЗ, при его отсутствии производится переход на микрооперацию обнуления счетчика 20, обнуления триггера 12 и приращения счетчика 22.Формула изобретенияУстройство для моделирования конечных автоматов, содержащее блок памяти описания функций, блок памяти тестов, блок памяти результатов моделирования, первый и второй мультиплексоры, первый и второй счетчики, первы элемент сравнения и первый регистр, причем выход первого счетчика подключен к первому входу первого элемента сравнения, о т л и ч а ющ е е с я тем, что, с целью расширения функциональных воэможностей устройства эа счет моделирования в многозначном алфавите, оно содержит третий счетчик, второй и третий регистры, триггер, второй, третий и четвертый элементы сравнения, первый и второй блоки постоянной памяти, блок памяти промежуточных результатов, буферный регистр, первый, второй н третий элементы ИЛИ и блок управления, при этом выход первого счетчика подключен к ервым адресным входам блока памяти тестов и блока памяти описания функций, к адресным входам блока памяти промежуточных результатов и блока памяти результатов моделирования, выход второго счетчика подключен к первому входу второго элемента сравнения и к второму адресному входу блока памяти описания функций, выход которого подключен к первому адресному входу первого бло 1520534 12ка постояннойпамяти, выход третьего счетчика подключен к первому входу третьего элемента сравнения и к второму адресному входу блока памяти5 тестов, выход которого подключен к второму адресному входу первого блока постоянной памяти, выход которого подключен к информационному входу блока памяти промежуточных результа О тов, выход которого подключен к первому входу четвертого элемента сравне,ния и к первому информационному входу первого мультиплексора, выход которого подключен к первому адресному 15 входу второго блока постоянной памяти, выход которого подключен к информационным входам блока памяти тестов и буферного регистра и объединен с входом символов теста устройства, 20 вход констант которого подключен к второму информационному входу первого мультиплексора, к второму входу четвертого элемента сравнения и к первому информационному входу второ го мультиплексора, выход которого подключен к информационному входу блока памяти результатов моделирования, выход которого подключен к второму адресному входу второго блока посто янной памяти, входы числа переменных, числа строк кубического покрытия и числа моделируемых наборов теста устройства подключены соответственно к информационным входам первого, вто- З 5 рого и третьего регистров, выходы которых подключены соответственно к вторым входам первого, второго и третьего элементов сравнения, выходы которых подключены к первому, второ му и третьему входам режима блока управления, четвертый и пятый входы режима которого подключены соответственно к выходам четвертого элемента сравнения и триггера, выход буферно го регистра подключен к второму информационному входу второго мультиплексора, вход синхронизации и вход запуска устройства подключены соответственно к одноименным входам блока управления, первый выход которогоподключен к выходу признака остановаустройства, вход описания функций которого подключен к информационномувходу блока памяти описания функций,выходы с второго по тринадцатый блока управления подключены соответственно к входу установки в "О" первого счетчика, к входам записи первого,второго и третьего регистров, к входу установки в "О" второго счетчика,к счетным входам первого и второгосчетчиков, к входу записи блока памяти описания функций, к входу установки в "О" третьего счетчика, к счетному входу третьего счетчика, к первому входу первого элемента ИЛИ, к входу установки в "О" триггера, че ырнадцатый выход блока управления подключен к входу чтения первого блокапостоянной памяти и к входу записиблока памяти промежуточных результатов, пятнадцатый выход блока управления - к входу установки в "1" триггера, шестнадцатый выход - к первомууправляющему входу второго мультиплексора и к первому входу второгоэлемента ИЛИ, семнадцатый выход - кпервому управляющему входу первогомультиплексора, к первому входу третьего элемента ИЛИ и к входу записибуферного регистра, восемнадцатыйвыход - к второму управляющему входупервого мультиплексора,к вторым входампервого и третьего элементов ИЛИ,выходпоследнего подключен к входу чтения второго блока постоянной памяти, девятнадцатый выход блока управления под"ключен к второму управляющему входувторого мультиплексора и к второмувходУ второго элемента ИЛИ, выход которого подключен к входу записи блока памяти результатов моделирования,выход первого элемента ИЛИ подключенк входу записи блока памяти тестов.1520534аиелроЮ сси РодоР уСическог крюгтгия Пересечен1520534 ОАединени иг Составитель В.Смирнов. Редактор В,Петраш Техред Л.Сердюкова Корректор Н.Король Заказ 6760/51 Тираж 668 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж, Раушская наб., д. 4/5 Гагарина, 10 ор Производственно-издательский комбинат "Патент",несение о лервдОделироданиемчередново набора Пера оако резулотама одоединеииюо Фон еаевеиЮРесРРу оо