Карта Карно

Карта Карно (K-карта скорочено) - метод спрощення виразів булевої алгебри, зроблене Морісом Карно в 1953 поліпшення Діаграм Вейча, винайдених Едвардом Вейчем в 1952. Карта Карно зменшує потребу в обширних обчисленнях, використовуючи перевагу людської можливості розпізнання шаблонів, дозволяє швидке розпізнавання і виключення потенційних станів гонитви.

Приклад карти Карно

В карті Карно булеві змінні переносяться (зазвичай з таблиці істинності) і впорядковуються згідно з принципами кода Грея, в якому тільки одна змінна змінюється при переході між сусідніми квадратами. Коли таблиця згенерована, і у відповідні комірки записані вихідні значення, дані організовуються в найбільші можливі групи, що містять 2ⁿ комірок (n=0,1,2,3...). Далі, працюючи з цими групами, отримують мінімізовану ДНФ.

Історія

Карта Карно була винайдена в 1952 Едвардом Вейчем і розроблена далі в 1953 Морісом Карно, інженером з телекомунікацій в Bell Labs.

Властивості

Карта Карно для чотирьох змінних. Примітка: чотири булеві змінні - A, B, C, і D. На верхній стороні решітки перший "0" представляє NOT A, другий "0" представляє NOT B, "1" представляє A, і так далі. Всього можливо 16 перестановок з чотирьох змінних, таким чином маємо 16 можливих виходів.

Призначення

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

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

Проблеми

Карта Карно зазвичай стає важкою для розпізнання при збільшені кількості змінних. Загальне правило таке: карта Карно добре працює до чотирьох-п'яти змінних, і не має використовуватись з більше ніж шістьома змінними. Для виразів з більшою кількістю змінних може бути використаний Метод Куайна — Мак-Класкі. Сьогодні здебільшого для процесу мінімізації використовуються комп'ютери, для яких евристичний алгоритм еспресо став стандартною програмою мінімізації.

Спосіб дії

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

Коли карта Карно заповнена, для отримання мінімізованої функції "1"-ці або "0"-лі групуються в найбільші можливі прямокутні групи, в яких кількість комірок в групі має дорівнювати степеню 2. Наприклад, група може складатися з 4 комірок в лінію, 2 в висоту і 4 в ширину, 2 на 2 і так далі. Байдужий стан (зазвичай позначений Х) групується тільки тоді, коли група отримана з його використанням більша ніж без нього. Комірки можуть бути використані більше ніж один раз тільки якщо завдяки цьому утворюється менша кількість груп. Кожна "1" або "0" має бути задіяна як мінімум в одній групі.

У випадку використання карти Карно для частково заданих функцій в комірках, що відповідають невикористаним вхідним наборам проставляємо "Х" (зірочки, тильди тощо). Ці комірки при необхідності включаються в контури разом з "1" (при отримані формули на базі ДНФ), або "0" (при отримані формули на базі КНФ). При цьому функція після мінімізації виявляється простішою. Розглянемо карту Карно представлену на малюнку праворуч. Якщо при побудові функції не враховувати байдужі стани, то отримаємо функцію утворену трьома контурами $f(E,F,G,H)=({\overline {E}}{\overline {F}}G)+(E{\overline {F}}{\overline {G}}{\overline {H}})+({\overline {E}}{\overline {F}}H)$ на наступному кроці отримаємо $f(E,F,G,H)=({\overline {E}}{\overline {F}}(G+H))+(E{\overline {F}}{\overline {G}}{\overline {H}})$. Ця функція значно спроститься якщо використовувати байдужі стани при виділенні контурів. При цьому утворюється лише один контур (на малюнку вказаний пунктиром). В результаті отримаємо $f(E,F,G,H)=({\overline {F}})$.

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

Для побудови інверсної функції групуємо "0" замість "1".

Взаємозв'язки

Діаграма Венна для 4 множин з числами (0-15). Відповідає раніше показаній карті Карно для чотирьох зміних A, B, C, D.

Кожна комірка карти Карно відповідає мінтерму. Малюнок праворуч показує розташування кожного мінтерма на карті. Діаграма Венна для чотирьох множин названих A, B, C, D посилається на карту Карно представлену на попередньому малюнку:

• Змінна А карти Карно відповідає множині А діаграми Вена; і так далі.
• Мінтерм m0 карти Карно відповідає ділянці 0 в діаграмі Вена; і так далі.
• Мінтерм m9 це ABCD (1001) в карті Карно відповідає перетину ділянок А і D.

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

