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

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

Схемы микропрограммных автоматов (МПА) известны по авторскому свидетельству СССР 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].

По сравнению с МПА с классической структурной организацией автоматов Мура [1-6] в полезной модели РФ №82888 объем комбинационной схемы для вычисления a(t+1) по коду a(t) с учетом логических условий α_j∈{α₁,α₂,…,α_q} уменьшен в 2^q-1 раз, где q - количество входных переменных МПА, называемых также логическими условиями.

Для достижения такого эффекта исходная граф-схема алгоритма (ГСА) преобразуется за счет ввода пустых операторов. Методика синтеза таких МПА подробно изложена в работах [5, 6].

На фиг.1 представлена структурная схема МПА прототипа по полезной модели РФ №82888, БИ 13, 2009.

На фиг.1 введены обозначения:

ОУ - объект управления (или операционное устройство) - (1);

Rg - Регистр памяти логических условий α₁α₂…α_q - (2);

M - мультиплексор - (3);

RS - триггер хранения α - (4);

F₁ (1) - комбинационная схема для вычисления состояния автомата a(t+l) - код y₁y₂…y_m по коду состояния a(t) - x₁x₂…x_m и логическому условию α∈{α}.

F₂ - комбинационная схема формирования выходных команд A₁,A₂,…,A_k - (10);

F₃ - комбинационная схема преобразования кода состояния автомата x₁,x₂,…,x_m в код адреса логического условия α_j∈{α₁,α₂,…,α_q} - (9);

СС - схема синхронизации - (1).

Блок памяти состояний МПА представлен в виде структуры блоков 6, 7, 8.

Снижение объема памяти схемы F₁ в 2^q-1 раз в полезной модели РФ №82888 по сравнению с F₁ в классической структуре МПА достигнуто за счет введения третьей комбинационной схемы F₃ для преобразования кода a(t+1) - y₁y₂…y_m в адрес, соответствующий номеру α_j-z₁z₂…z_p, здесь p - разрядность адресного кода мультиплексора. При этом требуется дополнительный импульс синхронизации для опроса схемы F₃.

По адресу z₁z₂…z_p через мультиплексор M (3) осуществляется выбор одного α_j из множества {α}, причем именно того условия, которое необходимо для вычисления следующего состояния a(t+1) по коду a(t) и α_j∈{α}.

Такая процедура осуществляется комплексом последовательно связанных блоков F₃ (9) и мультиплексора M (3). Причем для обеспечения правильного функционирования необходим еще регистр памяти для записи адреса z₁z₂…z_p.

На фиг.1 такой регистр не показан, т.к. предполагается, что он внесен в структуру адресной части мультиплексора M (3).

Такая реализация средств выбора α_j∈{α} по коду y₁y₂..y_m через F3 (9) плюс M (3) с внутренним регистром памяти адреса z₁z₂…z_p усложняет конструкцию МПА по патенту РФ №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 введены следующие обозначения:

F₁ (1) - первая комбинационная схема для вычисления состояния автомата a(t+1) - код y₁y₂…y_m по коду состояния a(t) - x₁x₂…x_m и логическому условию α∈{α}.

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-триггеры;

F₂ (11) - вторая комбинационная схема, формирующая команды управления A₁,A₂,…,A_k по коду состояния a(t) - x₁x₂…x_m;

ОУ (12) - объект управления (операционное устройство);

α₁α₂…α_q - множество логических условий {α}, формируемых в ОУ( 12);

Rg (13) - четвертый регистр памяти, хранящий значения {α};

$${\alpha }_0,{\alpha }_j,\tilde{\alpha }$$ - выходы блока коммутатора (3), где

α₀ - безусловный переход,

$$\tilde{\alpha }$$ - несуществующие логические условия,

α_j∈{α} - одно из логических условий, выбираемое КМ (3) по коду y₁y₂...y_m,

α - выбираемое СВ (4), т.е. значение α₀ или α_j;

ERR (14) - ошибка;

БС (15) - блок синхронизации;

τ₁(t)&τ₂(t)&τ₃(t)&τ₄(t)=⌀

импульсы синхронизации, формируемые БС (15).

Для лучшего уяснения принципа функционирования микропрограммного автомата (далее автомат или МПА) приводится описание блоков МПА.

ОУ (12) - не является неотъемлемой частью МПА, но введено в структуру фиг.1 и 2 для того, чтобы показать связь МПА по его входам и выходам.

Все четыре регистра памяти Rg (2, 5, 7, 13) не имеют особенностей и различаются лишь разрядностью m для Rg (2, 5, 7) и q - для Rg (13).

Первая комбинационная схема как и в прототипе реализуется через ПЗУ или ПЛМ для определения кода y₁y₂..y_m по конкатенации αx₁x₂…x_m.

Вторая комбинационная схема F₂ (11) для автоматов Мура состоит из дешифратора с m-адресными входами x₁x₂…x_m, выходы которого объединяются схемами «ИЛИ», если одна и та же команда A_i соответствует нескольким выходам дешифратора, т.е. нескольким состояниям МПА - a(t).

