Управляющий автомат

Изобретение относится к к вычислительной технике и дискретной автоматике и может быть использовано при построении аппаратных средств обработки информации в быстродействующих системах реального времени. Технический результат - снижение сложности конструкции автомата Мили за счет уменьшения объема комбинационных схем. Управляющий автомат, содержащий операционное устройство, формирующее q-логических условий, три запоминающих регистра памяти, разрядностью m блок схем «И» и блок синхронизации, мультиплексор с триггером, дешифратор, второй блок схем «И», два блока схем «ИЛИ» и два кодирующих устройства. 8 ил., 1 табл.

 

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

Известны различные структуры управляющих автоматов, представленные в патентах 63588 БИ №15, 2007, А.С. СССР №1365986 БИ №1, 1988 патент РФ №2071111 и др. [11]. Недостатком представленных решений является сложность конструкции при реализации быстродействующих микропрограмм автоматов (МПА).

Наиболее близким к предлагаемому изобретению является классическая структура автоматов Мили, представленная во многих научных и учебных монографиях [1-5,12]. Структурная схема автомата Мили представлена на фигуре 1 где:

OY (1) - операционное устройство (объект управления); Rq 1(2) - регистр логических условий, Rq 2(3) и Rq 3(5) с блоком схем «И» (4) для парафазной передачи содержимого Rq 2 (3) на Rq 3 (5); F₁ (6) - комбинационная схема формирования кода y₁ y₂…y_m следующего состояния a(t+1), по коду X_m…x₂x₁ предыдущего состояния a(t) и конкатенации логических переменных α₁α₂…α_q; q - количество логических переменных; m - разрядность кода a(t) и a(t+1); F₂ (7) - комбинационная схема формирования выходных команд А₁, А₂…А_к(t) от тех же переменных {X} {а}, что и в схеме F₁.

Автомат Мили работает под действием сигналов τ₁ и τ₂ блока синхронизации (БС), причем τ₁(t) & τ₂(t)=Ø. Схемы F₁ (6) и F₂ (7) опрашиваются сигналом τ₁, поэтому длительность переходов в автомате Мили определяется временем ≥2τ, а длительность команд управления равна τ [1, 2].

Для удаленных объектов управления унитарный код A₁, А₂, …, A_к выходных сигналов схемы F₂ (7) представляется в двоичном коде разрядностью n=|log₂K|. Имеются также варианты реализации МПА Мили с единой комбинационной схемой, выполняющей функции схем F₁ (6) и F₂ (7) при этом разрядность переменных на входе определяется конкатенацией X₁X₂…X_m α₁α₂…α_q, а на выходе (m+n).

Недостатком классической реализации всех типов автоматов Мили является большой объем БИС ПЗУ или ПЛМ использующихся для построения комбинационных схем.

Целью настоящего изобретения является снижение сложности конструкции автомата Мили за счет уменьшения объема комбинационных схем.

Далее для краткости управляющий автомат будет именоваться просто автоматом.

Поставленная цель достигается тем, что в структуру автомата Мили вводится мультиплексор для выбора единственного логического условия из множества входных логических условий (переменных). Вводится также схема вычисления номера логического условия по коду состояния автомата и используется комбинационная схема F₁ со специальной функциональной организацией для определения как функций переходов, так и выходов.

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

