Digitaalipiirit/Karnaugh'n kartta

Digitaalipiirit

Karnaugh'n kartta (Karnaugh map / K-map) avulla voidaan esittää ja sieventää graaffisesti loogisia lausekkeita. Lausekkeen muuttujien määrää ei ole rajoitettu,mutta käytännössä menetelmä soveltuu enintään viiden muuttujan lausekkeiden sieventämiseen. Karnaugh'n kartta sisältää täsmälleen saman informaatioin kuin totuustaulu, mutta sieventämistä varten se on järjestetty tietyllä tavalla kaksiulotteiseksi ruudukoksi. Totuustaulun vaakariviä vastaa kartan yksi ruutu,joka sisältää funktion arvon.

Karnaugh'n kartan laatiminen

Tässä osassa käydään läpi kuinka kartta laaditaan ja miten totuustaulu muunnetaan Karnaugh'n kartaksi, kun muuttujia on 2-5. Kartan ruudukko on laadittava siten,että liikuttaessa ruudusta toiseen vaaka- tai pystysuunnassa vain yhden muuttujan arvo vaihtuu.

Kuvassa 1-1 (a) on kahden muuttujan funktion F(a,b) = Σm(1,2) = !ab + a!b totuustaulu,joka on kuvissa (b) ja (c) munnettu Karnaugh'n kartan muotoon. Kartan ruudut on numeroitu; numerot ovat kunkin ruudun vasemmassa yläkulmassa. Totuustaulun rivi vastaa samannumeroista kartan ruutua. Funktion arvo on ruudun keskellä. Muuttujien arvot voidaan merkitä Karnaugh'n karttaan kahdella eri tavalla. Kuvassa 1-1 (b) on kaarisuluilla merkitty se sarake ja rivi, joissa muuttuja saa arvon 1. Kuvassa 1-1 ( c) on esitetty vakioarvoisen muuttujan arvo kullakin vaaka- ja pystyrivillä. Kartasta havaitaan, että vierekkäiset ruudut vaaka- ja pystysuunnassa eroavat vain toisen muuttujan arvon osalta.

Kuva 1-1. Kahden muuttujan funktion (a) totuustaulu sekä (b) ja (c) Karnaughn´n kartan eri merkintätavat

Kuvassa 1-2 on kolmen muuttujan funktion F(a,b,c)=Σm(1,3,4,6)=!a!bc + !abc + a!b!c + ab!c totuustaulu ja Karnaugh'n kartta molemmilla tavoilla. Ruudut numeroitu kuten kahden muuttujan tapauksessa ja funktion arvot sijoitettu ruutuihin. Kuvan 1-2 kahden muuttujan tapauksessa ja funktion arvot sijoitettu ruutuihin. kuvan 1-2 (b) kaarisuluilla on taas osoitettu ne ruudut,joissa muuttujalla on arvo 1. On erityisesti huomattava ruutujen 4-7 järjestys. Sen on oltava kuten kuvassa,muuten kartan idea ei toteudu. Kartasta havaitaan miten vain yksi muuttuja vaihtaa arvoaan siirtyessä ruudusta toiseen vaaka- pystysuunnassa. Tämä pätee myös kun siirrytään ruudusta 4 ruutuun 0 tai ruudusta 1 ruutuun 5. Karnaugh'n kartan voi ajatella jatkuvan reunojensa yli ikään kuin paperi olisi taivutettu lieriöksi(kt. kuva 1-5). Kun luetaan ruutuja järjestyksessä vasemmalta oikealle tulee esimerkiksi ruudun 4 jälkeen ruutu 0.

Kuva 1-2. Kolmen muuttujan funktion totuustaulu, (b) ja (c) Karnaughn´n kartan esitystavat

Kahdesta Karnaughn´n kartan esitysmuodosta on kohdan (b) mukainen yksinkertaisempi ja havainnollisempi. Tavallisesti ruutuja ei numeroida, mutta joissakin tapauksissa siitä on hyötyä. Kuvissa 1-3 ja 1-4 on neljän ja viiden muuttujan kartat. Ruutujen numeroinnissa esiintyy hyppy nyt myös pystysuunnassa. Viiden muuttujan kartta muodostuu kahdesta osakartasta,joista toisessa yksi muuttuja (A) on aina 0 ja toisessa aina 1. Karttaa käytettäessä osakartat kuvitellaan siirretyiksi toisensa päälle. Viiden muuttujan kartan käyttö lausekkeen sieventämiseen on jo hankalaa. kuuden ja sitä useamman muuttujan kartan käyttö on liian monimutkaista,joten sieventäminen on suoritettava muilla menetelmillä.

Kuva 1-3. Neljän muuttujan (a) totuustaulu, (b) ja (c) Karnaughn´n kartta

Kuva 1-4. Viiden muuttujan Karnaughn´n kartta