Тороїдально зв'язні

Решітка є тороїдально зв'язна, таким чином прямокутні групи можуть утворюватися через краї. Наприклад, m9 може бути згрупована з m1; так само як m0, m8, m2, та m10 можуть утворити групу 4*4.

Розмір карти

Розмір карти Карно для n булевих змінних становить 2ⁿ.

• 
  k-карта для 2-х змінних
• 
  k-карта для 3-х змінних
• 
  k-карта для 4-х змінних

Приклад

Карта Карно використовується для полегшення процесу спрощення функцій булевої алгебри. Далі показана неспрощена функція від чотирьох булевих змінних $A$, $B$, $C$, $D$ та їх інверсій. Вона може бути представлена двома різними функціями:

• $f(A,B,C,D)=\sum _{}(6,8,9,10,11,12,13,14)$ Примітка: Значення в $\sum _{}$ є мінтермами для рядків, коли функція дає "1" на виході.
• $f(A,B,C,D)=({\overline {A}}BC{\overline {D}})+(A{\overline {B}}{\overline {C}}{\overline {D}})+(A{\overline {B}}{\overline {C}}D)+(A{\overline {B}}C{\overline {D}})+(A{\overline {B}}CD)+(AB{\overline {C}}{\overline {D}})+(AB{\overline {C}}D)+(ABC{\overline {D}})$

Таблиця істинності

Використавши визначені мінтерми, наступна таблиця істинності може бути створена.

#	$A$	$B$	$C$	$D$	$f(A,B,C,D)$
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-карта показує мінтерми і комірки, що покривають бажані мінтерми. Коричневий регіон є місцем перетину червоного і зеленого регіонів.

Існує 16 варіантів комбінації вхідних змінних, таким чином карта Карно має 16 позицій, і організована у вигляді решітки 4*4.

Двійкові цифри в карті показують вихід функції для будь-якої комбінації на вході. Таким чином 0 вписаний в верхню ліву комірку решітки через те, що ƒ = 0 коли A = 0, B = 0, C = 0, D = 0. Зауважте, що значення впорядковані згідно з кодом Грея, значить рівно одна змінна змінюється між двома суміжними комірками.

Після конструювання карти Карно наше завдання знайти мінімальні терми для використання в кінцевому виразі. Ці терми знаходяться шляхом окреслення груп 1-ць в карті. Група має бути прямокутною і мати площу, що дорівнює ступеню двійки (тобто 1, 2, 4, 8…). Прямокутник має бути максимально великим і без 0-в. Оптимальне групування в матриці позначене зеленим, червоним і синім. Зауважте, що групи можуть перетинатися. Зона перетинання червоної і зеленої групи позначена коричневим.

Решітка тороїдально зв'язна, що означає, що прямокутні групи можуть обгортатися навколо країв, таким чином $\scriptstyle A{\overline {D}}$ правильний терм, хоч і не частина мінімального набору, він покриває мінтерми 8, 10, 12 і 14.

Можливо важче уявити такий терм $\scriptstyle {\overline {B}}\,{\overline {D}}$, який обгортається навколо всіх чотирьох вершин, він покриває такі терми 0, 2, 8, 10.

Розв'язання

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

Для червоної групи:

• Змінна $A$ має одне й те саме значення (1) в кожній комірці групи, значить вона має бути включена в терм червоної групи.
• Змінна $B$ змінює своє значення, отже має бути виключена.
• $C$ завжди 0. Через те, що $C$ 0, вона має бути обернена (записана із символом інверсії, ${\overline {C}}$) перед включенням.
• $D$ змінюється.

Таким чином перший терм виглядає $A{\overline {C}}.$

Для зеленої групи ми бачимо, що $A$ та $B$ зберігають одне значення, а $D$ змінюється. $B$ - 0 і має бути обернене перед включенням. Отже другий терм $A{\overline {B}}.$

Аналогічно, синя група дає $BC{\overline {D}}.$

Розв'язки усіх груп об'єднуються в: $A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}.$

Інверсія

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

Три терма, що покривають інверсну функцію показані сірими прямокутниками з границями різного кольору.

• коричнева—${\overline {A}}\,{\overline {B}}$
• золота—${\overline {A}}\,{\overline {C}}$
• синя—$BCD$

Це породжує інверсію:

