Полезная книги (04Глава 3)

Посмотреть архив целиком

Глава 3. Структурный и абстрактный синтез устройств ВМ.


Структурный синтез операционных устройств ВМ. Операционное устройство ВМ можно представить состоящим как бы из двух частей — комбинационной и памяти. На входы комбинационной части поступают сигналы с выходов элементов памяти (триггеров) Q1, …, Qm, а также сигналы, приходящие по шинам управления x1, …, xm. Назначение шин управления состоит в том, чтобы из всех микроопераций, выполняемых устройством, выбрать одну, требуемую в данный момент. Сигналы с выходов комбинационных схем подаются на входы триггеров. Функция возбуждения входного i-го триггера записывается в следующем виде:

.

Значения всех переменных в этом выражении определены для одного и того же момента времени t, поэтому функции возбуждения триггеров являются переключательными функциями, которым соответствуют комбинационные схемы, формирующие входные сигналы для триггеров. Следовательно, если известен тип триггера, то задача структурного синтеза устройства заключается в составлении функции возбуждения каждого триггера, функции кодирования выходов заданного устройства и минимизации. При выполнении структурного синтеза используются матрицы переходов триггеров (табл. 3.1), где для каждого типа триггера указаны значения входных сигналов, определяющие переход триггера из одного состояния в другое. Если значение входного сигнала не влияет на данный переход, то в матрице указывается неопределенный коэффициент b. Для триггера DV–типа дополнительно указан второй коэффициент по управляющему входу.

Таблица 3.1

Переходы

Тип триггера

0 – 0

0

b

0

b

b a

b

1

b

0

0 – 1

1

b

1

1

1

1

0

0

1

1 – 0

b

1

0

0

1

0

1

1

0

1 – 1

b

0

1

b

b a

1

b

0

b


Алгоритм структурного синтеза

  1. Определяется необходимое число независимых шин управления. Число управляющих шин зависит от числа микроопераций, выполняемых устройством, и находится из соотношения , где L — число микроопераций.

  2. По числу различных состояний N устройства определяется необходимое количество триггеров: m, каждое состояние устройства кодируется m-разрядным двоичным кодом, i-й разряд соответствует выходному сигналу i-го триггера.

  3. Кодируется внутреннее состояние синтезируемого автомата.

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

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

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

  7. Согласно функциям возбуждения и в соответствии с выбранной (заданной) элементной базой строится структурная схема.

Синтез микропрограммных автоматов. Управляющий автомат, реализующий микропрограмму работы дискретного устройства, принято называть микропрограммным автоматом. Его синтез состоит из следующих этапов:

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

  2. Построения частных микропрограмм с учетом отметок граф-схемы алгоритма символами.

  3. Получение отмеченных частных микропрограмм.

  4. Построение графов частных управляющих автоматов Мили или Мура.

  5. Построения графа многофункционального автомата Мили или автомата Мура путем объединения состояний автоматов и введения настроечного алфавита.

  6. Структурный синтез.

Далее составляется таблица переходов микропрограммного автомата. Для автомата Мили таблица содержит четыре столбца: am и as — исходное состояние и состояние перехода; х(am, as)конъюнкция переменных из множества х, принимающая значение 1 на данном переходе; у(am, as) — подмножество выходных переменных, принимающих значение 1 на данном переходе. Каждая строка таблицы переходов соответствует одному пути перехода, т.е. дуге графа автомата с одним входным и одним выходным сигналами.

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

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

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

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

Алгоритм абстрактного синтеза заключается в следующем. Фиксируется начальное состояние a0 и для входного слова li, состоящего из r букв, назначается r внутренних состояний автомата ai1, ai2, …, air. Переходы в автомате назначаются так, что первая буква слова li переводит автомат из состояния a0 в состояние ai1, вторая буква — из состояния ai1 в состояние ai2 и т.д. Аналогичные последовательности внутренних состояний назначаются для всех остальных слов. Затем все конечные состояния air, в которые автомат попадает после подачи слов, входящих в событие Sj, отмечаются выходным сигналом уi.

Чтобы система переходов автомата была определенной для всех слов, имеющих одинаковые начальные отрезки, следует назначать одну и ту же последовательность состояний. В состояниях, не отмеченных буквами выходного алфавита у1, …, уk, а также в начальном состоянии автомат должен выдавать пустую букву, соответствующую событию Sk+1. Для запрещенного события последовательность состояний можно не назначать.

