Синтез комбінаційної схеми

Синтез комбінаційної схеми

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

.1 Визначення значень БФ

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

А= 1011000;

В= X101000;

С= XXXXXXX;

(А+В+С) = XX11001;

Відповідно, значення функцій F(x1,x2,x3,x4,x5) на наборах від 0 до 31 буде мати вигляд:

Таблиця 1

1.2 Мінімізація БФ (Карти Карно)

Отримуємо МДНФ і МКНФ булевой функції за допомогою метода карт Карно. Схеми карт Карно приведені нижче:

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

В результаті мінімізації, отримаємо:

=|x3|x4|x5+x1x4x5+|x2|x3x4+|x1|x3x4|x5

Таблиця 3 - Карта Карно для МКНФ

В результаті мінімізації, отримаємо:

Y=(x4+|x5)(x1+|x3)(x1+|x2+|x5)(|x1+|)

1.3 Мінімізація БФ (Квайна-МакКласки)

Отримуємо МДНФ і МКНФ булевої функції за допомогою метода Квайна-МакКласки. Для цього будуємо комплекси кубів, які відрізняються між собою кількістю одиниць ( в двох сусідніх кубів ця різниця дорівнює одиниці ) і склеюємо набори сусідніх кубів які відрізняються лише однією одиницею. Біля наборів що склеюються ставимо знак “ü”.Далі набори що склеюються повинні відрізнятись на одиницю і мати спільні Х. Склеювання проводимо поки не залишиться лише не склеюванні набори.

Спочатку знайдемо МДНФ. Комплекси кубів та їх склеювання.

C0:

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

C1:

X0 ü

X000 ü

X0000 ü

X ü

X010 ü

X0010 ü

X0 ü

X1000 ü

X ü

X0 ü

X00 ü

X000 ü

X11 ü

X0011 ü

X10

X1 ü

X01 ü

X ü

X10 ü

X ü

X0 ü

X100 ü

X00 ü

X111 ü

X0111 ü

X ü

X1110 ü

X11 ü

X011 ü

X1 ü

X101 ü

X ü

X110 ü

X ü

X0 ü

X1111 ü

X111 ü

X11 ü

X1 ü

C2 :

X0X0

X00X0

XX000

X001X

XX ü

XX0 ü

X0X ü

XX00

X0X11

XX1 ü

X1X ü

XX ü

X10X ü

X1X0 ü

XX111

X111X

XX11

X1X1 ü

X11X ü

XX ü

C3:

XXX

X1XXX

X1X1

Складемо таблицю покривань:

Таблиця 4 - Покривання

Ядро: X0X11

Будуємо скорочену таблицю покривань:

Таблиця 5 - Скорочена таблиця покривань

Найменша МДНФ:

Y=x1x4x5+|x1x2x4|x5+|x1|x3|x5+|x3|x4|x5+|x2|x3|x5+|x2|x3x4+x1|x4|x5+|x2x4x5+x3x4x5

Тепер знайдемо МКНФ. Для цього повторимо всі попередні дії для ДНФ.

C0:

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

ü

C1:

X01 ü

X001 ü

X0001 ü

X ü

X0 ü

X100 ü

X ü

X0 ü

X00 ü

X1 ü

X101 ü

X0101 ü

X ü

X110 ü

X0110 ü

X1 ü

X01 ü

X1001 ü

X ü

X0 ü

X1100 ü

X1 ü

X01 ü

X001 ü

X1 ü

X10 ü

X010 ü

X ü

X0 ü

X100 ü

X111 ü

X11 ü

X1101 ü

X1 ü

X1110 ü

X ü

X101 ü

X110 ü

X01 ü

X10 ü

X0 ü

X ü

X1111 ü

X1 ü

X ü

C2:

XXX01

0X1XX

XX10X

XX1X0

X11XX

Таблиця покривань приведена нижче:

Таблиця 6 - Покривання

Ядро: XXX01

XX1

XX10

Будуємо скорочену таблицю покривань:

Таблиця 7 - Скорочена таблиця покривань

Найменша МКНФ:

