Minimizacija logičkih funkcija i Karnoove mape

Jedno polje primene minimizacije logičkih funkcija je projektovanje digitalnih kola, gde se minimizacijom postiže manji utrošak materijala, jeftinija proizvodnja itd. Minimizacija logičkih funkcija može da se vrši na više načina. Jedan zgodan način su Karnoove mape. Ovaj metod je zgodan za minimizaciju funkcija sa do 4 parametra, nakon toga postaje prilično nezgodno formirati i obraditi tabelu, ali postupak jeste moguće algoritamski modelovati i automatizovati.

Karnoove mape

Karnoova mapa je tabelarni prikaz logičke funkcije, gde se po osama tabele predstavljaju vrednosti parametara. Karnoova mapa za funkciju sa dva parametra izgleda ovako:

Svako polje tabele predstavlja jednu kombinaciju vrednosti parametara. U ovom slučaju, parametri su p i q, svaki parametar može da ima logičke vrednosti 0 ili 1, što znači da imamo 2²=4 moguće kombinacije vrednosti parametara. U svako polje upisuje vrednost logičkog izraza za odgovarajuće vrednosti parametara.

Neka je logička formula f=p and not q. Tablica iskaza izgleda ovako:

Karnoovu mapu popunjavamo vrednostima iskaza f, po koordinatama za vrednosti p i q. Upareno je bojama.

Ako bismo gledali samo Karnoovu mapu, možemo da pročitamo izraz u DNF tako što uzmemo samo polja gde je 1. To je ovde samo jedno polje, za vrednost p=1 i q=0, pa je DNF forma oblika f = (p * -q).

Ovde nema prostora za optimizaciju jer je samo jedna kombinacija parametara takva da daje tačan rezultat.

Karnoova mapa za iskaz sa tri parametra

Kada imamo više od dva parametra, Karnoova mapa predstavlja kombinacije parametara. Sa tri parametra, p,q,r, po vertikali ćemo imati parametre p i q, sa njihovim kombinacijama (dakle, 4 reda) a po horizontali ćemo imati parametar r (dakle, 2 kolone). Sa četiri parametra ćemo imati tablicu 4x4, gde imamo sa jedne strane kombinacije za p i q, a sa druge za r i s. Za više od četiri parametra prati se ista logika ali tablica postaje veća i ima još nekoliko faktora koji se uzimaju u obzir.

Kombinacije dva parametra se ne ređaju numerički: 00,01,10,11, već po principu najmanjeg rastojanja – tako da se dve susedne kombinacije razlikuju samo za jedno mesto: 00, 01, 11, 10. Ovakav raspored je cikličan, pa Karnoova mapa može da se rotira, i zapravo je trodimenziona – leva i desna ivica se nastavljaju, gornja i donja se nastavljaju. Karnoova mapa je zapravo torus-krofna. Kombinacije se ređaju, dakle, 00, 01, 11, 10, 00, 01, 11, 10, 00 itd.

Sa tri parametra, kombinacije bi se ređale ovako: 000, 001, 011, 010, 110, 111, 101, 100, pa ukrug od početka.

Primer

Logički iskaz zapisan je u indeksnoj formi: f = Σ(0,2,4,5)

Napravićemo kombinacionu tablicu:

Napravićemo Karnoovu mapu. U mapi su upisane kombinacije koje svako polje predstavlja.

Popunićemo Karnoovu  mapu vrednostima iskaza za kombinaciju vrednosti parametara:

Zapisaćemo DNF ovog iskaza: DNF(f) = (-p * -q * -r) + (-p * q * -r) + (p * -q * -r) + (p * -q * r)

Sada možemo da radimo minimizaciju.

Pogledajmo poslednji red. Vidimo dve susedne jedinice. Za p=1, q=0 rezultat će biti 1 i za r=0 i za r=1, što znači da nije bitno šta je r – ako su p=1,q=0, iskaz je svakako tačan, u oba slučaja. Ovo je prostor za optimizaciju.

