Оптимізація логічних функцій. Карти Карно

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

Карти «Карно» були запропоновані в 1953 фізиком Морісом Карно як вдосконалений варіант діаграм, винайдених в 1952 році Едвардом В. Вейчем, і були покликані допомогти спростити цифрові електронні схеми.

У карту Карно булеві змінні передаються з таблиці істинності і упорядковуються за допомогою коду Грея, в якому кожне наступне число відрізняється від попереднього тільки одним розрядом.

Основним методом мінімізації логічних функцій, представлених у вигляді ДДНФ є операція попарного неповного склеювання і елементарного поглинання. Операція попарного склеювання здійснюється між двома термами (членами), що містять однакові змінні, входження яких (прямі і інверсні) співпадають для всіх змінних, окрім однієї. В цьому випадку всі змінні, окрім однієї, можна винести за дужки, а пряме і інверсне входження однієї змінної, яке залишилися в дужках, піддати склеюванню. Наприклад:

(2.18)

Можливість поглинання виходить з очевидного рівняння (2.6).

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

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

Приклади незаповнених карт Карно для трьох і чотири змінних приведені в таблицях 2.9 і 2.10 відповідно.

При складанні карт Карно у вигляді приведеному в таблицях 2.9 і 2.10 в заголовку і крайньому лівому стовпцях указуються порядок аргументів логічній функції і їх значення. Значення аргументів змінюються відповідно до кода Грея, тобто так щоб між сусідніми осередками зміна відбувалася тільки з одним з аргументів функції. Завдяки використанню кода Грея на карті верхній рядок є сусіднім з нижнім, а правий стовпець сусіднім з лівим. Таким чином вся карта Карно згортається у просторову фігуру тор (бублик). Оскільки верхній і нижній рядки в таблиці 2.9 сусідні, то карту Карно функції трьох змінних можна розглядати і як кільце (окремий випадок тора).

Таблиця 2.9 – Карта Карно функції трьох змінних

Х3	Х2, Х1
	Ка	р	т	а
	Ка	р	н	о

Таблица 2.10 – Карта Карно функции четырех переменных

Х4, Х3	Х2, Х1
	Ка		т
		р		а
	Ка		н
		р		о

 

Власне картами Карно є внутрішні області таблиць 2.9 (карта має розмірність 2х4 осередки) і 2.10 (карта має 4х4 осередки). На ці області в даному випадку для наочності умовно нанесені відповідні написи.

Карти Карно для 5 і більше змінних отримують з'єднанням декількох карт вигляду 2.10.

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

Сама мінімізація проводиться за наступними правилами (на прикладі ДНФ):

1) об'єднуємо суміжні одиничні клітинки, в область, так щоб одна вона містила 2n (n ціле число ) клітинок (пам'ятаємо про те, що крайні рядки і стовпці є сусідніми між собою), в області не повинно знаходитися клітинок, що містять нулі;

2) область повинна бути якомога більшою, а кількість областей якомога менше;

3) області можуть перетинатися;

4) можливі декілька варіантів накриття;

5) область повинна розташовуватися симетрично осі(ій) (осі розташовуються через кожні чотири клітки);

6) не суміжні області розташовані симетрично осі(ям) можуть об'єднуватися в одну.

Правила 1 – 4 використовуються у всіх випадках, правила 5 і 6 необхідні тільки при мінімізації функцій 5 і більше змінних.

Як приклад мінімізуємо функцію, задану таблицею істинності 2.8 (інверсний мажоритарний клапан). Даній таблиці істинності відповідатиме карта Карно приведена нижче на рисунку 2.1. На карті позначено три суміжні області S1, S2 і S3, виділені відповідно до приведених вище правил 1÷4 і з урахуванням того, що крайні стовпці карти Карно також вважаються суміжними (область S3).

Для виділених областей складемо логічні вирази і проведемо в них операції склеювання:

(2.19)

(2.20)

(2.21)

 

 

 

Об'єднуємо отримані вирази в ДНФ:

(2.22)

Така ДНФ називається тупиковою (видалення будь-якого аргументу в даній формі приведе до нерівної ДНФ) і в той же самий час мінімальною (що містить мінімальну кількість аргументів).

Для побудови електронної схеми з використанням тільки базових елементів ТТЛ-структур, тобто «І-НЕ» скористаємося законом Моргана і подвійного заперечення:

(2.23)

Ви разу (2.23) відповідає схема, приведена на рисунку 2.2.

 

 

2.4 Завдання, порядок виконання роботи і проведення
досліджень

2.4.1 Особливості використання лабораторного стенду
в даній лабораторній роботі

Лабораторний стенд призначений для дослідження цифрових мікросхем ТТЛ-структуры і включає тільки базові логічні елементи «І-НЕ» (мікросхеми К155ЛА3, К155ЛА1) і інвертори (мікросхеми К155ЛН1). Тому дослідження таких елементів як «І», «АБО», «СУМА ПО МОДУЛЮ 2» і ін. може бути проведено на їх еквівалентних схемах, побудованих в базисі функції «І-НЕ» (штрих Шеффера).

Підготовка до роботи

2.4.2.1 Вивчити основи алгебри логіки і роботу логічних елементів, що реалізовують функції однієї і двох змінних (інверсія, повторення, «І», «АБО», «НЕ», «І-НЕ», «АБО‑НЕ», «СУМА ПО МОДУЛЮ 2» й ін.).

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

2.4.2.2 По таблиці істинності функції «СУМА ПО МОДУЛЮ 2» скласти рівняння в ДДНФ і в базисі «І-НЕ». Розробити принципову схему, що реалізовує дану функцію на елементах лабораторного стенду.

2.4.2.3 Відповідно до варіанту (номер бригади) за таблицею 2.11 скласти логічне рівняння заданої логічної функції, мінімізувати його і розробити комбінаційну схему автомата на логічних елементах «І‑НЕ».

 

Таблиця 2.11 - Таблиця істинності логічного автомата

Входи

Вихід Y згідно варіанту

X3

X2

X1

 

Проведення досліджень

2.4.3.1 З елементів, що є на стенді, зібрати по черзі схеми, приведені на рисунку 2.3.

Подати на входи зібраних логічних схем вхідні рівні напруги («0» і «1») і по вихідній напрузі побудувати таблиці істинності. Порівняти їх з таблицями істинності, отриманими при підготовці до проведення роботи. Визначити яким логічним функціям дані схеми відповідають.

 

2.4.3.2 Побудувати таблицю істинності чотирьохвходового елементу DD10 і відповідне функціям елементу логічне рівняння.

З логічних елементів, що є на стенді, скласти і зібрати схему логічного елементу, що виконує такі ж функції, як і елемент DD10.

2.4.3.2 З логічних елементів, що є на стенді, зібрати схему логічного елементу «СУМА ПО МОДУЛЮ 2» (схема повинна бути отримана в ході домашньої підготовки до лабораторної роботи, див. підпункт 2.4.2.2)

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

Зміст звіту

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

 

3 ЛАБОРАТОРНА РОБОТА № 2
ДОСЛІДЖЕННЯ РОБОТИ КОДУЮЧИХ І ДЕКОДУЮЧИХ ПРИСТРОЇВ

Мета лабораторної роботи

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