Лекция 12.

Раздел 7. Синтез цифровых автоматов на жесткой логике

Тема 7.1. Структурный синтез МПА на жесткой логике. Синтез МПА автоматов Мура

На жесткой логике. Вопросы оптимизации МПА

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

Элементная база автоматов на жесткой логике состоит из простейших логических элементов: конъюнкторов (элементы «И»), дизъюнкторов (элементы «ИЛИ»), инверторов (элементы «НЕ»), их комбинаций (элементы «И-НЕ», «ИЛИ-НЕ», «И-ИЛИ-НЕ» и т.п.), а также включает в себя и более сложные элементы – дешифраторы (DC), мультиплексоры (MS), элементы памяти (триггера).

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

Символ «Ø» обозначает инверсию, «&» – конъюнкцию, «Ú» – дизъюнкцию. Часто вместо символа «&» используют «*», а в случае однобуквенных переменных – вообще его опускают, например функции, приведенные на рисунке, можно записать так: y = a b; y = Ø (a b Ú c d Ú e).

Рис. 3.5

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

y₁ = x₂ Ø x₁ x₀ Ú Ø x₂ x₁ x₀ Ú Ø x₂ Ø x₁ Ø x₀ ;

y₂ = x₂ Ø x₁ x₀ Ú Ø x₂ x₀ Ú x₂ Ø x₀ ;

y₃ = x₂ Ø x₀ Ú Ø x₂ x₀ Ú Ø x₁.

В приведенном примере в функциях y₁ , y₂ , y₃ встречаются одинаковые конъюнкции, которые обозначим через вспомогательные переменные Z _i и выразим через x _i:

Z₁ = x₂ Ø x₁ x₀; Z₂ = Ø x₂ x₁ x₀; Z₃ = Ø x₂ Ø x₁ Ø x₀ ;

Z₄ = Ø x₂ x₀; Z₅ = x₂ Ø x₀.

Выразим функции y₁ , y₂ , y₃ через дизъюнкцию Z _i :

y₁ = Z₁Ú Z₂ Ú Z₃; y₂ = Z₁Ú Z₄ Ú Z₅; y₃ = Z₅Ú Z₄ Ú Ø x₁ .

Функциональные схемы строятся по следующим правилам.

1. Входы схемы (переменные x _i) – с левой стороны схемы, выходы (переменные y _i) – с правой стороны.

2. Входы схемы (переменные x _i), значения которых используются в функциях с инверсиями, соединяются с входами инверторов, на выходах которых формируются значения Ø x _i.

3. Схемы, вычисляющие значения Z _i , строятся на конъюнкторах, на входы которых подаются соответствующие пере­менные x _i или Ø x _i.

4. Схемы, вычисляющие значения y _i , строятся на дизъюнкторах, на входы которых подаются соот­ветствующие переменные x_i ,Ø x_i или Z _i .

Рис. 3.6

5. Чтобы схема была легкочитаема, при ее изображении исполь­зуют «шины». Шина изображается более толстой линией на схеме, в которую вхо­дят и из которой вы­ходят тонкие линии, отображающие связи между элементами. Для идентификации этих связей непосред­ственно у шины ставятся либо обозначения соответствующих переменных, либо номера этих связей (первое предпочтительней). На рис. 3.6 приведена функциональная схема, реализующая функции y₁, y₂, y₃ .

Дешифратор (DC) преобразует позиционный двоичный код (двоичное число) в унитарный. Унитарный код содержит «1» только в одном разряде. Входы дешифратора (в отличие от входов простейших логических элементов) характеризуются своим весом (как разряды двоичного числа): младший разряд имеет вес 1, следующий разряд – вес 2, n-разряд имеет вес 2 ^n-1. Веса разрядов указываются на входах дешифратора. Полный дешифратор имеет 2 ⁿ выходов, имеющих нумерацию от 0 до 2 ⁿ –1. Таким образом, дешифратор с двумя входами имеет 4 выхода, с тремя входами – 8 выходов и т.д. На рис. 3.7 приведено изображение дешифратора с двумя входами x₁ x₀ .

