Пример проектирования УАЖЛ

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

Исходным для проектирования управляющего автомата (УА) является микропрограмма, представленная, например, в форме ГСА.

Различают два класса управляющих автоматов [2, 7]:

□ с "жесткой" логикой:

• автомат Мура;

• автомат Мили;

• С-автомат;

□ с программируемой логикой.

4.4.1. Управляющий автомат с "жесткой" логикой

Автоматы с "жесткой" логикой проектируются как обычные конечные структурные автоматы [2, 7, 8].

Сначала необходимо перейти от ГСА микропрограммы к графу автомата, для чего следует:

1. Разметить исходную микропрограмму.

2. Построить по размеченной микропрограмме граф автомата.

Далее реализуются стандартные процедуры синтеза структурного автомата, заданного графом:

□ кодирование алфавита входных и выходных символов автомата двоичными кодами;

□ кодирование внутренних состояний автомата;

□ выбор элемента памяти (типа триггера);

□построение автоматной таблицы переходов;

□ синтез комбинационной схемы, реализующей функцию переходов КСх 1;

□ синтез комбинационной схемы, реализующей функцию выходов КСх 2.

(Страница99)

Процедура разметки микропрограммы ставит в соответствие символам состояний автомата (а₁, а₂,..., а_M) некоторые объекты микропрограммы. Способы разметки микропрограмм различаются для автоматов различных типов.

Для автомата Мура разметка выполняется по следующим правилам [2]:

□ символом а₁ отмечается начальная и конечная вершина ГСА;

□ различные операторные вершины отмечаются разными символами состояний;

□ все операторные вершины должны быть отмечены.

Для автомата Мили разметка выполняется по следующим правилам [2]:

□ символом а₁ отмечается вход вершины, следующей за начальной, а также вход конечной вершины;

□ входы всех вершин, следующих за операторными, должны быть отмечены символами состояний;

□ если вход вершины отмечается, то лишь одним символом;

□ входы различных вершин, за исключением конечной, отмечаются различными символами.

Рассмотрим пример построения управляющего автомата Мура для устройства, реализующего операцию деления. Операционный автомат (см. рис. 4.4) и ГСА микропрограммы (см. рис. 4.5) этого устройства были построены ранее.

Шаг 1. Выполним разметку микропрограммы. Для этого сопоставим каждой операторной вершине ГСА в произвольном порядке (например, слева направо и сверху вниз) символ состояния автомата из множества {a₂, a₃,..a₁₄}. Начальную и конечную вершины сопоставим с начальным состоянием автомата а₁. Такая разметка показана на рис. 4.5.

Шаг 2. Построим граф автомата, заданного размеченной микропрограммой, которую получили на предыдущем шаге. Для этого вершины графа сопоставим с состояниями автомата а_1, a ₂,.., a₁₄.Соединим ориентированными ребрами те пары вершин графа, между которыми на ГСА микропрограммы существуют переходы, причем пометим ребра графа соответствующими условиями перехода. Если переход между двумя операторными вершинами микропрограммы осуществляется безусловно, то условие перехода на ребре графа — константа 1.

(Страница100)

Построив таким образом граф, мы фактически задаем алфавиты внутренних состояний и входных символов и определяем функцию переходов. Для задания алфавита выходных символов и функции выходов (для автомата Мура функция выходов зависит только от его состояний) следует сопоставить каждой вершине автомата в качестве выходного символа содержимое соответствующей операторной вершины ГСА микропрограммы. Таким образом, получим граф микропрограммного автомата, который приведен на рис. 4.6.

Рис. 4.6. Граф микропрограммного автомата Мура

Шаг 3. Кодирование алфавитов входных и выходных символов автомата двоичными кодами. Алфавит входных символов составляет множество двоичных переменных X= {x₁, x₂, х₃}, поэтому проблема кодирования входных символов двоичными переменными здесь не стоит. Что касается кодирования символов выходного алфавита, то отложим обсуждение этого вопроса до шага 8.