Ako pogledamo DNF videćemo da u poslednja dva člana (p * -q * -r) + (p * -q * r) možemo da zamenimo p * -q sa A i dobijemo (A * -r) + (A * r). Ako izdvojimo A ispred, dobijemo A*(r + -r) =  A*T = A, čime smo izbacili r. Daljim algebarskim postupkom možemo da svedemo iskaz na minimalni oblik.

Karnoova mapa omogućava da grafički primetimo ovakve minimizacije.

Vrednosti parametara idu uzastopno, što znači da ako vidimo dve jedinice u dva susedna polja, horizontalno ili vertikalno, to znači da je jedan parametar irelevantan i može se ukloniti. Ako vidimo 4 susedna polja, bilo horizontalno, vertikalno ili kao kvadrat 2x2, to znači da možemo da uklonimo dva parametra.

Na Karnoovoj mapi vidimo dva takva slučaja:

Treba uzeti u obzir da je Karnoova mapa „savijena“ u krofnu. To znači da možemo da redove pišemo i po rasporedu 01,11,10,00. U tom slučaju bi prvi red došao na kraj tabele, pa vidimo da postoji i taj par jedinica. Ovo je prikazano na sledećoj tabeli:

Pravilo je da jedno polje tabele može da se upotrebi samo jednom za optimizaciju, što znači da bismo u ovom slučaju morali da biramo da li ćemo da grupišemo polja 000,100 ili polja 100,101. Evo uporedno obe optimizacije. Vidimo da je prva bolja jer obuhvata dve grupe, a druga samo jednu, i ostavlja dve jedinice „same“ – te jedinice su oni članovi DNF koji ostaju nepromenjeni.

Nastavićemo sa levom optimizacijom. Vidimo da u gornjoj, uspravnoj, grupi parametar p=0, r=0, q ima ove vrednost, pa se q izbacuje. U donjoj grupi se izbacuje r. Svaka grupa postaće jedan DNF član. Tako dobijamo p=0, r=0  ili   p=1, q=0, što daje

DNF(f) = (-p * -r) + (p * -q)

I ovo je minimizovani iskaz.

Primer

Logička formula sa 4 parametra p,q,r,s zapisana je u sažetom, indeksnom obliku:

f = Σ(0,2,4,6,10,11,14,15)

Kombinacije su: 0000, 0010, 0100, 0110, 1010, 1011, 1110, 1111

Zapisaćemo ovaj iskaz u normalnoj formi. 0 je (-p * -q * -r * -s) itd.

f = (-p*-q*-r*-s)+(p*q*-r*-s)+(-p*q*-r*-s)+(-p*q*r*-s)+(p*-q*r*-s)+(p*q*r*-s)+(p*q*r*s)

Napravićemo kombinacionu tablicu i na osnovu nje Karnoovu mapu

 Imamo nekoliko načina grupisanja polja. Najmanje grupa daje nam grupisanje kvadrata dole i kvadrata gore. Gornji kvadrat dobija se „savijanjem“ mape u krug.

Ovako izdvojene grupe daju nam dva člana DNF. Prvi (gornja grupa) uklanja parametre q i r, a ostaju p=0 i s=0. Drugi, donji, uklanja parametre q i s, i ostaju p=1 i r=1. Dobijamo sledeći iskaz:

DNF(f) = (-p * -s) + (p * r)

Dont-care vrednosti i Karnoove mape

Ako logička funkcija sadrži dont-care vrednosti-kombinacije parametara, u karnoovu mapu upisujemo x, i ta polja možemo da tretiramo kao 0 ili kao 1, već po potrebi, šta nam je zgodnije.

Primer

 f = Σ(2,5,15) + Σd(0,1,3,4,7,9,13,14)

Rezultujući izraz ima dva člana. Tri X polja koja nisu obuhvaćena se ignorišu. Optimizovani izraz je:

f = (-r * -s) + (q * s)