При абстрактном синтезе целесообразно использовать следующие соотношения:

Алгоритм минимизации числа внутренних состояний автомата включает следующие действия:

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

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

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

  4. Пользуясь таблицей переходов автомата, снова отмечаются каждые состояния последовательности букв. Объединение состояний в группы продолжается до тех пор, пока новые группы состояний появляться не будут.

рис. 3.1

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

Запоминающий элемент имеет два выхода Q и , разрешенные сигналы на которых всегда противоположны, и два входа s (set – установка) и r (reset – сброс). Переключающий сигнал по входу s устанавливает запоминающий элемент в состояние «1», а по входу rв состояние «0». В общем случае запоминающий элемент может иметь несколько установочных входов.

Схема управления преобразует информацию, поступающую на входы А1…Аn, в сигналы, которые подаются на установочные входы запоминающего элемента. Как правило, триггеры имеют еще один вход — вход для синхронизирующих сигналов С. Сигналы, поступающие на этот вход, определяют момент приема триггером входной информации. Поскольку прием информации синхронизирован с моментом подачи сигнала на вход С, то такой триггер назван синхронизируемым, или синхронным.

Рассматриваемые ниже триггеры обладают следующими свойствами. На входы А1…Аn поступают сигналы, несущие логическую входную информацию, на вход С — сигнал синхронизации. Входная информация принимается на хранение триггером с поступлением сигнала синхронизации или изменением его фронта. Такой режим соответствует синхронной работе триггера. Но синхронный триггер может применяться и при асинхронной работе. При этом на синхронизирующий вход триггера сигналы могут поступать от схем, непосредственно не связанных с синхронизирующими сигналами.

Наряду с хранением информации триггер может выполнять различные логические функции. Логические свойства триггера можно описать с помощью таблицы переходов (табл. 3.2), которая Q(t+1) определяет зависимость выходных сигналов триггера от значений входных сигналов Ai(t) и состояния триггера Q(t) в предыдущий момент времени. Для каждого типа триггера, задаваемого таблицей переходов, вводят специальное обозначение входов, отличное от общего обозначения А.


Таблица 3.2а. Таблица переходов триггера D

Вход (время t)

Выход (время t+1)

0

0

1

1


Таблица 3.2б. Таблица переходов триггеров J-K, R -S,

Входы (время t)

Выход (время t+1)

0

0

Q(t)

Q(t)

-

0

1

1

1

0

1

0

0

0

1

1

1

-

R, , K

S, , J

J-K

R-S


Рассмотрим наиболее часто применяемые типы триггеров.

D – триггер имеет один логический вход D (delay – задержка), состояние которого с каждым синхронизирующим сигналом передается на выход, т.е. выходные сигналы представляют собой задержанные входные. Таким образом, D – триггер — элемент задержки входных сигналов на один такт. Характеристическое уравнение триггера Q(t+1)=D(t).

J-K – триггер имеет два логических входа: j и k. Сигнал по входу j(j=1) устанавливает триггер в единичное состояние, а по входу k(k=1) в нулевое состояние. Если j=k=1, то триггер изменяет свое состояние на противоположное; при одновременной подаче на входы сигналов j=k=0 триггер не изменяет своего состояния. Характеристическое уравнение триггера .

R-S – триггер имеет два логических входа: R и S. Одновременная подача на оба входа триггера сигналов, соответствующих единице, запрещена. Если на оба входа поданы сигналы, соответствующие нулю, то триггер на изменяет своего состояния. Характеристическое уравнение триггера .

Обычно триггер, управляемый по синхронному входу, кроме информационных входов А имеет, как правило, асинхронные входы предварительной установки триггера в состояние «0» или «1». Сигналы, поступающие на эти входы, пользуются приоритетом, т.е. независимо от состояния других входов триггера они сразу (по переднему фронту) устанавливают триггер в определенное состояние. Буквой обозначают асинхронный вход для установки триггера в состояние «1», а буквой — для установки триггера в состояние «0». Синхронный триггер имеет обычно инверсные установочные входы и реализует функцию, приведенную в таблице переходов (см. табл. 3.2, б). Синхронные триггеры с асинхронными и установочными входами получили название универсальных триггеров соответствующего типа.