${\overline {F}}={\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD$

Після використання законів де Моргана, може бути визначена КНФ:

${\overline {\overline {F}}}={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}$

$F=\left(A+B\right)\left(A+C\right)\left({\overline {B}}+{\overline {C}}+{\overline {D}}\right)$

Стани гонитви

Виключення

Попередня к-карта з доданим $A{\overline {D}}$ термом для уникнення стану гонитви

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

• В попередньому прикладі, потенційно умови гонитви існують, коли C 1 і D 0, A 1, і B змінюється з 1 на 0 (пересуваємось із синьої зони в зелену). В цьому випадку, вихід має залишатися рівним 1, але через те, що цей перехід не покритий специфічним термом в рівнянні, існує потенційна небезпека глюка (коротокочасного переходу в виходу в стан 0).
• Другий глюк може важче помітити: коли D 0 і A та B обидва 1, зі зміною C з 1 в 0 (при переході з блакитного стану в червоний).

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

В цьому випадку, додатковий терм $A{\overline {D}}$ виключить можливість станів гонитв, ставши мостом між зеленим і синім вихідними станами, а також між синім і червоним вихідними станами: це показано як жовтий регіон.

Цей терм зайвий в системах статичної логіки, але така надлишковість часто потрібна в реальних динамічних системах.

Аналогічно, додатковий терм ${\overline {A}}D$ має бути доданим в інверсну функцію для уникнення потенційних станів гонитви. Застосувавши закони де Моргана створюємо інший добуток сум для F, з новим чинником $\left(A+{\overline {D}}\right)$.

Приклади карт від двох змінних

Далі наведені усі можливі к-карти від двох змінних 2 × 2. Для кожного варіанта прописана мінімальні пряма і інверсна функції, стійкі до стану гонитви.

• 
  $\sum _{}$(0); K = 0
• 
  $\sum _{}$(1); K = A′B′
• 
  $\sum _{}$(2); K = AB′
• 
  $\sum _{}$(3); K = A′B
• 
  $\sum _{}$(4); K = AB
• 
  $\sum _{}$(1,2); K = B′
• 
  $\sum _{}$(1,3); K = A′
• 
  $\sum _{}$(1,4); K = A′B′ + AB
• 
  $\sum _{}$(2,3); K = AB′ + A′B
• 
  $\sum _{}$(2,4); K = A
• 
  $\sum _{}$(3,4); K = B
• 
  $\sum _{}$(1,2,3); K = A′ + B′
• 
  $\sum _{}$(1,2,4); K = A + B′
• 
  $\sum _{}$(1,3,4); K = A′ + B
• 
  $\sum _{}$(2,3,4); K = A + B
• 
  $\sum _{}$(1,2,3,4); K = 1

Приклад К-карти для функції 5-х змінних

Для таблиць 5 і більше змінних треба враховувати, що квадрати 4х4 віртуально розташовані один над одним в третьому вимірі, через це відповідні комірки двох сусідніх квадратів 4х4 є поєднаними, і відповідні терми можна склеювати.

Див. також

• Метод Куайна — Мак-Класкі
• Еспресо - евристичний алгоритм мінімізації
• Діаграма Венна

Посилання

Освітні

• Виявлення прямокутників, що перетинаються [Архівовано 3 лютого 2013 у Wayback Machine.], Герберт Глернер (Herbert Glarner).
• Використання карти Карно на практиці [Архівовано 2 листопада 2013 у Wayback Machine.], Проектування схеми для контролю трафіка.
• Приклад карти Карно [Архівовано 29 березня 2010 у Wayback Machine.]
• Мінімізація булевих функцій

Програмне забезпечення

• Kmap minimizer [Архівовано 3 березня 2012 у Wayback Machine.] Online Flash application, published 2009.
• Boolean Function Simplification Software [Архівовано 22 січня 2010 у Wayback Machine.], freeware application for the Palm OS.
• GKMap [Архівовано 11 січня 2010 у Wayback Machine.], free software application at SourceForge.net.
• GPA141 [Архівовано 11 червня 2010 у Wayback Machine.], Java applet for solving 5-variable Karnaugh maps available only in French.
• Karnaugh Map Minimizer [Архівовано 3 січня 2010 у Wayback Machine.], free software application at SourceForge.net.
• Karnaugh map minimization software [Архівовано 8 січня 2010 у Wayback Machine.], freeware application available in English, Czech, and German.
• Karma 3 [Архівовано 9 січня 2021 у Wayback Machine.], A set of logic synthesis tools including Karnaugh maps, Quine-McCluskey minimization, BDDs, probabilities, teaching module and more. Logic Circuits Synthesis Labs (LogiCS) - UFRGS, Brazil.
• Karnaugh Map Explorer 1.0, JavaScript application.
• Karno freeware application, published 1999.