Карноова карта

Карноова карта, Карноова мапа или скраћено К-мапа, је метод за упрошћавање израза Булове алгебре. Морис Карно је измислио овај метод 1953, као побољшање Веичевог дијаграма. Карноова мапа смањује потребу за напорним калкулацијама тако што користи људску способност препознавања образаца. Она такође дозвољава брзу идентификацију и елиминацију потенцијалних проблема са тркама услова.

Потребни Булови резултати су смештени из таблице истинитости у дводимензионалну матрицу где су ћелије поређане у Грејовом коду, и свака позиција сваке ћелије представља једну комбинацију улазних параметара, док вредност сваке ћелије представља одговарајућу излазну вредност. Бирају се оптималне групе јединица и нула, које представљају изразе канонског облика оригиналне таблице истинитости.^[1] Ови изрази се могу искористити за записивање минималног Буловог израза који представља захтевану логику.

Карноове мапе се користе да упрошћавање логичких проблема у реалном животу тако да се они могу имплементирати тако да захтевају минималан број логичких кола. Изрази суме производа се увек могу имплементирати коришћењем логичког кола И која се спајају у логичка кола ИЛИ, и производ сума се може имплементирати користећи логичка кола ИЛИ која се спајају у логичка кола И.^[2] Карноове мапе се могу користити и за упрошћавање логичких израза у софтверском дизајну. Булови услови, као на пример условне наредбе, се могу доста укомпликовати, што чини програмски код тешким за читање и одржавање. Када се минимизује, канонски облик израза суме производа и производа суме се може имплементирати директно помоћу И и ИЛИ логичких операција.^[3]

Карноове мапе се користе као процес упрошћавања функција Булове алгебре. Узмимо Булову или бинарну функцију описану у следећој таблици истинитости.

Таблица истинитости функције

	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

Следе две различите нотације које описују исту функцију у неупрошћеном облику Булове алгебре, користећи променљиве ${\displaystyle A}$, ${\displaystyle B}$, ${\displaystyle C}$, ${\displaystyle D}$ и њихове инверзне вредности.

• ${\displaystyle f(A,B,C,D)=\sum _{}m(6,8,9,10,11,12,13,14)}$ Напомена: Вредности у суми су оне које имају излаз 1 у таблици истинитости.

• ${\displaystyle 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}})}$

У овом случају, за улаз од 4 променљиве можемо добити 16 комбинација, па таблица истинитости има 16 редова и Карноова мапа има 16 позиција. Што значи да ће Карноова мапа бити распоређена у матрицу 4 × 4.

Вредности редова и колона (приказане на врху и са леве стране мапе) су поређане по Грејевом коду уместо бинарног бројевног поретка. Грејев код осигурава да се само једна променљива мења између сваког пара суседних ћелија. Свака ћелија комплетне Карноове мапе садржи бинарну цифру која представља решење функције за ту комбинацију улаза.

Након што је Карноова мапа конструисана она се користи за налажење најпростијих израза за информације из таблице истинитости. Суседне јединице у Карноовој мапи представљају могућности за упрошћавање израза. Минимални израз се добија заокруживањем група јединица на мапи. Те групе морају бити правоугаоног облика и морају да имају површину величине неког степена броја 2 (нпр.  1, 2, 4, 8...). Ти правоугаоници треба да буду што већи, али не смеју да садрже нуле. Групе смеју да се преклапају у циљу да се повећају. Оптимална груписања на овом примеру су приказана зеленим, црвеним и плавим линијама, и црвена и зелена група се преклапају. Црвена група је поље са 2 × 2 ћелије, зелена је 4 × 1, и област преклапања је означена браон бојом.

Мрежа је торусног облика што значи да се поља која се налазе на ивици матрице спајају са другим на крајевима матрице (видети слику). Ћелије скроз десно су заправо суседне са ћелијама које су скроз лево. То такође важи и за ћелије које се налазе скро на врху и на дну. Тако да ${\displaystyle A\scriptstyle {\overline {D}}}$ може да буде валидан израз – он укључује ћелије 12 и 8 на врху, и спаја их са ћелијама 10 и 14 на дну – као и ${\displaystyle \scriptstyle {\overline {B}}\,{\overline {D}}}$, који укључује 4 ћошка.

Када је Карноова мапа конструисана и суседне јединице повезане у правоугаоне групе, минимално алгебарско решење се може наћи посматрањем променљивих које остају у истим групама.

За црвену групу:

• Променљива ${\displaystyle A}$ је иста и једнака је јединици у целој групи, што значи да треба да буде укључена у алгебарску репрезентацију израза.

• Променљива ${\displaystyle B}$ не одржава исто стање, већ се мења из јединице у нули, и она треба да буде искључена.

• Променљива ${\displaystyle C}$ се не мења. Она је увек нула, чак и њен комплемент, што значи да треба да буде укључена.

