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

Настоящая полезная модель относится к области вычислительной техники и дискретной автоматики и может быть использована для построения микропрограммных автоматов и устройств управления технологическими процессами. Структурные схемы микропрограммных автоматов известны по авторским свидетельствам и патентам: патенты на полезную модель №63588 БИ№15,2007; а.с. СССР, №1365986 БИ №1,1988; патент РФ №2071111.
Наиболее близким к предлагаемой полезной модели является общераспространенная (классическая) структура [1-4] микропрограммного автомата (МПА). МПА на фиг.1 изображен вместе с операционным устройством (ОУ), которым управляет МПА. На фиг.1 обозначено:
1) схема синхронизации (СС), формирующая два непересекающихся во времени импульса τ и  (τ(t) &  (t)=ф) с периодом повторения T;
1
2) комбинационная схема формирования переходов автомата из состояния d(t) в d(t+1) - F(2); 3) регистр памяти кода d(t+1);
4) блок-схем «И»; 5) регистр памяти кода d(t);
2
6) дешифратор (DC); 7) F - схема формирования команд управления;
0
1
k
1
2
q
8) операционное устройство (ОУ), получающее команды A,A,...,A от МПА и формирующее логические условия α,α,...,α для МПА;
9) регистр памяти логических условий.
Функционирование и реализация автоматов Мура подробно описаны во всей учебной и научной литературе [1-4].
1
2
Реализация классической структуры начинается с перехода от граф-схемы заданного алгоритма управления (фиг.2) к графу автомата (фиг.3), из которого по известным [1,2,4] правилам выписываются булевы функции для реализации схем F и F. Детально все процедуры описаны в [5].
2
i
1
1
q
1
1
1
m+q
m+q
Комбинационная схема F - это набор элементов схем «ИЛИ», объединяющих выходы дешифратора (DC-6), соответствующие одинаковым командам А. Наиболее сложным блоком в МПА является комбинационная схема F, формирующая код следующего состояния d(t+1) по сводному коду (конкатенация) состояния d(t) и логических условий α,...,α. Для простых автоматов с m+q<12 (где m - разрядность кода d(t), q - число логических условий) схема F реализуется в виде набора элементов логики. Для сложных автоматов (m+q>12) схема F реализуется на ПЗУ, ПЛМ или ПЛИС [2, 3]. Сложность схемы F оценивается количеством бит для реализации на ПЗУ; V=m2, где (2) - количество констант ПЗУ разрядностью m.
Реализация остальных блоков МПА общеизвестна [1,4].
1
В предлагаемом устройстве (фиг.2) первый выход а) блока синхронизации СС(1) образует последовательную цепь блоков в виде первой комбинационной схемы F(2), связанной m-разрядными выходами с первым регистром памяти Рг(3), парафазной связью через блок схем И(4) со вторым регистром
1
2
3
3
1
Рг(5) и со вторым m-разрядным входом первой комбинационной схемы F(2), причем m-разрядный выход второго регистра памяти Рг(5) образует две независимые цепи блоков в виде адресных входов дешифратора ДС(6), связанного своими выходами со второй комбинационной схемой F(7) многоразрядные управляющие выходы которой связаны со входами операционного устройства ОУ(8), и вторая последовательная цепь в виде w-разрядного входа третьей комбинационной схемы F(9), выходы которой связаны с адресными входами мультиплексора М(10), выход мультиплексора М(10) связан с первым входом первого дополнительного регистра памяти (11), причем второй одноразрядный выход комбинационной схемы F(9) связан со вторым входом первого дополнительного регистра (11), выходы первого дополнительного регистра (11) связаны со входами дополнительного блока схем «И»(12) и через второй дополнительный регистр (13) с третьими двухразрядными входами первой (F(2)) комбинационной схемы, при этом второй б) выход блока синхронизации СС(1) связан с независимым входом синхронизации мультиплексора М(10); выходы операционного устройства ОУ(8) связаны с информационными входами мультиплексора М(10), третий выход в) блока синхронизации СС(1) опрашивает по вторым входам все схемы «И» основного (4) и дополнительного (12) блоков схем «И», при этом блок синхронизации СС(1) имеет два внешних входа «Пуск» и «Останов».
i
j
r
i
j
Для обеспечения правильности функционирования автомата по структуре фиг.2 исходная блок-схема алгоритма (фиг.3) должна быть преобразована так, чтобы после любого логического условия α следующим был бы оператор действия (А или пустой оператор), а не новое логическое условие α. Это требование реализуется тривиально введением пустых операторов только в те места, где за α следует сразу α(i,j∈). Граф переходов такого автомата для примера фиг.4 приведен на фиг.5. При этом правильность функционирования автомата (следовательно, и правильность выдачи управляющих команд) не нарушается. Примечание: пустому оператору не соответствует никакая команда управления - это пропуск такта функционирования для перехода к следующему состоянию.
1
2
q
3
j
3
С целью снижения сложности МПА за счет упрощения комбинационных схем в полезной модели предлагается не изменяя структуры блоков 3,4,...,7,8 (фиг.1) ввести мультиплексор, на информационные входы которого подаются сигналы α,α,...,α. Для определения адреса мультиплексора по коду состояния d(t) вводится комбинационная схема F, причем выходом этого мультиплексора являются значения α(t) выбранного логического условия α(j=1,2,...,q). Кроме того, F определяет значение разряда β(t), т.е. наличие или отсутствие безусловного перехода d(t)→d(t+1).
1
Эти выходы (αβ) образуют конкатенацию с кодом состояния d(t), т.е. код α(t)β(t)d(t), определяющий адрес схемы F. Для предлагаемой схемы МПА (фиг.2) схема синхронизации СС-1 должна теперь формировать три
1
2
3
1
2
3
непересекающихся во времени синхросигнала τ,τ,τ, т.е. τ(t)&τ(t)&τ(t)=φ.
j
По сравнению с графом фиг.4 в предложенной модели автомата (фиг.2) действительно из каждой вершины возможен безусловный переход к одной вершине или переход только к одной из двух вершин - в зависимости от единственного выбранного логического условия α (фиг.5).
Автомат функционирует в следующей последовательности. Перед командой «Пуск» производится установка в исходное «нулевое» состояние регистров 3, 5, 11, 13.
1
3
1
3
3
2
i
Первым импульсом а) блока синхронизации СС(1) производится параллельный опрос первой комбинационной схемы F(2) и третьей комбинационной схемы F(9), при этом через выходы схемы F(2) на Рг - (3) записывается код следующего состояния d(t+1), а через выходы F(9) записывается адрес мультиплексора М(10), одновременно по дополнительному выходу блока F(9) заносится по первому входу значение β(t) на первый дополнительный регистр (11). Вторым б) импульсом блока синхронизации СС(1) опрашивается мультиплексор и по второму входу первого дополнительного регистра (11) записывается значение логического условия α(t). Третьим в) импульсом блока синхронизации СС(1) опрашиваются блоки схем И(4, 12) и конкатенация кодов α(t+1)β(t+1)d(t+1) переносится на регистры 5 и 13, которые для следующего тактового импульса а) являются кодами α(t)β(t)d(t). При этом весь промежуток времени Т - 3τ (где Т - период следования импульсов синхронизации) код d(t) через DC(6) и F(7) преобразуется в управляющие команды длительностью (T - 3τ), которые и воздействуют на операционное устройство ОУ(8). В операционном устройстве ОУ(8) за время исполнения команды производятся действия (для роботов, например, выдвижение захвата детали, поворот и т.п.), которые изменяют показания датчиков (значения логических условий α) и тем самым подготавливается следующий цикл работы на другом периоде Т.
Согласно алгоритму (и графу переходов рис.5) автомат осуществляет переходы d(t)→d(t+1)→d(t)... до тех пор, пока снова не вернется в исходное нулевое состояние. При этом формируется сигнал «Останов» и автомат отключает сам себя от генератора синхроимпульсов блока СС(1). Программа управления выполнена. Сигнал «Останов» также может быть подан из внешней среды при фиксации наблюдателем наличия неправильно исполненной команды операционным устройством ОУ(8).
1
3
1
i
j
i
0
1
2
3
5
6
Рассмотрим реализацию схем F и F. Для рассматриваемого примера система булевых функций F выписывается (табл.1) на основании графа переходов (фиг.5). Более того, поскольку мультиплексор для каждого τd выбирает свое α, то система булевых функций переписывается в виде табл.2. Причем везде, где используется τd(t) без логического условия (f,f,f,f,f,f) Должен быть учтен также символ β.
1
1
Для данного простого примера вместо ПЗУ или ПЛМ может быть применена комбинационная схема F(2) на элементах логики И, ИЛИ, НЕ с отдельным дешифратором (16) на входе и шифратором (17) на выходе (фиг.7). Для упрощения чертежа соединения с β, α и  обозначены соответствующими символами. Как видно, вся F(2) для примера реализуется одной микросборкой двухвходовых схем ИЛИ (8 штук в корпусе), тремя И (4 двухвходовых И в корпусе), дешифратором (15) - 1 корпус и шифратором (16) - 1 корпус, т.е. всего 7 типовых микросхем.
2
j
j
2
j
Построение схемы F на элементах «ИЛИ» для автоматов Мура производится по типовой методике объединения входами схем «ИЛИ» тех выходов дешифратора (6), которым соответствуют одинаковые А Для рассматриваемого примера все операторы А различны и не повторяются в разных состояниях d(t) автомата, поэтому схема F(7) отсутствует, т.к. каждый выход DC(6) будет соответствовать своей команде A (табл.3).
3
j
Для построения схемы F по графу (фиг.5) выпишем условия преобразования кодов d(t) в адрес мультиплексора и значение β (табл.4). По табл.4 для каждого кода состояний однозначно определяется код адреса мультиплексора для выбора α и значение β. Причем при наличии β=0 может быть ситуация α или , но при наличии α или  не может быть β=1.
0
1
2
0
1
2
0
1
2
3
На основании табл.4 по типовой методике [1, 2] построены карты Карно для кода адреса ZZZ и β рис.8 (а, б, в, г), из которых составлена запись для булевых функций Z,Z,Z и β. Реализация этих функций представлена для примера на фиг.9. Для упрощения чертежа соединения с инверсией переменных xxxx обозначены соответствующими символами
1
6
j
1
14
Операционное устройство (8) не требует расшифровки при рассмотрении автомата управления, т.к. оно является для него внешним, формирующим логические сигналы - (в примере α÷α) и получающее от него команды управления А(А-А).
о
0
Реализация схемы синхронизации (СС) для формирования трех непересекающихся последовательных импульсов и формирования сигналов установки исходного состояния регистров и сигнала отключения от генератора по сигналу f тривиальна. По сути это типовой генератор импульсов длительностью т с двумя схемами задержки каждого из предыдущих импульсов на τ. Синхронизация пуска и останова осуществляется с помощью управляющего триггера и трех схем «И» [1, 5]. Прерывание последовательности импульсов командой «Останов» осуществляется возвратом управляющего триггера в исходное нулевое состояние по сигналу f.
m
Преимущества предложенной полезной модели автомата наиболее существенны для сложных автоматов с большим числом состояний (2≥32) и логических условий (q≥12), причем чем большее число логических условий
используется в автомате, тем более эффективна реализация автомата по схеме фиг.2. Сравнение затрат на комбинационные схемы проведем для трех вариантов МПА:
a)m=4
q=8
m+q=12
m+2=6
б)m=5
q=12
m+q=17
m+2=7
в)m=6
q=16
m+q=22
m+2=8
1
1
m+q
m+2
Для прототипа V(F)=m2. Для полезной модели V(F)=m2.
3
Кроме того, необходимо учесть затраты на F и мультиплексор.
3
2
3
3
3
m
V(F)=(logq)2. Затраты на мультиплексор по инженерной оценке >V(F), но ≤2V(F). Положим их равными 2V (F).
Прототип
Полезная модель
а)V(F<sub>1</sub>)=4·2<sup>12</sup>=2<sup>14</sup>
a)V(F<sub>1</sub>)=4·2<sup>6</sup>=2<sup>8</sup>
V(F<sub>3</sub>)=3·2<sup>4</sup>.
Т.е. сложность комбинационных схем полезной модели в 40 раз ниже прототипа. Остальные блоки у них одинаковы.
Прототип
Полезная модель
б)V(F<sub>1</sub>)=5·2<sup>17</sup> но т.к. ПЗУ
б)V(F<sub>1</sub>)=5·2<sup>7</sup>
с 5-тыо выходами отсутствуют,
V(F<sub>3</sub>)=4·2<sup>5</sup>=2<sup>7</sup>.
необходимо взять реальное
V<sub>p</sub>(F<sub>1</sub>)=8·2<sup>7</sup>=2<sup>10</sup>
V<sub>p</sub>(F<sub>1</sub>)=8·2<sup>17</sup>=2<sup>20</sup>
Для очень сложных автоматов при большем числе логических условий выигрыш становится еще более значимым.
Например, для m=6, q=16, m+q=11, m+2=8 получим
в) V(F<sub>1</sub>)=6·2<sup>22</sup>
в) V(F<sub>1</sub>)=6·2<sup>8</sup>
Реальное V(F<sub>1</sub>)=8·2<sup>22</sup>=2<sup>25</sup>
Реальное V(F<sub>1</sub>)=8·2<sup>8</sup>=2<sup>11</sup>
V(F<sub>3</sub>)=4·2<sup>6</sup>=2<sup>8</sup>
Приведенные примеры подтверждают эффективность полезной модели даже для простых автоматов (m≤4,q≤8). Эффективность модели увеличивается в быстро нарастающей прогрессии для сложных автоматов m≥5, q≥12.
Литература
1. Сапожников В.В., Кравцов Ю.А., Сапожников Вл. В. Теория дискретных устройств железнодорожной автоматики, телемеханики и связи. М.:Транспорт, 2001. - 307 с.
2. Баранов С.И., Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. - М.: Радио и связь, 1986. - 270 с.
3. Соловьев В.В. Проектирование цифровых систем на ПЛИС.- М.: Горячая линия - телеком, 2001. - 636 с.
4. Савельев А.Я. Прикладная теория автоматов. - М.'- Высшая школа, 1987. -272 с.
5. Мухопад Ю.Ф. Микроэлектронные информационно-управляющие системы. Иркутск: ИрГУПС, 2004. - 404 с.
6. Патенты РФ 2058041, 20449347, 2071112, 20779876, 20446396, 2046395, 2042190, 2042189, 2042188, 2018937.
Авторы
Мухопад Александр Юрьевич - аспирант ИрГУПС (11 публикаций, из них 1 патент на полезную модель).
Мухопад Юрий Федорович - доктор технических наук, профессор, заведующий кафедрой «Управление техническими системами» Иркутского государственного университета путей сообщения (~280 публикаций, из них>50 изобретений и патентов).
Таблица 1
f<sub>0</sub>=τα<sub>8</sub>
f<sub>1</sub>=τα<sub>0</sub>+<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" /><sub>1</sub>τα<sub>2</sub>
f<sub>2</sub>=τα<sub>1</sub>+<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" /><sub>6</sub>τα<sub>7</sub>
f<sub>3</sub>=α<sub>1</sub>τα<sub>2</sub>+τα<sub>12</sub>
f<sub>4</sub>=<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" /><sub>2</sub>τα<sub>3</sub>
f<sub>5</sub>=(τα<sub>4</sub>+τα<sub>9</sub>+τα<sub>10</sub>+τα<sub>11</sub>)
f<sub>6</sub>=τα<sub>5</sub>
f<sub>7</sub>=α<sub>5</sub>τα<sub>6</sub>
f<sub>8</sub>=α<sub>6</sub>τα<sub>7</sub>
f<sub>9</sub>=<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" /><sub>3</sub>τα<sub>13</sub>
f<sub>10</sub>=<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" /><sub>4</sub>τα<sub>14</sub>
f<sub>11</sub>=α<sub>4</sub>τα<sub>14</sub>
f<sub>12</sub>=<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" /><sub>5</sub>τα<sub>6</sub>
f<sub>13</sub>=α<sub>2</sub>τα<sub>3</sub>
f<sub>14</sub>=α<sub>3</sub>τα<sub>13</sub>
Таблица 2
f<sub>0</sub>=βτα<sub>8</sub>
f<sub>1</sub>=βτα<sub>0</sub>+<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" />τα<sub>2</sub>
f<sub>2</sub>=βτα<sub>1</sub>+<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" />τα<sub>7</sub>
f<sub>3</sub>=ατα<sub>2</sub>+βτα<sub>12</sub>
f<sub>4</sub>=<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" /><sub>2</sub>τα<sub>3</sub>
f<sub>5</sub>=β(τα<sub>4</sub>+τα<sub>9</sub>+τα<sub>10</sub>+τα<sub>11</sub>)
f<sub>6</sub>=βτα<sub>5</sub>
f<sub>7</sub>=ατα<sub>6</sub>
f<sub>8</sub>=ατα<sub>7</sub>
f<sub>9</sub>=<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" />τα<sub>13</sub>
f<sub>10</sub>=<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" />τα<sub>14</sub>
f<sub>11</sub>=ατα<sub>14</sub>
f<sub>12</sub>=<img he="5" wi="3" file="00000010.TIF" img-content="undefined" img-format="TIF" />τα<sub>6</sub>
f<sub>13</sub>=ατα<sub>3</sub>
f<sub>14</sub>=ατα<sub>13</sub>
Таблица 3
α(t)
А<sub>i</sub>
Примечание
0
A<sub>0</sub>
1
A<sub>1</sub>
2
A<sub>2</sub>
3
A<sub>3</sub>
4
A<sub>4</sub>
5
A<sub>8</sub>
6
A<sub>9</sub>
7
A<sub>15</sub>
Пустой оператор
8
A<sub>11</sub>
9
A<sub>5</sub>
10
A<sub>6</sub>
11
A<sub>7</sub>
12
A<sub>10</sub>
13
A<sub>12</sub>
Пустой оператор
14
A<sub>13</sub>
Пустой оператор
Таблица 4
Код α(t)
N<sub>0</sub>
β
Код адреса
0001
1
1
0000
0010
2
-
0001
0011
3
-
0010
0100
4
1
0000
0101
5
1
0000
0110
6
-
0101
0111
7
-
0110
1000
8
1
0000
1001
9
1
0000
1010
10
1
0000
1011
11
1
0000
1100
12
1
0000
1101
13
-
0011
1110
14
-
0100
0000
0
1
0000
N
β
Z<sub>3</sub>z<sub>2</sub>z<sub>1</sub>z<sub>0</sub>
Таблица 5
<img he="16" wi="117" file="00000011.TIF" img-content="undefined" img-format="TIF" />
<img he="7" wi="67" file="00000012.TIF" img-content="undefined" img-format="TIF" />
<img he="8" wi="67" file="00000013.TIF" img-content="undefined" img-format="TIF" />
<img he="7" wi="66" file="00000014.TIF" img-content="undefined" img-format="TIF" />