Мінімізація логічних функцій методом Карно – Вейча

Метод Карно і Вейча дозволяє виконати мінімізацію функцій графічно. Карта Карно для ДДНФ (діаграма Вейча — для ДКНФ) є аналогом таблиці істинності, зображеній у спеціальній формі. Кількість клітинок у карти визначається за виразом K=2^m , де m- кількість змінних, що описують логічну функцію. Кожна клітинка описується прямими або інверсними значеннями усіх змінних.

Карта заповнюється за допомогою таблиці істинності чи логічних виразів ДДНФ або ДКНФ.

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

Чим більше одиниць чи нулів у середині області, тим меншою кількістю змінних буде описуватись ця область.

Якщо змінна в середині області змінює своє значення, то вона не буде описувати цю область.

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

Такі карти Карно мають вид таблиці 2х2, рис 1., де в клітках вказано відповідні мінтерми у виді аналітичних формул.

Нехай функція f задана у вигляді таблиці істинності (табл.2.).

Запишемо її ДДНФ та заповнимо карту Карно (рис.2) відповідно до рис.1: в ті комірки, що відповідають мінтермам функції f ставимо 1, всі інші комірки заповнюються 0.

					Таблиця 2
				Значення	Значення	ДДНФ
	аргументу	функції
				x2	x1	f	мінтерм
				---
				---
Рис. 1.							Рис.2

В побудованій карті Карно виділимо області, що об’єднують 1. В нашому випадку це одна область - правий стовпчик карти Карно.

Аналізуємо, які змінні всередині області змінюють своє значення, а які ні.

Як видно з рис.2. змінна x₁ для верхньої 1 приймає значення , а для нижньої 1 - . Тобто ця змінна змінює своє значення всередині області, тому вона не характеризує цю область. Змінна x₂ для обох одиниць приймає значення , тому вона цю область характеризує.

Отже тоді мінімізована функція f буде записана в наступному вигляді:

За однією і тією ж картою Карно можна записувати як МДНФ так і МКНФ, але для них беруться інверсні значення:

- якщо карта заповнена по 1, то МДНФ – записується з прямими змінними, а МКНФ – з інверсними;

- якщо карта заповнена по 0, то МКНФ – записується з прямими значеннями, а МДНФ – з інверсними.

Наприклад, для функції f (рис.2) МКНФ (область виділена пунктиром) буде записана в наступному вигляді:

Як бачимо, для даної функції записи МДНФ та МКНФ співпали.

Структура карти Карно для функцій трьох змінних має вид таблиці 2х4, рис.3.

Рис. 3.

Рис.4.

Розглянемо приклад мінімізації функції від трьох змінних, якщо вже задана карта Карно (рис.4.)

Проектування і особливості роботи комбінаційних цифрових пристроїв (КЦП)

Початковими даними для проектування є опис алгоритму функціонування КЦП, вимоги до основних електричних параметрів, бібліотека елементів і конструктивно-технологічні особливості побудови логічних схем.

На шляху від початкового опису алгоритму функціонування до логічної схеми КЦП можна виділити декілька основних етапів:

1. Словесний опис алгоритму функціонування КЦП;

2. Складання таблиці істинності;

3. Запис логічного виразу в ДДНФ або ДКНФ;

4. Мінімізація логічних функцій будь-яким методом;

5. Побудова схеми, яка реалізує кінцевий вираз в будь-якому базисі;

6. Перевірка працездатності спроектованої логічної схеми.

7. Проаналізувати значення функції для кожної комбінації значень аргументів.

Робота пристрою може бути задана у вигляді придатному для мінімізації (етап 2 або 3).

Для виконання синтезу ЦП в базисі І, АБО, НЕ можна використовувати як логічний вираз f_МДНФ так і логічний вираз f_МКНФ.

Нехай робота цифрового пристрою задана таблицею істинності (рис.1)

х3х2х1	f(x1x2x3)	ДДНФ	ДКНФ	Запишемо логічну функцію:
0 0 0			---
0 0 1			---
0 1 0		---
0 1 1		---		Як бачимо, ДДНФ більш проста, тому використовуючи карти Карно знайдемо її мінімальне значення для МДНФ:
1 0 0		---
1 0 1		---		1 1
1 1 0			---
1 1 1		---
Рис. 1.

Розглянемо синтез КЦП в базисі І, АБО, НЕ використовуючи логічну функцію f_МДНФ

Для побудови схеми вкажемо тип логічних елементів та їх кількість. Потрібно:

- 2 елемент «НЕ» Þ та

- 2 елементи «І» Þ (має 2 входи) та (має 3 входи)

- 1 елемент «АБО» Þ для отримання результуючої функції f_МДНФ

-

Будуємо схему	Перевірка роботи схеми
	х3 x2 x1
0 1 0
1 1 0	?

Під час розроблення складних логічних пристроїв доводиться послідовно виконувати операції типу І-НЕ, АБО-НЕ над різною кількістю змінних. Щоб перетворити логічну функцію f_МДНФ або f_МКНФ використовують закон подвійного заперечення та правило де Моргана, таблиця 1.

Табл. 1.

• ⇐ Назад
• 1
• 23