Курсовий проект
з дисципліни «Схемотехніка ЕОМ»
На тему «Мінімізація і факторизація булевої функції»
Зміст
Введення
. Вихідні дані
. Побудова карт Карно
. Перехід від булевих виразів до функціональних схемами
. Мінімізація заданої функції
. Факторизація покриттів
. Схемних реалізація факторізірованного покриття
. Переклад схеми в універсальний базис
. Опис роботи схеми
Висновок
Список використаних джерел
Введення
Мета роботи: перетворити дану булеву функцію, мінімізувати її призвести факторизацию, оцінити економію, а також виконати схемну реалізацію факторізовано покриття.
При переході від кубічної записи булевої функції до функціональної схемою змінні одного куба об'єднуються знаком кон'юнкції, тобто є входами однієї схеми І, все куби об'єднуються один з одним знаком диз'юнкції, тобто виходи схем І є входами однієї схеми АБО. Біля входу схеми І ставиться змінна без інверсії, якщо на відповідному місці в кубі коштує 1; з інверсією, якщо на відповідному місці в кубі варто нуль; вхід залишається порожнім, якщо на відповідній місці стоїть X.
1. Вихідні дані
Варіант №12
Тип множества12L011X0 0011X 101X1 00X0X 111XX 0X010 01011
Малюнок 1
. Побудова карт Карно
Для проведення мінімізації складемо карти Карно для п'яти змінних за наступною схемою
Малюнок 2 - Карта Карно п'яти змінних
Даний набір містить в собі куби різному розмірності: одновимірної, двомірної і нульовий.
Одновимірна куб E12. На цьому кубі змінна x1 може приймати значення 0 і I. Для кожного значення x1 функція F (x1) також може приймати значення або 0, або 1.
. Двовимірний куб ^ * На цьому кубі змінні я ж ^ можуть приймати одне із значень 0 мулу I; всього можливо чотирьох комбінації, - що отпечено на рис.3 гуртками. На першій позиції кожної комбінації відзначено значення х (, на другий -позіціі - зс ^, Для кожної з комбінацій я ,: одне аз значень; 0 або I.
.
Двовимірний куб E 2 2. На цьому кубі змінні x 1 і x 2 можуть приймати одне із значень: 0 або 1. Для кожної з комбінацій x 1 x 2 функція F (x 1 x 2) може приймати одне із значень: 0 або 1.
У вихідних даних задана функція F (x 1, x 2, x 3, х 4, х 5), яка дорівнює 1 на наступних наборах
Диз'юнктивна нормальна форма такої функції
.
Побудуємо для даної функції карти Карно
Малюнок 3 - Карта Карно для вихідних даних
Побудова карт Карно за даними функціям вироблялося наступним чином, на прикладі набору 011X0. Так як друга і п'ята координата куба рівні 0, а друга і третя рівні 1, то одиниці проставляємо у всіх клітинах, де друга і п'ята координата куба рівні 0, а друга і третя рівні 1. Четверта позиція може бути як дорівнює 0 так і 1 , що проставляємо одиниці в клітинах, де четверта позиція дорівнює 0, або 1. Аналогічно заповнюються клітини для залишилися кубів
. Перехід від булевих виразів до функціональних схемами
При переході від кубічної записи булевої функції до функціональної схемою змінні одного куба об'єднуються знаком кон'юнкції, тобто є входами однієї схеми І, все куби об'єднуються один з одним знаком диз'юнкції, тобто виходи схем І є входами однієї схеми АБО. Біля входу схеми І ставиться змінна без інверсії, якщо на відповідному місці в кубі коштує 1; з інверсією, якщо на відповідному місці в кубі варто нуль; вхід залишається порожнім, якщо на відповідній місці стоїть X.
Будуємо функціональну схему для вихідних даних.
Знайдемо вартість схеми за такою формулою:
, (1)
Де n - загальне число координат, - розмірність куба
К - число кубів, на яких функція дорівнює 1
Малюнок 4 - функціональна схема
. Мінімізація заданої функції
Використовуються наступні принципи мінімізації:
. Побудувати максимальні куби на клітинах, де функцій 1 (прості імпліканти).
. Знайти клітини, які покриваються тільки одним кубом (відокремлені клітини або вершини куба).
. Включити в мінімальне покриття все куби, які п...
