Karnoova karta

Karnoova karta, Karnoova mapa ili skraćeno K-mapa, je metod za uprošćavanje izraza Bulove algebre. Moris Karno je izmislio ovaj metod 1953, kao poboljšanje Veičevog dijagrama. Karnoova mapa smanjuje potrebu za napornim kalkulacijama tako što koristi ljudsku sposobnost prepoznavanja obrazaca. Ona takođe dozvoljava brzu identifikaciju i eliminaciju potencijalnih problema sa trkama uslova.

Primer Karnoove karte

Potrebni Bulovi rezultati su smešteni iz tablice istinitosti u dvodimenzionalnu matricu gde su ćelije poređane u Grejovom kodu, i svaka pozicija svake ćelije predstavlja jednu kombinaciju ulaznih parametara, dok vrednost svake ćelije predstavlja odgovarajuću izlaznu vrednost. Biraju se optimalne grupe jedinica i nula, koje predstavljaju izraze kanonskog oblika originalne tablice istinitosti. Ovi izrazi se mogu iskoristiti za zapisivanje minimalnog Bulovog izraza koji predstavlja zahtevanu logiku.

Karnoove mape se koriste da uprošćavanje logičkih problema u realnom životu tako da se oni mogu implementirati tako da zahtevaju minimalan broj logičkih kola. Izrazi sume proizvoda se uvek mogu implementirati korišćenjem logičkog kola I koja se spajaju u logička kola ILI, i proizvod suma se može implementirati koristeći logička kola ILI koja se spajaju u logička kola I. Karnoove mape se mogu koristiti i za uprošćavanje logičkih izraza u softverskom dizajnu. Bulovi uslovi, kao na primer uslovne naredbe, se mogu dosta ukomplikovati, što čini programski kod teškim za čitanje i održavanje. Kada se minimizuje, kanonski oblik izraza sume proizvoda i proizvoda sume se može implementirati direktno pomoću I i ILI logičkih operacija.

Primer

Karnoove mape se koriste kao proces uprošćavanja funkcija Bulove algebre. Uzmimo Bulovu ili binarnu funkciju opisanu u sledećoj tablici istinitosti.

Tablica istinitosti funkcije

	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

Slede dve različite notacije koje opisuju istu funkciju u neuprošćenom obliku Bulove algebre, koristeći promenljive $A$, $B$, $C$, $D$ i njihove inverzne vrednosti.

• $f(A,B,C,D)=\sum _{}m(6,8,9,10,11,12,13,14)$ Napomena: Vrednosti u sumi su one koje imaju izlaz 1 u tablici istinitosti.

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

Karnoova mapa

K-mapa nacrtana na torusu i u ravni. Ćelije sa tačkama su susedne.

Konstrukcija Karnoove mape.

U ovom slučaju, za ulaz od 4 promenljive možemo dobiti 16 kombinacija, pa tablica istinitosti ima 16 redova i Karnoova mapa ima 16 pozicija. Što znači da će Karnoova mapa biti raspoređena u matricu 4 × 4.

Vrednosti redova i kolona (prikazane na vrhu i sa leve strane mape) su poređane po Grejevom kodu umesto binarnog brojevnog poretka. Grejev kod osigurava da se samo jedna promenljiva menja između svakog para susednih ćelija. Svaka ćelija kompletne Karnoove mape sadrži binarnu cifru koja predstavlja rešenje funkcije za tu kombinaciju ulaza.

Nakon što je Karnoova mapa konstruisana ona se koristi za nalaženje najprostijih izraza za informacije iz tablice istinitosti. Susedne jedinice u Karnoovoj mapi predstavljaju mogućnosti za uprošćavanje izraza. Minimalni izraz se dobija zaokruživanjem grupa jedinica na mapi. Te grupe moraju biti pravougaonog oblika i moraju da imaju površinu veličine nekog stepena broja 2 (npr.  1, 2, 4, 8...). Ti pravougaonici treba da budu što veći, ali ne smeju da sadrže nule. Grupe smeju da se preklapaju u cilju da se povećaju. Optimalna grupisanja na ovom primeru su prikazana zelenim, crvenim i plavim linijama, i crvena i zelena grupa se preklapaju. Crvena grupa je polje sa 2 × 2 ćelije, zelena je 4 × 1, i oblast preklapanja je označena braon bojom.

Mreža je torusnog oblika što znači da se polja koja se nalaze na ivici matrice spajaju sa drugim na krajevima matrice (videti sliku). Ćelije skroz desno su zapravo susedne sa ćelijama koje su skroz levo. To takođe važi i za ćelije koje se nalaze skro na vrhu i na dnu. Tako da $A\scriptstyle {\overline {D}}$ može da bude validan izraz – on uključuje ćelije 12 i 8 na vrhu, i spaja ih sa ćelijama 10 i 14 na dnu – kao i $\scriptstyle {\overline {B}}\,{\overline {D}}$, koji uključuje 4 ćoška.

Rešenje

K-mapa prikazuje minimalne izraze obojene kao pravougaonike i kvadrate. Braon oblast je preklapanje crvenog i zelenog pravougaonika.

Kada je Karnoova mapa konstruisana i susedne jedinice povezane u pravougaone grupe, minimalno algebarsko rešenje se može naći posmatranjem promenljivih koje ostaju u istim grupama.

Za crvenu grupu:

• Promenljiva $A$ je ista i jednaka je jedinici u celoj grupi, što znači da treba da bude uključena u algebarsku reprezentaciju izraza.