Специальными блоками в предлагаемом изобретении являются лишь блок коммутации КМ (3), выбирающий α_j из логических сигналов α₀α₁α₂…α_q по унитарному коду y₁y₂…y_m на один выход α, а также блок выбора СВ (4).

Блок коммутации КМ (3) фиг.3 представляет собой дешифратор (DC) (20), к выходам которого подсоединены q логических двухвходовых (21) элементов «И» (где q - количество логическим сигналов α₁α₂…α_q), к первым входам которых подсоединяются единичные выходы триггеров Rg (13), а ко вторым - только те q выходов, которым соответствует выбор конкретного α_j∈{α} при данном состоянии a(t).

Причем если разным состояниям a(t) соответствует выбор одного и того же α_j, то перед соединением выходов с входом элемента «И» эти выходы объединяются через логический элемент «ИЛИ» (22). Выходы всех q элементов «И» также объединяются схемой «ИЛИ» (23) с выходом, обозначенным символом α_j.

Две схемы «ИЛИ» - 24 и 25 осуществляют «сборку» тех состояний, при которых необходимо формировать сигналы α₀ или $$\tilde{\alpha }$$ .

Схема выбора СВ (4) производит выбор сигнала α₀ или α_j и формирует сигнал ошибки (ERR) на второй выход схемы СВ (13).

Схема выбора реализует условия:

$$ERR={\alpha }_0•\tilde{\alpha }+{\alpha }_0•{\alpha }_j+\tilde{\alpha }•{\alpha }_j+\tilde{\alpha }=\tilde{\alpha }+{\alpha }_0•{\alpha }_j$$

$$\alpha =\overline{ERR}\left({\alpha }_0{\overline{\alpha }}_j+{\tilde{\alpha }}_j{\overline{\alpha }}_0+\overline{{\alpha }_0}\overline{{\alpha }_j}\overline{\tilde{\alpha }}\right)$$

В последней формуле для вычисления α символом α_j обозначено конкретное значение α_j, которое может быть равным как «1», так и «0».

Реализация схемы выбора СВ (4) тривиальна на элементах логики (И, ИЛИ, НЕ, Триггер) и не требует детального отображения специальным чертежом.

Блок синхронизации БС (15) не имеет особенностей по сравнению со блоком синхронизации БС (1) фиг.1 прототипа и имеет такую же схему для реализации, представленную на фиг.4.

Такая схема согласно работе [9] выпускается промышленностью как отдельный интегральный модуль (ЧИП).

Описание функционирования МПА.

Первоначально МПА устанавливается в исходное состояние:

1) Устанавливается в исходное состояние схема коммутатор - т.е. триггеры регистра Rg (13), фиксирующие значения α₀, α_j и $$\tilde{\alpha }$$ .

2) Все регистры памяти автомата (т.е. Rg 2, 5, 7, 13) и RS-триггеры (8, 10) устанавливаются в нулевое состояние.

И только после этого дается сигнал «Пуск» (16) на блок синхронизации БС (15).

Далее выполняется последовательность действий по сигналам τ₁, τ₂, τ₃, τ₄.

Сигнал τ₁

1. Отключается исполнение команды A_j.

Опрашивается F₁ (1) и производится запись в Rg (2), Rg (5).

Сигнал τ₂

2. Опрашивается Rg (2), Rg (5).

Сигнал τ₃

3. Опрос СВ (4) и запись α_j в RS (8).

Сигнал τ₄

4. Перепись 5, 8 в 7, 10 (опрос 13).

Включение A_j и повторение первого пункта по установке исходного состояния МПА, т.е. установка коммутатора КМ (3) в исходное состояние.

Как известно τ₁(t)&τ₂(t)&τ₃(t)&τ₄(t)=⌀

Такая последовательность действий продолжается до получения сигнала f₀, т.е. заключительного перехода МПА в нулевое состояние, свидетельствующего об окончании программы МПА.

Рассмотрим простой пример ГСА (фиг.5), для которого введены два пустых оператора (3, 5) как и при синтезе схемы МПА прототипа.

Заданной ГСА (фиг.5) соответствует граф переходов (фиг.6). При числе состояний N=10 количество переменных в коде x₁x₂…x_m равно m=4.

Для примера прототипа схема F₃ имеет 4 входа и 2 выхода для определения адресного кода мультиплексора, т.к. q=3. В примере прототипа количество неиспользованных информационных входов мультиплексора равно 1. Обозначим в квадратных скобках количество входов и выходов схемы F₃ в виде F₃ [4, 2], а количество неиспользуемых информационных входов мультиплексора как М [1].

В предлагаемом изобретении нет ни F₃ [4, 2], ни М [1], а соответствие между α и a(t) задается таблицей 1.

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.

