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

Для реализации блока памяти заданы комбинированные синхронные двухтактные D - триггеры. Реализованная схема блока памяти представлена на рисунке 2.3.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 2.3 – Электрическая  функциональная схема блока памяти.

 

3. СТРУКТУРНЫЙ СИНТЕЗ ЛОГИЧЕСКОГО ПРЕОБРАЗОВАТЕЛЯ УА

 

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

Исходными данными для  составления расширенных структурных  таблиц переходов и выходов являются таблицы 2.1 и 2.2 и данные, полученные в результате структурного кодирования состояний автомата (например, данные таблицы 2.3). 

Расширенные структурные  таблицы переходов и выходов  отличаются от таблиц 2.1 и 2.2  введением дополнительных граф, содержащих информацию о структурном коде состояния автомата в текущий момент времени К(а_m), о структурном коде автомата в последующий момент времени К(а_s), а также структурный код функции возбуждения блока памяти F(а_m,а_s), который должен формироваться логическим преобразователем для подготовки перехода автомата из состояния а_m  в состояние а_s. В зависимости от используемых триггерных схем функция возбуждения F(а_m,а_s) определяется различным образом. Наиболее просто функция возбуждения определятся для  D  и T -триггеров.

При использовании D – триггеров функция возбуждения блока памяти находится на основании следующего уравнения:

 

F(а_m,а_s) = К(а_s).                                       (3.1)

 

Из уравнения (6.5) следует следующая система уравнений:

f₁ = d₁(а_s)

f₂ = d₂(а_s)

….                                                 (3.2)

f_r = d_r(а_s)

 

Для исходного синхронного управляющего автомата расширенная таблица переходов и выходов представлена в таблице 3.1.

 

 

 

 

Таблица 3.1 – Расширенная  таблица переходов и выходов

 

am	K(am)				as	K(as)				X(am,as)	Y(am,as)	F(am,as)
	d3	d2	d1	d0		d3	d2	d1	d0			f3	f2	f1	f0
a1	0	1	1	0	a2	1	0	1	0	x1	y1 y4 y6 y7	1	0	1	0
a1	0	1	1	0	a1	0	1	1	0	x1	y2 y3 y5 y7	0	1	1	0
a2	1	0	1	0	a7	0	0	1	1	x2	y1 y2 y4 y6 y7	0	0	1	1
a2	1	0	1	0	a3	0	0	1	0	x2x3	y2 y5 y7	0	0	1	0
a2	1	0	1	0	a4	0	0	1	0	x2x3x4	-	0	0	1	0
a3	0	0	1	0	a4	0	1	0	0	1	y2 y5 y7	0	1	0	0
a4	0	1	0	0	a5	0	1	0	1	x6	y1 y5 y6 y7	0	1	0	1
a4	0	1	0	0	a8	0	0	0	1	x6	y2 y4 y5	0	0	0	1
a5	0	1	0	1	a6	1	0	0	0	1	y3 y4 y6 y7	1	0	0	0
a6	1	0	0	0	a10	1	1	0	0	1	y1 y2 y4 y6 y7	1	1	0	0
a7	0	0	1	1	a8	0	0	0	1	x5	y2 y4 y5	0	0	0	1
a7	0	0	1	1	a3	0	1	0	0	x5x3	y2 y5 y7	0	1	0	0
a7	0	0	1	1	a4	0	1	0	0	x5x3x4	y2 y5 y7	0	1	0	0
a7	0	0	1	1	a8	0	0	0	1	x5x3x4	y2 y4 y5	0	0	0	1
a8	0	0	0	1	a8	0	0	0	1	x4	y2 y4 y5	0	0	0	1
a8	0	0	0	1	a9	1	0	0	1	x4	y2 y3 y5 y7	1	0	0	1
a9	1	0	0	1	a9	1	0	0	1	x6	y2 y3 y5 y7	1	0	0	1
a9	1	0	0	1	a6	1	0	0	0	x6	y1 y4 y6 y7	1	0	0	0

 

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

 

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

Составление логических уравнений для функций возбуждения  блока памяти F(а_m,а_s) сводится к составлению совокупности логических уравнений для каждой отдельной функции возбуждения элементов памяти (f₁ … f_r). Логические уравнения записываются как дизъюнкция конъюнкций структурного кода исходного состояния автомата K( a_m) и комбинации входных сигналов X (а_m,а_s) по тем строкам таблиц 6.6, 6.7, в которых в соответствующем столбце f_i  присутствует значение, равное 1.

 

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

f₁ = d₃ *d₂ *d₁ * 1 + d₃ *d₂ *d₁ * x₂ + …..,                                          (3.3)

f₂ = d₃ *d₂ *d₁ * x₁ + d₃ *d₂ *d₁ * x₂ + d₃ *d₂ *d₁ * x₃ * x₄ + …..,       (3.4)

f₃ = d₃ *d₂ *d₁ * x₁ + d₃ *d₂ *d₁ * x₁ + …..                                        (3.5)

В уравнениях (3.3 - 3.5) знаки конъюнкции могут не записываться, так же как и 1-ое значение условия перехода.

Функции возбуждения блока памяти:

f₀= d₃ d₂ d₁ d₀ x₂+ d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ x₅ +

d₃ d₂ d₁ d₀ x₅ x₃ x₄ + d₃ d₂ d₁ d₀ x₄+ d₃ d₂ d₁ d₀ x₄ + d₃ d₂ d₁ d₀ x₆

f₁= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ x₁ + d₃ d₂ d₁ d₀ x₂ + d₃ d₂ d₁ d₀ x₂ x₃ +

