Karnaugh’n kartta

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:

 Ryhmässä täytyy olla 1, 2, 4, 8 tai 16 tosi-solua. Jos kyseessä on 3 muuttujan kartta, suurin ryhmäkoko on 8.
 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ä.)
 Tavoitteena on aina mahdollisimman suuri ryhmäkoko noudattaen kuitenkin sääntöä 1.
 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ä (arvolla ei ole väliä):

 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:

Piirretään 4×4-ruutuinen Karnaugh’n kartta, johon merkitään minimitermit 1:llä ja ryhmitetään vierekkäiset (siniset alueet):

230px

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 muodossa .

Parista 1000 ja 1001 huomataan, että kaikki paitsi  säilyttää tilansa, jolloin se poistetaan ja jää .

Minimoinnin jälkeen yhdistetään ryhmät takaisin yhdeksi tulojen summa -lausekkeeksi: .

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.

230px

Nyt isommasta (violetista) alueesta saadaan vasemmalta oikealle ensin yläriviltä ja sen jälkeen alariviltä . Tutkimalla lauseketta huomataan, että  on ainoa, joka pitää tilansa. Lauseke supistuu siis muotoon .

Pienemmästä (vihreästä) alueesta saadaan  ja se supistuu muotoon , joten kokonainen lauseke on .

 Katso myös 
Boolen algebra
Kanoniset muodot

Lähteet


Luokka:Matemaattinen logiikka
Luokka:Digitaalitekniikka
Luokka:Tietokonetekniikka