Лекция 14.

Раздел 8. Синтез цифровых автоматов на программируемых матрицах (ПЛМ)

Тема 8.1. Структурный синтез МПА Мили на ПЛМ. Вопросы оптимизации МПА

Матричная реализация комбинационных схем (КС)

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

Существуют регулярные, настраиваемые пользователем структуры, называемые программируемыми логическими матрицами (ПЛМ). ПЛМ содержат в себе две матрицы – матрицу «И» (М_&) и матрицу «ИЛИ» (М₁), соединенные последовательно. Матрица «И» вычисляет конъюнкцию логических переменных, а матрица «ИЛИ» – дизъюнкцию полученных термов. Таким образом, пару матриц «И» и «ИЛИ» удобно использовать для вычисления булевых функций, заданных в виде ДНФ (дизъюнктивной нормальной формы).

В простейшем случае ПЛМ представляет матрицу – сеть горизонтальных и вертикальных шин. В узлах матрицы могут быть (а могут и не быть) полупроводниковые диоды.

Если в узле есть диод, то горизонтальная шина через него связана с вертикальной, если диода нет – то не связана. Каждая вертикальная шина такой матрицы – это простейший диодный элемент «И» или «ИЛИ» (в зависимости от направления включения диода и значения напряжения на резисторах матрицы).

На рис. 3.29 приведен пример двух матриц – «И» и «ИЛИ». Каждая вертикальная линия в этих матрицах – это один диодный ло­гический элемент «И» или «ИЛИ». На входы матриц подаются напря­жения Ux_I, соответствующие логическим переменным x_I. Значению x_I=0 в матрице соответствует Ux_I=0 [В], значению x_I = 1 соответствует Ux_I=Uип [В], где Uип – напряжение источника питания в вольтах. Выходные напряжения матриц Uу_I соответствуют значениям функций у_I , реали­зуемых данными матрицами. Причем нетрудно заметить, что в матрице «ИЛИ» Uу_I=Uип (у_I =1), если в узле матрицы на пресечении линий Uу_I и Ux_J есть диод и Ux_J=Uип (x_J=1). В матрице «И» Uу_I=Uип (у_I =1), если на всех входах, соединенных диодами с шиной Uу_I, значения Ux_J=Uип (x_J=1) и Uу_I=0 В (у_I =0), если хотя бы на одном из входов Ux_J= 0 В (x_J=0).

Таким образом, в примере (см. рис. 3.29) матрица «ИЛИ» реализует три функции У₁, У₂, У₃ от трех переменных x₁, x₂ , x₃ :

У ₁ = x₁ Ú x₃ ; У ₂ = x₁ Ú x₂ ; У ₃ = x₂ Ú x₃ ,

а матрица «И» реализует функции

У ₁ = x₁ x₃ ; У ₂ = x₁ x₂ ; У ₃ = x₂ x₃ .

Рис. 3.29

На рис. 3.29 матрицы изо­бражены фактически как принципиальные схемы, в ко­торых логические переменные x_I представлены напряжениями Ux_I , а функции у_I – напряже­ниями Uу_I . В функциональных схемах будем использовать бо­лее простое изображение мат­риц: в узлах вместо диодов бу­дем ставить точки, а входные и выходные сигналы будем обо­значать как x_J и у_I (рис. 3.30).

Рис. 3.30

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

Пусть дана система из трех булевых функций у₁, у₂, у₃ от четырех переменных x₁, x₂, x₃, x₄:

y₁ = Øx₁ x₂ Ú x₁ Øx₂Øx₄ Ú x₁ x₃ x₄;

y₂ = Øx₁ x₂ Ú Øx₁ Øx₃ x₄ Ú Øx₁ Øx₂ Øx₃Ú Øx₂ Øx₄;

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

Введем вспомогательные переменные Т_I , через которые выра­зим все дизъюнктивные термы, встречающиеся в функциях у₁, у₂, у₃ :

Т₁= Øx ₁ x ₂ ; Т ₂= x ₁ Øx ₂Øx ₄ ; Т ₃= x ₁ x ₃ x ₄ ; Т ₄= Øx ₁ Øx ₃ x ₄;

Т ₅ = Øx ₁ Øx ₂ Øx ₃ ; Т ₆= Øx ₂ Øx ₄; Т ₇ = x ₁ Øx ₃ .

Выразим функции у₁, у₂, у₃ через переменные Т_I :

y₁ = Т₁ Ú Т ₂ Ú Т ₃;

y₂ = Т₁ Ú Т ₄ Ú Т ₅ Ú Т ₆;

y₃ = Т₂ Ú Т ₇ Ú Т ₅.

В этих функциях че­рез переменные Т_I обозна­чены термы (логические произведе­ния), которые вы­числяются матрицей «И». С выходов матрицы «И» (М_&), сигналы, соответствующие термам Т_I, подаются на входы матрицы «ИЛИ» (М₁), где вычисля­ются зна­чения функций y₁, y₂ и y₃ . Схема приведена на рис. 3.31.

Рис. 3.31

С помощью матриц М_& («И») и М₁ («ИЛИ») можно реализовывать не только дизъюнктивные нормальные форм, но и ско­бочные выра­жения, которые часто явля­ются более ком­пактными.

Например, даны две функции:

y₁ = (x₁ x₂ Ú Øx₁ Øx₂) x₃ Ú Ø(x₁ x₂ Ú Øx₁ Øx₂) Øx₃;

y₂ = x₁ x₂ Ú Ø(x₁ x₂ Ú Øx₁ Øx₂) x_3.

Заметим, что выражение в скобках – (x₁ x₂ Ú Øx₁ Øx₂) – три раза встречается в функциях y₁ и y₂.

