Материал: Ковригин Теория автоматов Лабораторный практикум 2012
Зависимость входного сигнала Di(t) триггера от состояний всех D-триггеров в момент времени t и от значения входного сигнала автомата x(t) называют функцией возбуждения D-триггера.
Таким образом, в таблице возбуждения следует указать значение сигнала, который необходимо подать на D-вход каждого триггера при всех возможных комбинациях вход/код состояния. В нашем примере кодированная таблица переходов, дополненная функциями возбуждения, имеет вид, указанный в табл. 2.2.
Поскольку для D-триггера Q(t+1) = D(t) (времена t и t+1 означают время до и после поступления синхросигнала), таблица возбуждения тождественна кодированной таблице переходов автомата, за исключением того, как обозначается то, что вносится в эту таблицу (см. колонки 5-7 и 8-10 в табл. 2.2). Таким образом, при использовании D-триггеров фактически не нужно составлять отдельную таблицу возбуждения, достаточно назвать кодированную таблицу переходов таблицей «переход/возбуждение».
Таблица 2.2 Таблица переходов и функций возбуждения D-триггеров автомата
Номер |
|
Время t |
|
|
Время t+1 |
|
|
Время t |
|
|||||
X |
Q2 |
Q1 |
Q0 |
Q2 |
|
Q1 |
|
Q0 |
D2 |
|
D1 |
|
D0 |
|
набора |
|
|
|
|
||||||||||
1 |
2 |
3 |
4 |
5 |
|
6 |
|
7 |
8 |
|
9 |
|
10 |
|
|
|
|
|
|
||||||||||
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
|
1 |
0 |
|
0 |
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
|
1 |
|
0 |
0 |
|
1 |
|
0 |
2 |
0 |
0 |
1 |
0 |
1 |
|
0 |
|
0 |
1 |
|
0 |
|
0 |
4 |
0 |
1 |
0 |
0 |
1 |
|
0 |
|
1 |
1 |
|
0 |
|
1 |
5 |
0 |
1 |
0 |
1 |
0 |
|
0 |
|
0 |
0 |
|
0 |
|
0 |
8 |
1 |
0 |
0 |
0 |
0 |
|
0 |
|
1 |
0 |
|
0 |
|
1 |
9 |
1 |
0 |
0 |
1 |
1 |
|
0 |
|
1 |
1 |
|
0 |
|
1 |
13 |
1 |
1 |
0 |
1 |
1 |
|
1 |
|
0 |
1 |
|
1 |
|
0 |
14 |
1 |
1 |
1 |
0 |
1 |
|
0 |
|
0 |
1 |
|
0 |
|
0 |
12 |
1 |
1 |
0 |
0 |
1 |
|
1 |
|
1 |
1 |
|
1 |
|
1 |
15 |
1 |
1 |
1 |
1 |
0 |
|
0 |
|
0 |
0 |
|
0 |
|
0 |
Табл. 2.2, составленная по изложенной методике, определяет функции возбуждения входов всех триггеров. Аргументы этих функций записаны в колонках 1 4. Поскольку значения всех переменных определены для одного и того же момента времени t, то
21
функции возбуждения D-триггеров являются логическими функциями.
Минимизация функций возбу ждения
Минимизация это процесс нахождения такого эквивалентного выражения функции алгебры логики, которое содержит минимальное число вхождений переменных.
Представим функции возбуждения в минимальной дизъюнктивной нормальной форме (МДНФ). Один из наиболее удобных методов минимизации основан на использовании диаграмм Вейча (карт Карно).
Диаграмма Вейча это графическое представление таблицы истинности, которой задается логическая функция.
Диаграмма Вейча для логических функций четырех аргументов Х,Q2,Q1,Q0 приведена на рис. 2.3.
Она содержит 24 = 16 клеток, каждая из которых соответствует одному двоичному значению аргументов, на которых задается логическая функция. Эти наборы показаны на рис. 2.3 в каждой клетке. Разметка строк и столбцов диаграммы Вейча выполняется таким образом, что для любой клетки легко определить соответствующую ей комбинацию переменных по заголовкам строки и столбца, на пересечении которых находится эта клетка. Эта комбинация переменных (логическое произведение тех переменных, которые соответствуют записанным двоичным наборам), приведена в каждой клетке диаграммы Вейча (см. рис. 2.3).
При этом диаграмма строится таким образом, что склеивающиеся между собой наборы аргументов оказываются расположенными в соседних клетках, так как отличаются значением только одной переменной. Можно увидеть, что в первой и последней колонках диаграммы находятся склеивающиеся между собой наборы аргументов, то же самое можно сказать и в отношении верхней и нижней строк, т.е. эти колонки и строки следует считать соседними. Поэтому диаграмму Вейча для функций четырех аргументов следует представлять нанесенной на поверхность тора.
22
Рис. 2.3. Диаграмма Вейча для функций четырех аргументов
Имея такое изображение диаграммы Вейча с нанесенными значениями двоичных наборов аргументов, процесс составления диаграмм Вейча для функций возбуждения триггеров автомата предельно облегчается. Чтобы представить функцию возбуждения диаграммой Вейча, следует записать единицы и нули в клетки диаграммы, соответствующие наборам, на которых функция равна единице или нулю (рис. 2.4).
Из табл. 2.2 видно, что из 16 возможных состояний используются только 11. Остальные пять состояний являются запрещенными, они никогда не появляются при правильной работе автомата. Это состояния 0011, 0110, 0111, 1010, 1011 (им будут соответствовать незаполненные поля диаграмм Вейча). Отметим на диаграммах Вейча эти состояния символом « » (см. рис. 2.4).
На этих наборах аргументов значения функций могут быть произвольными, т.е. равными 0 или 1. Поэтому при синтезе схем с не полностью определенной функцией можно произвольно задать значения выходных сигналов для запрещенных комбинаций вход-
23
ных сигналов; нормальная работа схемы при этом не нарушается. При минимизации не полностью определенных функций на запрещенных комбинациях придают такие значения, которые приводят к получению минимальной ДНФ.
Рис. 2.4. Диаграммы Вейча функций возбуждения и функции Y
Для получения минимальной ДНФ с помощью диаграммы Вейча необходимо покрыть все единицы минимальным числом «пра-
24
вильных» площадей. «Правильная» площадь это прямоугольник или квадрат, содержащий 2n клеток диаграммы.
Для не полностью определенных функций отдельные значения, помеченные символом « », можно включать в покрытие, если это приводит к уменьшению числа площадей и/или к увеличению их размера.
При этом следует помнить, что площади покрытия могут пересекаться, т.е. наборы могут входить в несколько покрытий. Также возможно несколько вариантов минимального покрытия.
Покрытия, составленные по указанным правилам, приведены на рис. 2.4 для функций возбуждения и функции Y выхода автомата.
При записи минимальной ДНФ, полученной с помощь покрытий на диаграмме Вейча, руководствуются следующими правилами:
число простых импликант (самых коротких элементарных произведений) равно числу покрывающих площадей;
переменные, которые входят в простую импликанту, определяются переменными, входящими в покрытие только одним своим обозначением (либо без отрицания, либо с отрицанием).
Минимальные ДНФ для нашего примера приведены на рис. 2.4.
Логическая схема автомата
Логическая схема проектируемого автомата, построенная на базовых элементах ПЛИС XC10PC84 (см. приложение 1) по полученным минимальным ДНФ функций возбуждения D-триггеров и функции выхода Y, показана на рис. 2.5.
Чтобы обеспечить предварительную установку автомата в начальное состояние «0», в приведенной схеме автомата введен вход
CLR.
Временная диаграмма работы автомата приведена на рис. 2.6.
25