ПТЦА - Прикладная теория цифровых автоматов

1. Методы анализа и синтеза комбинационных схем.

Техническим аналогом булевой функции в вычислительной технике

является, так называемая, комбинационная схема, на вход которой поступают

и с выхода снимаются электрические сигналы в виде одного из уровней

напряжения, соответствующих значениям логического 0 и логической 1.

[pic]

Для выяснения, что же такое комбинационная схема, рассмотрим

схему S, имеющую m входов и n выходов (рис. 1). На её входы могут быть

поданы наборы значений входных переменных Xi {0,1}, [pic], а на выходах

формируются выходные переменные Yj({0,1}, [pic].

Схема S называется комбинационной, если каждую из n функций её

выходов Y1,Y2, ..., Yn можно представить как булеву функцию входных

переменных X1, X2, ..., Xm.

Комбинационная схема описывается с помощью системы уравнений (1), где

Fi – булева функция.

[pic]

Как следует из определения комбинационной схемы, значения выходных

переменных Yj в произвольный момент времени однозначно определяются

значениями входных переменных Xi.

Структурно комбинационная схема может быть представлена как

совокупность элементарных логических схем – логических элементов (ЛЭ).

ЛЭ выполняют над входными переменными элементарные логические операции типа

И-НЕ, И, ИЛИ, ИЛИ-НЕ и т.д. Число входов логического элемента

соответствует числу аргументов воспроизводимой им булевой функции.

Графическое изображение комбинационной схемы, при котором показаны связи

между различными элементами, а сами элементы представлены условными

обозначениями, называется функциональной схемой.

В ходе разработки комбинационных схем приходится решать задачи

анализа и синтеза.

Задача анализа состоит в определении статических и динамических

свойств комбинационной схемы. В статике определяются булевы функции,

реализуемые комбинационной схемой по известной ей структуре. В динамике

рассматривается способность надёжного функционирования схемы в

переходных процессах при смене значений переменных на входах схемы, т.е.

определяется наличие на выходах схемы возможных нежелательных импульсных

сигналов, которые не следуют непосредственно из выражений для булевых

функций, реализуемых схемой.

Задача синтеза заключается в построении из заданного набора

логических элементов комбинационной схемы, реализующей заданную систему

булевых функций.

Решение задачи синтеза не является однозначным, можно предложить

различные варианты комбинационных схем, реализующих одну и ту же систему

булевых функций, но отличающихся по тем или иным параметрам. Разработчик

комбинационных схем из этого множества вариантов выбирает один, исходя

из дополнительных критериев: минимального количества логических элементов,

необходимых для реализации схемы, максимального быстродействия и т.д.

Существуют различные методы синтеза комбинационных схем, среди которых

наиболее разработан канонический метод.

1.1. Канонический метод синтеза комбинационных схем.

Как отмечалось выше, комбинационная схема (КС) может иметь

несколько выходов. При каноническом методе предполагается, что каждая

выходная функция реализуется своей схемой, совокупность которых и даёт

требуемую КС. Поэтому синтез сложной КС с n выходами заменяется синтезом n

схем с одним выходом.

Согласно каноническому методу синтез КС включает в себя ряд этапов.

1. Подлежащая реализации булева функция (или её отрицание)

представляется в виде СДНФ.

2. С использованием методов минимизации определяется минимальная

ДНФ (МДНФ) или минимальная КНФ (МКНФ). Из полученных двух минимальных

форм выбирается более простая.

3. Булеву функцию в минимальной форме согласно п.2 представляют в

заданном (или выбранном разработчиком) базисе .

4. По представлению функции в заданном базисе строят комбинационную

схему.

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

F(X1,X2,...,Xm) может быть задана не на всех возможных наборах аргументов

X1, X2, ..., Xm. На тех наборах, где функция неопределенна, её

доопределяют так, чтобы в результате минимизации получить более простую

МДНФ или МКНФ. При этом упростится и сама КС. Кроме того, довольно часто с

целью получения ещё более простого представления функции МДНФ, полученная

в п.2, представляется в так называемой скобочной форме, т.е. выносятся за

скобки общие части импликант МДНФ.

Рассмотрим канонический метод синтеза на примере построения

схемы полного одноразрядного двоичного сумматора.

Как известно из курса машинной арифметики, полный одноразрядный

сумматор - это устройство, которое осуществляет сложение по mod 2

соответствующих разрядов (X1,X2) двоичных чисел с учётом переноса (Рm) в

данный разряд из соседнего младшего разряда суммы. Сумматор вырабатывает

цифру результата (S) в данном разряде и перенос (Рс) в соседний старший

разряд суммы. Таблица истинности такого сумматора (т.е. представление

булевой функции, которую он реализует, в виде СДНФ) представлена ниже.

|X1 |0|0|0|0|1|1|1|1|

|X2 |0|0|1|1|0|0|1|1|

|Pm |0|1|0|1|0|1|0|1|

|S |0|1|1|0|1|0|0|1|

|Pc |0|0|0|1|0|1|1|1|

[pic]

Необходимо получить булевы функции S=F1(X1,X2,Рm) и Рс=F2(X1,X2,Рm).

Карты Карно для этих функций приведены ниже (рис.2).

Как следует из приведённых карт, МДНФ соответствующих функций

имеет вид:

S=[pic][pic]Pm+[pic]X2[pic]+X1[pic][pic]+ X1 X2 Pm

Pc= X1 X2+X1 Pm+X2 Pm

Полученная система булевых функций представлена в базисе И, ИЛИ, НЕ.

Соответствующая ей КС приведена на рисунке 4.

Полученную комбинационную схему можно упростить, вынеся за скобки

общие части в выражениях для S и Рc, однако существенного результата это не

даст (желательно самостоятельно в этом убедиться).

Значительно упростить схему можно, если воспользоваться другим

базисом, например логическим элементом "ИСКЛЮЧАЮЩЕЕ ИЛИ". В этом случае

выражение для S можно записать S = (X1+X2+ Рm)mod2= X1( X2( Рm. Тогда схема

для S будет иметь вид (рис.3).

[pic]

Иногда для синтеза КС с несколькими выходами может использоваться

следующий приём. Будем считать, что при синтезе схемы сумматора функция S

является функцией четырёх переменных: S=f(X1,X2,Рm,Рс). Таблица

истинности для этого случая принимает вид изображенный в таблице 2.

[pic]

|0 |0 |0 |

|0 |1 |0 |

|1 |0 |1 |

|1 |1 |1 |

Из приведенной таблицы переходов для данного триггера Qt+1 =

f(Qt,Dt) можно получить таблицу функций его входов Dt = ((Qt, Qt+1).

|Q t |Q |D t |

| |t+1 | |

|0 |0 |0 |

|0 |1 |1 |

|1 |0 |0 |

|1 |1 |1 |

Как видно из таблицы, состояние, в которое переходит триггер (средний

столбец), совпадает с поступившим на его вход сигналом D(t) (правый

столбец). В связи с этим таблица функций возбуждения памяти

синтезируемого автомата с использованием D-триггеров будет полностью

совпадать с кодированной таблицей переходов этого автомата. Промышленность

выпускает D-триггера в интегральном исполнении. Например,

[pic]

K155TM2 (рис. 25).Таких триггеров два в одном корпусе. Вход С –вход

синхронизации, Q,(Q – выходы, Q – прямой, [pic] – инверсный. R, S –

входы установки в 0 и 1 соответственно. При подаче на вход R и S

логического нуля триггер устанавливается в соответствующие состояния

независимо от сигнала на входах D и C.

T-триггер – триггер со счетным входом – имеет один информационный вход

Т и один выход Q и осуществляет суммирование по модулю два значений

сигнала T и состояния Q в заданный момент времени.

Условное обозначение и таблица переходов T-триггера представлена на

рис 26.

[pic]

|T |Q t|Q |

| | |t+1 |

|0 |0 |0 |

|0 |1 |1 |

|1 |0 |1 |

|1 |1 |0 |

Таблица функций входов триггера Tt = f(Qt, Qt+1) представлена в

таблице.

|Q t |Q |T t |

| |t+1 | |

|0 |0 |0 |

|0 |1 |1 |

|1 |0 |1 |

|1 |1 |0 |

На основании этой таблицы можно получать функцию возбуждения элементов

памяти при синтезе автомата на базе T-триггера. Например, если автомат

перешел из состояния ai = 010 в состояние aj = 110, то для обеспечения

этого перехода функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 T1 = 1,

для второго триггера при переходе из 1 в 1 T2 = 0,

для третьего триггера при переходе из 0 в 0 T3 =0 и т.д.

В чистом виде промышленность не выпускает T-триггера.

RS-триггер – триггер с раздельными входами.

Данный триггер имеет два входных канала R и S и один выходной Q. Вход

S (set) называется входом установки в единицу, вход R (reset) – входом

установки в нуль. Условное обозначение и таблица переходов RS-триггера

представлена на рис. 27.

В таблице переходов при подаче комбинации S = R = 1 состояние

перехода Qt+1 не определено и эта комбинация сигналов является

запрещенной для RS-триггера.

Таблицу переходов можно более компактно изобразить в виде (см.

табл. 21б) Анализируя табл.21 б,в отмечаем что, например, переход триггера

из 0 в 0требует подачи комбинации R=0, S=0 или R=1,S=0, т.е. можно

сказать что этот переход будет при R=X (безразличное состояние) , S=0.

Аналогично рассуждая по отношению к другим переходам получим

следующую таблицу функций входов.

|R |S |Q t |Q | | |R |S |Q |

| | | |t+1 | | | | |t+1 |

|0 |0 |0 |0 | | |0 |0 |0 |

|0 |0 |1 |1 | | |0 |1 |1 |

|0 |1 |0 |1 | | |1 |0 |0 |

|0 |1 |1 |1 | | |1 |1 |– |

|1 |0 |0 |0 | | | | |б) |

|1 |0 |1 |0 | | | | | |

|1 |1 |0 |– | | | | | |

|1 |1 |1 |– |а) | | | | |

|Q t |Q |Rt |S |

| |t+1 | | |

|0 |0 |X |0 |

|0 |1 |0 |1 |

|1 |0 |1 |0 |

|1 |1 |0 |X |

На основании таблицы можно получить функцию возбуждения памяти

автомата при синтезе на базе RS-триггеров. Например, если автомат переходит

из состояния ai= 010 в состояние aj=110, то для обеспечения такого перехода

функции возбуждения должны быть:

для первого триггера при переходе из 0 в 1 R1 =0, S1 = 1;

для второго триггера при переходе из 1 в 1 R2 =0, S2 = X;

для третьего триггера при переходе из 0 в 0 R3 =X, S3= 0.

Аналогично для любого другого перехода автомата.

В чистом виде синхронный RS - триггер, используемый для синтеза ЦА,

промышленностью не выпускается.

JK- триггер – имеет два информационных входа J и K и один выход Q.

Вход J – вход установки в 1, вход K – вход установки в 0, т.е. эти входы

аналогичны соответствующим входам RS-триггера: J – соответствует S, K –

соответствует R. Однако, в отличие от RS-триггера, входная комбинация J =

1, K= 1 не является запрещённой. Условное обозначение и таблица переходов

JK-триггера представлены на рис.28. и в табл. 22.

|J |K |Q t |Q | | |J |K |Q |

| | | |t+1 | | | | |t+1 |

|0 |0 |0 |0 | | |0 |0 |Q t |

|0 |0 |1 |1 | | |0 |1 |0 |

|0 |1 |0 |0 | | |1 |0 |1 |

|0 |1 |1 |0 | | |1 |1 |Q t |

|1 |0 |0 |1 | | | | |б) |

|1 |0 |1 |1 | | | | | |

|1 |1 |0 |1 | | | | | |

|1 |1 |1 |0 |а) | | | | |

Как следует из таблиц переходов, для комбинаций входных сигналов JK

= 00(10 триггер ведет себя как RS-триггер, а при комбинации JK = 11 – как T-

триггер.

Анализируя таблицу переходов ( табл. 22 а), отмечаем, что переход

триггера, например, из 0 в 1 требует подачи входных сигналов J=1, K=0

или J=1, K=1, т.е. J=1, K=Х (безразличное значение). Аналогично

рассуждая по отношению к другим переходам, получим следующую

таблицу функций входов JK-триггера.

|Q t |Q |J |K |

| |t+1 | | |

|0 |0 |X |0 |

|0 |1 |1 |X |

|1 |0 |X |1 |

|1 |1 |0 |X |

На основании последней таблицы можно получить функцию возбуждения

элементов памяти при синтезе автомата на JK-триггерах. Например, при

переходе автомата из состояния ai=010 в состояние aj=110, функции

возбуждения должны быть:

для первого триггера при переходе из 0 в 1 J1 = 1,

K1 = X;

для второго триггера при переходе из 1 в 1 J2 = X,

K2 = 0;

для третьего триггера при переходе из 0 в 0 J3 = 0,

K3 = X.

Пример канонического метода структурного синтеза автомата.

Выполним структурный синтез частичного автомата А, заданного своими

таблицами переходов и выходов (табл. 23 и 24.).

[pic]

Синтез будем выполнять в следующем порядке:

1. Выберем в качестве элементов памяти D-триггер, функция входов

которого представлена в таблице стр. 33.

2. Закодируем входные, выходные сигналы и внутренние состояния автомата.

Количество входных абстрактных сигналов F = 3, следовательно

количество входных структурных сигналов L= ]log2F [ = ]log23[ = 2,

т.е. х1, х2.

Количество выходных абстрактных сигналов G = 4, следовательно

количество выходных структурных сигналов N =]log2G[ = ]log24[ = 2, т.е.

у1, у2. Количество внутренних состояний абстрактного автомата M = 4,

следовательно количество двоичных элементов памяти (триггеров) R = ] log2M

[ = ]log24[ = 2.

[pic]

Следовательно, структура ЦА с учетом того, что исходный автомат

является автоматом Мили, в качестве элементов памяти используется D-

триггер, может быть представлена в виде(рис. 29):

Кодирование входных, выходных сигналов и внутренних состояний

представлена в таблицах:

|0 |0 |0 |

|0 |1 |1 |

|1 |0 |1 |

|1 |1 |0 |

| |00 |01 |11 |10 |

|00 |00 |11 |01 |– |

|01 |– |10 |11 |– |

|11 |01 |– |10 |01 |

|0 |0 |X |0 |

|0 |1 |0 |1 |

|1 |0 |1 |0 |

|1 |1 |0 |X |

| |00 |01 |11 |10 |

|0 |0 |0 |X |

|0 |1 |1 |X |

|1 |0 |X |1 |

|1 |1 |X |0 |

| |00 |01 |11 |10 |

| | |1|2|2 |

| | |1|3|1 |

|T |=|1|5|1 |

| | |2|3|3 |

| | |2|4|1 |

| | |2|5|1 |

| | |3|4|2 |

| | |3|5|2 |

2. Упорядочим строки матрицы [pic], для чего построим матрицу [pic]

следующим образом. В первую строку матрицы [pic] поместим пару ((,() с

наибольшим весом р((,(). В нашем случае ((,() = (2,3), р(2,3) = 3. Из

всех пар, имеющих общий компонент с парой ((,() выбирается пара ((,() с

наибольшим весом и заносится во вторую строку матрицы [pic]. Ясно, что

{(,(}({(,(}(0. Затем из всех пар, имеющих общий компонент хотя бы с одной

из внесенных уже в матрицу [pic] пар выбирается пара с наибольшим весом и

заносится в матрицу [pic] и т.д.. В случае равенства весов пар вычисляются

суммы весов компонентов пар (весом р(() компонента ( называется число

появлений ( в матрице [pic]) и в матрицу [pic] заносится пара с

наибольшей суммой весов. В рассматриваемом автомате на второе место вслед

за парой (2,3) претендуют пары: (1,2) с р(1,2) = 2; (3,4) с р(3,4) = 2,

(3,5) с р(3,5) = 2.

Для определения того, какая пара займет второе место в матрице [pic]

находим веса компонентов пар:

р(1) = 3 р(2) = 3 р(1) + р(2) = 6

р(3) = 4 р(4) = 2 р(3) + р(4) = 6

р(3) = 4 р(5) = 2 р(3) + р(5) = 6

В данном случае для всех пар совпадают и их веса и веса их

компонентов. Поэтому на второе место матрицы [pic] может быть поставлена

любая из пар (1,2), (3,4), (3,5). Но тогда на 3-м и 4-м будут остальные

две. Выполнив упорядочивание всех пар, получим матрицу [pic] в виде:

| | |i|j|p(i|

| | | | |,j)|

| | |2|3|3 |

| | |1|2|2 |

|M |=|3|4|2 |

| | |3|5|2 |

| | |1|3|1 |

| | |1|5|1 |

| | |2|4|1 |

| | |2|5|1 |

3. Определяем разрядность кода для кодирования состояний автомата

(количество элементов памяти – триггеров). Всего состояний M=5. Тогда

R = ]log2M[ = ]log25[ =3.

Закодируем состояния из первой строки матрицы следующим образом: K2 =

K(а2) = 000; K3 = K(а3) = 001.

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

картой Карно:

[pic]

4. Вычеркнем из матрицы [pic] первую строку, соответствующую закодированным

состояниям а2 и а3. Получим матрицу [pic].

| | |i|j|p(i|

| | | | |,j)|

| | |1|2|2 |

| | |3|4|2 |

|M’|=|3|5|2 |

| | |1|3|1 |

| | |1|5|1 |

| | |2|4|1 |

| | |2|5|1 |

5. В силу упорядочивания п.2 в первой строке закодирован ровно один

элемент. Выберем из первой строки незакодированный элемент и обозначим его

(. (В нашем случае ( = 1).

6. Строим матрицу [pic], выбрав из [pic] строчки, содержащие (.

| | | | |i|j|p(i|

| | | | | | |,j)|

| | | | |1|2|2 |

|M(|=|M’|=|1|3|1 |

| | | | |1|5|1 |

Пусть B( = {(1,...,(F} – множество элементов из матрицы [pic],

которые уже закодированы. Их коды К(1,..., K(F соответственно. В нашем

случае:

B( = B3 = {2,3} K2 = 000 K3 = 001.

7. Для каждого K(f (f=1, ..., F) найдем [pic]– множество кодов, соседних с

[pic] и еще не занятых для кодирования состояний автомата. (Для

соседних кодов кодовое расстояние d=1).

K2 = 000 [pic] = {100, 010}

K3 = 001 [pic] = {011, 101}.

Построим множество [pic]

[pic]

Если оказывается, что [pic], то строим новое множество [pic], где [pic]–

множество кодов, у которых кодовое расстояние до кода [pic]равно 2 и т.д..

8. Для каждого кода из множества D( находим кодовое расстояние до кода

[pic].

K2 = 000 K3 = 001

d(100, 000) = 1 d(100, 001) = 2

d(010, 000) = 1 d(010, 001) = 2

d(011, 000) = 2 d(011, 001) = 1

d(101, 000) = 2 d(100, 001) = 1

9. Находим значение функции w для каждого кода из множества D(.

[pic]

10. Из множества D( выбираем код K(, у которого получилось минимальное

значение w в п.9. Выбираем код для состояния a1 К1 =100.

[pic]

11. Из матрицы [pic] вычеркиваем строки, в которых оба элемента уже

закодированы, в результате чего получим новую матрицу [pic]. Если в новой

матрице [pic] не осталось ни одной строки, то кодирование закончено. В

противном случае возвращаемся к п.5. В нашем случае имеем:

| | |i|j|p(i|

| | | | |,j)|

| | |3|4|2 |

| | |3|5|2 |

|M’|=|1|5|1 |

| | |2|4|1 |

| | |2|5|1 |

[pic]

К2 = 000 [pic] = {010}

K3 = 001 [pic] = {011, 101}

[pic]

K2 = 000 K3 = 001

d(010, 000) = 1 d(010, 001) = 2

d(011, 000) = 2 d(011, 001) = 1

d(101, 000) = 2 d(101, 001) = 1

[pic]

Выбираем К4 = 101.

[pic]

[pic]

К1 = 100 [pic] = {110}

K2 = 000 [pic] = {010}

К3 = 001 [pic] = {011}

[pic]

К1 = 100 K2 = 000 K3 = 001

d(110, 100) = 1 d(110, 000) = 2 d(110, 001) = 3

d(010, 100) = 2 d(010, 000) = 1 d(010, 001) = 2

d(011, 100) = 3 d(011, 000) = 2 d(011, 001) = 1

[pic]

Выбираем К5 = 011.

[pic]

Т.к. все состояния автомата закодированы, то работа алгоритма

заканчивается. Общее количество переключений триггеров:

[pic]

Минимально возможное количество переключений (если бы состояния были

закодированы соседним кодированием)

[pic]

Коэффициент эффективности кодирования:

[pic]

Рассмотренный алгоритм кодирования является машино-ориентированным,

существуют программы, реализующие этот алгоритм.

Необходимо отметить в заключении, что использование алгоритма

кодирования для D-триггеров или эвристического алгоритма для других типов

триггеров обеспечивает наиболее простую с точки зрения реализации схему,

но при этом возможны гонки. Для радикального устранения последних

используют аппаратные методы – триггеры с двойной памятью: триггеры,

управляемые фронтом и т.д..

Управляющие и операторные автоматы.

Принцип микропрограммного управления.

ЭВМ перерабатывает информацию, выполняя над ней какие-то операции. Для

выполнения операций над информацией используются операционные устройства –

процессоры, каналы ввода-вывода, устройства управления внешними

устройствами и т.д. Функцией операционного устройства является выполнение

заданного множества операций F={f1,...,fG} над входными словами

D={d1,...,dH} c целью вычисления слов R={r1,...,rQ}, которые представляют

результаты операций R=fg(D), где g=1,2,...,G.

Функциональная и структурная организация операционных устройств

базируется на принципе микропрограммного управления, который состоит в

следующем:

1. Любая операция fg(g=1,...,G), реализуемая устройством, рассматривается

как сложное действие, которое разделяется на последовательность

элементарных действий над словами информации. Эти элементарные действия

называются микрооперациями.

2. Для управления порядком следования микроопераций используются логические

условия, которые в зависимости от значений слов, преобразуемых

микрооперациями, принимают значения "ложь" или "истина" (1 или 0).

3. Процесс выполнения операций в устройстве описывается в форме алгоритма,

который представляется в терминах микроопераций и логических условий и

называется микропрограммой. Микропрограмма определяет порядок проверки

значений логических условий и следования микроопераций, необходимый для

получения требуемых результатов.

4. Микропрограмма используется как форма представления функции устройства,

на основе которой определяется структура и порядок функционирования

устройства во времени.

Т.о. из принципа микропрограммного управления следует, что структура

и порядок функционирования операционных устройств предопределяется

алгоритмом выполнения операции F={f1,...,fG}.

К элементарным действиям над словами информации микрооперациям

относятся: передача информации из одного регистра в другой, взятие

обратного кода, сдвиг и т.д.

Понятие операционного и управляющих автоматов.

Как показал академик В.М. Глушков в любом устройстве обработки

цифровой информации можно выделить два основных блока – операционный

автомат (ОА) и управляющий автомат (УА).

[pic]

Операционный автомат (ОА) служит для хранения слов информации,

выполнения набора микроопераций и вычисления значений логических условий,

т.е. операционный автомат является структурой, организованной для

выполнения действий над информацией. Микрооперации, выполняемые ОА,

задаются множеством управляющих сигналов Y={y1,....,yM}, с каждым из

которых отождествляется определенная микрооперация.

Значения логических условий, вычисляемые в операционном автомате,

отображаются множеством осведомительных сигналов X={x1,...,xL}, каждый из

которых отождествляется с определенным логическим условием.

Управляющий автомат (УА) генерирует последовательность управляющих

сигналов, предписанную микропрограммой и соответствующую значениям

логическим условий. Иначе говоря, управляющий автомат задает порядок

выполнения действий в ОА, вытекающий из алгоритма выполнения операций.

Наименование операции, которую необходимо выполнить в устройстве,

определяется кодом g операции, поступающим в УА извне. По отношению к УА

сигналы g1,...,gh, посредством которых кодируется наименование операции и

осведомительные сигналы x1,...,xL, формируемые в операционном автомате,

играют одинаковую роль: они влияют на порядок выработки управляющих

сигналов Y. Поэтому сигналы g1,...,gh и x1,...,xL относятся к одному классу

– к классу осведомительных сигналов, поступающих на вход УА.

Т.о. любое операционное устройство – процессор, канал ввода-вывода и

т.д. – является композицией операционного и управляющего автоматов.

Операционный автомат, реализуя действия над словами информации, является

исполнительной частью устройства, работой которого управляет управляющий

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

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

функциями – перечнем выполняемых ими действий.

Функция ОА определяется следующей совокупностью сведений:

1) множеством входных слов D={d1,...,dH}, вводимых в автомат в качестве

операндов;

2) множеством выходных слов R={r1,...,rQ}, представляющих результаты

операций;

3) множеством внутренних слов S={s1,...,sN}, используемых для представления

информации в процессе выполнения операций. Можно считать, что входные и

выходные слова совпадают с определенными внутренними D(S, R(S.

4) множеством микроопераций Y={ym}, реализующих преобразование S=(m(s) над

словами информации, где (m – вычисляемая функция;

5) множеством логических условий X={xi}, где xi=(i(si) и (i – булева

функция;

T.o. функция ОА задана, если заданы (определены) множества D, R, S, Y,

X. Время не является аргументом функции ОА. Функция устанавливает список

действий-микроопераций и логических условий, которые может выполнять

автомат, но никак не определяет порядок следования этих действий во

времени. Т.е. функция ОА характеризует средства, которые могут быть

использованы для вычислений, но не сам вычислительный процесс.

Порядок выполнения действий во времени определяется в форме функций

управляющего автомата.

Функция управляющего автомата – это операторная схема алгоритма (

микропрограммы), функциональными операторами которой являются символы

у1,...,уm, отождествляемые с микрооперациями, и в качестве логических

условий используются булевы переменные х1,...,хL. Операторная схема

алгоритма наиболее часто представляется в виде граф-схемы алгоритма (ГСА).

ГСА определяет вычислительный процесс последовательно во времени,

устанавливая порядок проверки логических условий х1-хL и порядок следования

микроопераций у1-уm.

СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ И МИКРОПРОГРАММ

Наиболее наглядно изображать микропрограммы и алгоритмы в виде

ориентированного графа, т.н. граф схемы алгоритма (ГСА). Кроме наглядности

это дает возможность использовать для анализа и преобразования

микропрограмм эффективные методы теории графов. При графическом описании

отдельные функции алгоритмов (микрооперации) отображаются в виде условных

графических изображений, т.н. вершин. В ГСА обычно используют вершины

следующих типов:

[pic]

- вершина «начало» имеет один выход, входов не имеет. Обозначает начало

микропрограммы.

- вершина «конец» имеет любое число входов, выходов не имеет. Обозначает

конец микропрограммы.

- операторная вершина имеет любое число входов, один выход. Внутри

операторной вершины записывается одна микрокоманда - совокупность

микроопераций, допускающих совместное (т.е. одновременное) выполнение.

[pic]

- условная вершина имеет любое число входов и 2 выхода. Внутри условной

вершины записывается булевое выражение, в зависимости от значения

которого осуществляется выбор направления дальнейшего выполнения

микропрограммы.

- особый вид условной вершины - ждущая - имеет множество входов, 2

выхода, 1 из которых заведен на вход. При попадании в ждущую вершину

выход из нее возможен только при выполнении условия Х.

Граф микропрограммы состоит из совокупности перечисленных вершин и

дуг, соединяющих выходы одних вершин с входами других. Соединение вершин

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

описываемого графом, и структуры операционного автомата.

Сама микропрограмма и ее граф должны быть корректны, т.е. отвечать

следующим условиям:

1. В графе должна быть только одна начальная и одна конечная вершина.

2. В любую вершину графа должен вести по крайней мере один путь из

начальной вершины.

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

крайней мере один путь в конечную вершину.

4. При всех возможных значениях логических условий и используемых слов

должен существовать путь из начальной вершины в конечную.

[pic]

Пример ГСА представлен на рисунке:

ГСА на рис.43 называется содержательной, т.к. внутри вершин записаны

в явном виде микрооперации и логические условия. Если же каждую

микрооперацию обозначить символами Yi, a логические условия через Xi, то

получится так называемая кодированная ГСА (рис.44 ). Для правильного

восприятия микропрограммы, заданной в виде кодированной ГСА, необходимо

знать соответствия между Yi, Xi и содержанием соответствующих микроопераций

и логических условий.

Для записи микроопераций внутри вершин используется так называемый

Ф-язык. Подробно с зтим языком можно ознакомиться в последующих курсах

«Схемотехника ЭВМ», «Теория и проектирование ЭВМ». Здесь же мы рассмотрим

только основные положения этого языка.

В этом языке существуют двоичные константы и переменные: 0010 -

константа, A(1:4) - четырехразрядное слово - четырехразрядная двоичная

переменная. Например, A(1:4)=1010 означает, что в первом разряде слова A

будет 1, во втором - 0 и т.д. A(2:3) - часть слова A, размещенная во втором

и третьем разрядах.

Наиболее употребительные операции Ф-языка:

присваивание - A( 0:3 ): = 1000, B( 1:4 ): = A( 5:8 ) и т.д.

инвертирование - A( 0:3 ): = ^ B( 1:4 )

конкатенации - С( 0:6 ): = A( 0:3 ). B( 1:3 )

Пример 1. A( 0:3 ): = 1100 B( 1:4 ): = A( 0:3 ) ( B( 1:4 ): = 1100

2. B( 1:4 ): = 0101 A( 0:3 ): = ^B( 1:4 ) ( A( 0:3 ): = 1010

3. A( 0:3 ): = 1101 B( 1:3 ): = 110 C( 0:6 ): = A( 0:3 ). B( 1:3

) ( C(0:6):=1101110

Запись вида A(2) означает, что здесь рассматривается второй разряд

слова A, т.е. это бит, записанный во втором разряде слова A.

При выполнении операций присваивания необходимо соблюдать равенство

разрядов в словах слева и справа от знака присваивания. Операции сложения,

логического сложения и т.д. в Ф-языке записываются обычным способом через

оператор присваивания:

C(0:n):=A(0:n)+B(0:n)

D(0:n):=A(0:n)vB(0:n) и т.д.

ОПЕРАЦИОННЫЕ ЭЛЕМЕНТЫ

Согласно принципа микропрограммного управления, любая сложная операция

распадается на ряд микроопераций, которые выполняются ОА. Различные

микрооперации выполняются элементарными ОА - так называемыми операционными

элементами (ОЭ), которые являются составными частями основного ОА.

Под операционным элементом понимают устройство, реализующее одну из

следующих функций или их произвольную комбинацию:

1. хранение слова информации С;

2. выполнение некоторых микроопераций, в результате которых вычисляется

новое значение слова С;

3. вычисления логического условия, зависящего от слова С;

Т.о. функция ОЭ определена, если заданы:

4. описание хранимого или вычисляемого слова;

5. описание множества микроопераций, выполняемых этим элементом;

6. описание вычисляемых этим элементом логических условий.

Для построения ОА ОЭ соединяются между собой с помощью цепей передачи

слов информации от выходов одних элементов к входам других.

В зависимости от выполняемых микроопераций ОЭ делятся на

разновидности: шина, регистр, счетчик, сумматор, схема сравнения,

дешифратор, шифратор и т.д.

Шина - это совокупность цепей, предназначенных для передачи слова

информации. Условное обозначение шины представлено на рис.45.

[pic]

Шины, изображенные на рис.45 называются неуправляемыми шинами.

Управляемые шины представлены на рис.46.

[pic]

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

микрооперации: у=0 : B(0:3):=0 , y=1 : B(0:3):=A(0:3)

Т.е. при y=1 осуществляется операция передачи. Разрядность шины может

быть произвольная, но обычно это 8, 12, 16, 24, 32 и т.д.

Регистр - это операционный элемент, служащий для запоминания слов и

обеспечивающий в общем случае выполнение следующих микроопераций:

7. установка регистра в 0 (сброс);

8. прием слова из другого регистра, шины и т.д.;

9. передача слова на другой регистр, шину и т.д.;

10. преобразование кодов хранимых слов в инверсные коды;

11. сдвиг хранимого слова влево или вправо на требуемое число разрядов.

[pic]

Регистр, выполняющий такие микрооперации, называется

многофункциональным. Т.к. регистр предназначен для хранения информации, то

он содержит элементы памяти, в качестве которых используются триггеры.

Количество триггеров определяет разрядность регистра. Будем обозначать

регистр в виде прямоугольника с указанием разрядности (рис.47 ).

Регистр может состоять из отдельных подрегистров, имеющих

самостоятельное значение (рис.48.). На рис.48 представлен регистр,

хранящий число в форме с плавающей запятой. В этом регистре три

подрегистра: для хранения знака Рг(0), характеристики Рг(1:7), мантиссы

Рг(8:31) числа.

Регистр может выполнять ряд микроопераций, например:

[pic]

Регистр, который выполняет микрооперацию у4 (сдвиг вправо) или у5

(сдвиг влево) называются регистром сдвига.

Сумматор - операционный элемент, выполняющий суммирование кодов чисел.

В зависимости от кодов чисел различают сумматоры прямого, обратного,

дополнительного кодов. Кроме того, сумматоры бывают комбинационными и

накапливающими.

Комбинационный сумматор вырабатывает выходные сигналы суммы и

переноса, определяемые комбинацией цифр слагаемых, одновременно поданных на

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

сигналов с входов выходные сигналы также исчезают.

Условное обозначение комбинационного сумматора представлено на рис.50.

[pic]

Накапливающим называется сумматор, который осуществляет сложение слов

A и B при подаче их на сумматор одного за другим. В накапливающем сумматоре

имеется дополнительный регистр для хранения результата.

[pic]

Структура и условное обозначение накапливающего сумматора представлены

на рис. 51.

Счетчик - операционный элемент, который реализует микрооперацию счета.

Микрооперация счета состоит в изменении состояния счетчика (значения

хранимого слова) на 1. Кроме того счетчик может выполнить и такие

микрооперации: установка в 0 и прием произвольного числа.

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

[pic]

[pic]

Счетчик, выполняющий микрооперацию у1 называется суммирующим,

микрооперацию у2 - вычитающим, обе микрооперации - реверсивный.

Дешифратор - операционный элемент, выполняющий функцию преобразования

некоторого n-разрядного двоичного кода в унитарный код «один из N». Если

N=2n - то такой дешифратор называется полным, если N<2n - то частичным.

Таблица истинности простейшего полного дешифратора (n=2) и его условное

обозначение приведены в табл. 25. и на рис. 53.

Промышленность может выпускать дешифраторы с инверсными выходами. Для

такого дешифратора таблица истинности и условное обозначение имеют вид

(табл. 26., рис. 54.)

[pic]

СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ ПО ГРАФ-СХЕМЕ АЛГОРИТМА

Граф-схема алгоритма есть форма представления микропрограммы, которую

должно выполнить операционное устройство (ОУ). При построении операционного

устройства, как состоящего из операционного (ОА) и управляющего (УА)

автоматов, необходимо уметь выделить функции ОА и УА из ГСА. Обычно

микропрограмма представляется в виде содержательной ГСА. В этом случае для

задания функций ОА необходимо перечислить все выполняемые микрооперации и

все проверяемые логические условия данной микропрограммы, а также описать

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

этих данных можно построить ОА методами, которые будут изложены в курсе

«Схемотехника ЭВМ». Для инициализации выполнения той или иной микрооперации

на ОА должны поступать в нужный согласно ГСА момент времени управляющие

сигналы Yi. Обычно при проектировании ОУ принимают определенный способ

кодирования микроопераций (чаще всего кодом, содержащим столько разрядов,

сколько всего различных микроопераций) и для разработки ОА считают, что УА

выдает код микроопераций, которые должны выполниться в данный момент

времени.

Для УА важна последовательность выдачи соответствующих кодов

микроопераций в зависимости от логических условий, вырабатываемых ОА и

анализируемых УА в нужные моменты времени. Если принят способ кодирования

микроопераций, то функции УА задаются кодированной ГСА. Поэтому для

различных содержательных ГСА , имеющих одинаковую кодированную ГСА, ОА

будут различны, но УА будет одним и тем же.

В дальнейшем будем рассматривать синтез только УА и только

кодированной ГСА.

Конечный автомат, интерпретирующий микропрограмму работы дискретного

устройства, называется микропрограммным автоматом. Одну и ту же ГСА можно

интерпретировать как автоматом Мили, так и автоматом Мура.

Абстрактный синтез микропрограммного автомата по ГСА осуществляется в

два этапа:

1. Получение отмеченной ГСА.

2. Построение графа автомата или таблиц переходов и выходов.

СИНТЕЗ АВТОМАТА МИЛИ

На этапе получения отмеченной ГСА входы вершин, следующих за

операторными, отмечают символами a1, a2,.. по следующим правилам:

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

вход конечной вершины;

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

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

различными символами;

4) если вход вершины отмечается, то только одним символом.

Ясно, что для проведения отметок потребуется конечное число символов

а1,...,am. Результатом первого этапа является отмеченная ГСА, которая

служит основой для второго этапа - перехода к графу или таблицам переходов-

выходов. Пример ГСА, отмеченной для автомата Мили, представлен на рис. 55.

[pic]

На втором этапе, из отмеченной ГСА, строят граф автомата или таблицы

переходов-выходов. Для этого полагают, что в автомате будет столько

состояний сколько символов ai понадобилось при отметке ГСА.

На плоскости рисунка отмечаем все состояния автомата ai. Для каждого

из состояний ai определяем по отмеченной ГСА все пути, ведущие в другие

состояния и проходящие обязательно только через одну операторную вершину.

Например, из состояния а1(рис.55.) есть переход в состояние a2 (путь

проходит через операторную вершину y1 y2) и в состояние a4 (путь проходит

через вершину y3 y4). Перехода из a1 в a3 нет, так как на этом пути нет ни

одной операторной вершины. Будем считать, что автомат осуществляет переход,

например, из a1 в a2 при условии x1 = 0 или x1 (см.ГСА, рис.55. ) и

вырабатывает на этом переходе выходные сигналы у1 у2 (то, что записано в

проходимой операторной вершине ГСА, рис.55.). Значение условий х2, х3, х4

на этом переходе не оказывает влияния на автомат.

Исключение составляет только путь, ведущий в конечную вершину, он

может не содержать ни одной операторной вершины (например, переход из а6 в

а1), т.е. не сопровождается выработкой выходных сигналов.

Отмечаем на графе все указанные пути для всех состояний в виде дуг,

которым приписываем условия перехода и выходной сигнал, вырабатываемый на

этом переходе. Получим граф автомата (рис.55. ).

[pic]

На этом графе переходам типа а3 (a4, a5 ( a1 приписывается

условие перехода 1, т.к. эти переходы являются безусловными и

выполняются всегда, когда автомат попадает в состояние а3 (или а5). На

основании отмеченной ГСА или графа автомата можно построить таблицу

переходов-выходов. Для микропрограммных автоматов таблица переходов-

выходов строится в виде списка и различаются прямая и обратная таблицы.

Для данного автомата прямая таблица представлена в табл. 27., обратная -

в табл. 28.

Табл. 27.Прямая таблица переходов- Табл.

28.Обратная таблица перехо-

выходов автомата Мили

дов - выходов автомата Мили

|am |as |X |Y | |am |as |X |Y |

|a1 |a2 |x1 |y1y2 | |a4 |a1 |x2 |y2 |

| |a4 |x1 |y3y4 | |a5 | |1 |y2 |

|a2 |a2 |x3x2 |y1y2 | |a6 | |x4 |- |

| |a5 |x3 |y2y3 | |a1 |a2 |x1 |y1y2 |

| |a6 |x3x2 |y4 | |a2 | |x3x2 |y1y2 |

|a3 |a4 |1 |y3y4 | |a6 | |x4 |y1y2 |

|a4 |a1 |x2 |y2 | |a4 |a3 |x2 |y1y4 |

| |a3 |x2 |y1y4 | |a1 |a4 |x1 |y3y4 |

|a5 |a1 |1 |y2 | |a3 | |1 |y3y4 |

|a6 |a1 |x4 |- | |a2 |a5 |x3 |y2y3 |

| |a2 |x4 |y1y2 | |a2 |a6 |x3x2 |y4 |

В приведенных таблицах am - исходное состояние, aS - состояние

перехода, Х - условие (входной сигнал), обеспечивающий переход из состояния

am в состояние as, Y - выходной сигнал, вырабатываемый автоматом при

переходе из am в aS.

СИНТЕЗ АВТОМАТА МУРА.

Для автомата Мура на этапе получения отмеченной ГСА разметка

производится согласно следующим правилам:

1) символом а1 отмечается начальная и конечная вершины;

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

3) все операторные вершины должны быть отмечены;

Пример ГСА, отмеченной для автомата Мура, представлен на рис. 56.

[pic]

Граф автомата Мура, соответствующий отмеченной ГСА (рис. ),

представлен на рис. . Построение его аналогично построению графа для

автомата Мили.

[pic]

Таблицы переходов-выходов автомата Мура представлены в табл. 29

(прямая) и табл. 30 (обратная). Обычно для автомата Мура в таблице

переходов-выходов дополнительный столбец для выходных сигналов не

используется и выходной сигнал записывается в столбце, где указывается

исходное состояние am или состояния перехода aS.

Табл. 29.Прямая таблица переходов Табл.

30.Обратная таблица переходов

автомата Мура.

автомата Мура.

|am(Y) |as |X | |am |as(Y) |X |

|a1(--) |a2 |x1 | |a6 |a1(-) |x4 |

| |a3 |x1 | |a7 | |1 |

|a2(y1y2) |a2 |x3 x2 | |a1 |a2(y1y2) |x1 |

| |a5 |x3 | |a2 | |x3 x2 |

| |a6 |x3 x2 | |a6 | |x4 |

|a3(y3y4) |a4 |x2 | |a1 |a3(y3y4) |x1 |

| |a7 |x2 | |a4 | |1 |

|a4(y1y4) |a3 |1 | |a3 |a4(y1y4) |x2 |

|a5(y2y3) |a7 |1 | |a2 |a5(y2y3) |x3 |

|a6(y4) |a1 |x4 | |a2 |a6(y4) |x3 x2 |

| |a2 |x4 | |a3 |a7(y2) |x2 |

|a7(y2) |a1 |1 | |a5 | |1 |

Получением графа или таблиц переходов-выходов заканчивается этап

абстрактного синтеза микропрограммного автомата. Как и для конечных

автоматов, на этапе абстрактного синтеза можно выполнить минимизацию

количества внутренних состояний автомата.

СТРУКТУРНЫЙ СИНТЕЗ МИКРОПРОГРАММНЫХ АВТОМАТОВ

Структурный синтез микропрограммных автоматов после получения графа

или таблицы переходов-выходов в принципе аналогичен каноническому методу

синтеза цифровых автоматов, рассмотренному ранее. Однако существуют и

определенные особенности в первую очередь связанные с тем, что для реальных

автоматов количество элементов памяти и входных сигналов может достигать

десяти и более. Функции возбуждения и выходных сигналов трудно поддаются

минимизации да и практически минимизация не дает существенного упрощения

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

практически не используется при синтезе микропрограммных автоматов.

При выполнении структурного синтеза строят так называемые структурные

таблицы переходов и выходов, которые также могут быть как прямыми так и

обратными.

Рассмотрим этапы структурного синтеза на конкретных примерах.

СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МИЛИ

Выполним структурный синтез микропрограммного автомата Мили,

заданного своей таблицей переходов-выходов (табл. 27 или табл. 28). В

качестве примера синтез будем выполнять по прямой таблице (табл. 27).

1. В исходном автомате количество состояний М=6, следовательно, число

элементов памяти

m = ] log 2 M [ = ] log 2 6 [ = 3.

Пусть для синтеза используются JK триггеры.

2. Кодируем внутренние состояния автомата, используя для этого карту Карно

(рис.57.) и по возможности метод соседнего кодирования. Рекомендуется

самостоятельно закодировать состояние с помощью эвристического алгоритма.

[pic]

3. Строим прямую структурную таблицу переходов-выходов автомата Мили (табл.

31). В данной таблице в столбцах k(am) и k(as) указывается код исходного

состояния и состояния перехода соответственно. В столбце функций

возбуждения ФВ указывается те значения функций возбуждения, которые на

данном переходе обязательно равны 1. Остальные (т.е. равные 0 или

принимающие неопределенные значения) не указываются. Это эквивалентно тому,

что всем неопределенным значениям функций возбуждения приписывается

значение 0, что в общем случае не дает минимальной функции, однако в

реальных автоматах минимизация обычно не делается в виду ее

неэффективности. Предлагается самостоятельно построить структурную таблицу

переходов с указанием всех значений функций возбуждения (в том числе и

неопределенных), выполнить минимизацию и сравнить результаты с приведенными

ниже.

Табл. 31. Структурная таблица переходов-выходов автомата Мили.

|Am |K(am)|as |K(as)|X |Y |ФВ |

|a1 |000 |a2 |010 |x1 |y1y2 |J2 |

| | |a4 |001 |x1 |y3y4 |J3 |

|a2 |010 |a2 |010 |x3x2 |y1y2 |- |

| | |a5 |110 |x3 |y2y3 |J1 |

| | |a6 |011 |x3x2 |y4 |J3 |

|a3 |101 |a4 |001 |1 |y3y4 |K1 |

|a4 |001 |a1 |000 |x2 |y2 |K3 |

| | |a3 |101 |x2 |y1y4 |J1 |

|a5 |110 |a1 |000 |1 |y2 |K1K2|

|a6 |011 |a1 |000 |x4 |- |K2K3|

| | |a2 |010 |x4 |y1y2 |K3 |

4. Для получения функций возбуждения поступаем следующим образом.

Выражение для каждой функции получается в виде логической суммы

произведений вида aiX, где ai - исходное состояние, X-условие перехода. Для

упрощения полученных выражений выполняем все возможные операции склеивания

и поглощения:

J1 = a2x3 + a4x2 K1 = a3 + a5

J2 = a1x1 K2 = a5 + a6x4

J3 = a1x1 + a2x3x2 K3 = a4x2 + a6x4 + a6x4 = a6 + a4x2

5. Для получения функций выходов поступаем аналогично:

y1 = a1x1 + a2x3x2 + a4x2 + a6x4

y2 = a1x1 + a2x3x2 + a2x3 + a4x2 + a5 + a6x4

y3 = a2x3 + a3 + a1x1

y4 = a1x1 + a2x3x2 + a3 + a4x2

6. Для построения функциональной схемы автомата по полученным выражениям

необходимо либо заменить ai его значениями через Q1Q2Q3 либо получить

сигнал, соответствующий ai. Обычно используют второй способ и для получения

сигнала ai применяют так называемый дешифратор состояний, на вход которого

поступают сигналы с выходов элементов памяти Q1Q2Q3. Кроме того, при

построении схемы стараются выделить общие части, встречающиеся в функциях

возбуждения или выходных сигналах. В этом случае окончательная система

уравнений, по которым строится схема, будет иметь вид:

A = a2x3x2+J2 ; J1 = D + B ; y1 = A + B + E ;

B = a4x2 ; K1 = a3 + a5; y2 = A + D + C + a5

+ E ;

C = a4x2 ; J2 = a1x1 ; y3 = D + F + a3

;

D = a2x3 ; K2 = a5 + a6x4 ; y4 = a3 + B + J3;

E = a1x1 ; K3 = a6 + C ;

F = a1x1 J3 = F+a2x3x2

Функциональная схема автомата, построенная на основании полученных

уравнений, представлена на рис. 58.

[pic]

СТРУКТУРНЫЙ СИНТЕЗ АВТОМАТА МУРА

Выполним структурный синтез микропрограммного автомата Мура, заданного

своей таблицей переходов-выходов (табл.29 или табл. 30). В качестве

примера синтез будем выполнять по обратной таблице (табл. 32).

1. В исходном автомате количество состояний М=7, следовательно число

элементов памяти

m = ] log 2 M [ = ] log 2 7 [ = 3

Пусть для синтеза используется D-триггеры.

2. Кодируем внутренние состояния автомата, используя алгоритм кодирования

для D-триггеров. Количество переходов в данное состояние легко определяется

из обратной таблицы: a1 ~ 2, a2 ~ 3, a3 ~ 2, a4 ~ 1, a5 ~ 1, a6 ~ 1, a7 ~

2.

Поэтому коды состояний следующие:

a2-000, a1-001, a3-010, a7-100, a4-011, a5-101, a6-110.

3. Строим структурную таблицу переходов - выходов автомата Мура.

Табл. 32. Структурная таблица переходов - выходов автомата Мура.

|am |K(am) |as(Y) |K(as) |X |ФВ |

|a6 |110 |a1(-) |001 |x4 |D3 |

|a7 |100 | | |1 |D3 |

|a1 |001 |a2(y1y|000 |x1 |- |

| | |2) | | | |

|a2 |000 | | |x3x2 | |

|a6 |110 | | |x4 | |

|a1 |001 |a3(y3y|010 |x1 |D2 |

| | |4) | | | |

|a4 |011 | | |1 |D2 |

|a3 |010 |a4(y1y|011 |x2 |D2D3 |

| | |4) | | | |

|a2 |000 |a5(y2y|101 |x3 |D1D3 |

| | |3) | | | |

|a2 |000 |a6(y4)|110 |x3x2 |D1D2 |

|a3 |010 |a7(y2)|100 |x2 |D1 |

|a5 |101 | | |1 |D1 |

Построение таблицы выполняется аналогично автомату Мили.

4. Выражения для функций возбуждения получаются в виде суммы произведений

aiх, где ai-исходное состояние, х - условие перехода.

D1 = a2x3 + a2x3x2 + a3x2 + a5

D2 = a1x1 + a4 + a3x2 + a2x3x2

D3 = a6x4 + a7 + a3x2 + a2x3

или

A = a3x2

B = a2x3x2

D1 = a2x3 + B + a3x2 + a5

D2 = a1x1 + a4 + A + B

D3 = a6x4 + a7 + A + a2x3

5. Выражения для выходных сигналов автомата Мура получаем, исходя из того,

что эти сигналы определяются только внутренним состоянием автомата.

y1 = a2 + a4

y2 = a2 + a5 + a7

y3 = a3 + a5

y4 = a3 + a4 + a6

6. Для построения функциональной схемы автомата как и в предыдущем случае

используем дешифратор состояний. Схема представлена на рис. 61 .

ЗАМЕЧАНИЯ.

1. При синтезе микропрограммных автоматов изложенным методом получаемые

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

некоторых случаях могут быть упрощены. В частности, можно доопределить

функции возбуждения на некоторых наборах единичным значением (а не нулевым,

как было ранее) и выполнить все операции склеивания. Например, в

синтезированном ранее автомате Мили таким образом можно получить значение

k1=1. Рекомендуется в этом убедиться самостоятельно.

Для упрощения схем автоматов можно также предварительно упростить ГСА,

уменьшив количество вершин или узлов методами, изложенными в / /.

Автомат Мили в течении такта сохраняет свое состояние и лишь в конце его

переходит в новое. Пока автомат находится в данном состоянии Ai он

вырабатывает выходные сигналы y=f(Ai,x), где х - сигналы, подаваемые на

вход автомата в течение данного такта. В связи с этим автомат Мили может

интерпретировать микропрограмму корректно только в том случае, если для

любого перехода выполняется условие независимости логических условий от

результатов выполнения микроопераций на данном переходе.

Условие независимости нарушается, если на некотором переходе из аm в

аs под действием сигнала х с выработкой уi наблюдается функциональная

зависимость х = f(уi). В таком случае выполнение микрооперации уi может

привести к изменению значения х и автомат, находясь в состоянии аm, и,

реагируя на набор входных сигналов, сформирует набор выходных сигналов, не

соответствующий микропрограмме. Чтобы избежать этого, можно использовать

следующие способы:

1) запомнить значение сигналов х на промежуток времени, равный

длительности такта;

2) ввести в автомат дополнительные состояния;

3) реализовать автомат по схеме Мура.

Запоминание значений сигналов х в течение такта осуществляется

операционным автоматом с помощью дополнительных элементов памяти –

триггеров. Интерпретация микропрограммы автоматом Мура рассматривалась

ранее. Введение дополнительных состояний иллюстрируется рис. 59 .

В исходном автомате (рис. 59.а) есть переходы из аi в аj под действием

сигналов х и х с выработкой y1 и y2 соответственно и имеет место х = f(y1,

y2). Действительно, введение вспомогательных состояний аk и аl позволяет

устранить возможную ошибку в выдаче выходных сигналов. На переходах аi аk

или аiаl выходные сигналы не вырабатываются. Переходы аi аk или аiаl

являются безусловными с выработкой y1 или y2 соответственно. В таком случае

изменение значения х, в результате выполнения микроопераций y1 или y2, не

повлияет на выходной сигнал, вырабатываемый автоматом, так как на переходах

аi аk или аiаl выходной сигнал уже не зависит от х.

[pic]

Синтез управляющего автомата Мура

на базе регистра сдвига.

Кроме рассмотренного ранее канонического метода, существуют и другие

методы синтеза управляющих автоматов, среди которых наиболее широко

используется синтез на базе регистра сдвига. Этот метод позволяет при

построении схемы отказаться от дешифратора, т.к. состояния кодируются

унитарным кодом. В автомате количество элементов памяти выбирается равным

количеству внутренних состояний. В каждый момент времени только один

триггер находится в 1, остальные в 0. Обычно при синтезе на базе регистра

сдвига используются D-триггеры. Очень эффективен данный метод для так

называемых линейных микропрограмм, т.е. микропрограмм без ветвлений

(отсутствует логические условия). Рассмотрим пример синтеза управляющего

автомата Мура данным методом. Пусть закодированная ГСА микропрограммы имеет

вид рис. 60. Разметив данную ГСА для автомата Мура, получаем семь

состояний. Следовательно число триггеров m=7. Выполним синтез с

использованием D-триггеров. Закодируем состояния унитарным кодом:

a1=1000000, a2=0100000,..., a7=0000001. Обратная структурная таблица

переходов-выходов для данного автомата представлена в таблице.

|am|Kam |as(y) |Kas |x |ФВ |

|а6|0000010|а1(-) |1000000|1 |D1 |

|а7|0000001| | |1 |D1 |

|а1|1000000|а2(y1 |0100000|1 |D2 |

| | |y2) | | | |

|а2|0100000|а3( y2)|0010000|1 |D3 |

|а3|0010000|а4(y3 |0001000|1 |D4 |

| | |y4) | | | |

|а4|0001000|а5( y2)|0000100|[pi|D5 |

| | | | |c] | |

|а5|0000100|а6(y3) |0000010|1 |D6 |

|а4|0001000|а7(y4) |0000001|x |D7 |

[pic]

На основании структурной таблицы записываем выражения для выходных

сигналов yi и функций Di :

D1 = a6 + a7 y1 = a2

D2 = a1 y2 = a2 + a3 + a5

D3 = a2 y3 = a4 + a6

D4 = a3 y4 = a4 + a7

D5 = a4[pic]

D6 = a5

D7 = a4(x

Т.к. состояния автомата закодированы унитарным кодом, то можно

отождествить каждое состояние с выходом соответствующего триггера, т.е.

принять аi=Qi. Для принятого способа кодирования переход из одного

состояния в другое как бы сопровождается сдвигом кода, за-

писанного в семиразрядном регистре. Этим и объясняется название метода.

Функциональная схема автомата Мура, построенная по полученным уравнениям,

приведена на рисунке 62. При определенных навыках синтез автомата Мура на

базе регистра сдвига выполняется непосредственно по отмеченной ГСА без

построения структурной таблицы переходов-выходов.

[pic]

[pic]

-----------------------

(1)

Табл.1. Таблица истинности полного одноразрядного двоичного сумматора.

(2)

Таблица 2. Таблица истинности сумматора.

(3)

1

X

&

X1

X2

&

X1

X2

1

X1

X2

1

X1

X2

=1

X1

X2

&

X1

X2

X3

[pic]

|№уровня |№элемента |уравнение |

|1 |1 |e1 = X1 |

| |2 |[pic]X2 |

| | |e2 = [pic] |

|2 |3 |e3 = [pic] |

|3 |4 |Y = e4 = e3 +|

| | |X5 |

| |1-ый такт|2-ой такт|3-ий такт|

|Y= e6 = e4 + e5 +|* |* |* |

|X5 |* |* |- |

|e5 = e3 [pic]X7 |- |* |- |

|[pic] |* |- |- |

|e3=X5 [pic]X6 |* |- |- |

|e2=X5 [pic]X4 |* |- |- |

|e1=X1 [pic]X2 | | | |

|Входное слово|Zi1 |Zi2 |Zi3 |Z |

|Последователь|am |ai2 = ( (am, |ai3 = ( (ai2,|ai4 = ((ai3,|

|ность | |Zi1 ) |Zi2 ) |Zi3 ) |

|cостояний | | | | |

|Выходное |wi1 = ( (am, |wi2 = ( (ai2,|wi3 = ( (ai3,|wi4 = ( |

|слово |Zi1) |Zi2) |Zi3) |(ai4) |

| |w1 |w2 |w3 |w4 |

| |a1 |a2 |a3 |a4 |

|z1 |a2 |a3 |a4 |a4 |

|z1 |a4 |a1 |a1 |a1 |

Cледовательно, структурный автомат с двумя входами x1 и x2 и двумя

выходами y1 и y2 может быть представлен в виде:

Таблица переходов D-триггера.

Рис. 24.

Таблица функции входов D-триггера.

Таблица переходов T-триггера.

Таблица функции входов T-триггера.

Таблица переходов RS-триггера.

RS-триггер

Т

T

C

Q

Рис. 27.

Таблица функций входов RS-триггера.

в)

Табл 21. а), б), в).

Т

J

K

Q

JK-триггер

Таблица переходов JK-триггера.

Рис. 28.

Табл. 22 а), б).

Таблица функций выходов JK-триггера.

x1x2

Q1Q2

x1x2

Q1Q2

Рис. 30 .

Кодированная таблица переходов.

Рис. 31 .

Кодированная таблица выходов

x1x2

Q1Q2

x1x2

Q1Q2

Рис. 32 .

Карта Карно для у1.

Рис.33 .

Карта Карно для у2.

x1x2

Q1Q2

x1x2

Q1Q2

Рис. 34 .

Карта Карно для D1.

Рис. 35.

Карта Карно для D2.

Таблица функции входов T-триггера.

Таблица функций возбуждения.

x1x2

Q1Q2

Карта Карно для Т1.

[pic]

Карта Карно для Т2.

[pic]

x1x2

Q1Q2

x1x2

Q1Q2

Таблица функции входов RS-триггера.

Таблица функций возбуждения.

x1x2

Q1Q2

x1x2

Q1Q2

x1x2

Q1Q2

x1x2

Q1Q2

x1x2

Q1Q2

Таблица функции входов JK-триггера.

Таблица функций возбуждения.

x1x2

Q1Q2

Карта Карно для J1.

Карта Карно для K1.

x1x2

Q1Q2

x1x2

Q1Q2

Карта Карно для J2.

Карта Карно для K2.

x1x2

Q1Q2

x1x2

Q1Q2