Рис. 3.7

Значения x₁ x_{0 –} двоичное число, указывающее номер выхода дешифратора, на котором будет сформирован сигнал «1». Функции y_i, на выходе дешифратора имеют вид

y₀ = Ø x₁ Ø x₀ ; y₂ = x₁ Ø x₀ ;

y₁ = Ø x₁ x₀ ; y₃ = x₁ x₀ .

Функцию дешифратора можно пояснить также следующей таблицей истинности (табл. 3.3).

Таблица 3.3

Многие дешифраторы имеют еще один дополнительный вход – «разрешение работы дешифратора». На рис. 3.8 приведен пример такого дешифратора, который называется дешифратор – демультиплексор.

Рис. 3.8

Если на вход V подается «0», то на всех выходах дешифратора – нули; если на вход V подается «1», то дешифратор работает в соответствии с приведенной таблицей истинности, а функции y_i, на выходе дешифратора имеют вид

y₀ = S (Ø x₁ Ø x₀ ); y₂ = S (x₁ Ø x₀ );

y₁ = S (Ø x₁ x₀ ); y₃ = S (x₁ x₀ ).

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

Рис. 3.9

У этого мультиплексора один управляющий вход (Х) и два ин­формационных (a и b). Если на управляющий вход Х подать «0», то на вы­ходе MS значение y = a, если на Х подать «1», то значение y = b. Другими словами, приведенный на рисунке MS – это переключатель на два по­ложения, которым выбирается один из двух источников информации (a и b) для приемника У. Функцию MS можно описать выражением

y = Ø х a Ú х b.

Количество управляющих входов у MS может быть 2, 3 и более. В этом случае MS – это переключатель не на два, а на 2 ⁿ положений (где n – количество управляющих входов), позволяющий выбирать один из 2 ⁿ информационных входов. Номер этого информационного входа задается двоичным числом, подаваемым на управляющие входы: х_n-1 ...х₁ х₀. На рис. 3.10 приведен пример MS с четырьмя информационными входами (a, b, c, d) и двумя управляющими (x₁x₀).

Рис. 3.10

Функцию MS такого можно описать выражением

y = a (Ø x₁ Ø x₀ ) Ú b (x₁ Ø x₀ ) Ú c (Ø x₁ x₀ ) Ú d (x₁ x₀ ).

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

Простейшим элементом памяти является статический асинхронный RS-триггер. RS-триггер – это элемент, имеющий два устойчивых состояния, которые обычно обозначают как «0» и «1» (рис. 3.11).

Рис. 3.11

Для установки RS-триггера в одно из устойчивых состояний «0» или «1» у него имеется два входа: R – для установки в состояние «0» и S – для установки в состояние «1». Выходы RS-триггера обычно обозначаются как Q (прямой выход) и ØQ (инверсный выход). Значение на выходе Q («0» или «1») обычно отождествляют с состоянием триггера «0» или «1». Если через Q_t обозначить значение на выходе Q в момент времени t, а через Q_{t+1 –} обозначить значение на выходе Q в момент времени t+1, то поведение RS-триггера можно описать следующей таблицей (табл. 3.4).

Из таблицы видно, что при R=0 и S=1 происходит установка триггера в состояние «1» (Q_t+1 = 1), при R=1 и S=0 происходит установка триггера в состояние «0» (Q_t+1 = 0). Эти установки происходят независимо от предыдущего состояния триггера Q_t. При R=0 и S=0 триггер сохраняет свое состояние, а комбинация R=1 и S=1 является недопустимой, так как одновременно установить триггер в состояния «0» и «1» невозможно. На рис. 3.11 приведено изображение статического асинхронного RS-триггера.

Таблица 3.4

Недостатком асинхронного RS-триггера является то, что изменение его состояния возможно в произвольный момент времени сразу же после изменения сигналов на его входах R и S, поэтому асинхронный RS-триггер часто используют как элемент памяти для построения синхронных триггеров. В синхронных триггерах изменение состояния возможно только в момент подачи на специальный вход «С» импульса синхронизации. Существуют триггеры, синхронизируемые импульсом С и фронтом импульса С. Фронтом импульса синхронизации называют переход значения С из «0» в «1» (положительный фронт) или из «1» в «0» (отрицательный фронт). Триггеры, синхронизируемые фронтом импульса С, нашли наибольшее применение в цифровых устройствах.

