Karnaugh’n kartta

Esimerkki Karnaugh’n kartasta

Karnaugh’n kartta on loogisten lausekkeiden sieventämiseen tarkoitettu graafinen työkalu. Sitä käytetään yksinkertaistamaan logiikan supistamista ja eliminoimaan suunnitteluvirheitä digitaalitekniikassa.

Rakenne ja toiminta

Karnaugh’n kartta on taulukko, johon on sijoitettu loogisen lausekkeen totuustaulu niin, että siirryttäessä solusta viereiseen vain yhden muuttujan lähtöarvo muuttuu, mikä on keskeinen ominaisuus. Jokaista riviä ja saraketta vastaavat tietyt lähtöarvot. Jotta kartta toimisi, nämä on järjestettävä tietyllä tavalla, toisin sanottuna järjestyksen on noudatettava Gray-koodauksen periaatetta.

Kartasta muodostetaan sievennetty tulojen summa- tai summien tulo-muotoinen lauseke. Sieventämisessä kartalta etsitään vierekkäisiä soluja, joissa on sama arvo. Tarkastelun kohteeksi valitaan joko tosi- tai epätosi-solut riippuen siitä, kumman muotoinen lauseke halutaan johtaa: tosi-solut tulojen summaa varten ja epätosi-solut summien tuloa varten. Tarkoitus on jakaa kartta mahdollisimman isoihin suorakulmaisiin alueisiin, joiden solujen määrä on jokin kahden potenssi (1, 2, 4, 8...), joiden sisällä kaikissa soluissa on sama arvo, jotka voivat mennä päällekkäin, ja jotka sisältävät lopulta kaikki solut, joissa on tarkastelun kohteeksi valittu totuusarvo.

Sievennetyssä lausekkeessa tulee olemaan yhtä monta termiä kuin kartalta on löydetty yhtenäisiä alueita. Jokaista yhtenäistä aluetta vastaava termi muodostetaan etsimällä ne muuttujat, joiden lähtöarvot pysyvät koko sen alueella samoina. Tulojen summa-lauseketta (ykkösalueet) varten jokainen tällainen muuttuja jonka lähtöarvo on tosi, otetaan termiin sinällänsä, ja jokainen sellainen jonka lähtöarvo on epätosi, otetaan termiin komplementoituna. Vastaavasti summien tulo-lauseketta (nolla-alueet) varten lähtöarvonsa koko alueella samana säilyttävistä muuttujista todet otetaan komplementoituina, ja epätodet sinällänsä.

Jokainen kartan solu vastaa yhtä lausekkeen kanonisen muodon minimitermiä tai maksimitermiä. Toisin sanoen Karnaugh'n karttaa ei voi soveltaa, jos lausekkeet eivät ole kanonisessa muodossa.

Solujen vierekkäisyysehto

Kaksi kartan solua on vierekkäin joko vaaka tai pystytasossa, mutta ei viistosti. Lisäksi kaksi solua, jotka ovat samassa linjassa (vaaka tai pysty) ja vastakkaisissa reunoissa, ovat vierekkäin, koska kartan reunat kietoutuvat ympäri.

Tulojen summa -muotoisten lausekkeiden sievennys

Ryhmien muodostaminen tosi-soluista, kun kyseessä on kanoninen tulojen summa -muotoinen lauseke:

1. Ryhmässä täytyy olla 1,2,4,8 tai 16 tosi-solua. Jos kyseessä on 3 muuttujan kartta, suurin ryhmäkoko on 8.
2. Jokaisen tosi-solun ryhmässä täytyy olla vierekkäin ainakin yhden toisen tosi-solun kanssa, mutta kaikkien tosi-solujen ei tarvitse olla vierekkäin kaikkien kanssa. (Esim. 4-soluinen neliönmuotoinen ryhmä)
3. Tavoitteena aina mahdollisimman suuri ryhmäkoko noudattaen kuitenkin sääntöä 1.
4. Jokaisen tosi-solun täytyy kuulua johonkin ryhmään. Ryhmät saavat leikata, eli kahdella ryhmällä voi olla yhteinen tosi-solu.

Summien tulo - muotoisen lausekkeen sievennys kartan avulla toimii vastaavalla tavalla, mutta ryhmät muodostetaan epätosi-soluista.

Esimerkki

Totuustaulu, jossa X merkitsee don't care -termejä:

A B C D	f(A, B, C, D)
0 0 0 0	0
0 0 0 1	0
0 0 1 0	0
0 0 1 1	0
0 1 0 0	0
0 1 0 1	0
0 1 1 0	0
0 1 1 1	1
1 0 0 0	1
1 0 0 1	1
1 0 1 0	X
1 0 1 1	X
1 1 0 0	X
1 1 0 1	X
1 1 1 0	X
1 1 1 1	X

Valitaan totuustaulusta minimitermit (rivit, joiden totuusarvo on 1), jolloin saadaan tulojen summa -lauseke:

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

Piirretään 4x4 Karnaugh'n kartta, johon merkitään minimitermit 1:llä ja ryhmitetään vierekkäiset (siniset alueet):

Ryhmityksen jälkeen minimoidaan jokainen ryhmä erikseen. Ideana on etsiä sellaiset muuttujat, jotka eivät vaihda tilaansa eri termeissä. Toinen keino on supistaa lausekkeita Boolen algebran säännöillä. Yksittäinen solu kohdassa 0111 ei minimoidu, joten se pysyy ennallaan ${\overline {A}}BCD$

Parista 1000 ja 1001 huomataan, että kaikki paitsi $D$ säilyttää tilansa, jolloin se poistetaan ja jää $A{\overline {B}}\,{\overline {C}}$

Minimoinnin jälkeen yhdistetään ryhmät takaisin yhdeksi tulojen summa -lausekkeeksi $f(A,B,C,D)={\overline {A}}BCD+A{\overline {B}}\,{\overline {C}}$

Don't care -termien hyödyntäminen

Don't care -termit ovat binäärikombinaatioita, jotka eivät koskaan ilmene tai ovat kiellettyjä. Esimerkiksi BCD-koodissa on kuusi kiellettyä binäärikombinaatiota, joita ei koskaan käytetä. Luonteensa vuoksi niiden voidaan ajatella olevan "jokereita" eli joko tosia tai epätosia. Karnaugh'n kartassa don't care -termejä voidaan käyttää hyödyksi parantamaan minimointitulosta. Seuraavassa esimerkissä lasketaan edellinen esimerkki uudelleen ottaen don't care -termit huomioon.

Nyt isommasta (violetista) alueesta saadaan vasemmalta oikealle ensin yläriviltä ja sen jälkeen alariviltä $AB{\overline {C}}\,{\overline {D}}+AB{\overline {C}}D+ABCD+ABC{\overline {D}}+A{\overline {B}}\,{\overline {C}}\,{\overline {D}}+A{\overline {B}}\,{\overline {C}}D+A{\overline {B}}CD+A{\overline {B}}C{\overline {D}}$. Tutkimalla lauseketta huomataan, että $A$ on ainoa, joka pitää tilansa. Lauseke supistuu siis muotoon $A$.

Pienemmästä (vihreästä) alueesta saadaan ${\overline {A}}BCD+ABCD$ ja se supistuu muotoon $BCD$, joten kokonainen lauseke on $f(A,B,C,D)=A+BCD$

Katso myös

• Boolen algebra
• Kanoniset muodot

Lähteet

• Floyd, Thomas L.: Digital Fundamentals 7th ed. Prentice Hall, 2000. englanti