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

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

1.1 Визначення значень БФ

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

А= 1 011 000;

В= X101000;

С= XXXXXXX;

(А+В+С) = XX11001;

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

Таблиця 1

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

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

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

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

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

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

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

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

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

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

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

C0:

C1:

000X0

0X000

X0000

0001X

0X010

X0010

010X0

X1000

1000X

100X0

10X00

1X000

00X11

X0011

01X10

100X1

10X01

1001X

10X10

1010X

101X0

1X100

11X00

0X111

X0111

0111X

X1110

10X11

1X011

101X1

1X101

1011X

1X110

1110X

111X0

X1111

1X111

11X11

111X1

1111X

C2 :

0X0X0

X00X0

XX000

X001X

100XX

10XX0

10X0X

1XX00

X0X11

10XX1

10X1X

101XX

1X10X

1X1X0

XX111

X111X

1XX11

1X1X1

1X11X

111XX

C3:

10XXX

1X1XXX

1X1X1

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

Таблиця 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:

00X01

0X001

X0001

0010X

001X0

0X100

1000X

100X0

10X00

001X1

0X101

X0101

0011X

0X110

X0110

010X1

01X01

X1001

0110X

011X0

X1100

100X1

10X01

1X001

100X1

10X10

1X010

1010X

101X0

1X100

0X111

01X11

X1101

011X1

X1110

0111X

1X101

1X110

11X01

11X10

111X0

1110X

X1111

111X1

1111X

C2:

XXX01

0X1XX

XX10X

XX1X0

X11XX

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

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

Ядро: XXX01

01XX1

1XX10

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

Таблиця 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

1XX10

XXX01

0X1XX

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|(b15×4) |(b15|x1|x2|x4) |b16|(b18|x3x4) | (b18x3x4) |(b18|x4x1) |(b19|x1))

D2=|(|b0|(b2|x1) |b6|(b10|x5x6) |(b11×2) |b11|(b12×4) |b13|b14|b16|(b17×3) |(b18|x1x3|x4))

D3=|(|b4|b5|(b7|x5x6) | (b10×5) |(b10|x5|x6) |(b10Vx5x6) |(b11|x2) |(b12×4) |b13|(b15×4) |(b15|x1|x2) |(b19|x1))

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

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

Y1=|(|(b2|x1) | (b5|x1) | (b10|x5x6) | (b11×2) |b14|b16)

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

Y3=|(|b|(b7|x5x6) |b8| (b9|x2) |(b11×2) |(b12|x3) |(b15×4) |(b18|x3x4))

Y4=|(|b0|b3|(b9x2) |(b12×4) |b13|(b15|x4x2))

Y5=|(|b13|(b15×2|x4) |(b15|x1|x2|x4) |b19)

Y6=|(|b6|b8|(b9|x2) |(b11×2) |(b16|x3) |(b18x3x4)(b18×1|x4) |(b18|x1|x3|x4) |b20)

Y7=|(|b1|b4|(b7x5) |(b10×5) |(b17×3) |(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) |(b18×4|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))

J2=|(|a1|(a9|x1) |(a11×2) |(a18×2|x4))

J3=|(|a0|a1|(a5|x2)|(a9x1) |a10|(a13x3x4) |(a13×1|x4) |(a13|x1|x3|x4) |(a18×4))

J4=|(|a4|(a8x5) |(a8|x5|x6) |a10|a14|a16|a21|(a22×1))

J5=|(|a6|(a13x3x4) |(a13×1|x4) |(a13|x1x3|x4) |(a18×1|x2|x4) |a19|a21)

K1=|(|(a3x5) |(a3|x5|x6) |a15|a16)

K2=|(|a7|(a8x5) |(a8|x5|x6) |(a8|x5x6) |a19)

K3=|(|a2x1) |(a3|x5|x6) |a4|(a8x5) |(a12×4) |(a12|x3|x4) |(a17×3) |a21)

K4=|(|a2|x1) |(a3|x5x6) |(a5x2) |(a9|x1) |(a11|x2) |(a18|x1|x2|x4) |a20)

K5=|(|(a3|x5x6) |a12|x3|x4) |(a17|x3) |(a22|x1))

Y1=a4+a10+a12+a18

Y2=a1+a7+a18+a21

Y3=a3+a6+a8+a16+a20

Y4=a1+a7+a14+a15+a19

Y5=a13+a15+a19

Y6=a3+a8+a17+a21

Y7=a2+a9+a22

Y8=a5+a11+a12

Y9=a4+a10+a13

Y10=a16

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