На рис. 3.12 приведено изо­браже­ние двух RS-триггеров, синхро­низируемых фронтом им­пульса синхронизации С. Наклон­ная черта на входе С показывает, по какому фронту импульса С – по­ложительному (/) или отрицательному (\) – происходит переход триг­гера из одного состояния в другое.

Рис. 3.12

Кроме RS-триггеров широкое применение в цифровых устройствах нашли D-триггеры и JK-триггеры (также синхронизируемые фронтом импульса С).

D-триггер, в отличие от RS-триггера, имеет всего один информационный вход – D. Синхронный D-триггер изменяет свое состояние также в момент поступления на его вход «С» импульса синхронизации С. Новое состояние Q_t+1 не зависит от предыдущего Q_t , а зависит только от значения на входе D в момент поступления импульса С на вход С триггера. JK-триггер называется универсальным, так как на его основе можно реализовать функции других триггеров. Закон его функционирования можно представить в виде табл. 3.5.

На рис. 3.13 приведены изо­бражения D-триггера, син­хронизируемого положитель­ным фронтом импульса С, и JK-триггера, синхронизи­руемого отрицательным фронтом импульса С.

Рис. 3.13

Автоматы с жесткой логикой обычно строятся или как автоматы Мура, или как автоматы Мили. Поскольку функционирование и тех, и других зависит не только от входных сигналов (логических условий X_i), но и от текущего состояния автомата, необходимым элементом УА является память состояний. В качестве элементов памяти обычно используются триггеры различных типов: RS-, D-, JK-, T-триггеры, синхронизируемые фронтом (положительным или отрицательным) импульса синхронизации С. По фронту импульса С автомат переходит из одного состояния в другое. Выходные сигналы автомата – микрокоманды – также вырабатываются синхронно с импульсом С.

Таблица 3.5

Различие автоматов Мура и Мили следующее: в автомате Мура вырабатываемая автоматом микрокоманда Y_i зависит только от текущего состояния автомата, а в автомате Мили – от текущего состояния и значений логических условий на входе автомата.

Синтез автомата Мура по ГСА. Простейшая реализация

Разметка состояний автомата Мура по ГСА

Каждой операторной вершине ГСА автомата Мура соответствует определенное состояние – ai . Начальное состояние автомата соответствует началу ГСА, а точнее – входу в первую вершину ГСА. Первая вершина ГСА обычно соответствует логическому условию «Пуск», поэтому начальное состояние можно отметить на входе этой вершины. Поскольку этому состоянию не соответствует никакая операторная вершина, то и автомат в начальном состоянии не выдает никаких микрокоманд.

Рис. 3.14

При такой отметке начального состояния конечное состояние автомата соответствует завершению ГСА (перед вершиной «Конец»).

Для корректной работы автомата необходимо, чтобы после завершения выполнения алгоритма автомат вернулся в начальное состояние. Таким образом можно совместить начальное и конечное состояния автомата и обозначить их одинаково a₀.

Часто дополнительно введенную операторную вершину, соответствующую микрокоманде «Операция выполнена», отмечают как конечное состояние автомата (a₀), а так как конечное состояние автомата должно совпадать с начальным, в ГСА вводится еще одна дополнительная операторная вершина, которая отмечается состоянием a₀, так же, как конечная (рис. 3.14). Такое преобразование ГСА имеет определенные преимущества: если автомат «свободен», он не «молчит», а выдает микрокоманду «Операция выполнена», что говорит о его готовности к работе.

Остальным операторным вершинам соответствуют состояния, которые можно пронумеровать так: a₁, a₂, a₃ и т.д. (см. рис. 3.14).

Таким образом, ГСА автомата Мура (рис. 3.14 в нашем примере) отличается от исходной ГСА (см. рис. 3.2) еще одной дополнительной вершиной с состоянием a₀. Обе вершины, помеченные состоянием a₀, можно мысленно совместить, так как после завершения операции автомат должен вернуться в начальное состояние