Шаг 4. В процессе кодирования внутренних состояний автомата могут решаться проблемы исключения гонок в автомате, проблемы минимизации комбинационной схемы, обеспечивающей функцию переходов автомата. Для решения этих задач разработаны достаточно сложные алгоритмы, которые описаны в литературе, например, [2, 5]. Здесь мы не будем касаться этой стороны процедуры синтеза автомата.

Следует отметить, что проблемы гонок могут быть полностью решены при использовании в автомате двухтактных элементов памяти, причем способ кодирования состояний в этом случае роли не играет. Правда, затраты оборудования при таком решении несколько возрастают, по сравнению с использованием метода противогоночного кодирования, но во-первых, эффективность метода заметно проявится лишь при достаточно большом числе состояний автомата (25 — 40), а во-вторых, большинство современных интегральных элементов памяти (триггеров) выпускаются именно двухтактными. Применение специальных методов кодирования "с учетом сложности комбинационных схем" [2] так же обеспечивает заметный эффект лишь для достаточно громоздких автоматов.

В нашем примере воспользуемся простейшим методом кодирования состояний автомата, когда код состояния совпадает с двоичным числом, соответствующим номеру состояния. В рассматриваемом автомате насчитывается 14 состояний (см. рис. 4.6), поэтому для их кодирования требуется четырехразрядный двоичный код (2⁴>14; 2³<14) — табл. 4.2.

Таблица 4.2. Кодирование состояний автомата

Состояние автомата	Код Т1 Т2 Т3 Т4	Состояние автомата	Код Т1 Т2 Т3 Т4
a1		a8
a2		а9
a3		a10
a4		a11
a5		a12
a6		a13
a7		a14

Шаг 5. Выбор элемента памяти (типа триггера). При выборе элемента памяти следует учитывать простоту управления им. С этой точки зрения удобнее выбирать триггеры, управляемые по единственному информационному входу к таким относятся D- и T-триггеры. В нашем примере в качестве элемента памяти автомата выберем синхронный двухтактный D-триггер. Очевидно, для реализации нашего автомата понадобятся четыре D-триггера.

Шаг 6. Построение автоматной таблицы переходов (табл. 4.3). Эта таблица практически описывает функцию переходов автомата, строится по графу автомата и определяет, какие значения необходимо подать на управляющие входы триггеров на каждом переходе автомата в новое состояние. Строка таблицы соответствует одному переходу автомата. Таким образом, автоматная таблица содержит столько строк, сколько ребер в графе автомата (включая и петли, если они имеются в графе).

Таблица 4.3. Автоматная таблица переходов

Шаг 7. Синтез комбинационной схемы, реализующей функцию переходов автомата. Эта комбинационная схема в нашем случае реализует четыре булевы функции D₁, D₂, D₃, D_4, зависящие от четырехразрядного двоичного кода состояния автомата Т₁Т₂Т₃Т₄ и трехбитного вектора входных символов x₁x₂x₃. Комбинационная схема, описываемая системой четырех булевых функций от семи переменных, должна обеспечивать переходы автомата в соответствии с графом рис. 4.6.

Для построения этой схемы можно построить четыре карты Карно для D₁, D₂, D₃, D₄ по таблицам истинности, заданным соответствующими столбцами автоматной таблицы переходов, и минимизировать эти функции. Менее трудоемкий способ состоит в предварительной дешифрации состояний автомата (булевы функции четырех переменных) и записи функций возбуждения через значения a_i и x_k. Воспользуемся последним способом, тем более, что дешифрированные состояния автомата пригодятся нам и на следующем шаге при формировании функции выходов.

Итак, предусмотрим дешифратор, на входы которого поступает двоичный код состояния автомата а на выходах формируется унитарный код . Кстати, поскольку на входах дешифратора не могут появиться комбинации 0000 и 1111 (их мы не использовали при кодировании состояний), то схему дешифратора можно минимизировать. (Как? Попробуйте построить такой дешифратор самостоятельно.) Рассмотрим столбец D ₁автоматной таблицы переходов, отметив те наборы входных переменных функции возбуждения (из { а }и {x}), на которых D₁ принимает единичные значения. Можно записать:

