Карта Карно

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Приклад карти Карно

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

В карті Карно булеві змінні переносяться (зазвичай з таблиці істинності) і впорядковуються згідно з принципами кода Грея, в якому тільки одна змінна змінюється при переході між сусідніми квадратами. Коли таблиця згенерована, і у відповідні комірки записані вихідні значення, дані організовуються в найбільші можливі групи, що містять 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" (при отримані формули на базі КНФ). При цьому функція після мінімізації виявляється простішою.

Розглянемо карту Карно представлену на малюнку праворуч. Якщо при побудові функції не враховувати байдужі стани, то отримаємо функцію утворену трьома контурами 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}).

K-map with dont-cares.GIF

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

Для побудови інверсної функції групуємо "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 булевих змінних становить 2n.

Приклад[ред.ред. код]

Карта Карно використовується для полегшення процесу спрощення функцій булевої алгебри. Далі показана неспрощена функція від чотирьох булевих змінних 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. Для кожного варіанта прописана мінімальні пряма і інверсна функції стійкі до стану гонитви.

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

Karnaugh map minimize.gif

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

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. а б «Карти Карно - Правила спрощення». Архів оригіналу за 2013-07-06. Процитовано 2009-05-30. 

External links[ред.ред. код]

Освітні

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