Мінімізація логічних елементів

Важливим етапом проектування комп’ютерних схем є мінімізація мулевих функцій, тобто знаходження їхніх виражень з мінімальним числом букв. Мінімізація забезпечує побудову економічних схем комп’ютерів.

Пошук канонічної форми запису є початковим етапом синтезу логічних схем. Найбільше поширення одержали досконала диз'юнктивна нормальна форма (ДДНФ) і досконала кон’юнктивна нормальна форма (ДКНФ). Для одержання цих форм вводяться поняття мінтермів (конституєнта 1) і макстермів (конституєнта 0).

Мінтерм — це функція п змінних, яка дорівнює одиниці тільки на одному наборі. Мінтерм одержують як кон'юнкцію п змінних, що входять до нього у прямому виді, якщо значення даної змінної в наборі X_і = 1, і – із запереченням, якщо Х_і = 0. При п змінних є 2ⁿ мінтермів m₀,m1,…, m_R, де R = 2ⁿ – 1. Всі мінтерми двох змінних наведені в таблиці 1.

Таблиця 1

Мінтерми двох змінних

X1	Х2	F9		Мінтерми	Макстерми
					M
					M
					M
					M

Значення функції F₉, які відповідають, згідно з таблицею істинності, кожному i-му наборові, позначені через , , , . Представлення функції F₉ у ДДНФ є диз'юнктивною сумою мінтермів, які відповідають наборам змінних, для яких = 1:

Макстерм — це функція п змінних, яка дорівнює нулю тільки на одному наборі. Макстерм одержують як диз'юнкцію усіх змінних, що входять до нього у прямому ви­гляді, коли значення X_i = 0, або в інверсному вигляді, якщо значення X_i = 1. Число макстермів дорівнює 2ⁿ, для функції двох змінних вони наведені в табл. 1. Пред­ставлення функції F9 у ДКНФ записується у вигляді:

Методи мінімізації:

1. Спрощення функції із використанням аксіом та законів алгебри логіки.

2. Діаграми Вейча (карти Карно)

3. Метод Квайна-Мак Класкі (табличний)

Розглянемо метод мінімізації за допомогою діаграм Вейча.

	1	1	.	.

Кожна клітинка діаграми Вейча відповідає одному з наборів змінних (конституенті 1). В клітинці записується значення функції, яке вона приймає на даному наборі. Сусідні клітинки можна включати в об’єднання (2, 4, 8, 16… клітинок)

Для даного об’єднання в доданку функції залишаться тільки ті змінні, які не змінюють свого значення для всіх клітинок об’єднання.

Приклади мінімізації Вейча:

а)

	x1
x2	1	1
		x3

б)

	x1
x2	1		1
		x3

в)

	x1
x2	1
1			1	x4
		x3

г)

	x1
x2	1
1		1		x4
		x3

4. Базові логічні елементи (комбінаційні схеми)

Булеві функції одного і двох аргументів називають елементарними. Схему, яка здійснює елементарну логічну операцію, називають логічним елементом (вентилем). Сукупність взаємозалежних логічних елементів з формальними методами опису називається логічною схемою.

Назви і умовні графічні позначення основних логічних елементів, які застосовуються в комп'ютерній схемотехніці, наведені в табл. 1. Значення змінних (операндів) відображаються електричними сигналами з двома чітко вираженими рівнями значень.

Таблиця 1

Назви і умовні графічні позначення основних логічних елементів

Назва операції	Назва елемента	Запис функції	Умовне графічне позначення	Західний стандарт
Заперечення (інверсія)	НІ
Диз'юнкція (логічне додавання)	АБО (ЧИ)
Кон'юнкція (логічне множення)	І
Заперечення диз'юнкції	АБО-НІ (НЕ ЧИ)
Заперечення кон'юнкції (функція Шеффера)	І-НІ (НЕ І)
Заперечення еквівалентності (нерівнозначність)	Виключаюче АБО
Еквівалентність	Еквівалентність
Імплікація	ЯКЩО, ТО
Заборона	ЗАБОРОНА

Дата добавления: 2014-01-11