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

Настоящее изобретение относится к вычислительной технике и дискретной автоматике и может быть использовано для построения устройств управления в системах обработки информации, а также для управления технологическими процессами в реальном времени.
Схемы микропрограммных автоматов (МПА) известны по авторскому свидетельству СССР 1365986, БИ 1, 1988, патентам РФ №2071111, 2058041, 2071112, 20779876, 20446396, 2046395, 2042190, 2042189, 2042188, 2018937.
Известны также структурные схемы автоматов Мура и Мили, подробно описанные в научно-технической литературе [1-6].
Известны МПА с самоконтролем, описанные в [1-3], а также в патенте РФ 63588 (авторы: Мухопад А.Ю, Мухопад Ю.Ф., Бадмаева Т.С.)
МПА с самоконтролем имеют ту же структуру, однако для обеспечения самоконтролируемости исходное состояние автомата a(t) и вычисляемое состояние a(t+1) представлены избыточными кодами.
Варианты такого кодирования наиболее полно изложены в работе [1].
В патенте РФ 63588 этот же метод реализован за счет использования модифицированного геометрического кода (МГК) для представления a(t+1) и двоичного непозиционного кода (ДНК) для a(t).
Однако и этот способ по патенту РФ №63588 довольно сложен, т.к. размер кода состояния a(t+1) увеличивается примерно в два раза по сравнению с двоичным позиционным (или двоичным соседним) кодом, используемым в МПА с «классической» структурной организацией [1-4].
Целью настоящего изобретения является упрощение конструкции МПА и введение средств самоконтроля, не сводящихся к способу избыточного кодирования, а следовательно, обеспечение самоконтролируемости меньшими затратами оборудования.
Наиболее близкими прототипом к предложенному изобретению (по составу блоков и связей между ними) является МПА по полезной модели РФ №82888, БИ 13, 2009 - авторы: Мухопад А.Ю., Мухопад Ю.Ф. [7].
j
1
2
q
q-1
По сравнению с МПА с классической структурной организацией автоматов Мура [1-6] в полезной модели РФ №82888 объем комбинационной схемы для вычисления a(t+1) по коду a(t) с учетом логических условий α∈{α,α,…,α} уменьшен в 2 раз, где q - количество входных переменных МПА, называемых также логическими условиями.
Для достижения такого эффекта исходная граф-схема алгоритма (ГСА) преобразуется за счет ввода пустых операторов. Методика синтеза таких МПА подробно изложена в работах [5, 6].
На фиг.1 представлена структурная схема МПА прототипа по полезной модели РФ №82888, БИ 13, 2009.
На фиг.1 введены обозначения:
ОУ - объект управления (или операционное устройство) - (1);
1
2
q
Rg - Регистр памяти логических условий αα…α - (2);
M - мультиплексор - (3);
RS - триггер хранения α - (4);
1
1
2
m
1
2
m
F (1) - комбинационная схема для вычисления состояния автомата a(t+l) - код yy…y по коду состояния a(t) - xx…x и логическому условию α∈{α}.
2
1
2
k
F - комбинационная схема формирования выходных команд A,A,…,A - (10);
3
1
2
m
j
1
2
q
F - комбинационная схема преобразования кода состояния автомата x,x,…,x в код адреса логического условия α∈{α,α,…,α} - (9);
СС - схема синхронизации - (1).
Блок памяти состояний МПА представлен в виде структуры блоков 6, 7, 8.
1
1
3
1
2
m
j
1
2
p
3
q-1
Снижение объема памяти схемы F в 2 раз в полезной модели РФ №82888 по сравнению с F в классической структуре МПА достигнуто за счет введения третьей комбинационной схемы F для преобразования кода a(t+1) - yy…y в адрес, соответствующий номеру α-zz…z, здесь p - разрядность адресного кода мультиплексора. При этом требуется дополнительный импульс синхронизации для опроса схемы F.
1
2
p
j
j
По адресу zz…z через мультиплексор M (3) осуществляется выбор одного α из множества {α}, причем именно того условия, которое необходимо для вычисления следующего состояния a(t+1) по коду a(t) и α∈{α}.
3
1
2
p
Такая процедура осуществляется комплексом последовательно связанных блоков F (9) и мультиплексора M (3). Причем для обеспечения правильного функционирования необходим еще регистр памяти для записи адреса zz…z.
На фиг.1 такой регистр не показан, т.к. предполагается, что он внесен в структуру адресной части мультиплексора M (3).
j
1
2
m
1
2
p
Такая реализация средств выбора α∈{α} по коду yy..y через F3 (9) плюс M (3) с внутренним регистром памяти адреса zz…z усложняет конструкцию МПА по патенту РФ №82888, а, кроме того, в МПА по указанному патенту нет каких-либо средств самоконтроля.
Целью изобретения является упрощение конструкции МПА в части вычисления адреса логических условий, а также введение аппаратных средств самоконтроля.
Предлагаемый микропрограммный автомат представлен на фиг.2.
Микропрограммный автомат, состоящий из регистра памяти логических условий, двух регистров памяти состояний с парафазной связью между ними и двух комбинационных схем, отличается тем, что первая комбинационная схема (1) образует последовательную цепь блоков через m параллельных выходов, которая через первый регистр памяти (2) связана с первыми входами коммутатора (3), три выхода которого связаны со входами схемы выбора (4), причем выходы первой комбинационной схемы одновременно связаны с первыми m входами второго регистра памяти (5), парафазно связанного через блок схем «И» (6) с третьим регистром памяти (7), выходы которого соединены с первыми m входами первой комбинационной схемы (1), а первый выход схемы выбора (4) связан с единичным входом первого триггера (8), парафазно связанного через независимые схемы «И» (9) со вторым триггером (10), единичный выход которого связан с (m+1)-м входом первой комбинационной схемы (1), причем m выходов третьего регистра памяти связаны со входами второй комбинационной схемы (11), k выходов которой образуют последовательную цепь блоков в виде операционного устройства (12), q выходов которого через четвертый регистр памяти (13) связаны со второй группой входов коммутатора (3), при этом второй выход схемы выбора (4) образует внешнюю клемму фиксации ошибки (14); причем микропрограммный автомат включает в себя также блок синхронизации (15) с внешними входами Пуск (16) и Останов (17), четыре выхода которого образуют разделенные во времени импульсы синхронизации, связанные с соответствующими управляющими входами первой комбинационной схемы (1), блоком схем «И» (6) и схемами «И» (9), а также с первым (2) и четвертым (13) регистрами памяти.
На фиг.2 введены следующие обозначения:
1
1
2
m
1
2
m
F(1) - первая комбинационная схема для вычисления состояния автомата a(t+1) - код yy…y по коду состояния a(t) - xx…x и логическому условию α∈{α}.
Rg (2) - первый регистр памяти;
КМ (3) - коммутатор;
СВ (4) - схемы выбора;
Rg a(t+1) (5) - регистр памяти кода состояния a(t+1);
& (6) - блок схем «И»;
Rg a(t) (7) - регистр памяти состояний a(t);
RS (8, 9) - первый (8) и второй (9) RS-триггеры;
2
1
2
k
1
2
m
F(11) - вторая комбинационная схема, формирующая команды управления A,A,…,A по коду состояния a(t) - xx…x;
ОУ (12) - объект управления (операционное устройство);
1
2
q
αα…α - множество логических условий {α}, формируемых в ОУ( 12);
Rg (13) - четвертый регистр памяти, хранящий значения {α};
<mrow><msub><mi>α</mi><mn>0</mn></msub><mo>,</mo><msub><mi>α</mi><mi>j</mi></msub><mo>,</mo><mover accent="true"><mi>α</mi><mo>˜</mo></mover></mrow>
- выходы блока коммутатора (3), где
0
α - безусловный переход,
<mover accent="true"><mi>α</mi><mo>˜</mo></mover>
- несуществующие логические условия,
j
1
2
m,
α∈{α} - одно из логических условий, выбираемое КМ (3) по коду yy...y
0
j
α - выбираемое СВ (4), т.е. значение α или α;
ERR (14) - ошибка;
БС (15) - блок синхронизации;
1
2
3
4
τ(t)&τ(t)&τ(t)&τ(t)=⌀
импульсы синхронизации, формируемые БС (15).
Для лучшего уяснения принципа функционирования микропрограммного автомата (далее автомат или МПА) приводится описание блоков МПА.
ОУ (12) - не является неотъемлемой частью МПА, но введено в структуру фиг.1 и 2 для того, чтобы показать связь МПА по его входам и выходам.
Все четыре регистра памяти Rg (2, 5, 7, 13) не имеют особенностей и различаются лишь разрядностью m для Rg (2, 5, 7) и q - для Rg (13).
1
2
m
1
2
m
Первая комбинационная схема как и в прототипе реализуется через ПЗУ или ПЛМ для определения кода yy..y по конкатенации αxx…x.
2
1
2
m
i
Вторая комбинационная схема F(11) для автоматов Мура состоит из дешифратора с m-адресными входами xx…x, выходы которого объединяются схемами «ИЛИ», если одна и та же команда A соответствует нескольким выходам дешифратора, т.е. нескольким состояниям МПА - a(t).
j
0
1
2
q
1
2
m
Специальными блоками в предлагаемом изобретении являются лишь блок коммутации КМ (3), выбирающий α из логических сигналов ααα…α по унитарному коду yy…y на один выход α, а также блок выбора СВ (4).
1
2
q
j
Блок коммутации КМ (3) фиг.3 представляет собой дешифратор (DC) (20), к выходам которого подсоединены q логических двухвходовых (21) элементов «И» (где q - количество логическим сигналов αα…α), к первым входам которых подсоединяются единичные выходы триггеров Rg (13), а ко вторым - только те q выходов, которым соответствует выбор конкретного α∈{α} при данном состоянии a(t).
j
j
Причем если разным состояниям a(t) соответствует выбор одного и того же α, то перед соединением выходов с входом элемента «И» эти выходы объединяются через логический элемент «ИЛИ» (22). Выходы всех q элементов «И» также объединяются схемой «ИЛИ» (23) с выходом, обозначенным символом α.
0
<mover accent="true"><mi>α</mi><mo>˜</mo></mover>
Две схемы «ИЛИ» - 24 и 25 осуществляют «сборку» тех состояний, при которых необходимо формировать сигналы α или
.
0
j
Схема выбора СВ (4) производит выбор сигнала α или α и формирует сигнал ошибки (ERR) на второй выход схемы СВ (13).
Схема выбора реализует условия:
<mrow><mi>E</mi><mi>R</mi><mi>R</mi><mo>=</mo><msub><mi>α</mi><mn>0</mn></msub><mo>•</mo><mover accent="true"><mi>α</mi><mo>˜</mo></mover><mo>+</mo><msub><mi>α</mi><mn>0</mn></msub><mo>•</mo><msub><mi>α</mi><mi>j</mi></msub><mo>+</mo><mover accent="true"><mi>α</mi><mo>˜</mo></mover><mo>•</mo><msub><mi>α</mi><mi>j</mi></msub><mo>+</mo><mover accent="true"><mi>α</mi><mo>˜</mo></mover><mo>=</mo><mover accent="true"><mi>α</mi><mo>˜</mo></mover><mo>+</mo><msub><mi>α</mi><mn>0</mn></msub><mo>•</mo><msub><mi>α</mi><mi>j</mi></msub></mrow>
<mrow><mi>α</mi><mo>=</mo><mover accent="true"><mrow><mi>E</mi><mi>R</mi><mi>R</mi></mrow><mo stretchy="true">¯</mo></mover><mrow><mo>(</mo><mrow><msub><mi>α</mi><mn>0</mn></msub><msub><mrow><mover accent="true"><mi>α</mi><mo stretchy="true">¯</mo></mover></mrow><mi>j</mi></msub><mo>+</mo><msub><mover accent="true"><mi>α</mi><mo>˜</mo></mover><mi>j</mi></msub><msub><mrow><mover accent="true"><mi>α</mi><mo stretchy="true">¯</mo></mover></mrow><mn>0</mn></msub><mo>+</mo><mover accent="true"><mrow><msub><mi>α</mi><mn>0</mn></msub></mrow><mo stretchy="true">¯</mo></mover><mover accent="true"><mrow><msub><mi>α</mi><mi>j</mi></msub></mrow><mo stretchy="true">¯</mo></mover><mover accent="true"><mover accent="true"><mi>α</mi><mo>˜</mo></mover><mo stretchy="true">¯</mo></mover></mrow><mo>)</mo></mrow></mrow>
j
j
В последней формуле для вычисления α символом α обозначено конкретное значение α, которое может быть равным как «1», так и «0».
Реализация схемы выбора СВ (4) тривиальна на элементах логики (И, ИЛИ, НЕ, Триггер) и не требует детального отображения специальным чертежом.
Блок синхронизации БС (15) не имеет особенностей по сравнению со блоком синхронизации БС (1) фиг.1 прототипа и имеет такую же схему для реализации, представленную на фиг.4.
Такая схема согласно работе [9] выпускается промышленностью как отдельный интегральный модуль (ЧИП).
Описание функционирования МПА.
Первоначально МПА устанавливается в исходное состояние:
0
j
<mover accent="true"><mi>α</mi><mo>˜</mo></mover>
1) Устанавливается в исходное состояние схема коммутатор - т.е. триггеры регистра Rg (13), фиксирующие значения α, α и
.
2) Все регистры памяти автомата (т.е. Rg 2, 5, 7, 13) и RS-триггеры (8, 10) устанавливаются в нулевое состояние.
И только после этого дается сигнал «Пуск» (16) на блок синхронизации БС (15).
1
2
3
4
Далее выполняется последовательность действий по сигналам τ, τ, τ, τ.
1
Сигнал τ
j
1. Отключается исполнение команды A.
1
Опрашивается F (1) и производится запись в Rg (2), Rg (5).
2
Сигнал τ
2. Опрашивается Rg (2), Rg (5).
3
Сигнал τ
j
3. Опрос СВ (4) и запись α в RS (8).
4
Сигнал τ
4. Перепись 5, 8 в 7, 10 (опрос 13).
j
Включение A и повторение первого пункта по установке исходного состояния МПА, т.е. установка коммутатора КМ (3) в исходное состояние.
1
2
3
4
Как известно τ(t)&τ(t)&τ(t)&τ(t)=⌀
0
Такая последовательность действий продолжается до получения сигнала f, т.е. заключительного перехода МПА в нулевое состояние, свидетельствующего об окончании программы МПА.
Рассмотрим простой пример ГСА (фиг.5), для которого введены два пустых оператора (3, 5) как и при синтезе схемы МПА прототипа.
1
2
m
Заданной ГСА (фиг.5) соответствует граф переходов (фиг.6). При числе состояний N=10 количество переменных в коде xx…x равно m=4.
3
3
3
Для примера прототипа схема F имеет 4 входа и 2 выхода для определения адресного кода мультиплексора, т.к. q=3. В примере прототипа количество неиспользованных информационных входов мультиплексора равно 1. Обозначим в квадратных скобках количество входов и выходов схемы F в виде F [4, 2], а количество неиспользуемых информационных входов мультиплексора как М [1].
3
В предлагаемом изобретении нет ни F [4, 2], ни М [1], а соответствие между α и a(t) задается таблицей 1.
3
1. N=10, m=4, q=3, F[4, 2], M [1]
Таблица 1
α
a(t)
0
0, 1, 4, 8, 9, 10
1
2,6
2
3
3
5,7
~
11-15
Тогда блок КМ (3) будет иметь вид, представленный на фиг.3.
3
На фиг.7 и 8 приведен пример ГСА и граф переходов из описаний прототипа [7]. Для него N=15, m=4, q=6, F[4, 4], М [2].
Таблица 2 определяет правило соединения схем «ИЛИ, И» в КМ и DC (20).
0
j
0
j
1
2
m
<mover accent="true"><mi>α</mi><mo>˜</mo></mover>
<mover accent="true"><mi>α</mi><mo>˜</mo></mover>
<mover accent="true"><mi>α</mi><mo>˜</mo></mover>
В таблице 2 приведены списки для выбора α,
или α по номерам состояний a(t). Эти списки табл.2 полностью определяют правила соединения выходов внутреннего дешифратора (DC) КМ с выходами α,
или α. При этом
соответствует выходу DC с номером 15, т.к. такое состояние отсутствует в графе переходов, а следовательно соответствующие им коды yy…y могут появиться на входе КМ только при неисправной работе блоков МПА. Преимущество предложенных подходов к синтезу МПА по сравнению с классическим на БИС становится очевидным после анализа работы [14, 15].
Второй пример (фиг.7, 8)..
3
2. N=15, m=4, q=6, F[4, 3], М [2]
Таблица 2
α
a(t)
0
0, 1, 4, 5, 9, 10, 11, 8
1
2
2
3
3
13
4
14
5
6
6
7
~
15
Рассмотрим третий реальный пример, соответствующий (фиг.9) алгоритму сложения мантисс чисел с плавающей запятой (см. [10]).
Граф переходов представлен фиг.10.
0
Здесь α - 0, 1, 3, 4, 5, 8, 15-20, 22-24.
j
α - 2, 5-14, 21.
<mover accent="true"><mi>α</mi><mo>˜</mo></mover>
→25-31.
j
Соответствия α→a(t) приведено в таблице 3.
В этом случае m=5, q=6.
3
Число неиспользованных информационных входов мультиплексора в прототипе равно 2, F[5, 3], М [2].
3
3. N=25, m=5, q=6, F [5, 3], M [2]
Таблица 3
α
a(t)
0
0, 1, 3, 4, 8, 15-20, 22-24
1
2, 7
2
5
3
10, 12, 14
4
6
5
9
6
11, 21
~
25-31
Четвертый пример (фиг.11, 12).
Наиболее сложным алгоритмом управления, известным по литературе, является алгоритм в форме ГСА проверки работоспособности ПЗУ с ультрафиолетовым стиранием информации по авторскому свидетельству СССР (фиг.11) №157034, БИ 8, 1990, авторы Скосырский Г.С. и Мухопад Ю.Ф. [11].
3
Граф переходов ГСА приведена на фиг.12. В этом случае m=6, q=10, Fимеет 6 входов и 4 выхода, при этом в мультиплексоре прототипа из 16 информационных входов 6 выходов не используются.
3
4. N=38, m=6, q=10, F[6, 4], М [6]
j
3
6
10
11
12
Как видно из таблицы 4 в этом случае при q=10 для выбора α используются 16 выходов дешифратора, т.к. для α объединяются схемой «ИЛИ» выходы 11, 18, 35; для α - 7, 32, для α - 12, 22, для α - 13, 23 и для α - 14, 24.
Таблица 4
α
a(t)
0
0, 1, 3, 6, 8, 9, 15, 16, 20, 21, 25-28, 30, 31, 34, 36
1
5
2
-
3
18, 11, 35
4
33
5
29
6
10, 7, 32
7
2
8
4
9
-
10
12, 22
11
13, 23
12
14, 24
~
38-63
1
1
2
m
j
1
m+1
m+q
В предложенной структуре МПА сохраняются все преимущества прототипа по сравнению с классическими структурами Мура. Действительно, поскольку на входе F (1) кроме кода xx…x только один сигнал α∈{α}, то объем F (1) V=m·2 как в прототипе. Тогда как в классических схемах Мура V=m·2.
3
j
0
<mover accent="true"><mi>α</mi><mo>˜</mo></mover>
Однако новая структура МПА по сравнению с прототипом обладает и новым качеством, т.к. схема становится самоконтролируемой и выдает сигнал ошибки ERR на клемму (14) при наличии неисправности. Кроме того, вместо триггера (4), комбинационной схемы F и мультиплексора с внутренним регистром памяти используется одна схема КМ (3), формирующая как сигналы α, так и сигналы α,
для самоконтроля МПА.
0
j
1
2
1
2
k
2
<mrow><msub><mover accent="true"><mi>α</mi><mo>˜</mo></mover><mi>n</mi></msub></mrow>
При фактической исправности блока синхронизации БС (15) и схемы выбора СВ (4) анализ сигналов α, α,
фиксирует факт неисправности МПА, который может появиться в любом из блоков МПА от входа F (1) и до выхода. Неконтролируемым остается лишь блок F(l 1), формирующий выходные команды A,A,…,A. Однако, если в ГСА все операторы действия разные (не повторяются), то в схеме F нет необходимости, т.к. она заменяется типовым дешифратором (DC). Способ контроля дешифратора известен [14].
2
j
Но и при повторении команд в структуре ГСА схема F - это всего лишь несколько схем «ИЛИ», т.к. обычно в ГСА уровень повторяемости A невысок [12, 13].
2
Следовательно, вероятность выхода из строя схемы F на 2-3 порядка ниже чем остальных схем МПА. Поэтому можно считать, что контролируемость исправности МПА в предложенной структурной схеме является тотальной.
Рассмотренные примеры подтверждают преимущества изобретения:
1. Предложенный МПА реализуется одинаковыми средствами независимо от сложности ГСА.
2. Обеспечение режима самоконтроля за счет наличия весьма простой схемы выбора СВ (4).
3
j
3. Упрощение конструкции за счет отсутствия блоков для вычисления адреса мультиплексора (F) и самого мультиплексора для выбора логического условия α.
Т.е. предложенная структурная схема МПА является новой и соответствует поставленной цели изобретения.
Литература
1. Сапожников В.В., Кравцов Ю.А., Сапожников Вл.В. Теория дискретных устройств железнодорожной автоматики, телемеханики и связи. М.: Транспорт, 2001. - 307 с.
2. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. - М.: Радио и связь, 1986. - 270 с.
3. Соловьев В.В. Проектирование цифровых систем на ПЛИС. - М.: Горячая линия - телеком, 2001. - 636 с.
4. Савельев А.Я. Прикладная теория автоматов. - М.: Высшая школа, 1987. - 272 с.
5. Мухопад Ю.Ф. Микроэлектронные системы управления. - Братск: БГУ, 2009. - 285 с.
6. Мухопад Ю.Ф. Теория дискретных устройств. - Иркутск: ИрГУПС, 2010. - 172 с.
7. Патент РФ №82888, БИ №13, 2009.
8. Патенты РФ №2058041, 20449347, 2071112, 20779876, 20446396, 2046395, 2042190, 2042189, 2042188, 2018937.
9. Угрюмов Е.П. Цифровая схемотехника. - СПб.: БХВ-Питер, 2010. - 687 с.
10. Кирий В.Г. Теория автоматов. - Иркутск: ИрГТУ, 2007. - 144 с.
11. Авторское свидетельство СССР №1547034, БИ №8, 1990.
12. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. - СПб.: Наука, 2000. - 264 с.
13. Карпов Ю.Г. Теория автоматов. - СПб.: Питер, 2003. - 206 с.
14. Прищепа Л.С., Илюшкин В.А. Устройство для контроля дешифраторов. / Интеллектуальные системы в управлении, конструировании и образовании. Томск: STT, 2002. - вып.2. - с.160-163.