Синтез комбинационной схемы и проектирование управляющего автомата Мура

1 Синтез комбинационной схемы

1.1 Определение значений БФ

Булевая функция 5 переменных F (x1, x2, x3, x4, x5) задается своими значениями, которые определяются 7-разрядовими двоичными эквивалентами чисел,: по значению чисел А, В (на наборах 7-13), С (наборы 14-20), по значению (наборы 21-27) и на наборах 28-31 функции принимает неопределенные значения.

А=13 эквивалентно 4910=1100012.

Проставляем символ неопределенного значения Х110001.

В=07 эквивалентно 1010=10102.

Проставляем символ неопределенного значения ХХХ1010.

С=21 эквивалентно 2310=101112.

Проставляем символ неопределенного значения XХ10111.

А+В+С=41 эквивалентно 7210=10010002.

Соответственно, значение функций F (x1, x2, x3, x4, x5) на наборах от 0 до 31 будет иметь вид

Таблица 1

1.2 Минимизация БФ

Получаем МДНФ и МКНФ булевой функции с помощью метода карт Карно. Схемы карт Карно приведены ниже.

Таблица 2 Карта Карно к МДНФ

В результате минимизации, получим:

_ _ _ _ _ _ _ _ _ _ _ _ _

Y=X₁X₃X₄+X₂X₄X₅+X₃X₄X₅+X₁X₂X₃X₄+X₁X₄X₅+X₁X₃X₄

Таблица 3 Карта Карно к МКНФ

В результате минимизации, получим:

_ _ _ _ _ _ _ _ _ _

y=(X₁+X₂+X₄+X₅) (X₁+X₃ +X₄ +X₅) (X₁+ X₃+ X₄+ X₅) (X₁+X₂+ X₄) (X₁+X₃+ X₄)

_ _

(X₁+X₃+X₅)

1.3 Описание минимизации БФ заданными методами

Для выбора минимальной из МДНФ и МКНФ оценим сложность схемы с помощью цены по Квайну. Цена по Квайну определяется как суммарное число входов логических элементов в составе схемы.

Такой подход обусловлен тем, что

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

все классические методы минимизации БФ обеспечивают минимальность схеме именно в содержании цены по Квайну.

Схема с минимальной ценой по Квайну часто реализуется с наименьшим числом конструктивных элементов - корпусов интегральных микросхем.

Для данных функций мы имеем:

C_кв (МДНФ)=19+6+5=30;

C_кв(МКНФ)=21+6+5=32.

Так как минимальной ценой является Cкв(МКНФ), то для реализации схемы будем использовать МДНФ.

1.4 Приведение БФ к заданному базису

Заданный базис: 3 И-НЕТ.

Приведем выражение к заданному базису:

_ _ _ _ _ _ _ _ _ _ _ _ _

Y=X₁X₃X₄+X₂X₄X₅+X₃X₄X₅+X₁X₂X₃X₄+X₁X₄X₅+X₁X₃X₄ =

Для реализации функции по останьому выражению необходимо 16 элементов 3И-НЕТ (Рис. 1). Ранг данной схемы равняется 4, что негативно отображается на скорости. Использовал факторный алгоритм возможно улучшить схему, увеличить скорость его работы.

Рис. 1 Функциональная схема для заданного базиса

2. Проектирование автоматов

.1 Выбор задания

Граф-схемы алгоритмов избираются каждым студентом в индивидуальном порядке. Она состоит из четырех блоков: E, F, G, H. Студенты избирают графскую схему из пяти блоков с номерами 0…4 на основании чисел А, В, С и (А+В+С) по следующим правилам:

блок «Е» - схема под номером (А) mod 5 = 13 mod 5 = 3;

блок «F» - схема под номером (В) mod 5 = 7 mod 5 = 2;

блок «G» - схема под номером (С) mod 5 = 21 mod 5 = 1;

блок «H» - схема под номером (А+В+С) mod 5 = 41 mod 5 = 1.

Расположение избирается с использованием номера группы. Тип триггера находим по таблицы на основании числа (А) mod 3 = 13 mod 3 = 1.

Получаем D - тригер для автомата Моли и JK - тригер для Мура. Для парных номеров по списку (21) - серия КР555.

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

2.2    Автомат Мура

Строим таблицу переходов для автомата Мура.

Кодировку состояний выполняем по евристическому алгоритму. Для этого строим матрицу Т.

║T║ =

i │ j │ P (i, j)

│ 2 │ 1

│ 24│ 1

│ 25│ 1

│ 4 │ 1

│ 6 │ 1