(4.2)

Обратите внимание, что функция D₁ не зависит от входных переменных { х }(частный случай!). Действительно, переход, например, из состояния а₉ в зависимости от значения х₂ может произойти в а₁₀ или в a₁₁, но в обоих этих состояниях значение старшего разряда кодов одинаково. То же для D₁ можно сказать и обо всех остальных переходах, зависящих от входных символов (из a₁, a₅, a₁₂).

Теперь запишем булевы выражения для остальных функций возбуждения.

(4.3)

(4.4)

(4.5)

Шаг 8. Синтез комбинационной схемы, реализующей функцию выходов. Функция выходов автомата Мура зависит только от его внутреннего состояния и задана непосредственно на графе автомата (см. рис. 4.6). Выходами микропрограммного автомата являются микрооперации, поступающие в точки управления операционного автомата. Поэтому выходные символы микропрограммного автомата обычно не кодируют, а формируют на выходе значение вектора микроопераций. При большом числе микроопераций с целью уменьшения связности между ОА и УА на вход ОА передают не вектор микроопераций, а номер активной в данном такте микрооперации. Подробнее об этом — в следующем разделе.

Из графа автомата (см. рис. 4.6) видно, что микрооперация у ₁должна вырабатываться автоматом, когда он находится в состоянии а₂, микрооперация у ₂— в состоянии а ₃ и т.д. Микрооперация у ₅должна вырабатываться автоматом, находящимся в состоянии а ₅ и а ₁₀. Запишем функцию выходов автомата в виде системы булевых функций (Напомним, что переменные а₁, а₂,..., a₁₄ являются булевыми, принимающими единичное значение, когда автомат находится в соответствующем состоянии, и нулевое значение во всех остальных случаях):

(4.6)

Шаг 9. Теперь изобразим функциональную схему управляющего автомата, используя выражения (4.2) — (4.6) с учетом выбранного типа элемента памяти.

Управляющий микропрограммный автомат с жесткой логикой (автомат Мура), изображенный на рис. 4.7, имеет три двоичных входа x₁, x₂, x₃, вход тактового сигнала CLK и семнадцать двоичных выходов — микрооперации y₁, y₂,..., y₁₇

Память автомата представлена четырьмя двухтактными синхронными D-триггерами, объединенными общей цепью синхронизации (CLK). Выходы триггеров поступают на вход дешифратора DC "4→ 16", на выходах которого формируется унитарный код текущего состояния автомата. Поскольку проектируемый автомат является автоматом Мура, выходы дешифратора фактически являются выходами управляющего автомата (значениями микроопераций). Исключение составляет микрооперация у_5, которая формируется как дизъюнкция двух различных состояний автомата, поскольку эта микрооперация присутствует в двух различных операторных вершинах исходной микропрограммы (см. рис. 4.5).

Рис 4.7. Микропрограммный автомат Мура — функциональная схема

Функции возбуждения триггеров формируют значения D_i, i {1, 2, 3, 4} на выходах одно- или двухуровневых схем, построенных согласно выражениям (4.2) — (4.5). Обратите внимание, что в выражениях (4.3) и (4.5) имеется одинаковый терм — а₁₂х₃. На функциональной схеме выход конъюнктура, реализующего этот терм, поступает на два входа различных дизъюнкторов, "обеспечивая" одновременно две функции возбуждения — D₂ и D₄.

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

(4.7)

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

Итак, мы построили микропрограммный автомат с "жесткой" логикой. Давайте представим, что нам понадобилось незначительно изменить исходную микропрограмму, например, добавить еще одну операторную вершину. Практически это приведет к необходимости полного перепроектирования всей схемы автомата. Это особенность автоматов с "жесткой" логикой является их серьезным недостатком.

Для того чтобы уменьшить зависимость структуры автомата от реализуемых им микропрограмм, используют управляющие автоматы с программируемой логикой.

Дата добавления: 2015-04-25