3.1.1.2. Построение графа переходов автомата Мура
(по ГСА рис. 3.14)

Вершины графа соответст­вуют состояниям автомата, дуги – переходам из состояния a_m в сос­тояние a_s. У вершин графа записы­ваются микрокоманды, соответст­вующие состояниям, в начале дуги – логические условия, опреде­ляющие переход из состояния a_m в состояние a_s (рис. 3.15).

Рис. 3.15

3.1.1.3. Построение прямой таблицы переходов автомата Мура

Прямая таблица переходов (таб­л. 3.6) строится по графу переходов (см. рис. 3.15). Количество строк в таблице равно коли­честву переходов в графе. В столбце а_m за­писываются состояния, из которых начи­нается переход, в столбце a_{s –} состояния, в которые перешел автомат из а_m. В столбце Ya_s записываются Y_{i –} мик­рокоманды, вырабатываемые автоматом в состоянии a_s. В столбце Xa_ma_s записываются логические условия (их конъюнкция), обеспечи­вающие переход из состояния а_m в состояние a_s. Прямая таблица по­зволяет проверить полноту переходов, показанных на графе перехо­дов: дизъюнкция всех Xa _ma _s из состояния a _m должна быть равна «1». В нашем примере дизъюнкция всех Xa₀ a _s равна Ø x ₃ Ú x ₃ = 1 .

Таблица 3.6

3.1.1.4. Кодирование состояний автомата. Выбор элементов памяти