• Promenljiva $B$ ne održava isto stanje, već se menja iz jedinice u nuli, i ona treba da bude isključena.

• Promenljiva $C$ se ne menja. Ona je uvek nula, čak i njen komplement, što znači da treba da bude uključena.

• I promenljiva $D$ se menja, što znači da je isključujemo.

Znači, prvi deo izraza u Bulovoj sumi proizvoda je izraz $A{\overline {C}}$.

Za zelenu grupu, $A$ i $B$ održavaju isto stanje, dok se $C$ i $D$ menjaju, što znači da dobijamo $A{\overline {B}}$.

Na isti način, plava grupa nam daje izraz $BC{\overline {D}}$.

Konačno rešenje je jednostavno proizvod ovih grupa, odnosno $A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}$.

Na ovaj način smo uz pomoć Karnoovih mapa uprostili izraz

$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}})$

u

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

Takođe bi bilo moguće doći do ovog rešenja pažljivom upotrebom aksioma Bulove algebre, ali vreme koje je potrebno za tako nešto raste eksponencijalno.

Inverz

Inverzna funkcija se rešava na isti način, s tim što se u tom slučaju grupišu nule umesto jedinica.

Tri izraza iskorišćena da pokriju inverznu funkciju su pokazana sa sivim pravougaonicima sa različitim bojama okvira:

• Braon—${\overline {A}}\,{\overline {B}}$
• Zlatna—${\overline {A}}\,{\overline {C}}$
• Plava—$BCD$

Što nam daje inverznu funkciju:

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

Kroz korišćenje De Morganovih zakona proizvod suma može biti određen:

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

Nebitna stanja

Vrednost f(A,B,C,D) za ABCD = 1111 je zamenjena nebitnim stanjem. Ovo briše zelenu oblast kompletno i omogućava crvenoj da bude veća. Takođe dozvoljava plavoj oblasti u inverznoj funkciji da se poveća.

Karnoove mapa takođe dozvoljavaju laku minimizaciju funkcija za čije tablice istinitosti koje sadrže nebitna stanja. Nebitno stanje je kombinacija ulaza za koje dizajner ne želi da zna šta je izlaz. Upravo zato, te slučajeve možemo iskoristiti i kao nule i kao jedinice, šta nam više odgovara. One se uglavnom označavaju sa X ili d.

Primer na desnoj strani je isti kao i primer iznad, ali je u njemu vrednost F za ABCD = 1111 zamenjen sa nebitnim stanjem. Ovo nam omogućava da crvenu grupu proširimo skroz do dna, i samim tim, izbacimo zelenu grupu.

Na osnovu ovoga dobijamo novu jednačinu:

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

Primetite da je prvi izraz $A$, a ne $A{\overline {C}}$. U ovom slučaju smo izgubili izraz zelene grupe, uprostili smo crvenu grupu i izbegli trku uslova (prikazanu žutom bojom).

Slučaj za inverznu funkciju je sledeći:

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

Trke uslova

Eliminacija

Karnoove mape su korisne za detektovanje i eliminaciju trka uslova.

• U primeru iznad, potencijalna trka uslova postoji kada je C jednako 1 i D jednako 0, A je 1, i B se menja iz 1 u 0 (pomerajući se sa plavog u zeleno stanje). Za ovaj slučaj, izlaz je definisan da ostane nepromenjen u 1, ali zato što ovaj prelaz nije pokriven odgovarajućim izrazom, postoji potencijal za kratkotrajni kvar (trenutna promena izlaza u 0).

• Drugi potencijalni kratkotrajni kvar u istom primeru je teže primetiti. Kada je D jednako 0 i A i B su 1, sa C-om koje se menja iz 1 u 0 (pomeranjem iz plavog u crveno stanje). U ovom slučaju se kratkotrajni kvar obavija oko vrha i dna mape

Iznad k-mape je dodat izraz $A{\overline {D}}$ da bi se izbegla trka uslova.

Da li će se ovi kratkotrajni kvarovi javiti, zavisi od fizičke prirode implementacije, i da li treba da brinemo o njima zavisi od primene.

U ovom slučaju, dodatni izraz $A{\overline {D}}$ bi eliminisao potencijalnu trku uslova, spajajući zeleno i plavo izlazno stanje ili plavo i crveno izlazno stanje: ovo je prikazano kao žuta oblast (koja se obavija sa dna na vrh sa desne strane) u dijagramu desno.

Izraz je nepotreban u izrazima statičke logike sistema, ali takvi redundantni izrazi su potrebni da bi se obezbedile dinamičke performanse bez trke uslova.

Slično, dodatni izraz ${\overline {A}}D$ se mora dodati na inverznu funkciju da bi se eliminisala potencijalna trka uslova. Koristeći De Morganov zakon dobijamo još jedan izraz proizvoda suma F, ali sa novim faktorom $\left(A+{\overline {D}}\right)$.

Primeri mapa sa 2 promenljive

Slede primeri sa svim mogućim Karnoovima mapama sa 2 promenljive. Pored svake se nalaze i minimalni izrazi kao funkcija $\sum m()$ i minimalni uslovi bez trke uslova.

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

Spoljašnje veze

• Quine–McCluskey algorithm implementation with a search of all solutions Arhivirano na sajtu Wayback Machine (3. novembar 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 Arhivirano na sajtu Wayback Machine (29. mart 2010)