МИКРОПРОГРАММНЫЙ АВТОМАТ Российский патент 1994 года по МПК G06F9/00 G06F7/00 

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

Целью изобретения является упрощение автомата.

На фиг. 1 представлена структурная схема автомата; на фиг. 2 и 3 - часть микропрограммы алгоритма; на фиг. 4 - пример функциональной схемы блока элементов И, блоков элементов ИЛИ и элемента ИЛИ с комбинационной частью автомата; на фиг. 5 - временные диаграммы работы автомата.

Микропрограммный автомат (фиг. 1) содержит сдвиговый регистр 1, блок 2 элементов И, блок 3 элементов ИЛИ, элемент ИЛИ 4, блок 5 элементов ИЛИ. Входы 6₁,...,6_L автомата подключены к входам второй группы блока 2 элементов И, входы первой группы которого и входы блока 5 элементов ИЛИ соединены с информационными выходами сдвигового регистра 1. Выходы 7₁,...,7_H блока 2 элементов И соединены с соответствующими входами блока 3 элементов ИЛИ, выходы блока 5 элементов ИЛИ подключены к выходам 8₁,...,8_K автомата, выходы 9₁, . ..,9_P блока 3 элементов ИЛИ соединены с соответствующими информационными входами сдвигового регистра 1, а выходы 10₁,...,10_G блока 3 элементов ИЛИ подключены к соответствующим входам элемента ИЛИ 4, выход 11 которого соединен с первым входом режима сдвигового регистра 1. Тактовый вход, вход сброса, последовательный информационный вход и второй вход режима сдвигового регистра 1 подключены соответственно к входам 12, 13, 14, 15 автомата.

Микропрограмма алгоритма (фиг. 2) представлена четырьмя операторными вершинами с соответствующими управляющими сигналами Y_K, Y_K+1, Y_K+2 и двумя условными вершинами с соответствующими сигналами , где переменные , могут принимать одно из двух состояний: "0" и "1" и обозначаться соответственно X_l,, X_l+1.

На фиг. 3 показан граф автомата Мура для представленной на фиг. 2 микропрограммы. В вершины графа вписаны соответствующие состояния a_i,...,a_i+3 автомата Мура и управляющие сигналы Y_k,...,Y_k+2. В начале стрелок записаны условия перехода.

Блок 2 элементов И (фиг. 4) содержит пять элементов И 16,..., 20, причем первые входы элементов И 16, 17 подключены к (i+1)-у выходу Q_i+1, а первые входы элементов И 18, 19, 20 - к (i+3)-у выходу Q_i+3 сдвигового регистра 1. Вторые входы элементов И 16, 17, 18 подключены к входам 6₁, 6₂, 6₃, на которые поступают сигналы X_l, соответственно, а вторые и третьи входы элементов И 19, 20 соединены с входами 6₁, 6₂ и 6₄соответственно, на которые поступают сигналы X_l, и X_l+1. Выходы элементов И 16,...,20 подключены к выходам 7₁,...,7₅ соответственно. Блок 3 элементов ИЛИ содержит шесть элементов ИЛИ 21, 26, причем выход 7₁ подключен к первому инверсному входу элемента ИЛИ 21 и первому входу элемента ИЛИ 24, выход 7₂ - к второму инверсному входу элемента ИЛИ 21 и первому входу элемента ИЛИ 23, выход 7₃ - к первому инверсному входу элемента ИЛИ 22 и первому входу элемента ИЛИ 25, выход 7₄ - к второму инверсному входу элемента ИЛИ 22 и второму входу элемента ИЛИ 24, выход 7₅ - к второму входу элемента ИЛИ 23. Второй вход элемента ИЛИ 25 соединен с выходом элемента ИЛИ 21, а входы элемента ИЛИ 26 - с выходами элементов ИЛИ 22, 23. Выходы элементов ИЛИ 25, 24, 26 подключены к выходам 9₁, 9₂, 9₃, а выходы элементов ИЛИ 23, 24 и первый вход элемента ИЛИ 25 соединены соответственно с выходами 10₁, 10₂ и 10₃. Элемент ИЛИ 4 содержит элемент ИЛИ 27, входы которого подключены к выходам 10₁, 10₂, 10₃, а выход - к выходу 11. Блок 5 элементов ИЛИ содержит элемент ИЛИ 28, входы которого подключены к i-у и (i + 2 ) - y выходам Q_i и Q_i+2сдвигового регистра 1, а выход - к выходу 8₁, выходы 8₂ и 8₃ соединены с (i+1)-м и (i+3)-м выходами Q_i+1 и Q_i+3 сдвигового регистра 1.

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