Предлагаемый автомат содержит операционное устройство ОУ (1), выходы которого через первый запоминающий регистр R_q1 (2) связаны с информационными входами мультиплексора М (3), единичный и нулевой выходы которого связаны с соответствующими входами триггера Тр (4); последовательная цепь блоков состоит из второго запоминающего регистра R_q2 (5), блока схем И (6) для парафазной связи с третьим запоминающим регистром R_q3 (7), дешифратора DC (8), второго блока схем И (9), первого блока ПЛИ 1 (10), шифратора CD1 (11), связанного со входами второго регистра памяти R_q2 (5) и вторым шифратором CD2 (12), связанным с адресными входами мультиплексора М (3); автомат содержит второй блок схем ИЛИ (13), выходы которого связаны с управляющими входами операционного устройства ОУ (1) и блок синхронизации БС (14) с внешними входами Пуск (15) и Останов (16) формирующего последовательность четырех не пересекающихся во времени импульсов синхронизации, причем из 2^m выходов дешифратора DC (8) каждый из q выходов связан с парой элементов «И» блока И (8), связанных по второму входу с единичным и с нулевым выходом триггера Тр (4); все 2q выходов элементов «И» блока И (8) и (2^m-q) выходов дешифратора DC (8), не связанных с элементами «И» блока И (9), соединены со входами первого и второго блоков элементов ИЛИ (11), ИЛИ (13), где m - разрядность второго и третьего запоминающих регистров R_q2 (5), R_q3 (7), а q - количество логических условий, формируемых операционным устройством ОУ (1).

Объект управления или операционное устройство ОУ (1) не является неотъемлемой составляющей автомата управления, однако он введен в структуру прототипа и предлагаемого изобретения для определения взаимодействия МПА с внешней средой.

Для того чтобы автомат с предложенной структурной организацией мог правильно функционировать и удовлетворять требованиям поставленной цели, исходную (заданную) граф-схему управления ОУ (1) следует преобразовать по определенному правилу:

- если в граф-схеме алгоритма (ГСА) имеется непосредственная связь между логическим условием α_i без промежуточного оператора А_к Є {A(t)}, то между ними ставится пустой оператор. На фиг.3 дан пример ГСА, а на фиг.4 - преобразованная ГСА для МПА с выделенным мультиплексором (фиг.2).

На фиг.5 приведен граф переходов для фиг.1, полученный по известной методике разметки ГСА для автоматов Мили [1-3]. В автоматах Мили разметка ГСА неоднозначна, поэтому выбирается тот вариант, при котором каждому состоянию не может быть сопоставлено два или более логических условий (фиг.5). По графу переходов определяется как число пар схем «И» в блоке (9), равное числу (q) входных логических условий α_i, так и соединение каждой пары с конкретным выходом дешифратора DC (8).

По графу переходов определяется также правило соединения и число схем «ИЛИ» в первом или втором блоках схем «ИЛИ» 1 (10) и «ИЛИ» 2 (13). Для представленного примера (фиг.6) получим следующие зависимости:

τa₁=(α₀ a ₀+α₀ a ₉)

τa₆=(α₀ a ₅+α₀ a ₁₀)

τa₇=α₀+a ₆

τa₈=α₅+a ₇

τa₉=α₂+a ₂

Причем номер α_i в формулах для a_i нет необходимости указывать, т.к. на каждый такт будет выбрано свое значение α_j, тогда для каждого a _i запишется только α или , например:

Аналогично получим:

A₃=α₄ a ₂

A₇=αa ₄

Символ τ можно опустить, т.к. это сигнал синхронизации DC(8). На фиг.2 показан выход мультиплексора в виде α и , если же типовой мультиплексор допускает выход только α, то между триггером Tp(4) и мультиплексором ставится элемент «НЕ», что непринципиально.

Все вновь введенные блоки, кроме блока синхронизации БС (14) и второго блока кодирования CD2 (12), не имеют особенностей. Первый шифратор CD(1) типовой, т.к. преобразует унитарный код A₁, А₂, …, А_р в двоичный код состояния a(t+1) в виде y₁y₂…y_m. Второй шифратор CD2 (12) - это преобразователь кода y₁y₂…y_m, соответствующий состоянию a(t+1), в код номера логического условия меньшей разрядности z₁z₂…z_r. Кроме того в структуру CD2 (12) введен внутренний запоминающий регистр для кода y₁y₂…y_m. Возможна реализация и с запоминающим регистром на выходе CD2 (12), а не на входе.