На фиг.7 и 8 приведен пример ГСА и граф переходов из описаний прототипа [7]. Для него N=15, m=4, q=6, F₃ [4, 4], М [2].

Таблица 2 определяет правило соединения схем «ИЛИ, И» в КМ и DC (20).

В таблице 2 приведены списки для выбора α₀, $$\tilde{\alpha }$$ или α_j по номерам состояний a(t). Эти списки табл.2 полностью определяют правила соединения выходов внутреннего дешифратора (DC) КМ с выходами α₀, $$\tilde{\alpha }$$ или α_j. При этом $$\tilde{\alpha }$$ соответствует выходу DC с номером 15, т.к. такое состояние отсутствует в графе переходов, а следовательно соответствующие им коды y₁y₂…y_m могут появиться на входе КМ только при неисправной работе блоков МПА. Преимущество предложенных подходов к синтезу МПА по сравнению с классическим на БИС становится очевидным после анализа работы [14, 15].

Второй пример (фиг.7, 8)..

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, 1, 3, 4, 5, 8, 15-20, 22-24.

α_j - 2, 5-14, 21.

$$\tilde{\alpha }$$ →25-31.

Соответствия α_j→a(t) приведено в таблице 3.

В этом случае m=5, q=6.

Число неиспользованных информационных входов мультиплексора в прототипе равно 2, F₃ [5, 3], М [2].

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].

Граф переходов ГСА приведена на фиг.12. В этом случае m=6, q=10, F₃ имеет 6 входов и 4 выхода, при этом в мультиплексоре прототипа из 16 информационных входов 6 выходов не используются.

4. N=38, m=6, q=10, F₃ [6, 4], М [6]

Как видно из таблицы 4 в этом случае при q=10 для выбора α_j используются 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

В предложенной структуре МПА сохраняются все преимущества прототипа по сравнению с классическими структурами Мура. Действительно, поскольку на входе F₁ (1) кроме кода x₁x₂…x_m только один сигнал α_j∈{α}, то объем F₁ (1) V=m·2^m+1 как в прототипе. Тогда как в классических схемах Мура V=m·2^m+q.

Однако новая структура МПА по сравнению с прототипом обладает и новым качеством, т.к. схема становится самоконтролируемой и выдает сигнал ошибки ERR на клемму (14) при наличии неисправности. Кроме того, вместо триггера (4), комбинационной схемы F₃ и мультиплексора с внутренним регистром памяти используется одна схема КМ (3), формирующая как сигналы α_j, так и сигналы α₀, $$\tilde{\alpha }$$ для самоконтроля МПА.

При фактической исправности блока синхронизации БС (15) и схемы выбора СВ (4) анализ сигналов α₀, α_j, $${\tilde{\alpha }}_n$$ фиксирует факт неисправности МПА, который может появиться в любом из блоков МПА от входа F₁ (1) и до выхода. Неконтролируемым остается лишь блок F₂ (l 1), формирующий выходные команды A₁,A₂,…,A_k. Однако, если в ГСА все операторы действия разные (не повторяются), то в схеме F₂ нет необходимости, т.к. она заменяется типовым дешифратором (DC). Способ контроля дешифратора известен [14].

Но и при повторении команд в структуре ГСА схема F₂ - это всего лишь несколько схем «ИЛИ», т.к. обычно в ГСА уровень повторяемости A_j невысок [12, 13].

Следовательно, вероятность выхода из строя схемы F₂ на 2-3 порядка ниже чем остальных схем МПА. Поэтому можно считать, что контролируемость исправности МПА в предложенной структурной схеме является тотальной.

Рассмотренные примеры подтверждают преимущества изобретения:

1. Предложенный МПА реализуется одинаковыми средствами независимо от сложности ГСА.

2. Обеспечение режима самоконтроля за счет наличия весьма простой схемы выбора СВ (4).

3. Упрощение конструкции за счет отсутствия блоков для вычисления адреса мультиплексора (F₃) и самого мультиплексора для выбора логического условия α_j.

Т.е. предложенная структурная схема МПА является новой и соответствует поставленной цели изобретения.

Литература

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.

Изобретение относится к вычислительной технике и дискретной автоматике и может быть использовано для построения устройств управления в системах обработки информации, а также для управления технологическими процессами в реальном времени. Техническим результатом является упрощение конструкции автомата. В структуру автомата введен специализированный коммутатор, который по коду состояния автомата y₁y₂…y_m производит выбор значения безусловного перехода α₀, значения условного перехода α_j и наличие $$\overline{\alpha }$$ , которые не должны появляться при заданном алгоритме управления. Схема выбора автомата по тому же коду y₁y₂…y_m осуществляет передачу α₀ или α_j на вход комбинационной схемы автомата, вычисляющей y₁y₂…y_m по входному коду x₁x₂…x_m и значению логического условия α_j. Схема выбора формирует также сигнал ошибки в работе автомата на основе логического анализа α₀, α_j, $$\overline{\alpha }$$ . 12 ил., 4 табл.

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