Матеріал з Вікіпедії — вільної енциклопедії.
Приклад карти Карно
В карті Карно булеві змінні переносяться (зазвичай з таблиці істинності) і впорядковуються згідно з принципами кода Грея, в якому тільки одна змінна змінюється при переході між сусідніми квадратами. Коли таблиця згенерована, і у відповідні комірки записані вихідні значення, дані організовуються в найбільші можливі групи, що містять 2n комірок (n=0,1,2,3...)[1]. Далі, працюючи з цими групами, отримують мінімізовану ДНФ.
Зміст
Історія
Карта Карно була винайдена в 1952 Едвардом Вейчем і розроблена далі в 1953 Морісом Карно, інженером з телекомунікацій в Bell Labs.Властивості
Карта Карно для чотирьох змінних. Примітка: чотири булеві змінні - A, B,
C, і D. На верхній стороні решітки перший "0" представляє NOT A, другий
"0" представляє NOT B, "1" представляє A, і так далі. Всього можливо 16
перестановок з чотирьох змінних, таким чином маємо 16 можливих виходів.
Призначення
Зазвичай, значні обчислення потрібні для отримання мінімального виду булевої функції, однак карта Карно зменшує потребу таких обчислень завдяки:- Використанню можливості людського розуму по розпізнаванню шаблонів для визначення які терми мають бути поєднані для отримання найпростішого виразу.
- Дозволяє швидко визначити та видалити потенційні стани гонитв, які неминучі в булевих рівняннях.
- Забезпечує найкращу допомогу в спрощенні до шістьох змінних, однак з більшою кількістю змінних стає складно розрізнити оптимальні шаблони.
- Допомагає в навчанні про булеві функції та їх мінімізацію.
Проблеми
Карта Карно зазвичай становиться важкою для розпізнання при збільшені кількості змінних. Загальне правило таке, карта Карно добре працює до чотирьох-п'яти змінних, і не має використовуватись з більше ніж шістьома змінними. Для виразів з більшою кількістю змінних може бути використаний Метод Куайна — Мак-Класкі. Сьогодні здебільшого для процесу мінімізації використовуються комп'ютери, для яких евристичний алгоритм еспресо став стандартною програмою мінімізації.Спосіб дії
Кожна змінна має два значення: початкове та обернене. Змінні впорядковуються згідно з кодом Грея, тобто тільки одна змінна змінюється між двома суміжними комірками. У відповідні комірки записуємо вихідні значення функції.Коли карта Карно заповнена, для отримання мінімізованої функції "1"-ці або "0"-лі групуються в найбільші можливі прямокутні групи, в яких кількість комірок в групі має дорівнювати степеню 2.[1] Наприклад, група може складатися з 4 комірок в лінію, 2 в висоту і 4 в ширину, 2 на 2 і так далі. Байдужий стан (зазвичай позначений Х) групується тільки тоді, коли група отримана з його використанням більша ніж без нього. Комірки можуть бути використані більше ніж один раз тільки якщо завдяки цьому утворюється менша кількість груп. Кожна "1" або "0" має бути задіяна як мінімум в одній групі.
-
У випадку використання карти Карно для частково заданих функцій в комірках, що відповідають невикористаним вхідним наборам проставляємо "Х" (зірочки, тильди тощо). Ці комірки при необхідності включаються в контури разом з "1" (при отримані формули на базі ДНФ), або "0" (при отримані формули на базі КНФ). При цьому функція після мінімізації виявляється простішою. Розглянемо карту Карно представлену на малюнку праворуч. Якщо при побудові функції не враховувати байдужі стани, то отримаємо функцію утворену трьома контурами 
на наступному кроці отримаємо 
.
Ця функція значно спроститься якщо використовувати байдужі стани при
виділенні контурів. При цьому утворюється лише один контур (на малюнку
вказаний пунктиром). В результаті отримаємо 
.
Для побудови інверсної функції групуємо "0" замість "1".
Взаємозв'язки
Діаграма Венна для 4 множин з числами (0-15). Відповідає раніше показаній карті Карно для чотирьох зміних A, B, C, D.
- Змінна А карти Карно відповідає множині А діаграми Вена; і так далі.
- Мінтерм m0 карти Карно відповідає ділянці 0 в діаграмі Вена; і так далі.
- Мінтерм m9 це ABCD (1001) в карті Карно відповідає перетину ділянок А і D.
Тороїдально зв'язні
Решітка є тороїдально зв'язна, таким чином прямокутні групи можуть утворюватися через края. Наприклад, m9 може бути згрупована з m1; так само як m0, m8, m2, та m10 можуть утворити групу 4*4.Розмір карти
Розмір карти Карно для n булевих змінних становить 2n.-
k-карта для 2-х змінних
-
k-карта для 3-х змінних
-
k-карта для 4-х змінних
Приклад
Карта Карно використовується для полегшення процесу спрощення функцій булевої алгебри. Далі показана неспрощена функція від чотирьох булевих змінних
, 
, 
, 
, та їх інверсій. Вона може бути представлена двома різними функціями:
Примітка: Значення в 
є мінтермами для рядків, коли функція дає "1" на виході.
Таблиця істинності
Використавши визначені мінтерми, наступна таблиця істинності може бути створена.| # | |
|
|
|
 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 2 | 0 | 0 | 1 | 0 | 0 |