На матрицах М_& («И») и М₁ («ИЛИ») сформируем функцию f = x₁x₂ Ú Øx₁Øx₂ , затем эту функцию используем в матрице М_& («И») для формирования термов, а затем и значений функций y₁ и y₂. Введем переменные Т_I :

Т₁ = x₁ x₂ ; Т₂ = Øx₁ Øx₂ .

Через Т₁ и Т₂ выразим функцию f :

f = Т₁ Ú Т₂ .

Введем еще три переменные Т_I , в которых кроме x₁, x₂, x₃ используем функцию f:

Т₃ = f Ù x ₃; Т₄ = Øf Ù Øx ₃; Т₅ = Øf Ù x ₃.

Преобразуем функции y₁ и y₂ и запишем их в следующем виде:

y₁ = (Т₁Ú Т₂) x ₃ Ú Ø( Т₁Ú Т₂) Øx ₃ = f Ù x ₃ Ú Øf Ù Øx ₃ = Т₃ Ú Т₄;

y₂ = Т₁Ú Ø( Т₁Ú Т₂) x ₃= Т ₁ Ú Øf Ù x ₃= Т₁ Ú Т₅.

Таким образом, порядок вычислений функций y₁ и y₂ сле­дующий. Матрица М_& вычисляет Т₁ = x₁ x₂ и Т₂ = Øx₁ Øx₂, затем матрица М₁ вычисляет f = Т₁ Ú Т₂ . Значение f в прямом и инверсном виде пода­ется на вход матрицы М_& , где вы­числяются Т₃, Т₄ и Т₅ , а затем матрица М₁ вычисляет y₁ = Т₃ Ú Т₄ и y₂ = Т₁ Ú Т₅ . На рис. 3.32 приве­дена схема, реализующая данный способ вычисления скобочных бу­левых функций.

Рис. 3.32

3.3.2. Простейшая матричная реализация автомата Мили

Рассмотрим реализацию автомата Мили на ПЛМ на примере из п. 3.1.2. Отличие в синтезе автомата Мили на ПЛМ состоит только на этапах построения обратной структурной таблицы и функцио­нальной схемы автомата.

Возьмем за основу структурную таблицу автомата Мили на жесткой логике из п. 3.1.2. Будем использовать в качестве элементов памяти состояний D-триггеры. Добавим в таблицу еще один столбец Тa_ma_s, в который будем записывать функции переходов: Тa_ma_s = a_m Ù Xa_ma_s , где Xa_ma_s – конъюнкция логических условий, обеспечивающих данный переход из a_m в a_s; a_{m –} состояние автомата, из которого начинается переход, представленное кодом состояния Ka_m , заданного значениями Q₁Q₀ на выходах элементов памяти Т₁ Т₀. Если, например, код состояния a_m имеет значение Ka_m = 10, то значения на выходах элементов памяти состояний Q₁Q₀ также равны 10. Так как здесь Q₁=1, то Q₁ войдет в функцию перехода без инверсии, а Q₀ = 0 поэтому войдет в функцию с инверсией. Например, для пятой строки структурной таблицы автомата функция перехода из a₂ в a₃ имеет вид Т₂ =a₂x₁; так как Ka₂ =01, то Т₁ = ØQ₁Q₀x_1.

Обратная структурная таблица автомата Мили с памятью состояний на D-триггерах (для матричной реализации) имеет вид (табл. 3.13).

Структурная схема ав­то­мата Мили на матрицах (простей­шая реализация) имеет вид, пока­занный на ри­с. 3.33. В схеме авто­мата исполь­зуются две матрицы – М_& («И»), кото­рая используется для вычис­ления функций перехо­дов Тa_ma_s, и М₁ («ИЛИ»), выпол­няющая две функции – вычисление функций (Fa_ma_s) управле­ния эле­ментами па­мяти состояний ПС) D₁ и D₀ и вы­чис­ление функций выхо­дов (Ya_ma_s) авто­мата y_i.

Таблица 3.13

Рис. 3.33

Функции D₁ , D₀ и y_i для нашего примера находятся как дизъюнк­ции соот­ветст­вующих функций переходов Тa_ma_s:

D₁ = T₅ Ú T₆ Ú T₇ ; D₀ = T₃ Ú T₄ Ú T₆Ú T₇ ;

y₁ = y₂ = T₃ ; Y₃ = T₅ ; y₄ = y₅ = T₆Ú T₇ ; y₆ = T₄ ; y₇ = T₂ .

Как видно из этих выражений, функция переходов Т₁ не используется ни в одной из функций D_i и y_i, поэтому ее можно не вычислять. Таким образом, функциональная схема автомата Мили на ПЛМ (для нашего примера) будет состоять из следующих элементов.

– Память состояний. В нашем примере – два D-триггера: Т₁ Т_0.

– Инверторы для формирования инверсных значений логиче­ских условий x_I .

– Матрица М_&, имеющая шесть верти­кальных шин (по количеству фор­мируемых функ­ций пере­ходов Тa_ma_s) и одинна­дцать горизон­таль­ных (удвоенное ко­личество элементов памяти и ло­гических условий плюс один – шина для сигнала синхронизации С).

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

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

Рис. 3.34

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

Матрицы М_& и М₁ характеризуются площадями S_M& и S_M1, вычислить которые для каждого конкретного примера можно по структурной таблице автомата (или по функциональной схеме). Например, площадь S_M& = 66: 11 горизонтальных шин и 6 вертикальных. Как видно из простого примера на рис. 3.34, площади мат­риц М_& и М₁ исполь­зуются неэффективно по двум причинам:

1) при общем количе­стве логических усло­вий ½X½= 3 в каждом конкретном переходе из a_m в a_s участвует всего одно;

2) при об­щем количестве ½Y½=7, на каждом пе­реходе автомат выра­батывает всего одну микрокоманду.