Для схем DC(8), БИ(9), ИЛИ(10), CD(11) по уровню имеющейся технологии СБИС фирм Xilinx, Altera может быть осуществлена реализация всего комплекса блоков 2-14, исключая генератор тактовых импульсов, входящий в состав блока синхронизации БС(14).

Реализация блоков (8), (9), (10), (11), (12), (13) и их взаимосвязей определяет также возможность создания заказной БИС с новой организацией ПЛМ, отличной от классического варианта, требующего значительно большего объема, чем предлагаемое решение, т.к. на входе блока И(9) всего (m+1) переменных вместо (m+q) в прототипе. Кроме того в типовой ПЛМ к каждому логическому элементу «И» подключается m входов, а здесь только два: один от j-го выхода DC (8), а второй - от α или от Однако и без заказной БИС нет препятствий к реализации блоков (8)-(11) на элементах типовой логики.

Блок синхронизации состоит из генератора импульсов ГИ(20) со входом от источника питания (Е), четыре выхода которого с сигналами τ₁, τ₂, τ₃, τ₄ поданы на первые входы элементов И21, И22, И23, И24 передающие сигналы τ₁, τ₂, τ₃, τ₄ на выход блока синхронизации БС (14), а вторые входы элементов И21, И22, И23, И24 связаны с единственным выходом второго триггера Tp (25), нулевой вход которого связан с клеммой Пуск (15), а единичный с клеммой остановки (16) через элемент ИЛИ (26), второй вход которого связан с сигналом окончания программы управления (е), причем τ₁(t) & τ₂(t) & τ₃(t) & τ₄(t)=⌀. Генератор импульсов с таким правилом формирования четырех сигналов известен, выпускается в виде интегральной схемы и подробно описан в [10].

При отсутствии специализированной микросхемы [10] генератора импульсов τ₁, τ₂, τ₃, τ₄ создается специальная схема фиг.8, состоящая из генератора импульсов ГИ (20) с одним выходом τ, связанным с двухразрядным счетчиком Сч (21), параллельные выходы которого через второй дешифратор DC2 (22) образуют непересекающуюся во времени последовательность импульсов τ₁, τ₂, τ₃ и τ₄, причем вход синхронизации второго дешифратора DC 2 (22) связан с единым выходом второго триггера Тр2 (23), связанного с клеммой (15) «Пуск» и через элемент ИЛИ (24) связанного по нулевому входу с клеммой останов (16), и входом сигнала окончания программы (е).

Предлагаемый автомат может быть реализован также без схемы DC2 (12), преобразующей код y₁ y₂…y_m в код номера j логического условия α_j. Для этого на графе переходов каждому логическому условию α_j нужно присвоить номер предыдущего состояния a(t), после которого проверяется α_j на переходе от a(t) к a(t+1). Тогда код y₁y₂…y_m будет непосредственно определять номер j для α_j. В этом случае выходы регистра R_g1 (2) следует специальным образом соединять с информационными входами мультиплексора М (3). Для безусловного перехода α₀ резервируется нулевой вход.

Для примера α₁ α₂ α₃ α₄ α₅ α₆ должны быть соединены с 1, 2, 9, 4, 7, 8 входами, остальные незадействованные информационные входы мультиплексора М (3) должны быть соединены с нулевым входом М (3).

Для автоматов с числом состояний N≥32 такой мультиплексор может оказаться сложным, поэтому этот вариант целесообразен лишь в том случае, если объем затрат на первый вариант M₁ (3), DC (12) больше, чем М₂ (3); здесь M₁ и М₂ обозначают мультиплексоры для 1-го и 2-го вариантов.

Предлагаемый автомат работает в следующей последовательности.

