Карта Карно: відмінності між версіями
[неперевірена версія] | [перевірена версія] |
Bunyk (обговорення | внесок) |
|||
(Не показані 28 проміжних версій 22 користувачів) | |||
Рядок 1: | Рядок 1: | ||
[[Зображення:K-map 6,8,9,10,11,12,13,14 anti-race.svg|thumb|праворуч|Приклад карти Карно]] |
[[Зображення:K-map 6,8,9,10,11,12,13,14 anti-race.svg|thumb|праворуч|Приклад карти Карно]] |
||
'''Карта Карно''' ('''K-карта''' |
'''Карта Карно''' ('''K-карта''' скорочено) - метод спрощення виразів [[Булева алгебра|булевої алгебри]], зроблене [[Моріс Карно|Морісом Карно]] в 1953 поліпшення '''Діаграм Вейча,''' винайдених [[Едвард Вейч|Едвардом Вейчем]] в 1952. Карта Карно зменшує потребу в обширних обчисленнях, використовуючи перевагу людської можливості розпізнання шаблонів, дозволяє швидке розпізнавання і виключення потенційних [[стан гонитви|станів гонитви]]. |
||
В карті Карно булеві змінні переносяться (зазвичай з [[таблиці істинності]]) і впорядковуються згідно з принципами [[Код Грея|кода Грея]], в якому тільки одна змінна змінюється при переході між сусідніми квадратами. Коли таблиця згенерована, і у відповідні комірки записані вихідні значення, дані організовуються в найбільші можливі групи, що містять 2<sup>n</sup> комірок (n=0,1,2,3...)<ref name="KMapRulesOfSimplification">{{cite web|url=http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karrules.html|title=Карти Карно - Правила спрощення|accessdate=2009-05-30}}</ref>. Далі, працюючи з цими групами, отримують мінімізовану [[ДНФ]]. |
В карті Карно булеві змінні переносяться (зазвичай з [[таблиці істинності]]) і впорядковуються згідно з принципами [[Код Грея|кода Грея]], в якому тільки одна змінна змінюється при переході між сусідніми квадратами. Коли таблиця згенерована, і у відповідні комірки записані вихідні значення, дані організовуються в найбільші можливі групи, що містять 2<sup>n</sup> комірок (n=0,1,2,3...)<ref name="KMapRulesOfSimplification">{{cite web|url=http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karrules.html|title=Карти Карно - Правила спрощення|accessdate=2009-05-30|archiveurl=https://web.archive.org/web/20170418140519/http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karrules.html|archivedate=2017-04-18|deadurl=yes}}</ref>. Далі, працюючи з цими групами, отримують мінімізовану [[ДНФ]]. |
||
== Історія == |
== Історія == |
||
Рядок 11: | Рядок 11: | ||
==Властивості== |
==Властивості== |
||
[[File:K-map minterms.svg|thumb|Карта Карно для чотирьох змінних. Примітка: чотири булеві змінні - A, B, C, і D. На верхній стороні решітки перший "0" |
[[File:K-map minterms.svg|thumb|Карта Карно для чотирьох змінних. Примітка: чотири булеві змінні - A, B, C, і D. На верхній стороні решітки перший "0" представляє NOT A, другий "0" представляє NOT B, "1" представляє A, і так далі. Всього можливо 16 [[Перестановка|перестановок]] з чотирьох змінних, таким чином маємо 16 можливих виходів.]] |
||
===Призначення=== |
===Призначення=== |
||
Зазвичай, значні обчислення потрібні для отримання мінімального виду булевої функції, однак карта Карно зменшує потребу таких обчислень завдяки: |
Зазвичай, значні обчислення потрібні для отримання мінімального виду [[Булева функція|булевої функції]], однак карта Карно зменшує потребу таких обчислень завдяки: |
||
*Використанню можливості |
*Використанню можливості людського розуму по розпізнаванню шаблонів для визначення які терми мають бути поєднані для отримання найпростішого виразу. |
||
*Дозволяє швидко визначити та видалити потенційні [[стан гонитви|стани гонитв]], які неминучі в булевих рівняннях. |
*Дозволяє швидко визначити та видалити потенційні [[стан гонитви|стани гонитв]], які неминучі в булевих рівняннях. |
||
*Забезпечує найкращу допомогу в спрощенні до шістьох змінних, однак з більшою кількістю змінних стає складно розрізнити оптимальні шаблони. |
*Забезпечує найкращу допомогу в спрощенні до шістьох змінних, однак з більшою кількістю змінних стає складно розрізнити оптимальні шаблони. |
||
* |
*Допомагає в навчанні про булеві функції та їх мінімізацію. |
||
===Проблеми=== |
===Проблеми=== |
||
Карта Карно зазвичай |
Карта Карно зазвичай стає важкою для розпізнання при збільшені кількості змінних. Загальне правило таке: карта Карно добре працює до чотирьох-п'яти змінних, і не має використовуватись з більше ніж шістьома змінними. Для виразів з більшою кількістю змінних може бути використаний [[Метод Куайна — Мак-Класкі]]. Сьогодні здебільшого для процесу мінімізації використовуються комп'ютери, для яких [[евристичний алгоритм]] [[Еспресо (логіка)|еспресо]] став стандартною програмою мінімізації. |
||
===Спосіб дії=== |
===Спосіб дії=== |
||
Кожна змінна має два значення: початкове та |
Кожна змінна має два значення: початкове та обернене. Змінні впорядковуються згідно з кодом Грея, тобто тільки одна змінна змінюється між двома суміжними комірками. У відповідні комірки записуємо вихідні значення функції. |
||
Коли карта Карно заповнена, для отримання мінімізованої функції "1"-ці або "0"-лі групуються в найбільші можливі [[Прямокутник|прямокутні]] групи, в яких кількість комірок в групі має дорівнювати [[степінь|степеню]] 2.<ref name="KMapRulesOfSimplification" /> Наприклад, група може складатися з 4 комірок в лінію, 2 в висоту і 4 в ширину, 2 на 2 і так далі. [[Байдужий стан]] (зазвичай позначений Х) групується тільки тоді, коли група отримана з його використанням більша ніж без нього. Комірки можуть бути використані більше ніж один раз тільки якщо завдяки цьому утворюється менша кількість груп. Кожна "1" або "0" має бути задіяна як мінімум в одній групі. |
Коли карта Карно заповнена, для отримання мінімізованої функції "1"-ці або "0"-лі групуються в найбільші можливі [[Прямокутник|прямокутні]] групи, в яких кількість комірок в групі має дорівнювати [[степінь|степеню]] 2.<ref name="KMapRulesOfSimplification" /> Наприклад, група може складатися з 4 комірок в лінію, 2 в висоту і 4 в ширину, 2 на 2 і так далі. [[Байдужий стан]] (зазвичай позначений Х) групується тільки тоді, коли група отримана з його використанням більша ніж без нього. Комірки можуть бути використані більше ніж один раз тільки якщо завдяки цьому утворюється менша кількість груп. Кожна "1" або "0" має бути задіяна як мінімум в одній групі. |
||
Рядок 33: | Рядок 33: | ||
:{| class="wikitable" |
:{| class="wikitable" |
||
|- |
|- |
||
| У випадку використання карти Карно для частково заданих функцій в комірках, що відповідають невикористаним вхідним наборам проставляємо "Х" (зірочки, |
| У випадку використання карти Карно для частково заданих функцій в комірках, що відповідають невикористаним вхідним наборам проставляємо "Х" (зірочки, тильди тощо). Ці комірки при необхідності включаються в контури разом з "1" (при отримані формули на базі ДНФ), або "0" (при отримані формули на базі [[КНФ]]). При цьому функція після мінімізації виявляється простішою. |
||
Розглянемо карту Карно представлену на малюнку праворуч. Якщо при побудові функції не враховувати байдужі стани, то отримаємо функцію утворену трьома контурами <math>f(E, F, G, H) = (\overline{E}\overline{F}G) + (E\overline{F}\overline{G}\overline{H}) + (\overline{E}\overline{F}H)</math> |
Розглянемо карту Карно представлену на малюнку праворуч. Якщо при побудові функції не враховувати байдужі стани, то отримаємо функцію утворену трьома контурами <math>f(E, F, G, H) = (\overline{E}\overline{F}G) + (E\overline{F}\overline{G}\overline{H}) + (\overline{E}\overline{F}H)</math> на наступному кроці отримаємо <math>f(E, F, G, H) = (\overline{E}\overline{F}(G + H)) + (E\overline{F}\overline{G}\overline{H})</math>. |
||
Ця функція значно спроститься якщо використовувати байдужі стани при виділенні контурів. При цьому утворюється лише один контур (на малюнку вказаний пунктиром). В результаті отримаємо <math>f(E, F, G, H) = (\overline{F})</math>. |
Ця функція значно спроститься якщо використовувати байдужі стани при виділенні контурів. При цьому утворюється лише один контур (на малюнку вказаний пунктиром). В результаті отримаємо <math>f(E, F, G, H) = (\overline{F})</math>. |
||
||[[Файл:K-map with dont-cares.GIF|міні]] |
||[[Файл:K-map with dont-cares.GIF|міні]] |
||
Рядок 52: | Рядок 52: | ||
*Мінтерм m9 це A<span style="text-decoration:overline">BC</span>D (1001) в карті Карно відповідає перетину ділянок А і D. |
*Мінтерм m9 це A<span style="text-decoration:overline">BC</span>D (1001) в карті Карно відповідає перетину ділянок А і D. |
||
Таким чином, кожен мінтерм визначає унікальний перетин всіх чотирьох множин. |
Таким чином, кожен мінтерм визначає унікальний перетин всіх чотирьох множин. Діаграма Вена може містити безкінечну кількість множин і все ще відповідати відповідній карті Карно. Із збільшенням множин і змінних, і діаграма Вена, і карта Карно стають складнішими для малювання і управління. |
||
=== |
===Тороїдально зв'язні=== |
||
Решітка є [[тор (геометрія)| |
Решітка є [[тор (геометрія)|тороїдально]] зв'язна, таким чином прямокутні групи можуть утворюватися через краї. Наприклад, ''m''9 може бути згрупована з ''m''1; так само як ''m''0, ''m''8, ''m''2, та ''m''10 можуть утворити групу 4*4. |
||
===Розмір карти=== |
===Розмір карти=== |
||
Рядок 70: | Рядок 70: | ||
==Приклад== |
==Приклад== |
||
Карта Карно використовується для полегшення процесу спрощення функцій [[Булева алгебра|булевої алгебри]]. Далі показана неспрощена функція від чотирьох булевих змінних <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math> |
Карта Карно використовується для полегшення процесу спрощення функцій [[Булева алгебра|булевої алгебри]]. Далі показана неспрощена функція від чотирьох булевих змінних <math>A</math>, <math>B</math>, <math>C</math>, <math>D</math> та їх інверсій. Вона може бути представлена двома різними функціями: |
||
*<math>f(A, B, C, D) = \sum_{}(6, 8, 9, 10, 11, 12, 13, 14)</math> Примітка: Значення в <math>\sum_{}</math> є мінтермами для рядків, коли функція дає "1" на виході. |
*<math>f(A, B, C, D) = \sum_{}(6, 8, 9, 10, 11, 12, 13, 14)</math> Примітка: Значення в <math>\sum_{}</math> є мінтермами для рядків, коли функція дає "1" на виході. |
||
Рядок 157: | Рядок 157: | ||
Після конструювання карти Карно наше завдання знайти мінімальні терми для використання в кінцевому виразі. Ці терми знаходяться шляхом окреслення груп 1-ць в карті. Група має бути прямокутною і мати площу, що дорівнює ступеню двійки (тобто 1, 2, 4, 8…). Прямокутник має бути максимально великим і без 0-в. Оптимальне групування в матриці позначене зеленим, червоним і синім. Зауважте, що групи можуть перетинатися. Зона перетинання червоної і зеленої групи позначена коричневим. |
Після конструювання карти Карно наше завдання знайти мінімальні терми для використання в кінцевому виразі. Ці терми знаходяться шляхом окреслення груп 1-ць в карті. Група має бути прямокутною і мати площу, що дорівнює ступеню двійки (тобто 1, 2, 4, 8…). Прямокутник має бути максимально великим і без 0-в. Оптимальне групування в матриці позначене зеленим, червоним і синім. Зауважте, що групи можуть перетинатися. Зона перетинання червоної і зеленої групи позначена коричневим. |
||
Решітка |
Решітка тороїдально зв'язна, що означає, що прямокутні групи можуть обгортатися навколо країв, таким чином <math>\scriptstyle A\overline{D}</math> правильний терм, хоч і не частина мінімального набору, він покриває мінтерми 8, 10, 12 і 14. |
||
Можливо важче уявити такий терм <math>\scriptstyle\overline{B}\,\overline{D}</math>, який обгортається навколо всіх чотирьох вершин, він покриває такі терми 0, 2, 8, 10. |
Можливо важче уявити такий терм <math>\scriptstyle\overline{B}\,\overline{D}</math>, який обгортається навколо всіх чотирьох вершин, він покриває такі терми 0, 2, 8, 10. |
||
Рядок 163: | Рядок 163: | ||
===Розв'язання=== |
===Розв'язання=== |
||
Коли карта Карно побудована і отримані групи, розв'язок може бути отриманий шляхом виключення надлишкових змінних використавши аксіоми булевої алгебри. |
Коли карта Карно побудована і отримані групи, розв'язок може бути отриманий шляхом виключення надлишкових змінних використавши [[Аксіома|аксіоми]] булевої алгебри. |
||
Для червоної групи: |
Для червоної групи: |
||
Рядок 200: | Рядок 200: | ||
[[Файл:K-map 6,8,9,10,11,12,13,14 anti-race.svg|thumb|Попередня к-карта з доданим <math>A\overline{D}</math> термом для уникнення стану гонитви]] |
[[Файл:K-map 6,8,9,10,11,12,13,14 anti-race.svg|thumb|Попередня к-карта з доданим <math>A\overline{D}</math> термом для уникнення стану гонитви]] |
||
Карта Карно корисна для виявлення та виключення [[стан гонитви|станів гонитви]]. Їх дуже легко визначити використовуючи карту Карно через те, що умови гонитви існують коли рухаєшся між будь-якою парою суміжних але роз'єднаних, груп окреслених на карті. |
Карта Карно корисна для виявлення та виключення [[стан гонитви|станів гонитви]]. Їх дуже легко визначити використовуючи карту Карно через те, що умови гонитви існують, коли рухаєшся між будь-якою парою суміжних але роз'єднаних, груп окреслених на карті. |
||
* В попередньому прикладі, потенційно умови гонитви |
* В попередньому прикладі, потенційно умови гонитви існують, коли C 1 і D 0, A 1, і B змінюється з 1 на 0 (пересуваємось із синьої зони в зелену). В цьому випадку, вихід має залишатися рівним 1, але через те, що цей перехід не покритий специфічним термом в рівнянні, існує потенційна небезпека ''глюка'' (коротокочасного переходу в виходу в стан 0). |
||
* Другий глюк може важче помітити: коли D 0 і A та B обидва 1, зі зміною C з 1 в 0 (при переході з блакитного стану в червоний). |
* Другий глюк може важче помітити: коли D 0 і A та B обидва 1, зі зміною C з 1 в 0 (при переході з блакитного стану в червоний). |
||
Рядок 209: | Рядок 209: | ||
В цьому випадку, додатковий терм <math>A\overline{D}</math> виключить можливість станів гонитв, ставши мостом між зеленим і синім вихідними станами, а також між синім і червоним вихідними станами: це показано як жовтий регіон. |
В цьому випадку, додатковий терм <math>A\overline{D}</math> виключить можливість станів гонитв, ставши мостом між зеленим і синім вихідними станами, а також між синім і червоним вихідними станами: це показано як жовтий регіон. |
||
Цей терм [[логічна надлишковість|зайвий]] в системах статичної логіки, але така надлишковість часто потрібна в реальних динамічних системах. |
Цей терм [[логічна надлишковість|зайвий]] в системах статичної логіки, але така надлишковість часто потрібна в реальних [[Динамічна система|динамічних системах]]. |
||
Аналогічно, додатковий терм <math>\overline{A}D</math> має бути доданим в інверсну функцію для уникнення потенційних станів гонитви. |
Аналогічно, додатковий терм <math>\overline{A}D</math> має бути доданим в інверсну функцію для уникнення потенційних станів гонитви. Застосувавши закони де Моргана створюємо інший добуток сум для F, з новим чинником <math>\left(A + \overline{D}\right)</math>. |
||
===Приклади карт від двох змінних=== |
===Приклади карт від двох змінних=== |
||
Далі наведені усі можливі к-карти від двох змінних 2 × 2. Для кожного варіанта прописана мінімальні пряма і інверсна функції стійкі до стану гонитви. |
Далі наведені усі можливі к-карти від двох змінних 2 × 2. Для кожного варіанта прописана мінімальні пряма і інверсна функції, стійкі до стану гонитви. |
||
<gallery> |
<gallery> |
||
File:K-map 2x2 none.svg | <math>\sum_{}</math>(0); ''K'' = 0 |
File:K-map 2x2 none.svg | <math>\sum_{}</math>(0); ''K'' = 0 |
||
Рядок 238: | Рядок 238: | ||
[[Зображення:Karnaugh map minimize.gif|міні|праворуч]] |
[[Зображення:Karnaugh map minimize.gif|міні|праворуч]] |
||
Для таблиць 5 і більше змінних треба враховувати, що квадрати 4х4 |
Для таблиць 5 і більше змінних треба враховувати, що квадрати 4х4 віртуально розташовані один над одним в третьому вимірі, через це відповідні комірки двох сусідніх квадратів 4х4 є поєднаними, і відповідні терми можна склеювати. |
||
== Див. також == |
== Див. також == |
||
*[[Метод Куайна — Мак-Класкі]] |
*[[Метод Куайна — Мак-Класкі]] |
||
* |
*{{нп|Еспресо (логіка)|Еспресо - евристичний алгоритм мінімізації|en|Espresso heuristic logic minimizer}} |
||
*[[Діаграма Венна]] |
*[[Діаграма Венна]] |
||
Рядок 249: | Рядок 249: | ||
{{reflist}} |
{{reflist}} |
||
== Посилання == |
|||
==External links== |
|||
'''Освітні''' |
'''Освітні''' |
||
* [http:// |
* [http://www.gandraxa.com/detect_overlapping_subrectangles.xml Виявлення прямокутників, що перетинаються] {{Webarchive|url=https://web.archive.org/web/20130203031048/http://gandraxa.com/detect_overlapping_subrectangles.xml |date=3 лютого 2013 }}, Герберт Глернер (Herbert Glarner). |
||
* [http://www.sccs.swarthmore.edu/users/06/adem/engin/e15/lab1/ Використання карти Карно на практиці], Проектування схеми для контролю трафіка. |
* [http://www.sccs.swarthmore.edu/users/06/adem/engin/e15/lab1/ Використання карти Карно на практиці] {{Webarchive|url=https://web.archive.org/web/20131102213404/http://www.sccs.swarthmore.edu/users/06/adem/engin/e15/lab1/ |date=2 листопада 2013 }}, Проектування схеми для контролю трафіка. |
||
* [http://www.generalnumbers.com/karnaugh_application1.html Приклад карти Карно] |
* [http://www.generalnumbers.com/karnaugh_application1.html Приклад карти Карно] {{Webarchive|url=https://web.archive.org/web/20100329050449/http://www.generalnumbers.com/karnaugh_application1.html |date=29 березня 2010 }} |
||
* [http://www.world-class-programme.com/Karnaugh-Map.asp Мінімізація булевих функцій] |
* [https://web.archive.org/web/20100123205847/http://www.world-class-programme.com/Karnaugh-Map.asp Мінімізація булевих функцій] |
||
'''Програмне забезпечення''' |
'''Програмне забезпечення''' |
||
* [http://2b2.eu/fun/game.php?gid=14 Kmap minimizer] Online Flash application, published 2009. |
* [http://2b2.eu/fun/game.php?gid=14 Kmap minimizer] {{Webarchive|url=https://web.archive.org/web/20120303030651/http://2b2.eu/fun/game.php?gid=14 |date=3 березня 2012 }} Online Flash application, published 2009. |
||
* [http://pages.csam.montclair.edu/~antoniou/bfs/ Boolean Function Simplification Software], freeware application for the [[Palm OS]]. |
* [http://pages.csam.montclair.edu/~antoniou/bfs/ Boolean Function Simplification Software] {{Webarchive|url=https://web.archive.org/web/20100122074505/http://pages.csam.montclair.edu/~antoniou/bfs/ |date=22 січня 2010 }}, freeware application for the [[Palm OS]]. |
||
* [http://sourceforge.net/projects/gkmap GKMap], free software application at [[SourceForge.net]]. |
* [http://sourceforge.net/projects/gkmap GKMap] {{Webarchive|url=https://web.archive.org/web/20100111211418/http://sourceforge.net/projects/gkmap/ |date=11 січня 2010 }}, free software application at [[SourceForge.net]]. |
||
* [http://www.gpa.etsmtl.ca/cours/gpa141/exercices.html GPA141], Java applet for solving 5-variable Karnaugh maps available only in French. |
* [http://www.gpa.etsmtl.ca/cours/gpa141/exercices.html GPA141] {{Webarchive|url=https://web.archive.org/web/20100611234649/http://www.gpa.etsmtl.ca/cours/gpa141/exercices.html |date=11 червня 2010 }}, Java applet for solving 5-variable Karnaugh maps available only in French. |
||
* [http://k-map.sourceforge.net/ Karnaugh Map Minimizer], free software application at [[SourceForge.net]]. |
* [http://k-map.sourceforge.net/ Karnaugh Map Minimizer] {{Webarchive|url=https://web.archive.org/web/20100103004712/http://k-map.sourceforge.net/ |date=3 січня 2010 }}, free software application at [[SourceForge.net]]. |
||
* [http://www.karnaughmap.eu/ Karnaugh map minimization software], freeware application available in English, Czech, and German. |
* [http://www.karnaughmap.eu/ Karnaugh map minimization software] {{Webarchive|url=https://web.archive.org/web/20100108120420/http://www.karnaughmap.eu/ |date=8 січня 2010 }}, freeware application available in English, Czech, and German. |
||
* [http://www.inf.ufrgs.br/logics/ Karma 3], 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. |
* [http://www.inf.ufrgs.br/logics/ Karma 3] {{Webarchive|url=https://web.archive.org/web/20210109073843/http://www.inf.ufrgs.br/logics/ |date=9 січня 2021 }}, 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. |
||
* [http://www.ee.calpoly.edu/~rsandige/KarnaughExplorer.html Karnaugh Map Explorer 1.0], JavaScript application. |
* [https://web.archive.org/web/20071214072752/http://www.ee.calpoly.edu/~rsandige/KarnaughExplorer.html Karnaugh Map Explorer 1.0], JavaScript application. |
||
* [http://www.geocities.com/ResearchTriangle/2608/Karnaugh.html Karno] freeware application, published 1999. |
* [https://web.archive.org/web/20091027124749/http://www.geocities.com/ResearchTriangle/2608/Karnaugh.html Karno] freeware application, published 1999. |
||
[[Категорія:Булева алгебра]] |
[[Категорія:Булева алгебра]] |
||
[[Категорія: |
[[Категорія:Обчислювальні задачі]] |
||
[[Категорія:Логіка в інформатиці]] |
|||
[[ar:خريطة كارنوف]] |
|||
[[ca:Mapa de Karnaugh]] |
|||
[[cs:Karnaughova mapa]] |
|||
[[de:Karnaugh-Veitch-Diagramm]] |
|||
[[en:Karnaugh map]] |
|||
[[es:Mapa de Karnaugh]] |
|||
[[et:Karnaugh' kaart]] |
|||
[[fi:Karnaugh’n kartta]] |
|||
[[fr:Table de Karnaugh]] |
|||
[[gl:Mapa de Karnaugh]] |
|||
[[he:מפת קרנו]] |
|||
[[hu:Karnaugh-tábla]] |
|||
[[it:Mappa di Karnaugh]] |
|||
[[ja:カルノー図]] |
|||
[[nl:Karnaugh-diagram]] |
|||
[[pl:Metoda Karnaugh]] |
|||
[[pt:Mapa de Karnaugh]] |
|||
[[ro:Diagramă Karnaugh]] |
|||
[[ru:Карта Карно]] |
|||
[[sk:Karnaughova mapa]] |
|||
[[sr:Карноова карта]] |
|||
[[sv:Karnaughdiagram]] |
|||
[[vi:Bìa Karnaugh]] |
|||
[[zh:卡诺图]] |
Поточна версія на 14:03, 7 серпня 2023
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg/220px-K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg.png)
Карта Карно (K-карта скорочено) - метод спрощення виразів булевої алгебри, зроблене Морісом Карно в 1953 поліпшення Діаграм Вейча, винайдених Едвардом Вейчем в 1952. Карта Карно зменшує потребу в обширних обчисленнях, використовуючи перевагу людської можливості розпізнання шаблонів, дозволяє швидке розпізнавання і виключення потенційних станів гонитви.
В карті Карно булеві змінні переносяться (зазвичай з таблиці істинності) і впорядковуються згідно з принципами кода Грея, в якому тільки одна змінна змінюється при переході між сусідніми квадратами. Коли таблиця згенерована, і у відповідні комірки записані вихідні значення, дані організовуються в найбільші можливі групи, що містять 2n комірок (n=0,1,2,3...)[1]. Далі, працюючи з цими групами, отримують мінімізовану ДНФ.
Карта Карно була винайдена в 1952 Едвардом Вейчем і розроблена далі в 1953 Морісом Карно, інженером з телекомунікацій в Bell Labs.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ef/K-map_minterms.svg/220px-K-map_minterms.svg.png)
Зазвичай, значні обчислення потрібні для отримання мінімального виду булевої функції, однак карта Карно зменшує потребу таких обчислень завдяки:
- Використанню можливості людського розуму по розпізнаванню шаблонів для визначення які терми мають бути поєднані для отримання найпростішого виразу.
- Дозволяє швидко визначити та видалити потенційні стани гонитв, які неминучі в булевих рівняннях.
- Забезпечує найкращу допомогу в спрощенні до шістьох змінних, однак з більшою кількістю змінних стає складно розрізнити оптимальні шаблони.
- Допомагає в навчанні про булеві функції та їх мінімізацію.
Карта Карно зазвичай стає важкою для розпізнання при збільшені кількості змінних. Загальне правило таке: карта Карно добре працює до чотирьох-п'яти змінних, і не має використовуватись з більше ніж шістьома змінними. Для виразів з більшою кількістю змінних може бути використаний Метод Куайна — Мак-Класкі. Сьогодні здебільшого для процесу мінімізації використовуються комп'ютери, для яких евристичний алгоритм еспресо став стандартною програмою мінімізації.
Кожна змінна має два значення: початкове та обернене. Змінні впорядковуються згідно з кодом Грея, тобто тільки одна змінна змінюється між двома суміжними комірками. У відповідні комірки записуємо вихідні значення функції.
Коли карта Карно заповнена, для отримання мінімізованої функції "1"-ці або "0"-лі групуються в найбільші можливі прямокутні групи, в яких кількість комірок в групі має дорівнювати степеню 2.[1] Наприклад, група може складатися з 4 комірок в лінію, 2 в висоту і 4 в ширину, 2 на 2 і так далі. Байдужий стан (зазвичай позначений Х) групується тільки тоді, коли група отримана з його використанням більша ніж без нього. Комірки можуть бути використані більше ніж один раз тільки якщо завдяки цьому утворюється менша кількість груп. Кожна "1" або "0" має бути задіяна як мінімум в одній групі.
У випадку використання карти Карно для частково заданих функцій в комірках, що відповідають невикористаним вхідним наборам проставляємо "Х" (зірочки, тильди тощо). Ці комірки при необхідності включаються в контури разом з "1" (при отримані формули на базі ДНФ), або "0" (при отримані формули на базі КНФ). При цьому функція після мінімізації виявляється простішою. Розглянемо карту Карно представлену на малюнку праворуч. Якщо при побудові функції не враховувати байдужі стани, то отримаємо функцію утворену трьома контурами на наступному кроці отримаємо . Ця функція значно спроститься якщо використовувати байдужі стани при виділенні контурів. При цьому утворюється лише один контур (на малюнку вказаний пунктиром). В результаті отримаємо .
Кожна отримана в карті Карно група продукує кон'юнкцію змінних, що не міняють своє значення в межах окресленої області, якщо змінна нульова, тоді в кон'юнкції ставимо заперечення. Аналогічні дії виконуємо для всіх груп (контурів). Кон'юнкції об'єднуємо диз'юнкцією.
Для побудови інверсної функції групуємо "0" замість "1".
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a2/K-map_4-variable_Venn_with_minterms.svg/220px-K-map_4-variable_Venn_with_minterms.svg.png)
Кожна комірка карти Карно відповідає мінтерму. Малюнок праворуч показує розташування кожного мінтерма на карті. Діаграма Венна для чотирьох множин названих 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 |
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b7/K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14.svg/220px-K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14.svg.png)
Існує 16 варіантів комбінації вхідних змінних, таким чином карта Карно має 16 позицій, і організована у вигляді решітки 4*4.
Двійкові цифри в карті показують вихід функції для будь-якої комбінації на вході. Таким чином 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.
Три терма, що покривають інверсну функцію показані сірими прямокутниками з границями різного кольору.
- коричнева—
- золота—
- синя—
Це породжує інверсію:
Після використання законів де Моргана, може бути визначена КНФ:
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg/220px-K-map_6%2C8%2C9%2C10%2C11%2C12%2C13%2C14_anti-race.svg.png)
Карта Карно корисна для виявлення та виключення станів гонитви. Їх дуже легко визначити використовуючи карту Карно через те, що умови гонитви існують, коли рухаєшся між будь-якою парою суміжних але роз'єднаних, груп окреслених на карті.
- В попередньому прикладі, потенційно умови гонитви існують, коли 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7f/Karnaugh_map_minimize.gif/220px-Karnaugh_map_minimize.gif)
Для таблиць 5 і більше змінних треба враховувати, що квадрати 4х4 віртуально розташовані один над одним в третьому вимірі, через це відповідні комірки двох сусідніх квадратів 4х4 є поєднаними, і відповідні терми можна склеювати.
- ↑ а б Карти Карно - Правила спрощення. Архів оригіналу за 18 квітня 2017. Процитовано 30 травня 2009.
Освітні
- Виявлення прямокутників, що перетинаються [Архівовано 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.