• И променљива ${\displaystyle D}$ се мења, што значи да је искључујемо.

Значи, први део израза у Буловој суми производа је израз ${\displaystyle A{\overline {C}}}$.

За зелену групу, ${\displaystyle A}$ и ${\displaystyle B}$ одржавају исто стање, док се ${\displaystyle C}$ и ${\displaystyle D}$ мењају, што значи да добијамо ${\displaystyle A{\overline {B}}}$.

На исти начин, плава група нам даје израз ${\displaystyle BC{\overline {D}}}$.

Коначно решење је једноставно производ ових група, односно ${\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}}$.

На овај начин смо уз помоћ Карноових мапа упростили израз

${\displaystyle 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}})}$

у

${\displaystyle f(A,B,C,D)=A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}}$

Такође би било могуће доћи до овог решења пажљивом употребом аксиома Булове алгебре, али време које је потребно за тако нешто расте експоненцијално.

Инверзна функција се решава на исти начин, с тим што се у том случају групишу нуле уместо јединица.

Три израза искоришћена да покрију инверзну функцију су показана са сивим правоугаоницима са различитим бојама оквира:

• Браон—${\displaystyle {\overline {A}}\,{\overline {B}}}$
• Златна—${\displaystyle {\overline {A}}\,{\overline {C}}}$
• Плава—${\displaystyle BCD}$

Што нам даје инверзну функцију:

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

Кроз коришћење Де Морганових закона производ сума може бити одређен:

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

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

Карноове мапа такође дозвољавају лаку минимизацију функција за чије таблице истинитости које садрже небитна стања. Небитно стање је комбинација улаза за које дизајнер не жели да зна шта је излаз. Управо зато, те случајеве можемо искористити и као нуле и као јединице, шта нам више одговара. Оне се углавном означавају са X или d.

Пример на десној страни је исти као и пример изнад, али је у њему вредност F за ABCD = 1111 замењен са небитним стањем. Ово нам омогућава да црвену групу проширимо скроз до дна, и самим тим, избацимо зелену групу.

На основу овога добијамо нову једначину:

${\displaystyle F=A+BC{\overline {D}}.\,}$

Приметите да је први израз ${\displaystyle A}$, а не ${\displaystyle A{\overline {C}}}$. У овом случају смо изгубили израз зелене групе, упростили смо црвену групу и избегли трку услова (приказану жутом бојом).

Случај за инверзну функцију је следећи:

${\displaystyle {\overline {F}}={\overline {A}}{\overline {B}}+{\overline {A}}{\overline {C}}+{\overline {A}}D}$

Карноове мапе су корисне за детектовање и елиминацију трка услова.

• У примеру изнад, потенцијална трка услова постоји када је C једнако 1 и D једнако 0, A је 1, и B се мења из 1 у 0 (померајући се са плавог у зелено стање). За овај случај, излаз је дефинисан да остане непромењен у 1, али зато што овај прелаз није покривен одговарајућим изразом, постоји потенцијал за краткотрајни квар (тренутна промена излаза у 0).

• Други потенцијални краткотрајни квар у истом примеру је теже приметити. Када је D једнако 0 и A и B су 1, са C-ом које се мења из 1 у 0 (померањем из плавог у црвено стање). У овом случају се краткотрајни квар обавија око врха и дна мапе

Да ли ће се ови краткотрајни кварови јавити, зависи од физичке природе имплементације, и да ли треба да бринемо о њима зависи од примене.

У овом случају, додатни израз ${\displaystyle A{\overline {D}}}$ би елиминисао потенцијалну трку услова, спајајући зелено и плаво излазно стање или плаво и црвено излазно стање: ово је приказано као жута област (која се обавија са дна на врх са десне стране) у дијаграму десно.

Израз је непотребан у изразима статичке логике система, али такви редундантни изрази су потребни да би се обезбедиле динамичке перформансе без трке услова.

Слично, додатни израз ${\displaystyle {\overline {A}}D}$ се мора додати на инверзну функцију да би се елиминисала потенцијална трка услова. Користећи Де Морганов закон добијамо још један израз производа сума F, али са новим фактором ${\displaystyle \left(A+{\overline {D}}\right)}$.

Следе примери са свим могућим Карноовима мапама са 2 променљиве. Поред сваке се налазе и минимални изрази као функција ${\displaystyle \sum m()}$ и минимални услови без трке услова.

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

• Quine–McCluskey algorithm implementation with a search of all solutions Архивирано на сајту Wayback Machine (3. новембар 2013), by Frédéric Carpon.
• Detect Overlapping Rectangles, by Herbert Glarner.
• Using Karnaugh maps in practical applications, Circuit design project to control traffic lights.
• K-Map Tutorial for 2,3,4 and 5 variables
• Karnaugh Map Example Архивирано на сајту Wayback Machine (29. март 2010)