В связи с тем, что кодирование состояний автомата Мура реализуется следующим образом:
a_i - 0...10000...0,
a_i+1 - 0...01000...0,
a_i+2 - 0...00100...0,
a_i+3 - 0...00010...0, в процессе работы в каждом такте необходимо выполнить сдвиг информации в сдвиговом регистре 1 на один разряд в сторону старших разрядов таким образом, что за время выполнения алгоритма, представленного соответствующей линейной микропрограммой, единица, предварительно зафиксированная в первом разряде сдвигового регистра 1, последовательно проходит через все разряды N сдвигового регистра. Таким образом, в сдвиговом регистре осуществляется сдвиг единичного кода вида 0...010...0. Количество разрядов N сдвигового регистра 1 определяется максимальным числом неповторяющихся состояний автомата Мура, реализуемым на линейной цепи граф-схемы автомата (фиг. 3). Поскольку все вершины граф-автомата могут быть объединены в три линейные цепи: C₁ = {a_i, a_i+1, a_i+2}, C₂ = {a_i, a_i+1, a_i+3, a_i+3, a_i+2}, C₃ = {a_i,a_i+1,a_i+3, a_i+3, a_i+1, a_i+2} и линейная цепь C₃ содержит максимальное количество операторных вершин и переходов, то N = 4. Выходами линейных цепей являются операторные вершины a_i+1 и a_i+3, а входами - a_i+2, a_i+3, a_i+1. На любом переходе, принадлежащем линейной цепи, а также при условии, что состояния линейной цепи следуют одно за другим в порядке возрастания индексов состояний, т.е. в виде a_i, a_i+1...., a_i+j,..., где j = 0, 1, 2, 3,..., код нового состояния автомата Мура образуется путем сдвига текущего состояния на один разряд в сторону старших разрядов сдвигового регистра 1. Во всех остальных условиях, а также при переходах между выходами и входами линейных цепей и автомата Мура выполняются параллельная засылка кода нового состояния и стирание кода текущего состояния в сдвиговом регистре 1 путем возбуждения информационных входов D_i,...,D_i+3. Таким образом, элемент ИЛИ 4 задействован в обоих случаях, поскольку формирует управляющий сигнал сдвига в сторону старших разрядов сдвигового регистра 1 и сигнал разрешения записи по параллельным информационным входам сдвигового регистра, а блок 3 элементов ИЛИ - только во втором случае, поскольку формирует сигнал установки в единичное состояние и сигнал обнуления соответствующих разрядов сдвигового регистра 1.

Таким образом, блок 2 элементов И является преобразователем кодов состояний сдвигового регистра 1 и входных сигналов автомата в сигналы возбуждения. Блок 3 элементов ИЛИ осуществляет формирование сигналов сброса в "ноль" и установки в "единицу" разрядов сдвигового регистра 1. Элемент ИЛИ 4 формирует сигналы разрешения записи (S1=1) или сдвига (S1=0) содержимого сдвигового регистра. Блок 5 элементов ИЛИ формирует выходные сигналы автомата.

Перед началом работы автомата происходит обнуление сдвигового регистра 1 по сигналу, поступающему на вход 13, а начальным состоянием сдвигового регистра является такое состояние, когда присутствует единичный сигнал Q₁ на выходе первого разряда сдвигового регистра. Установка в начальное состояние выполняется с приходом тактового сигнала и при наличии единичных сигналов на входах 14 и 15, т.е. при следующей комбинации сигналов на входах сдвигового регистра 1: DSR = 1, S0 = 1, Q₁= 1. Единичный сигнал Q₁ с выхода первого разряда сдвигового регистра 1 поступает на первые входы блоков 2 и 5 и участвует в формировании соответствующих управляющих сигналов Y₁,...,Y_K, а также при наличии условных переходов, пройдя через блок 3 элементов ИЛИ и элемент ИЛИ 4, формирует сигналы, поступающие на соответствующие информационные параллельные входы D₁,...,D_n и вход S1 сдвигового регистра 1. Если между состояниями a₁ и a₂ автомата нет условного перехода, то с приходом следующего тактового сигнала и при наличии сигналов DSR=0, S0=1, S1= 0 на входах сдвигового регистра 1 в нем выполняется сдвиг вправо его содержимого, в результате чего появляется единичный сигнал на выходе Q₂сдвигового регистра. Если между состояниями a₁ и a_i автомата существует условный переход, на первом выходе 7₁ блока 2 формируется единичный сигнал, который поступает на вход блока 3, в результате чего на вход D₁сдвигового регистра 1 поступает нулевой сигнал, а на вход D_i - единичный сигнал с одновременным формированием элементом ИЛИ 4 единичного сигнала на выходе 11. Таким образом, при наличии сигналов S0=1, S1=1 на входах сдвигового регистра 1 с поступлением следующего тактового сигнала в последнем происходит смена состояний. Аналогичные действия выполняются на каждом безусловном и условном переходах автомата Мура.

В соответствии с граф-схемой автомата (фиг. 3) на соответствующих выходах 8₁, ...,8_K блока 5 необходимо получить управляющие сигналы Y_k, Y_k+1, Y_k+2 с учетом сигналов и , поступающих на соответствующие входы 6₁,. ..,6_L блока 2.