Синтез триггерных устройств. Универсальные триггеры классифицируются по способу их построения на два основных типа: основной — вспомогательный (MS) со срабатыванием по заднему фронту сигнала синхронизации и основной — коммутирующий (М – К) со срабатыванием по переднему фронту сигнала синхронизации. Исходными данными при разработке триггера служат заданные описания его логического функционирования и требования к основным электрическим параметрам. Общая методика синтеза триггерных устройств следующая:

  1. Составление таблицы переходов. Функционирование триггера может быть задано в различной форме: словесным описанием, в виде временных диаграмм, таблицами состояний и т.п. Входной алфавит определяется типом проектируемого триггера, а выходной алфавит и функции выходов выбираются двоичные. При структурном проектировании в качестве исходной информации о функционировании триггера используют таблицы переходов.

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

  3. Минимизация полученных функция возбуждения и выходов.

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

  5. Составление электрической схемы триггера.

Синтез MS-триггера. При синтезе MS-триггеров с некоторыми ограничениями можно применить общую теорию конечных автоматов. Входной алфавит определяется типом проектируемого триггера, а выходной алфавит и функции выходов — двоичные. Для такого триггера закодированные внутренние состояния (Si) автомата приведены в табл. 3.3, 3.4.

Таблица 3.3.

Si

M

S

S0

0

0

S1

0

1

S2

1

0

S3

1

1


Таблица 3.4.

Pi

C

V

K

P0

0

0

0

P1

0

0

1

P2

0

1

0

P3

0

1

1

P4

1

0

0

P5

1

0

1

P6

1

1

0

P7

1

1

1






Таблица 3.5.

Pi

Si

S0

S1

S2

S3

P0

S0

S0

S3

S3

P1

S0

S0

S3

S3

P2

S0

S0

S3

S3

P3

S0

S0

S3

S3

P4

S0

S3

P5

S0

S1

S1

P6

S2

S2

S3

P7

S2

S1

Таблицы переходов и синтез двухступенчатого триггера рассмотрим на примере синхронного J-K – триггера, собранного на базе бистабильных ячеек и логических схем И — НЕ. Закодированные слова, подаваемые на входы триггера, приведены в табл. 3.6. С помощью таблицы кодирования внутренних состояний и входных слов составляется таблица переходов синхронного триггера. При отсутствии синхросигнала (по его заднему фронту) происходит перезапись состояния первой ступени М-триггера во вторую ступень S-триггера. Если на вход С подается сигнал синхронизации, то перезапись по переднему фронту из М в S запрещается. Таким образом, входные слова Р0…Р3 оказывают на автомат одинаковое воздействие.

Прочерком в таблице переходов (табл. 3.5) обозначены избыточные состояния. Так, если автомат находится в состоянии S1 или S2, то слово Р4 не может быть подано на вход, потому что не произошла перезапись из М в S. Длительность синхросигнала должна быть достаточной для того, чтобы произошла перепись информации из М в S, по той же причине на вход не попадаются слова: Р5, если автомат находится в состоянии S2; Р6, если автомат находится в состоянии S1; Р7, если автомат находится в состоянии S1 или S2.

Таблица 3.6.


Выходные сигналы

Функции возбуждения

C

J

K

Q1(t)

Q2(t)

Q1(t+1)

Q2(t+1)

0

x

x

0

0

0

0

b

1

b

1




0

1

0

0

b

1

0

1




1

0

1

1

1

b

1

0




1

1

1

1

1

b

1

b

1

0

0

0

0

0

0

b

1

b

1

1

0

0

0

1

1

0

0

1

0

1

0

0

1

1

1

1

1

b

1

b

1

0

1

0

0

0

0

b

1

b

1

1

0

1

0

1

0

1

b

1

1

b

1

0

1

1

0

1

0

1

1

1

0

1

0

1

1

b

1

1

0

0

0

1

0

1

0

b

1

1

1

0

0

1

1

1

0

1

0

1

0

1

b

b

1

1

1

0

1

1

1

1

1

b

1

b

1

1

1

0

0

1

0

1

0

b

1

1

1

1

0

1

1

1

1

1

0

1

1

1

1

1

0

1

0

1

1

b


Однако допустима подача входного слова Р5, если автомат находится в состоянии S1, и входного слова Р6, когда автомат находится в состоянии S2, так как в этом случае М находится в нулевом состоянии.

По таблице переходов составляется кодированная таблица переходов и функций возбуждения J-K – триггера (таблица 3.6), по которой находятся функции возбуждения по каждому входу триггеров, при этом используются любые методы минимизации.

Функция возбуждения

; ; ;

или в базисе И—НЕ