│ 7 │ 1

│ 5 │ 1

│ 6 │ 1

│ 7 │ 1

│ 13 │ 1

│ 14 │ 1

│ 6 │ 1

│ 7 │ 1

│ 6 │ 1

│ 7 │ 2

│ 8 │ 1

│ 9 │ 1

│ 8 │ 1

│ 10 │ 1

│ 11 │ 1

│ 11 │ 1

│ 13 │ 1

│ 14 │ 1

│ 12 │ 1

│ 13 │ 1

│ 15 │ 1

│ 15 │ 1

│ 17 │ 1

│ 19 │ 1

│ 20 │ 1

│ 19 │ 1

│ 20 │ 2

│ 22 │ 2

│ 26 │ 1

│ 18 │ 1

│ 21 │ 1

│ 21 │ 1

│ 22 │ 1

│ 23 │ 1

│ 25 │ 1

│ 26 │ 1

│ 25 │ 1

│ 26 │ 2

│ 24 │ 1(1) = 3(2) = 4(3) = 5(4) = 3(5) = 3(6) = 6(7) = 5(8) = 3(9) = 2(10) = 4(11) = 4(12) = 2(13) = 4(14) = 2(15) = 5(16) = 4(17) = 2(18) = 2(19) = 3(20) = 3(21) = 5(22) = 4(23) = 2(24) = 2(25) = 3(26) = 3

Дальше согласно правил алгоритма строим матрицу М

║M║ =│ j │ P (i, j)

│ 7 │ 2

│ 7 │ 1

│ 6 │ 1

│ 6 │ 1

│ 7 │ 1

│ 13 │ 1

│ 6 │ 1

│ 6 │ 1

│ 8 │ 1

│ 15 │ 1

│ 5 │ 1

│ 7 │ 1

│ 9 │ 1

│ 8 │ 1

│ 13 │ 1

│ 11 │ 1

│ 13 │ 1

│ 19 │ 1

│ 20 │ 1

│ 20 │ 2

│ 22 │ 2

│ 26 │ 2

│ 21 │ 1

│ 25 │ 1

│ 26 │ 1

│ 2 │ 1

│ 4 │ 1

│ 14 │ 1

│ 10 │ 1

│ 15 │ 1

│ 17 │ 1

│ 19 │ 1

│ 26 │ 1

│ 21 │ 1

│ 22 │ 1

│ 23 │ 1

│ 25 │ 1

│ 25 │ 1

│ 11 │ 1

│ 14 │ 1

│ 12 │ 1

│ 24 │ 1

│ 18 │ 1

│ 24 │ 1

Определяем разрядность кода для кодировки состояний автомата