Перед сигналом пуск (15) автомат устанавливается в «нулевое» (начальное) состояние, т.е. устанавливается нулевой код на адресных входах мультиплексора М (3) и на регистре Rg2 (5). По сигналу «Пуск» импульсом τ₁ опрашивается мультиплексор М (3) и на триггер Тр (4) записывается значение α_j (t). Импульсом τ₂ переписывается содержимое Rg2 (5) через схемы И (6) на Rg3 (7). В начальный момент переписывается нулевое значение. Далее импульсом τ₃ производится опрос дешифратора DC (8), формируется код y₁ y₂…y_m, который запоминается в блоке DC2 (12) и на Rg2, и синхронизируется выдача команд A_j для выполнения их операционным устройством и записи новых измененных значений αj на Rg1 (2) после исполнения A_j.

Четвертым импульсом производится перепись кода y₁ y₂…y_m на адресные входы мультиплексора и работа продолжается в новом периоде Т, состоящем из последовательности импульсов τ₁-τ₄. Работа продолжается до формирования сигнала (е), фиксирующего возврат в нулевое состояние. Тогда сигналом (е) через схему ИЛИ (26) триггер Тр (25) переходит в нулевое состояние и автомат сам себя отключает от генератора импульсов ГИ (20) (фиг.7).

В предлагаемом изобретении объем комбинационной схемы, состоящей из блоков (8), (9), (10), (11), (12), (13), существенно уменьшен по сравнению с объемом схем F₁ и F₂ в прототипе.

Действительно, при раздельной реализации схем F₁ и F₂ в прототипе объем F₁ составит V₁=m2^m+q, a V₂=n2^m+q, где n=|log₂K|, К - количество разных A_jЄ{A}, . Общий объем V=(m+n)2^m+q, а при n=m V=m2^m+q+1. При совместимой реализации F₁ и F₂ в едином блоке объем схемы также составит V=(m+n)2^m+q. В предлагаемом изобретении при реализации схемы F₂ (13) для удаленных объектов управления ОУ (1) с выходами в виде двоичного кода n=log₂K, вместо унитарного кода A₁A₂…А_к, как это изображено на фиг.2, объем полного комплекса схем (8) - (14) составит W=(m+n)2^m+1 или W=m2^m+2 при n=m.

Произведем сравнение для сверх простых (СП), простых (ПА), средней сложности (СС) и сложных автоматов (СА), имеющих различные характеристики m, q [7]. Результаты представлены в табл.1 с оценкой объема ПЗУ в килобитах при n=m. Выигрыш в объеме БИС ПЗУ представлен коэффициентом Q=2^q-1. Даже для очень простого примера ГСА фиг.3, где m=4, q=6 получим V=m2^m+q+1=4*2¹¹=2¹³=8192 бита, тогда W=m2^m+2=4*2⁶=2⁸=256 бит. Объем эквивалентной схемы автомата уменьшается в Q раз. Q=2^q-1=2⁵=32.

Сложные автоматы с m>6 не встречаются на практике, т.к. их обычно декомпозируют (разделяют на части) и реализуют независимо. Представленное сравнение объемов убедительно свидетельствует о преимуществах предлагаемого изобретения.

Для n<m цифровые данные как для V, так и для W изменятся в меньшую сторону, однако выигрыш Q=2^q-1 сохраняется, т.к. он определяется уменьшением количества входных переменных с (m+q) для классического варианта до m+1 в предлагаемом изобретении.

Следует заметить, что на сегодня объем БИС ПЛМ и ПЛИС позволяет реализовать МПА со структурной организацией (фиг.1) классического типа. Однако энергетические затраты могут доходить до 0,4 мкВт на вентиль, что приводит к необходимости рассеивания тепла в единицы ватт на кристалле для сложных и средней сложности автоматов.

В прототипе (фиг.1) меньше структурных единиц (блоков), но они более сложны для реализации, чем в предлагаемом изобретении (фиг.2). В предлагаемом изобретении больше по количеству структурных единиц, но все они в десятки, сотни и даже тысячи раз проще в зависимости от сложности самого алгоритма работы МПА. Незначительно усложняется лишь блок синхронизации, но он не вносит определяющего вклада в затраты оборудования автомата управления.