Y=(x4+|x5)(x1+|x2+|x5)( |x1+x3)( |x3+x4)( |x3+x5) (|x2+|x3)

1.4 Опис мінімізації БФ заданими методами

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

Такий підхід обумовлений тим, що:

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

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

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

Для даних функцій ми маємо:

С(МДНФ)=43

С(МКНФ)=21

Так як ціна МКНФ менше, то для реалізації схеми будемо використовувати МКНФ.

1.5 Приведення БФ до заданого базису

Заданий базис: 3 АБО, так як це не повний функціональний базис, то ми використовуємо базис 3 АБО-НІ.

Y=|(|(Х1Х3))+|(|(|Х3|X5))+|(|(|X1|X2|X3))+|(|(|X2|X4|X5))+|(|(X2X4|X5))+ |(|(|X1X2|X4X5))

Для реалізації функції по останньому виразу необхідно 15 елементів 3 АБО-НІ (Рис.1). Ранг даної схеми дорівнює 5.

Рисунок 1 - Комбінаційна схема

1.6 Аналіз комбінаційної схеми методом П-алгоритму

Для аналізу методом П-алгоритму ми пронумерували кожен вихід елемента схеми.

Нульове покриття С0:

10XX0

XX10

XXX01

X1XX

2. Проектування керуючих автоматів Мілі та Мура

2.1 Вибір вихідних даних

Граф схема складається з чотирьох блоків E,F,G,H і вершин BEGIN та END.

Вони обираються наступним чином:

блок E 17 mod 5 = 2;

- блок F 7 mod 5 = 2;

блок G 1 mod 5 = 1;

блок H 25 mod 5 = 0.

Блоки E, F, G, H з’єднуються між собою схемою яка має вигляд :

Рисунок 2 - Алгоритм

Граф-схема алгоритму показана в додатку 1.

Тип тригера обирається за формулою: 17mod4=1.

Отже для автомата Мілі використовуємо D тригер, а для Мура - JK. Серія інтегральних мікросхем для побудови принципових мікросхем КР 555.

2.2 Структурний синтез автомата Мілі

2.2.1 Розмітка ГСА для автомата Мілі

Для автомата Мілі розмітка ГСА позначається буквою bi. Відмічаються входи в вершини, які слідують за операторними. Виходячи з цього ми отримуємо для автомата Мілі 21 стан.

2.2.2 Кодування станів

Оскільки ми використовуємо D тригер, а його особливістю є те, що вихід тригера такий же як стан у момент часу (t+1), то для оптимального кодування будуємо таблицю переключення автомата, тобто записуємо скільки разів автомат переключається у певний стан.

Таблиця 8 - Переключення автомата

Оптимальне кодування станів буде таким:

Таблиця 9 - Оптимальне кодування станів

2.2.3 Таблиця переходів автомата Мілі

На основі ГСА і закодованих стані будуємо таблицю 10 переходів автомата.

Останній стовбець таблиці 10 заповнюється за допомогою оберненої таблиці переходів D- тригера .

булевий мінімізація комбінаційний керуючий автомат

Таблиця 10 - Переходи автомата

Побудуємо на основі останньої колонки Таблиці 13 функції збудження і приведемо їх до базису І-НІ:

D1=| (| (b2x1) | (b7|x5|x6) |(b12|x3) |b13|b14|(b15x4) |(b15|x1|x2|x4) |b16|(b18|x3x4) | (b18x3x4) |(b18|x4x1) |(b19|x1))

D2=|(|b0|(b2|x1) |b6|(b10|x5x6) |(b11x2) |b11|(b12x4) |b13|b14|b16|(b17x3) |(b18|x1x3|x4))

D3=|(|b4|b5|(b7|x5x6) | (b10x5) |(b10|x5|x6) |(b10Vx5x6) |(b11|x2) |(b12x4) |b13|(b15x4) |(b15|x1|x2) |(b19|x1))

D5=|(|b0|b1|(b2|x1) |(b5|x1) |b5x7) |(b7|x5x6) |b8|(b9|x2) |(b12|x3) |(b18|3x4))