Предположим, что сдвиговый регистр 1 находится в состоянии a_i, т.е. на его i-м выходе Q_i присутствует единичный сигнал, который, поступая на вход блока 5 и пройдя через элемент ИЛИ 28, формирует на соответствующем выходе 8₁ сигнал Y_k (фиг. 4). Поскольку переход к состоянию a_i+1 (фиг. 3) является безусловным, то с приходом следующего тактового сигнала на управляющих входах сдвигового регистра 1 присутствуют следующие сигналы: S0=1, S1=0, что приводит к сдвигу информации на один разряд вправо, т.е. к появлению единичного сигнала на (i+1)-м выходе Q_i+1 сдвигового регистра 1. Это вызывает появление единичного сигнала на выходе 8₂, соответствующем сигналу Y_k+1, и срабатывание одного из двух элементов И 16, 17 в зависимости от наличия одного из двух сигналов X_l и (фиг. 4). С учетом этого происходит на следующем такте работы автомата, либо условный переход к состоянию a_i+2, либо условный переход к состоянию a_i+3 автомата (фиг. 3). Для примера рассмотрим случай, когда выполняется условие =1. Тогда единичный сигнал Q_i+1 через элемент И 17 с выхода 7₂поступает на соответствующий вход блока 3, т.е. на входы элементов ИЛИ 21 и 23 (фиг. 4). Вместе с этим единичный сигнал Q_i+1, поступая на вход блока 5, появляется на выходе 8₂, соответствующем сигналу Y_k+1. На выходах элементов ИЛИ 21 и 23 формируются соответственно сигналы D_i+1⁽⁰⁾и D_i+3⁽¹⁾, которые в дальнейшем участвуют в обнулении (i+1)-го и установке в единичное состояние (i+3)-го разрядов сдвигового регистра 1. Единичный сигнал D_i+3⁽¹⁾ через элемент ИЛИ 26 поступает на выход 9₃, который соединен с (i+3)-м информационным входом D_i+3 сдвигового регистра, а с выхода 10₁ поступает через элемент ИЛИ 27 на выход 11 (фиг. 4). Нулевой сигнал D_i+1⁽⁰⁾ через элемент ИЛИ 25 поступает на выход 91, который соединен с (i+1)-м информационным входом D_i+1сдвигового регистра 1. Таким образом, с приходом следующего тактового сигнала на управляющих входах сдвигового регистра присутствуют следующие сигналы: S0=1, S1=1, что приводит к записи информации по (i+1)-у и (i+3)-у параллельным входам D_i+1 и D_i+3, т.е. к принудительной установке состояния a_i+3. Единичный сигнал на (i+3)-м выходе Q_i+3 сдвигового регистра 1 участвует в формировании сигнала Y_k+2 на соответствующем выходе 8₃. Из состояния a_i+3 возможны три условных перехода (фиг. 3). Рассмотрим случай, когда выполняется условие =1, X_l+1=1. Единичный сигнал Q_i+3 через элемент И 20 с выхода 7₅ поступает на соответствующий вход блока 3, т.е. на один из входов элемента ИЛИ 23 (фиг. 4). На выходе элемента ИЛИ 23 формируется единичный сигнал D_i+3⁽¹⁾, который поступает на выход 10₁ и через элемент ИЛИ 26 на выход 9₃. Таким образом, на выходе 11 формируется единичный сигнал S1= 1, что позволяет с приходом следующего тактового сигнала записать единичный сигнал в (i+3)-й разряд сдвигового регистра 1, т.е. подтвердить его текущее состояние. Аналогично выполняются все указанные на фиг. 3 условные и безусловные переходы между состояниями автомата Мура.

На фиг. 5 приняты следующие обозначения Б2, Б3, Э4, Б5 - блоки 2, 3, элемент ИЛИ 4, блок 5 соответственно; t₁, t₂, t_3, t₄, t₅ - время срабатывания сдвигового регистра 1 и блоков 2, 3, элемента 4, блока 5 соответственно, причем t₅= t₂, t₃ = t₃¹ = t₄, где t₃¹ - время срабатывания первого уровня логических схем блока 3 (фиг. 4); T_ц - длительность цикла, причем T_ц = t₁ + t₂ + t₃.

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

МИКРОПРОГРАММНЫЙ АВТОМАТ, содержащий сдвиговый регистр, блок элементов И, два блока элементов ИЛИ и элементов ИЛИ, причем информационные выходы сдвигового регистра соединены с входами первой группы блока элементов И, входы второй группы которого подключены к группе входов автомата, а выходы соединены с соответствующими входами первого блока элементов ИЛИ, выходы первой группы которого подключены к соответствующим параллельным информационным входам сдвигового регистра, первый вход режима которого соединен с выходом элемента ИЛИ, выходы второго блока элементов ИЛИ являются выходами автомата, тактовый вход и вход сброса сдвигового регистра подключены соответственно к входу синхронизации и входу установки в нулевое состояние автомата, отличающийся тем, что, с целью упрощения, выходы второй группы первого блока элементов ИЛИ соединены с соответствующими входами элемента ИЛИ, второй вход режима и последовательный информационный вход сдвигового регистра соединены соответственно с входом положительного потенциала и входом установки в начальное состояние автомата, а информационные выходы сдвигового регистра подключены также к соответствующим входам второго блока элементов ИЛИ.