| 3 | 0 | 0 | 1 | 1 | 0 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 0 | 1 | 0 |
| 6 | 0 | 1 | 1 | 0 | 1 |
| 7 | 0 | 1 | 1 | 1 | 0 |
| 8 | 1 | 0 | 0 | 0 | 1 |
| 9 | 1 | 0 | 0 | 1 | 1 |
| 10 | 1 | 0 | 1 | 0 | 1 |
| 11 | 1 | 0 | 1 | 1 | 1 |
| 12 | 1 | 1 | 0 | 0 | 1 |
| 13 | 1 | 1 | 0 | 1 | 1 |
| 14 | 1 | 1 | 1 | 0 | 1 |
| 15 | 1 | 1 | 1 | 1 | 0 |
Карта Карно
K-карта показує мінтерми і комірки, що покривають бажані мінтерми.
Коричневий регіон є місцем перетину червоного і зеленого регіонів.
Двійкові цифри в карті показують вихід функції для будь-якої комбінації на вході. Таким чином 0 вписаний в верхню ліву комірку решітки через те, що ƒ = 0 коли A = 0, B = 0, C = 0, D = 0. Зауважте, що значення впорядковані згідно з кодом Грея, значить рівно одна змінна змінюється між двома суміжними комірками.
Після конструювання карти Карно наше завдання знайти мінімальні терми для використання в кінцевому виразі. Ці терми знаходяться шляхом окреслення груп 1-ць в карті. Група має бути прямокутною і мати площу, що дорівнює ступеню двійки (тобто 1, 2, 4, 8…). Прямокутник має бути максимально великим і без 0-в. Оптимальне групування в матриці позначене зеленим, червоним і синім. Зауважте, що групи можуть перетинатися. Зона перетинання червоної і зеленої групи позначена коричневим.
Решітка тороїдально зв'язна, що означає, що прямокутні групи обгортатися навколо країв, таким чином
правильний терм, хоч і не частина мінімального набору, він покриває мінтерми 8, 10, 12 і 14.Можливо важче уявити такий терм
, який обгортається навколо всіх чотирьох вершин, він покриває такі терми 0, 2, 8, 10.Розв'язання
Коли карта Карно побудована і отримані групи, розв'язок може бути отриманий шляхом виключення надлишкових змінних використавши аксіоми булевої алгебри.Для червоної групи:
- Змінна має одне й те саме значення (1) в кожній комірці групи, значить вона має бути включена в терм червоної групи.
- Змінна змінює своє значення, отже має бути виключена.
- завжди 0. Через те, що 0, вона має бути обернена (записана із символом інверсії,
) перед включенням. - змінюється.
Для зеленої групи ми бачимо, що
та зберігають одне значення, а змінюється. - 0 і має бути обернене перед включенням. Отже другий терм 
Аналогічно, синя група дає
Розв'язки усіх груп об'єднуються в:
Інверсія
Інверсія функції знаходиться таким самим шляхом, тільки групуються 0.Три терма, що покривають інверсну функцію показані сірими прямокутниками з границями різного кольору.
- коричнева—
- золота—
- синя—
Стани гонитви
Виключення
Попередня к-карта з доданим 
термом для уникнення стану гонитви
термом для уникнення стану гонитви- В попередньому прикладі, потенційно умови гонитви існують, коли C 1 і D 0, A 1, і B змінюється з 1 на 0 (пересуваємось із синьої зони в зелену). В цьому випадку, вихід має залишатися рівним 1, але через те, що цей перехід не покритий специфічним термом в рівнянні, існує потенціальна небезпека глюка (коротокочасного переходу в виходу в стан 0).
- Другий глюк може важче помітити: коли D 0 і A та B обидва 1, зі зміною C з 1 в 0 (при переході з блакитного стану в червоний).
В цьому випадку, додатковий терм
виключить можливість станів гонитв, ставши мостом між зеленим і синім
вихідними станами, а також між синім і червоним вихідними станами: це
показано як жовтий регіон.Цей терм зайвий в системах статичної логіки, але така надлишковість часто потрібна в реальних динамічних системах.
Аналогічно, додатковий терм
має бути доданим в інверсну функцію для уникнення потенційних станів
гонитви. Застосував закони де Моргана створюємо інший добуток сум для F,
з новим чинником 
.Приклади карт від двох змінних
Далі наведені усі можливі к-карти від двох змінних 2 × 2. Для кожного варіанта прописана мінімальні пряма і інверсна функції стійкі до стану гонитви.-
(0); K = 0
-
(1); K = A′B′
-
(2); K = AB′
-
(3); K = A′B
-
(4); K = AB
-
(1,2); K = B′
-
(1,3); K = A′
-
(1,4); K = A′B′ + AB
-
(2,3); K = AB′ + A′B
-
(2,4); K = A
-
(3,4); K = B
-
(1,2,3); K = A′ + B′
-
(1,2,4); K = A + B′
-
(1,3,4); K = A′ + B
-
(2,3,4); K = A + B
-
(1,2,3,4); K = 1
Приклад К-карти для функції 5-х змінних
Немає коментарів:
Дописати коментар
Примітка: лише член цього блогу може опублікувати коментар.