На основі передостанньої колонки Таблиці 10 будуємо функції виходу:

Y1=|(|(b2|x1) | (b5|x1) | (b10|x5x6) | (b11x2) |b14|b16)

Y2=|(|b0|b3| (b9x2) |b14|b16|(b17|x3) |(b18|x1|x3|x4) |b20)

Y3=|(|b|(b7|x5x6) |b8| (b9|x2) |(b11x2) |(b12|x3) |(b15x4) |(b18|x3x4))

Y4=|(|b0|b3|(b9x2) |(b12x4) |b13|(b15|x4x2))

Y5=|(|b13|(b15x2|x4) |(b15|x1|x2|x4) |b19)

Y6=|(|b6|b8|(b9|x2) |(b11x2) |(b16|x3) |(b18x3x4)(b18x1|x4) |(b18|x1|x3|x4) |b20)

Y7=|(|b1|b4|(b7x5) |(b10x5) |(b17x3) |(b18|x1x3|x4))

Y8=|(| (b2|x1) |(b5x1) |b7|x5|x6) |(b10|x5|x6) |(b11|x2))

Y9=|(|(b2|x1) |(b5|x1) |(b15|x1|x2|x4) |(b19|x1))

Y10=|(|(b12|x3) |(b18x4|x3))

За отриманими функціями збудження та виходу будуємо схему автомата Мілі. Вона представлена у додатку 2.

2.3 Структурний синтез автомата Мура

2.3.1 Розмітка ГСА для автомата Мура

Для автомата Мура розмітка ГСА позначається буквою аi (Додаток 1).

Відмічаються всі операторні вершини, вершина початку та кінця позначається а0. Таким чином для автомата Мура ми отримали 23 стани.

2.3.2 Кодування станів

Для оптимального кодування станів автомата використовуємо евристичний метод. Для цього будуємо матрицю Т. Перший стовбець цієї матриці номер вихідного стану, другий - номер стану в який переключається автомат, а третій кількість переходів між даними станами.

Матриця Т:

Оптимальне кодування станів буде таким:

Таблиця 11 - Оптимальне кодування станів

2.3.3 Таблиця переходів автомата Мура

На основі ГСА і закодованих стані будуємо таблицю13 переходів автомата.

Останній стовбець таблиці 12 заповнюється за допомогою оберненої таблиці переходів JK- тригера ( таблиця 12 ).

Таблиця 12 - Обернена таблиці переходів JK- тригера

Таблиця 13 - Переходи автомата

Побудуємо на основі останнього cтовпця функції збудження і переведемо ці функції у зручний базис (і-ні).

J1=|(|a4|a5|(a12|x3x4) |(a13|x3x4))=|(|a1|(a9|x1) |(a11x2) |(a18x2|x4))=|(|a0|a1|(a5|x2)|(a9x1) |a10|(a13x3x4) |(a13x1|x4) |(a13|x1|x3|x4) |(a18x4))=|(|a4|(a8x5) |(a8|x5|x6) |a10|a14|a16|a21|(a22x1))=|(|a6|(a13x3x4) |(a13x1|x4) |(a13|x1x3|x4) |(a18x1|x2|x4) |a19|a21)=|(|(a3x5) |(a3|x5|x6) |a15|a16)=|(|a7|(a8x5) |(a8|x5|x6) |(a8|x5x6) |a19)=|(|a2x1) |(a3|x5|x6) |a4|(a8x5) |(a12x4) |(a12|x3|x4) |(a17x3) |a21)=|(|a2|x1) |(a3|x5x6) |(a5x2) |(a9|x1) |(a11|x2) |(a18|x1|x2|x4) |a20)=|(|(a3|x5x6) |a12|x3|x4) |(a17|x3) |(a22|x1))=a4+a10+a12+a18=a1+a7+a18+a21=a3+a6+a8+a16+a20=a1+a7+a14+a15+a19=a13+a15+a19=a3+a8+a17+a21=a2+a9+a22=a5+a11+a12=a4+a10+a13=a16

За отриманими функціями збудження та виходу будуємо схему автомата Мура. Вона представлена у додатку 3.