Kolmen muuttujan kartan voi kuvitella lieriöksi. Neljän muuttujan kartan voi ajatella taivutetun toroidin muotoiseksi doniksiksi (kuva 1-5)

Kuva 1-5. Kolmen ja neljän muuttujan kartan havainnollistus

Karnaughn´n kartta voidaan piirtää myös usealla muulla tavalla. Mitkä tahansa kaksi muuttujaa voidaan vaihtaa keskenään tai minkä tahansa muuttujan 0- ja 1-alueet voidaan vaihtaa keskenään.

Loogisten lausekkeiden sieventäminen Karnaugh'n kartalla

Sieventämisen periaatteet

Lausekkeiden sieventämisellä voidaan pienentää toteutukseen tarvittavaa komponenttimäärää ja mahdollisesti poistaa tarpeettomia termejä ja muuttujia, jolloin piiristä tulee halvempi,luotettavampi ja selkeämpi. Kahdesta viiteen muuttujaa sisältävät lausekkeet voidaan sieventää Karnaugh'n kartalla. Enemmän muuttujaa sisältävät lausekkeet on sievennettävä tietokonemenetelmillä. Aikasemmin on esitetty erimerkkejä lausekkeiden sieventämisestä kytkentäalgebran avulla. Yleensä siitä ei kannata tehdä, sillä on vaikeaa nähdä mitä aksioomia ja teoreemoja ja missä järjestyksessä niitä kannattaa käyttää.

Karnaugh'n kartan täyttäminen

Funktion arvot on ensin sijoitettava kartalle. Kartan täyttö on helppoa, jos funktion totuustaulu tunnetaan. Nollat ja ykköset sijoitetaan totuustaulun funktiosarakkeesta kukin omaa vaakariviään vastaavan kartan ruutuu. Jos totuustaulua ei tunneta, kartta voidaan laatia esimerkin 1-1 kuvaamalla tavalla, jos funktio on esitetty tulojen summa-muodossa. Mikäli funktio on esitetty summien tulo-muodossa,karttaan saadaan jokaisesta summatermistä nolla niihin ruutuihin, joissa kyseinen termi saa arvon 0.

Sieventäminen Karnaugh'n kartalla

Sen jälkeen kun arvot on sijoitettu kartalle, aloitetaan sieventäminen. Sieventämisellä on mahdollista saada joko yksinkertaisin tulojen summamuotoinen lauseke tai summien tulomuotoinen lauseke. Tapauksessa 1-6 tarkastellaan ruutuja,joissa funktiolla on arvo 1, kuvassa 1-7 ruutuja, joissa arvo on 0.

Kuva 1-6. Funktion F(A,B,C,D) = !AB + AC!D + AB!CD + CD Karnaugh'n kartta

Kuva 1-7. Kuvan 1-6 kartan kaikki ykköset on peitetty mahdollisimman vähillä ja mahdollisimman suurilla alueilla.

Sieventäminen perustuu siihen, että kaikki ykköset (nollat) peitetään mahdollisimman suurilla alueilla, jolloin termeissä on vähän muuttujia. Alue muodostuu vierekkäisistä ruuduista, joissa lausekkeella on arvo yksi (nolla). Alueen koon tulee olla 2^n (1,2,4,8, tai 16) ruutua,joissa n kokonaisluku, ja sen tulee vastata tulotermiä (summatermiä). Sama ruutu voi kuulua useampaan alueeseen. Esimerkki kuvan 1-6 kartan kaikki ykköset voidaan peittää kuvan 1-7 alueilla. Kuvaan 1-7 on merkitty mikä tulotermi kuvaa mitäkin aluetta. Kutakin aluetta vastaava tulotermi valitaan niin, että se saa kyseisellä alueella arvon 1. !AB:llä merkityllä aluella A = O ja B = 1, AC-alueella A= C = 1, BD:llä B = D = 1 ja CD:llä C = D = 1. Sievennetty lauseke on tulotermien summa eli F(A,B,C,D) = !AB + AC + BD + CD. Vaikka sievennetyn lausekkeen tulotermien määrä ei ole vähentynyt alkuperäiseen lausekkeeseen verrattuna, on se kuitenkin selvästi yksinkertaisempi, koska termeissä on vähemmän muuttujia.

Jos tuloksesta halutaan mahdollisimman yksinkertainen summien tulomuotoinen lauseke,niin menetellään seuraavasti. Koska nyt on peitettävä kaikki nollat, alueet muodostuvat kuvan 1-8 mukaisesti.

Kuva 1-8. Summien tulomuotoisen lausekkeen muodostaminen.

Alueiden termit ovat nyt summamuotoisia. Lisäksi on huomattava, että muuttuja invertoidaan, jos sillä on alueessa arvo 1, sillä summatermin on saatava arvo 0.

Lähteet

• Seppo Haltsonen, Jaakko Levomäki, Esko T. Rautanen: Digitaalitekniikka. Edita, 2004. ISBN 951-37-3886-8.