Предлагаемое изобретение позволяется реализовать МПА на БИС меньшей сложности и повысить его надежность как за счет снижения числа элементов, так и за счет ухода от проблем теплоперегрева кристалла.

Таблица 1
МПА	m	Ч	m+q+1	m+2	V	W	Q
СП	3	4	8	5	0,768	0,096	8
ПА	4	8	13	6	32	0,25	128
СС	5	12	18	7	1280	0,625	2048
СА	6	16	23	8	48000	1,5	32000

Литература

1. Баранов С.И. Скляров В.А. Цифровые устройства на программируемых БИС с матричной структурой. - М.: Радио и связь, 1986. - 270 с.

2. Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. - СПб.: Наука, 2000. - 234 с.

3. Соловьев В.В. Климович А. Логическое проектирование цифровых схем на ПЛИС. - М.: Горячая линия телеком, 2008. - 375 с.

4. Мухопад Ю.Ф. Микроэлектронные системы управления. - Братск: БрГУ, 2009. - 285 с.

5. Мухопад Ю.Ф. Теория дискретных устройств. Иркутск: ИрГУПС. - 2010. - 172 с.

6. Мухопад А.Ю. Мухопад Ю.Ф. Микропрограммный автомат. Патент полезн. модель РФ №82888, БИ №13, 2009.

7. Мухопад А.Ю. Структурный синтез автоматов управления системами обработки информации реального времени. - Автореферат канд. диссерт. Братск: БрГУ, 2010. - 19 с.

8. Мухопад А.Ю. Обеспечение надежности сложных автоматов управления мехатроникой / Тр. международной научной школы «Фундаментальные и прикладные проблемы надежности и диагностики машин и механизмов. - СПб.: Научный совет РАН по проблемам машиностроения и технологических процессов, 2009. - С.17-19.

9. Mukhopad Yr. F. Mukhopad A. Yr. Microelectronic controlling of realtime complicated technical systems / International journal of applied and fundamental research (JSSN 1996-3955), 2009, №2. - p.26-29.

10. Угрюмов Е.П. Цифровая схемотехника СПб.: БХВ - Питер, 2010, 797 с.

11. Патенты РФ 2058041, 20449347, 2071112, 20779876, 20446396, 2046395, 2042190,2042189,2042188, 2018967.

12. Постников А.И. Основы теории цифровых автоматов. - Красноярск: КрГТУ, 1999. - 251 с.

Управляющий автомат, содержащий операционное устройство, формирующее q-логических условий, три запоминающих регистра памяти, разрядностью m блок схем «И» и блок синхронизации, отличающийся тем, что в конструкцию автомата включены мультиплексор с триггером, дешифратор, второй блок схем «И», два блока схем «ИЛИ» и два кодирующих устройства; выходы операционного устройства через первый запоминающий регистр связаны с информационными входами мультиплексора, единичный и нулевой выходы которого связаны с соответствующими входами триггера, а последовательная цепь блоков состоит из второго запоминающего регистра, блока схем «И» для парафазной связи с третьим запоминающим регистром, дешифратора, второго блока схем «И», первого блока «ИЛИ», шифратора, связанного с входами второго регистра памяти и вторым шифратором, связанным с адресными входами мультиплексора, причем автомат содержит второй блок схем «ИЛИ», выходы которого связаны с управляющими входами операционного устройства, и блок синхронизации с внешними входами «Пуск» и «Останов», формирующий последовательность четырех не пересекающихся во времени импульсов синхронизации, причем из 2^m выходов дешифратора каждый из q выходов связан с парой элементов «И» блока «И», связанных по второму входу с едиными и с нулевым выходом триггера, причем все 2q выходов элементов «И» блока «И» и (2^m-q) выходов дешифратора не связанных с элементами «И» блока «И» соединены со входами первого и второго блоков элементов «ИЛИ», где m - разрядность второго и третьего запоминающих регистров.