Главная | Обратная связь | Поможем написать вашу работу!

Мінімізація логічних функцій із застосуванням карт Карно

Карта Карно є специфічною формою зображення таблиці істинності ЛФ, що подана у вигляді ДДНФ.

Загальний вигляд карти Карно для функцій двох, трьох і чотирьох змінних поданий на рисунку 1.8. У клітинках карт також наведені, як довідкова інформація для полегшення їх заповнення, двійкові набори аргументів та їх десяткові порядкові номери у порядку їх звичайного розташування у таблицях істинності – від набору x₁ =…= x_n = 0 до набору x₁ =…= x_n = 1.

n = 2

n = 3

n = 4

n = 3

Рис. 1.8. Загальний вигляд карт Карно для функцій 2-х, 3-х, і 4-х змінних

Слід звернути увагу на те, що така нумерація відповідає порядку слідування аргументів x₁x₂x₃x₄ у кодовому слові (аргумент з більшим індексом – молодший). Для зворотного порядку індексації нумерація клітинок карти буде іншою.

Кількість клітинок карти дорівнює числу можливих варіантів вхідних слів (наборів аргументів) і при кількості аргументів n дорівнює 2ⁿ. У кожну клітинку ставиться 1 тільки у тому випадку, якщо набір аргументів, який відповідає цій клітинці, присутній у запису функції у вигляді ДДНФ, тобто функція на цьому наборі має значення одиниці (нульові значення функції в карті розміщати необов’язково). Фактично при заповненні карти Карно одиницями аргументи ЛФ та їх інверсії, які записані навколо карти, використовуються як координати відповідних клітинок.

За цих умов кількість аргументів у членах мінімізованої ЛФ буде мінімальною. При охопленні усіх точок карти Карно слід пам’ятати, що права та ліва границі карти – це сусідні стовпчики, так само, як верхній та нижній рядки карти Карно – це сусідні рядки (наприклад, чотири одиниці, розташовані в кутах карти, утворюють один контур).

На рисунку 1.9 зображено три варіанти вибору замкнених областей на тій самій карті Карно, оптимальним у даному випадку, очевидно, є варіант, зображений ліворуч.

Рис. 1.9. Варіанти вибору замкнених областей на карті Карно

2. Кожна замкнена область на карті Карно у мінімізованій ЛФ буде подана членом, кількість аргументів якого на k менша загального числа аргументів функції (тобто n - k). Тільки ті аргументи (або їх інверсії) будуть присутні у цьому члені, які в середині даної області не змінюють свого значення. Тобто це означає, що вони в середині цієї області мають значення тільки з інверсією, або тільки без інверсії.

Пояснити це можна таким чином. Для ЛЕ АБО з двома входами (ДДНФ логічної функції ) ця карта матиме вигляд:

Мінімізуючи цю ДДНФ у прикладі, який був розглянутий раніше, ми користувалися правилом склеювання:

Цей запис відповідає області, що охоплює дві верхні клітинки карти Карно елемента АБО. Ми бачимо, що в результаті склеювання у нас залишився тільки аргумент х₁, який в обох клітинках даної області присутній тільки без інверсії. Аргумент х₂, який у лівій клітинці має значення без інверсії, а у правій – з інверсією, виключений з остаточного виразу.

Для області, що охоплює дві ліві клітинки карти, маємо:

Остаточно маємо:

Таким чином, ми фактично виконали операцію склеювання за допомогою карти Карно.

Треба також зазначити, що якщо для карти Карно кількість нулів значно менша за кількість одиниць, то зручніше склеювати саме їх. Не треба тільки забувати, що у цьому випадку ми отримаємо не найменшу функцію, а її інверсію, яку потім треба проінвертувати.

Інколи, при проектуванні конкретних цифрових пристроїв, заздалегідь відомо, що деякі вхідні слова ніколи не використовуються (використання їх в даній схемі заборонено). На цих наборах ЛФ можна довизначити за власним бажанням аби максимально спростити її мінімізацію. Наведемо приклад такого довизначення ЛФ під час її мінімізації. Нехай на рисунку 1.10 картою Карно подана деяка ЛФ, невизначені значення якої позначені літерою X.


	X		X
		X
X
	X

Рис. 1.10. Приклад довизначення логічної функції

Як можна побачити на остаточному варіанті карти Карно, який показано праворуч від початкового варіанта карти, три верхні невизначені значення функції було замінено на одиниці, а два нижні значення – на нулі. Таким чином вдалося створити лише два контури по чотири одиниці, тобто зменшити кількість членів мінімізованої ДНФ до двох, в кожному з яких є тільки два аргументи.

Розглянемо приклад застосування алгоритму синтезу логічного пристрою з одним виходом, ЛФ якого є функцією чотирьох змінних і подана у вигляді таблиці 1.9.

Таблиця 1.9

х₁

х₂

х₃

х₄

Відповідна ЛФ у вигляді ДДНФ:

На підставі даної таблиці та отриманої ЛФ будуємо карту Карно, на якій позначаємо як визначені, так і невизначені значення функції, як показано на рисунку 1.11.




		X

Рис. 1.11. Довизначення ЛФ, заданої таблицею 1.9

Як можна легко помітити, при заміні невизначеного значення на одиницю проблема покриття площі карти мережею замкнених областей може бути вирішена досить просто. Мінімізована функція матиме вигляд:

Пояснити відсутність змінних х₃ та х₄ можна дуже просто. Це означає, що для кожного набору змінних, де функція має значення логічної 1, можна знайти такий самий набір (за винятком змінних х₃ та х₄, які на ньому мають протилежні значення), де функція теж має значення логічної 1. Це переконливо свідчить про те, що функція у не залежить від вказаних вище аргументів.

Запишемо мінімізовану функцію у базисі АБО-НІ. Для цього застосуємо закон інверсії або правило де Моргана:

Структурну схему синтезованого логічного пристрою зображено на рисунку 1.12.

Таким чином, карта Карно фактично дозволяє одночасно виконати всі операції склеювання, які можливі для ЛФ, поданої у ДДНФ. Після застосування карти Карно подальша мінімізація ЛФ іноді ще можлива – за умови переходу до логічних базисів, які містять більш складні ЛЕ (наприклад, суматори по модулю два), або за рахунок застосування розподільного закону.

Рис. 1.12. Схема синтезованого логічного пристрою

⇐ Предыдущая 2 3 4 5 678 9 10 11 Следующая ⇒