Главная страница  |  Описание сайта  |  Контакты
МИКРОПРОГРАММНЫЙ АВТОМАТ
МИКРОПРОГРАММНЫЙ АВТОМАТ

МИКРОПРОГРАММНЫЙ АВТОМАТ

Патент Российской Федерации
Суть изобретения: Изобретение относится к вычислительной технике и может быть использовано в микропрограммных устройствах управления с жесткой логикой, например в устройствах управления быстродействующих специализированных ЭВМ. Целью изобретения является упрощение. Автомат содержит сдвиговый регистр 1, блок 2 элементов И, блок 3 элементов ИЛИ, элемент ИЛИ 4, блок 5 элементов ИЛИ. Использование единичного кодирования состояний абстрактного автомата позволяет значительно упростить структуру комбинационной части автомата при одновременном увеличении разрядности сдвигового регистра 1 до N, где N-число состояний абстрактного автомата. 5 ил.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

   С помощью Яндекс:  

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2018937
Класс(ы) патента: G06F9/00, G06F7/00
Номер заявки: 5005585/24
Дата подачи заявки: 09.08.1991
Дата публикации: 30.08.1994
Заявитель(и): Винницкий политехнический институт
Автор(ы): Кожемяко В.П.; Мартынюк Т.Б.; Кутаев Ю.Ф.; Буда А.Г.; Кожемяко К.В.
Патентообладатель(и): Винницкий политехнический институт
Описание изобретения: Изобретение относится к вычислительной технике и может быть использовано в микропрограммных устройствах управления с жесткой логикой, например в устройствах управления быстродействующих специализированных ЭВМ.
Целью изобретения является упрощение автомата.
На фиг. 1 представлена структурная схема автомата; на фиг. 2 и 3 - часть микропрограммы алгоритма; на фиг. 4 - пример функциональной схемы блока элементов И, блоков элементов ИЛИ и элемента ИЛИ с комбинационной частью автомата; на фиг. 5 - временные диаграммы работы автомата.
Микропрограммный автомат (фиг. 1) содержит сдвиговый регистр 1, блок 2 элементов И, блок 3 элементов ИЛИ, элемент ИЛИ 4, блок 5 элементов ИЛИ. Входы 61,...,6L автомата подключены к входам второй группы блока 2 элементов И, входы первой группы которого и входы блока 5 элементов ИЛИ соединены с информационными выходами сдвигового регистра 1. Выходы 71,...,7H блока 2 элементов И соединены с соответствующими входами блока 3 элементов ИЛИ, выходы блока 5 элементов ИЛИ подключены к выходам 81,...,8K автомата, выходы 91, . ..,9P блока 3 элементов ИЛИ соединены с соответствующими информационными входами сдвигового регистра 1, а выходы 101,...,10G блока 3 элементов ИЛИ подключены к соответствующим входам элемента ИЛИ 4, выход 11 которого соединен с первым входом режима сдвигового регистра 1. Тактовый вход, вход сброса, последовательный информационный вход и второй вход режима сдвигового регистра 1 подключены соответственно к входам 12, 13, 14, 15 автомата.
Микропрограмма алгоритма (фиг. 2) представлена четырьмя операторными вершинами с соответствующими управляющими сигналами YK, YK+1, YK+2 и двумя условными вершинами с соответствующими сигналами , где переменные , могут принимать одно из двух состояний: "0" и "1" и обозначаться соответственно Xl, , Xl+1.
На фиг. 3 показан граф автомата Мура для представленной на фиг. 2 микропрограммы. В вершины графа вписаны соответствующие состояния ai,...,ai+3 автомата Мура и управляющие сигналы Yk,...,Yk+2. В начале стрелок записаны условия перехода.
Блок 2 элементов И (фиг. 4) содержит пять элементов И 16,..., 20, причем первые входы элементов И 16, 17 подключены к (i+1)-у выходу Qi+1, а первые входы элементов И 18, 19, 20 - к (i+3)-у выходу Qi+3 сдвигового регистра 1. Вторые входы элементов И 16, 17, 18 подключены к входам 61, 62, 63, на которые поступают сигналы Xl, соответственно, а вторые и третьи входы элементов И 19, 20 соединены с входами 61, 62 и 64соответственно, на которые поступают сигналы Xl, и Xl+1. Выходы элементов И 16,...,20 подключены к выходам 71,...,75 соответственно. Блок 3 элементов ИЛИ содержит шесть элементов ИЛИ 21, 26, причем выход 71 подключен к первому инверсному входу элемента ИЛИ 21 и первому входу элемента ИЛИ 24, выход 72 - к второму инверсному входу элемента ИЛИ 21 и первому входу элемента ИЛИ 23, выход 73 - к первому инверсному входу элемента ИЛИ 22 и первому входу элемента ИЛИ 25, выход 74 - к второму инверсному входу элемента ИЛИ 22 и второму входу элемента ИЛИ 24, выход 75 - к второму входу элемента ИЛИ 23. Второй вход элемента ИЛИ 25 соединен с выходом элемента ИЛИ 21, а входы элемента ИЛИ 26 - с выходами элементов ИЛИ 22, 23. Выходы элементов ИЛИ 25, 24, 26 подключены к выходам 91, 92, 93, а выходы элементов ИЛИ 23, 24 и первый вход элемента ИЛИ 25 соединены соответственно с выходами 101, 102 и 103. Элемент ИЛИ 4 содержит элемент ИЛИ 27, входы которого подключены к выходам 101, 102, 103, а выход - к выходу 11. Блок 5 элементов ИЛИ содержит элемент ИЛИ 28, входы которого подключены к i-у и (i + 2 ) - y выходам Qi и Qi+2сдвигового регистра 1, а выход - к выходу 81, выходы 82 и 83 соединены с (i+1)-м и (i+3)-м выходами Qi+1 и Qi+3 сдвигового регистра 1.
Автомат работает следующим образом.
В связи с тем, что кодирование состояний автомата Мура реализуется следующим образом:
ai - 0...10000...0,
ai+1 - 0...01000...0,
ai+2 - 0...00100...0,
ai+3 - 0...00010...0, в процессе работы в каждом такте необходимо выполнить сдвиг информации в сдвиговом регистре 1 на один разряд в сторону старших разрядов таким образом, что за время выполнения алгоритма, представленного соответствующей линейной микропрограммой, единица, предварительно зафиксированная в первом разряде сдвигового регистра 1, последовательно проходит через все разряды N сдвигового регистра. Таким образом, в сдвиговом регистре осуществляется сдвиг единичного кода вида 0...010...0. Количество разрядов N сдвигового регистра 1 определяется максимальным числом неповторяющихся состояний автомата Мура, реализуемым на линейной цепи граф-схемы автомата (фиг. 3). Поскольку все вершины граф-автомата могут быть объединены в три линейные цепи: C1 = {ai, ai+1, ai+2}, C2 = {ai, ai+1, ai+3, ai+3, ai+2}, C3 = {ai,ai+1,ai+3, ai+3, ai+1, ai+2} и линейная цепь C3 содержит максимальное количество операторных вершин и переходов, то N = 4. Выходами линейных цепей являются операторные вершины ai+1 и ai+3, а входами - ai+2, ai+3, ai+1. На любом переходе, принадлежащем линейной цепи, а также при условии, что состояния линейной цепи следуют одно за другим в порядке возрастания индексов состояний, т.е. в виде ai, ai+1...., ai+j,..., где j = 0, 1, 2, 3,..., код нового состояния автомата Мура образуется путем сдвига текущего состояния на один разряд в сторону старших разрядов сдвигового регистра 1. Во всех остальных условиях, а также при переходах между выходами и входами линейных цепей и автомата Мура выполняются параллельная засылка кода нового состояния и стирание кода текущего состояния в сдвиговом регистре 1 путем возбуждения информационных входов Di,...,Di+3. Таким образом, элемент ИЛИ 4 задействован в обоих случаях, поскольку формирует управляющий сигнал сдвига в сторону старших разрядов сдвигового регистра 1 и сигнал разрешения записи по параллельным информационным входам сдвигового регистра, а блок 3 элементов ИЛИ - только во втором случае, поскольку формирует сигнал установки в единичное состояние и сигнал обнуления соответствующих разрядов сдвигового регистра 1.
Таким образом, блок 2 элементов И является преобразователем кодов состояний сдвигового регистра 1 и входных сигналов автомата в сигналы возбуждения. Блок 3 элементов ИЛИ осуществляет формирование сигналов сброса в "ноль" и установки в "единицу" разрядов сдвигового регистра 1. Элемент ИЛИ 4 формирует сигналы разрешения записи (S1=1) или сдвига (S1=0) содержимого сдвигового регистра. Блок 5 элементов ИЛИ формирует выходные сигналы автомата.
Перед началом работы автомата происходит обнуление сдвигового регистра 1 по сигналу, поступающему на вход 13, а начальным состоянием сдвигового регистра является такое состояние, когда присутствует единичный сигнал Q1 на выходе первого разряда сдвигового регистра. Установка в начальное состояние выполняется с приходом тактового сигнала и при наличии единичных сигналов на входах 14 и 15, т.е. при следующей комбинации сигналов на входах сдвигового регистра 1: DSR = 1, S0 = 1, Q1= 1. Единичный сигнал Q1 с выхода первого разряда сдвигового регистра 1 поступает на первые входы блоков 2 и 5 и участвует в формировании соответствующих управляющих сигналов Y1,...,YK, а также при наличии условных переходов, пройдя через блок 3 элементов ИЛИ и элемент ИЛИ 4, формирует сигналы, поступающие на соответствующие информационные параллельные входы D1,...,Dn и вход S1 сдвигового регистра 1. Если между состояниями a1 и a2 автомата нет условного перехода, то с приходом следующего тактового сигнала и при наличии сигналов DSR=0, S0=1, S1= 0 на входах сдвигового регистра 1 в нем выполняется сдвиг вправо его содержимого, в результате чего появляется единичный сигнал на выходе Q2сдвигового регистра. Если между состояниями a1 и ai автомата существует условный переход, на первом выходе 71 блока 2 формируется единичный сигнал, который поступает на вход блока 3, в результате чего на вход D1сдвигового регистра 1 поступает нулевой сигнал, а на вход Di - единичный сигнал с одновременным формированием элементом ИЛИ 4 единичного сигнала на выходе 11. Таким образом, при наличии сигналов S0=1, S1=1 на входах сдвигового регистра 1 с поступлением следующего тактового сигнала в последнем происходит смена состояний. Аналогичные действия выполняются на каждом безусловном и условном переходах автомата Мура.
В соответствии с граф-схемой автомата (фиг. 3) на соответствующих выходах 81, ...,8K блока 5 необходимо получить управляющие сигналы Yk, Yk+1, Yk+2 с учетом сигналов и , поступающих на соответствующие входы 61,. ..,6L блока 2.
Предположим, что сдвиговый регистр 1 находится в состоянии ai, т.е. на его i-м выходе Qi присутствует единичный сигнал, который, поступая на вход блока 5 и пройдя через элемент ИЛИ 28, формирует на соответствующем выходе 81 сигнал Yk (фиг. 4). Поскольку переход к состоянию ai+1 (фиг. 3) является безусловным, то с приходом следующего тактового сигнала на управляющих входах сдвигового регистра 1 присутствуют следующие сигналы: S0=1, S1=0, что приводит к сдвигу информации на один разряд вправо, т.е. к появлению единичного сигнала на (i+1)-м выходе Qi+1 сдвигового регистра 1. Это вызывает появление единичного сигнала на выходе 82, соответствующем сигналу Yk+1, и срабатывание одного из двух элементов И 16, 17 в зависимости от наличия одного из двух сигналов Xl и (фиг. 4). С учетом этого происходит на следующем такте работы автомата, либо условный переход к состоянию ai+2, либо условный переход к состоянию ai+3 автомата (фиг. 3). Для примера рассмотрим случай, когда выполняется условие =1. Тогда единичный сигнал Qi+1 через элемент И 17 с выхода 72поступает на соответствующий вход блока 3, т.е. на входы элементов ИЛИ 21 и 23 (фиг. 4). Вместе с этим единичный сигнал Qi+1, поступая на вход блока 5, появляется на выходе 82, соответствующем сигналу Yk+1. На выходах элементов ИЛИ 21 и 23 формируются соответственно сигналы Di+1(0)и Di+3(1), которые в дальнейшем участвуют в обнулении (i+1)-го и установке в единичное состояние (i+3)-го разрядов сдвигового регистра 1. Единичный сигнал Di+3(1) через элемент ИЛИ 26 поступает на выход 93, который соединен с (i+3)-м информационным входом Di+3 сдвигового регистра, а с выхода 101 поступает через элемент ИЛИ 27 на выход 11 (фиг. 4). Нулевой сигнал Di+1(0) через элемент ИЛИ 25 поступает на выход 91, который соединен с (i+1)-м информационным входом Di+1сдвигового регистра 1. Таким образом, с приходом следующего тактового сигнала на управляющих входах сдвигового регистра присутствуют следующие сигналы: S0=1, S1=1, что приводит к записи информации по (i+1)-у и (i+3)-у параллельным входам Di+1 и Di+3, т.е. к принудительной установке состояния ai+3. Единичный сигнал на (i+3)-м выходе Qi+3 сдвигового регистра 1 участвует в формировании сигнала Yk+2 на соответствующем выходе 83. Из состояния ai+3 возможны три условных перехода (фиг. 3). Рассмотрим случай, когда выполняется условие =1, Xl+1=1. Единичный сигнал Qi+3 через элемент И 20 с выхода 75 поступает на соответствующий вход блока 3, т.е. на один из входов элемента ИЛИ 23 (фиг. 4). На выходе элемента ИЛИ 23 формируется единичный сигнал Di+3(1), который поступает на выход 101 и через элемент ИЛИ 26 на выход 93. Таким образом, на выходе 11 формируется единичный сигнал S1= 1, что позволяет с приходом следующего тактового сигнала записать единичный сигнал в (i+3)-й разряд сдвигового регистра 1, т.е. подтвердить его текущее состояние. Аналогично выполняются все указанные на фиг. 3 условные и безусловные переходы между состояниями автомата Мура.
На фиг. 5 приняты следующие обозначения Б2, Б3, Э4, Б5 - блоки 2, 3, элемент ИЛИ 4, блок 5 соответственно; t1, t2, t3, t4, t5 - время срабатывания сдвигового регистра 1 и блоков 2, 3, элемента 4, блока 5 соответственно, причем t5= t2, t3 = t31 = t4, где t31 - время срабатывания первого уровня логических схем блока 3 (фиг. 4); Tц - длительность цикла, причем Tц = t1 + t2 + t3.
Формула изобретения: МИКРОПРОГРАММНЫЙ АВТОМАТ, содержащий сдвиговый регистр, блок элементов И, два блока элементов ИЛИ и элементов ИЛИ, причем информационные выходы сдвигового регистра соединены с входами первой группы блока элементов И, входы второй группы которого подключены к группе входов автомата, а выходы соединены с соответствующими входами первого блока элементов ИЛИ, выходы первой группы которого подключены к соответствующим параллельным информационным входам сдвигового регистра, первый вход режима которого соединен с выходом элемента ИЛИ, выходы второго блока элементов ИЛИ являются выходами автомата, тактовый вход и вход сброса сдвигового регистра подключены соответственно к входу синхронизации и входу установки в нулевое состояние автомата, отличающийся тем, что, с целью упрощения, выходы второй группы первого блока элементов ИЛИ соединены с соответствующими входами элемента ИЛИ, второй вход режима и последовательный информационный вход сдвигового регистра соединены соответственно с входом положительного потенциала и входом установки в начальное состояние автомата, а информационные выходы сдвигового регистра подключены также к соответствующим входам второго блока элементов ИЛИ.