Так как поведение автомата всегда зависит от его текущего состояния а_m, необходимо хранить код состояния а_m в памяти состояний автомата. Объем памяти зависит от способа кодирования состояний. При минимальном кодировании каждому состоянию соответствует число в двоичном представлении, причем количество разрядов этого числа n определяется выражением n = ] log₂ | A | [. Другой крайний случай – унитарное кодирование, при котором n = | A | . От выбранного способа кодирования и самого кодирования состояний может зависеть сложность схемы автомата.

Используем для нашего примера минимальное кодирование состояний. Так как автомат имеет пять состояний, то минимальное количество элементов памяти

n = ] log₂ | A | [ = ] log₂ 5 [ = 3.

Выберем в качестве элементов памяти D-триггеры. Для нашего примера их количество равно трем. Обозначим их как Т_{2 ,} Т_{1 ,} Т₀ , причем Т₂ соответствует старшему разряду кода состояний. Выходы триггеров обозначаются соответственно Q_2, Q_1, Q₀. Значение числа Q₂Q₁Q₀ на этих выходах есть код состояния автомата.

Закодируем состояния автомата произвольно (Ka _i = Q₂Q₁Q₀):

К а₀ = 100. К а₁ = 001. К а₂ = 010.

К а₃ = 000. К а₄ = 011.

3.1.1.5. Обратная структурная таблица автомата Мура

Обратная структурная таблица автомата Мура (табл. 3.7) строится на основе прямой таблицы переходов путем упорядочивания строк по столбцу a_s и добавления столбцов:

Ka _{m –} код состояния a _m;

Ka _{s –} код состояния a _s.

F a _m a _s – функции управления элементами памяти при переходе из состояния a _m в состояние a _s. Поскольку в качестве элементов памяти используем D-триггеры, в этом столбце записываем только D_i, соответствующие триггерам, которые необходимо установить в состояние «1», чтобы обеспечить переход в состояние с кодом K a _s.

Таблица 3.7

3.1.1.6. Функции управления элементами памяти
и функции выходов автомата

Функции управления элементами памяти записываются по обратной структурной таблице автомата:

D _i = F( a _m , X a _m a _s).

Смысл этого выражения следующий (например для D₂): значение функции D₂ должно быть равно 1 (см. обратную структурную таблицу) в двух случаях (1-я и 2-я строки таблицы): если автомат находился в состоянии a₀, а значение x ₃ = 0; если автомат находился в состоянии a₃, а значение x ₂ =1. Таким образом, функция D ₂ имеет вид

D ₂ = a₀Øx ₃ Ú a₃ x ₂.

Остальные функции D ₁ и D ₀ записываются аналогично:

D ₁ = a₁ x ₁ Ú a₄ x ₁ Ú a₃Øx ₂ = x ₁ (a₁ Ú a₄) Ú a₃ Øx ₂.

D ₀ = a₀ x ₃ Ú a₃Øx ₂.

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

y _i = F( a _s).

Так как y_i в автомате Мура зависят только от текущего состояния автомата, то для нашего примера они имеют вид

y₁ = y₂ = a₁. y₃ = a₂. y₄ = y₅ = a₃. y₆ = a₄. y₇ = a₀.

Это означает следующее: в состоянии a₁ автомат вырабатывает микрокоманды y₁ и y₂ , в состоянии a₂ – микрокоманду y₃ и т.д.

3.1.1.7. Структурная схема автомата Мура на жесткой логике

Структурная схема автомата Мура состоит из следующих цифро­вых узлов (рис. 3.16).

Рис. 3.16

Память состояний (ПС), де­шифратор состояний (DC), комбинационная схема фор­мирования сигналов управ­ления элементами памяти состояний (КС_F), комбина­ционная схема формирова­ния выходных сигналов ав­томата (КС_У). Взаимодейст­вие узлов автомата следую­щее. Автомат находится в некотором состоянии a_m, код которого Ka_m в виде значений Q на вы­ходе триггеров памяти состояний (ПС) подается на вход дешифратора состояний (DC), на выходе которого собственно и формируются зна­чения переменных a_m. На выходах комбинационной схемы КС_У формируются микрокоманды У, а на выходах схемы КС_F формируются значения функций управления элементами памяти, которые обеспечивают переход автомата в новое состояние a _s при поступлении импульса синхронизации С на вход синхронизации ПС.

3.1.1.8. Функциональная схема автомата Мура на жесткой логике

Функциональная схема автомата Мура состоит из следующих цифровых узлов.

· Память состояний. В нашем примере – триггеры Т2, Т1, Т0.

· Дешифратор состояний DC. Дешифратор необходим для преобразования двоичного кода состояний автомата Ka _m в унитарный, соответствующий переменным a _i , используемым в записанных выше функциях. В нашем примере дешифратор DC имеет 3 входа и 8 выходов. На вход DC подается Ka_m – код состояния a_m , а на выходах DC формируется унитарный код состояния автомата a _m: единица на i-том выходе дешифратора DC формируется при Ka_m = i.

· Комбинационная схема формирования сигналов управления элементами памяти состояний автомата реализует функции

D _i = F( a _m , X a _m a _s)..

· Комбинационная схема формирования выходных сигналов автомата реализует функции y _i = F( a _s).

В функциональной схеме (рис. 3.17) использованы «шины». Шины представляют собой множество соединений схемы, изображенных в виде одной утолщенной линии. Вход в шину и выход из нее конкретного соединения обозначаются либо одним и тем же числом, либо содержательным обозначением сигнала, передаваемого по этому соединению. Применение шин в схемах позволяет избежать большого числа пересечений на схеме и делает ее более простой для чтения.

С целью упрощения схемы в ней не по­казаны элементы, обеспечивающие ус­тановку автомата в начальное состояние а₀ с кодом Ка₀ = 100. Этот вопрос будет рассмотрен ниже.

Рис. 3.17. Функциональная схема Мура

На рис. 3.18 приведены временные диаграммы, поясняющие работу автомата Мура. Находясь в некотором состоянии a _i, автомат вырабаты­вает выходной сигнал (микрокоманду) y_j, соответствующий этому состоя­нию. В это же время формируются сигналы управления элементами памяти D _i, которые определяют следующее состояние автомата в зависимости от теку­щего и значений логи­ческих условий x_i. При поступлении на вход синхронизации авто­мата положительного фронта импульса С ав­томат переходит в но­вое состояние, определяемое значениями D_i на входах триггеров Т₂ Т₁ Т₀.

Рис. 3.18