R =] log2 N [=] log2 26 [= 5

Результаты кодировки:

a1 1010100101000100011100000000110000101011100110101011010111101001001000101100010010111111111010000110111010110011001100011110001101

Подсчет эффективности кодировки:

Количество переключений триггеров:

W = E P (i, j)*d (i, j) = P (1,2)*d (1,2) + P (1,24)*d (1,24) + P (1,25)*d (1,25) + P (2,4)*d (2,4) + P (2,6)*d (2,6) + P (2,7)*d (2,7) + P (3,5)*d (3,5) + P (3,6)*d (3,6) + P (3,7)*d (3,7) + P (3,13)*d (3,13) + P (3,14)*d (3,14) + P (4,6)*d (4,6) + P (4,7)*d (4,7) + P (5,6)*d (5,6) + P (5,7)*d (5,7) + P (6,8)*d (6,8) + P (6,9)*d (6,9) + P (7,8)*d (7,8) + P (8,10)*d (8,10) + P (9,11)*d (9,11) + P (10,11)*d (10,11) + P (10,13)*d (10,13) + P (10,14)*d (10,14) + P (11,12)*d (11,12) + P (11,13)*d (11,13) + P (12,15)*d (12,15) + P (13,15)*d (13,15) + P (15,17)*d (15,17) + P (15,19)*d (15,19) + P (15,20)*d (15,20) + P (16,19)*d (16,19) + P (16,20)*d (16,20) + P (16,22)*d (16,22) + P (16,26)*d (16,26) + P (17,18)*d (17,18) + P (18,21)*d (18,21) + P (19,21)*d (19,21) + P (20,22)*d (20,22) + P (21,23)*d (21,23) + P (21,25)*d (21,25) + P (21,26)*d (21,26) + P (22,25)*d (22,25) + P (22,26)*d (22,26) + P (23,24)*d (23,24) = 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*2 + 1*2 + 2*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 2*1 + 2*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 2*1 + 1*1 = 60

Минимально возможное количество переключений триггеров:

= E P (i, j) = 48

Коэффициент эффективности кодировки: 1.25

Выписываем из таблицы выражения для триггеров:

J1=a6*x4+a8+a11*x1+a11*nx1+a21*x4+a22*nx4*nx1=*x4+a8+a11+a21*x4+a22*nx4*nx1

K1=a3*x5+a3*nx5*x2+a3*nx5*nx2+a9+a10*x5+a15*nx4*x3+a16*x4*x3+a16*nx4*x1+a16*nx4*nx1+a17+a19+a24+a26=*x5+a3+a9+a10*x5+a15*nx4*x3+a16*x4*x3+a16+a17+a19+a24+a26

J2=a2*x5+a9+a10*x5+a10*nx5*x6+a15*nx4*nx3+a16*x4*nx3+a16*nx4*nx1+a18+a20+a21*nx4*nx3+a24=a1+a4*x2+a4*nx2+a11*x1+a12+a14+a19+a22*x4*x3+a22*nx4*x1+*nx4*nx1=+a4+a11*x1+a12+a14+a19+a22*x4*x3+a22

J3=a1+a6*nx4+a7*x6+a15*x4+a19+a22*x4*x3+a22*x4*nx3+a22*nx4*x1+a22*nx4*nx1=a1+a6*nx4+a7*x6+a15*x4+a19+a22=a2*x5+a2*nx5*x2+a2*nx5*nx2+a10*x5+a10*nx5*nx6+a10*nx5*x6+*x4*nx3+a16*x4*x3+a16*nx4*x1+a16*nx4*nx1+a24+a25=+a10+a16+a24+a25

J4=a1+a3*x5+a6*x4+a7*nx6+a10*nx5*x6+a13*x2+a16*x4*x3+a16*nx4*x1+a16*nx4*nx1+a17+a19=a1+a3*x5+a6*x4+a7*nx6+a10*nx5*x6+a13*x2+a16*x4*x3+a16*nx4+a17+a19=a2*nx5*x2+a2*nx5*nx2+a4*x2+a4*nx2+a5*x2+a5*nx2+a9+a14+a15*x4+a15*nx4*nx3+a21*nx4*x3+a21*nx4*nx3+a22*x4*x3+a22*x4*nx3+a22*nx4*x1+a22*nx4*nx1+a24=a2*nx5+a4+a5+a9+a14+a15*x4+a15*nx4*nx3+a21*nx4+a22+a24=a1+a3*x5+a3*nx5*nx2+a6*nx4+a6*x4+a23=a1+a3*x5+a3*nx5*nx2+a6+a23

K5=a4*x2+a5*x2+a10*nx5*x6+a12+a13*x2+a13*nx2+a24=*x2+a5*x2+a10*nx5*x6+a12+a13+a24

Для повышения функциональности схемы можно выделить одинаковые элементы:

Z₁ = nx5+nx6                          Z₅ = nx4+x1                           

Z₂ = x4+nx3                            Z₆ = nx4+x3

Z₃ = nx4+nx1                          Z₇ = nx4+nx3₄ = x4+x3

Выполняем необходимые превращения для представления ФЗ в рамках нужной серии:

J1=a6*x4+a10*x5+a10*z1+a16*z2+a22*z2=n((na6+nx4) (na10+nx5) (na10+nz1) (na16+nz2) (na22+nz2))=a6*nx4+a7*x6+a9+a16*z3+a17+a19+a20=n((na6+x4) (na7+nx6) (na16+nz3)*na9*na17*na19*na20)=a3*nx1+a13*x2+a24=n((na3+x1) (na13+nx2)*na24)=a2*x5+a2*nx5*x2+a5*x2+a7*x6+a14+a16*z4+a16*z5=n((na2+nx5)*

(na2+n (nx5*x2)) (na5+nx2) (na7+nx6) (na16+nz4) (na16+nz5)*na14)=a3*nx5+a5+a15*x4+a22*z4+a22*z5+a25=n((na3+x5) (na15+nx4)*

(na22+nz4) (na22+nz5)*na5*na25)=a1+a13*nx2+a15*z6+a21*z6=n((na1*(na13+x2) (na15+nz6) (na21+nz6))

K2=a10*z1+a11*x1+a12+a14+a22*z3+a23+a25+a26=n((na10+nz1) (na11+nx1) (na22+nz3)*na12*na14*na23*na25*na26)=a2*nx5+a4+a21*x4=n((na2+x5) (na21+nx4)*na4)

K4=a3*x5+a3*nx5*nx2+a4*nx2+a10*nx5*x6+a15*z7+a18+a20=n((na3+ nx5) (na3+n (nx5*nx2)) (na4+x2) ((na10+n (nx5*x6)) (na15+nz7)*na18*na20)=a7*nx6+a8+a9+a21*z7+a26=n((na7+x6) (na21+nz7)*na8*na9*na26)

Формируем функции выходов автомата:

Y1=a7+a12+a15+a21=n (na7*na12*na15*na21)

Y2=a2+a7+a8+a9=n (na2*na7*na8*na9)=a3+a6+a10+a14+a19+a25=n (na3*na6*na10*na14*na19*na25)=a6+a9+a17+a18+a23+a24=n (na6*na9*na17*na18*na23*na24)=a2+a5+a6+a16+a18+a22+a24=n (na2*na5*na6*na16*na18*na22*na24)=a10+a20+a26=n (na10*na20*na26)=a4+a11=n (na4*na11)=a13+a15+a21=n (na13*na15*na21)=a5+a12+a16+a22=n (na5*na12*na16*na22)10=a19+a25=n (na19*na25)

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

.3 Автомат Моли

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

b1 - 00000            b3 - 00011   b8 -   00111- 00001        b7 - 00101   b9 - 01011- 00010 b10 - 01001 b11 - 10011

b17 -  00100          b12 - 10001 b16 - 10101

b18 -  01000          b2 - 00110 b19 - 11001

b22 -  10000          b5 - 01010   b21 - 11010

b13 - 10010

b6 - 0110015 - 10100

b20 - 11000

Записываем результаты в таблицу:

D₁= b9*nx5*nx6+b9*nx5*x6+b10*x1+b14*x4+b17+b18+b19nx4*x3+b20*nx4* nx1+b20*x4*x3+b20*nx4*x1+b22= b9*nx5+b10*x1+b14*x4+b17+b18+b19nx4*x3+b20*nx4+b20*x4*x3+b22

D₂= b4*x2+b4*nx2+b7+b8+b9*x5+b14*nx4*x3+b15*x4*x3+b15*nx4*x1+b15* nx4*nx1+b17+b18+b19*x4= b4+b7+b8+b9*x5+b14*nx4*x3+b15*x4*x3+b15*nx4+b17+b18+b19*x4

D₃= b1+b4*nx2+b5*nx4+b5*x4+b6*x6+b14*x4+b14*nx4*nx3+b15*x4*nx3+ b16+ b20*nx4*nx1+b22= b1+b4*nx2+b5+b6*x6+b14*x4+b14*nx4*nx3+b15*x4*nx3+ b16+b20*nx4*nx1+b22

D₄ = b1+b4*x2+b5*x4+b7+b10*nx1+b11+b12*nx2+b12*x2+b13+b19*x4= b1+b4*x2+b5*x4+b7+b10*nx1+b11+b12+b13+b19*x4

D₅=b2+b3+b5*nx4+b5*x4+b6*nx6+b6*x6+b7+b8+b9*x5+b9*nx5*nx6+ b10*nx1+b10*x1+b12*nx2+b13+b14*x4+b17= b2+b3+b5+b6+b7+b8+b9*x5+b9*nx5*nx6+ b10+b12*nx2+b13+b14*x4+b17

Исходные состояния автомата Моли:

Y₁ = b4*nx2+b10*nx1+b11+b12*x2+b17

Y₂ = b1+b4*nx2+b5*nx4+b5*x4+b6*x6= b1+b4*nx2+b5+b6*x6

Y₃= b4*x2+b7+b12*nx2+b14*nx4*nx3+b15*x4*nx3+b19*nx4*nx3+b20*x4*nx3

Y₄ = b4*x2+b5*x4+b14*x4+b16+b19*x4+b21₅ = b1+b3+b4*x2+b6*nx6+b15*nx4*nx1+b16+b18+b20*nx4*nx1+b21+b22₆ = b7+b14*nx4*x3+b15*x4*x3+b15*nx4*x1+b19*nx4*x3+b20*x4*x3+ b20*nx4*x1

Y₇ = b2+b8+b9*x5

Y₈ = b9*nx5*nx6+b10*x1+b11+b12*x2+b17₉ = b3+b6*nx6+b10*nx1+b15*nx4*nx1+b18+b20*nx4*nx1+b22₁₀ = b14*nx4*nx3+b18*x4*nx3+b19*nx4*nx3+b20*x4*nx3

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

Заключение

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

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