Мінімізація систем перемикальних функцій

Мета роботи: оволодіння методом мінімізації систем перемикальних

функцій. Дослідження часових параметрів схем з

багатьма виходами.

Теоретичні відомості

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

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

Задача мінімізації систем перемикальних функцій добре досліджена в класі функціонально повних систем: І, АБО, НЕ. Розглянемо мінімізацію систем функцій у диз’юнктивних нормальних формах булевої алгебри. Для усунення повторення однакових елементів у схемі на етапі мінімізації системи функцій необхідно виявити однакові імпліканти у запису різних функцій.

Для мінімізації можуть бути використані різні методи, зокрема, методи Квайна та Квайна – Мак-Класкі.

Вихідною формою для мінімізації системи функцій методом Квайна та Квайна – Мак-Класкі є ДДНФ системи перемикальних функцій, для отримання якої необхідно подати в ДДНФ кожну функцію. При цьому кожній конституенті одиниці приписується множина ознак, що визначають її приналежність до певної функції.

Етапи мінімізації системи перемикальних функцій наступні:

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

2. Виконати склеювання термів.

3. Виконати всі можливі поглинання.

4. Скласти таблицю покриття.

5. Вибрати покриття для кожної функції.

Відмінності мінімізації систем перемикальних функцій від мінімізації окремих функцій полягають у наступному.

Склеювання здійснюються тільки для тих термів, що мають хоча б одну однакову ознаку. Отриманому в результаті склеювання терму присвоюється множина ознак, що є перетинанням множин ознак термів, які склеюються.

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

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

Під час вибору остаточної форми подання перемикальної функції системи з використанням таблиці покриттів необхідно прагнути до того, щоб загальне число букв у покритті було мінімальним.

Розглянемо мінімізацію системи перемикальних функцій на прикладі.

Допустимо, що система перемикальних функцій задана таблицею істинності (табл. 3. 1). Побудувати комбінаційну схему даної системи на логічних елементах 3І та 2АБО – НЕ.

Згідно з табл. 3. 1 подамо кожну із функцій в ДДНФ:

;

.

Таблиця 3. 1

0 0 0	1	1
0 0 1	0	1
0 1 0	1	0
0 1 1	1	1
1 0 0	0	0
1 0 1	1	0
1 1 0	0	1
1 1 1	1	1

1. Запишемо ДДНФ функції заданої системи, приписуючи кожній конституенті одиниці ознаку входження в функції і :

.

Для зручності виконання склеювання пронумеруємо кожну конституенту одиниці із ДДНФ функції і виконаємо всі склеювання:

:

1 2 3 4 5 6 7

1 – 2. ;

1 – 3. ;

2 – 4. ;

3 – 4. ;

4 – 7. ;

5 – 7. ;

6 – 7. .

Після проведення всіх поглинань, з урахуванням ознак кожної кон’юнкції, одержимо:

.

Подальші склеювання і поглинання неможливі. Одержано прості імпліканти заданої системи перемикальних функцій і .

Складаємо імплікантну таблицю мінімального покриття (табл. 3. 2). Стовпці матриці позначаємо конституентами одиниці із ДДНФ функції . Для кожної конституенти одиниці відводимо стільки стовпців таблиці, скільки різних номерів функцій має ознака конституенти. Рядки таблиці помічаємо простими імплікантами системи булевих функцій. Її заповнення виконується аналогічно методу мінімізації Квайна.

Таблиця 3. 2

Прості імпліканти системи функцій	Конституенти одиниці функції
	1	2	2	1	1	2	1	2	1	2
		+	+
	+	+
	+			+
			+			+
					+	+
				+	+
					+	+			+	+
							+		+
									+	+
								+		+

Ядром функції , очевидно, являються прості імпліканта: ;

. Оскільки ядро функції не покриває всіх стовпців таблиці, знаходимо тупикові функції:

;

;

;

.

За МДНФ функції приймаємо найпростішу тупикову функцію . Тоді МДНФ .

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

; .

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

Аналогічним чином мінімізуємо заперечення функції . За табл. 3. 1 запишемо ДДНФ функції , тобто запишемо конституенти одиниці, при яких функція має нульове значення

.

1 2 3 4 5

Пронумеруємо конституенти одиниці функції і виконаємо всі склеювання:

3 – 4. ;

3 – 5. .

Після проведення всіх поглинань, з урахуванням ознак кожної кон’юнкції, одержимо

.

Так як подальші склеювання і поглинання неможливі, складаємо імплікантну таблицю мінімального покриття (табл. 3. 3).

Очевидно, ядро функції складають прості імпліканти: ; ; ; . Так як ядро функції покриває всі стовпці таблиці, то воно і є МДНФ функції :

.

Звідси ; .

Таблиця 3. 3

Прості імпліканти системи функцій	Конституенти одиниці функції
	1	2	1	2	2	1
	+
		+
				+	+
			+	+
			+			+

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

І /АБО

І – НЕ / І – НЕ

= АБО / І – НЕ

АБО – НЕ / АБО;

І / АБО

І – НЕ / І – НЕ

АБО / І – НЕ

АБО – НЕ / АБО

Виходячи із заперечень функцій системи, запишемо ще чотири нормальні форми:

І / АБО – НЕ

І – НЕ / І

АБО / І

АБО – НЕ / АБО – НЕ

І / АБО – НЕ

І – НЕ / І

АБО / І

АБО – НЕ / АБО - НЕ

Очевидно, що із отриманих восьми нормальних форм в заданому базисі можна реалізувати тільки дві нормальні форми: І / АБО – НЕ і АБО – НЕ / АБО – НЕ.

З урахуванням числа входів логічних елементів функції і в операторній формі І / АБО – НЕ можна подати у вигляді:

; .

Структурна схема комбінаційної схеми системи функцій і на логічних елементах 3І та 2АБО – НЕ показана на рис. 3. 1, а.

Складність даної схеми у числі умовних корпусів мікросхем

Максимальна затримка поширення сигналів від входів комбінаційної схеми до її виходу

t_з = 14 нс + 12 нс = 26 нс

З урахуванням числа входів заданих логічних елементів задану систему функцій в операторній формі АБО – НЕ / АБО – НЕ можна подати у вигляді:

;

.

Структурна схема КС системи функцій на логічних елементах 2АБО – НЕ показана на рис. 3. 1, б.

Рис. 3. 2. Структурна схема системи функцій, побудованої:

а – на логічних елементах 3І, 2АБО-НЕ;

б – на логічних елементах 2АБО - НЕ

Складність даної схеми умовних корпусів мікросхем.

Максимальна затримка поширення сигналів від входів даної комбінаційної схеми до її виходів становить t_З = 12 нс ∙ 4 = 48 нс.

З проведеного аналізу видно, що комбінаційну схему системи функцій варто реалізувати на логічних елементах 3І та 2АБО – НЕ.