d₃ d₂ d₁ d₀ x₂ x₃ x₄

f₂= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ +

d₃ d₂ d₁ d₀ x₅ x₃ + d₃ d₂ d₁ d₀ x₅ x₃ x₄

f₃= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀ x₄ +

d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ x₅ x₃ x₆

 

   Для автомата типа Мили функции выходов (y_i) формируется так же, как для функций возбуждения элементов памяти. Для этого используется графа Y(а_m,а_s) соответствующей структурной таблицы. Функции выходов для автомата типа Мили представляют собой дизъюнкции конъюнкций структурного кода исходного состояния автомата K( a_m) и комбинации входных сигналов X (а_m,а_s) по тем строкам таблицы 6.6, в которых присутствует выходной сигнал y_i. Логические уравнения составляются для всех выходных сигналов.

 

Функции выходов:

y₁= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ x₂ + d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ +

d₃ d₂ d₁ d₀ x₆

y₂= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ x₂ x₃ + d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀ x₅ + d₃ d₂ d₁ d₀ x₃ x₅ + d₃ d₂ d₁ d₀ x₅ x₃ x₄+ d₃ d₂ d₁ d₀ x₅ x₃ x₄ +

d₃ d₂ d₁ d₀ x₄ + d₃ d₂ d₁ d₀ x₄ + d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ x₆

y₃= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀ x₄ + d₃ d₂ d₁ d₀ x₆

y₄= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ x₂ + d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀ +   d₃ d₂ d₁ d₀ x₅ + d₃ d₂ d₁ d₀ x₃ x₅ x₄ + d₃ d₂ d₁ d₀ x₄+ d₃ d₂ d₁ d₀ x₅

y₅= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ x₂ x₃ + d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀ x₆+ d₃ d₂ d₁ d₀ x₆ +   d₃ d₂ d₁ d₀ x₅ x₃ + d₃ d₂ d₁ d₀ x₅ x₃ x₄ + d₃ d₂ d₁ d₀ x₅ x₃ x₄ + d₃ d₂ d₁ d₀ x₄+ d₃ d₂ d₁ d₀ x₄+ d₃ d₂ d₁ d₀ x₆

y₆= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ x₂ + d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀+

d₃ d₂ d₁ d₀ x₆

y₇= d₃ d₂ d₁ d₀ x₁+ d₃ d₂ d₁ d₀ x₁ + d₃ d₂ d₁ d₀ x₂ + d₃ d₂ d₁ d₀ x₂ x₃+ d₃ d₂ d₁ d₀ +   d₃ d₂ d₁ d₀ x₆ + d₃ d₂ d₁ d₀ + d₃ d₂ d₁ d₀ + d₃d₂d₁d₀x₅x₃ + d₃d₂d₁d₀x₅x₃x₄ +

d₃ d₂ d₁ d₀ x₅x₃x₄+ d₃ d₂ d₁ d₀ x₄+ d₃ d₂ d₁ d₀ x₆+ d₃ d₂ d₁ d₀ x₆

 

3. Минимизация логических функций

Минимизация в широком  смысле слова — такое преобразование логических выражений, которое упрощает их в смысле некоторого критерия. Целью минимизации одиночных логических функций является сокращение ранга и числа элементарных конъюнкций,  входящих в исходную ДНФ логической функции. В результате минимизации по таким критериям могут быть получены кратчайшие и/или минимальные тупиковые дизъюнктивные нормальные формы, обеспечивающие минимальную структурную сложность при реализации логической функции в элементных базисах И, ИЛИ, НЕ; И-НЕ; ИЛИ-НЕ и прочее.

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

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

При реализации системы  логических функций на программируемой логической матрице наиболее эффективен  метод группой минимизации, который легко реализуется и гарантирует минимизацию площади ПЛМ, занимаемой на кристалле интегральной схемы. Простейший метод групповой минимизации состоит в следующем: в системе логических уравнений для функций возбуждения и функций выходов отыскиваются группы одинаковых элементарных конъюнкций. Для каждой группы одинаковых элементарных конъюнкций вводится фиктивная переменная с каким – либо индексом (например, Z₁, … Z_s). Далее все исходные логические уравнения переписываются в терминах фиктивных переменных. Затем на ПЛМ реализуют элементарные конъюнкции, соответствующие каждой фиктивной переменной и их дизъюнкции в соответствии с уравнениями, содержащими фиктивные переменные. Данный метод групповой минимизации существенно уменьшает число промежуточных шин в ПЛМ и, таким образом, потребную площадь кристалла ПЛМ. Следует отметить, что для автомата типа Мили данный метод групповой минимизации более эффективен, чем для автомата типа Мура.

 

 

 

Таблица 3.3 – Минимизация  логических функций

Z1	d3 d2 d1 d0 x1
Z2	d3 d2 d1 d0 x1
Z3	d3 d2 d1 d0 x2
Z4	d3 d2 d1 d0 x2 x3
Z5	d3 d2 d1 d0 x2 x3 x4
Z6	d3 d2 d1 d0
Z7	d3 d2 d1 d0 x6
Z8	d3 d2 d1 d0 x6
Z9	d3 d2 d1 d0
Z10	d3 d2 d1 d0
Z11	d3 d2 d1 d0 x5
Z12	d3 d2 d1 d0 x5 x3
Z13	d3 d2 d1 d0 x5 x3 x4
Z14	d3 d2 d1 d0 x5 x3 x4
Z15	d3 d2 d1 d0 x4
Z16	d3 d2 d1 d0 x4
Z17	d3 d2 d1 d0 x6
Z18	d3 d2 d1 d0 x6

 

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