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.
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.
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.
Ryhmien muodostaminen tosi-soluista, kun kyseessä on kanoninen tulojen summa -muotoinen lauseke:Summien tulo - muotoisen lausekkeen sievennys kartan avulla toimii vastaavalla tavalla, mutta ryhmät muodostetaan epätosi-soluista.
Totuustaulu, jossa X merkitsee don't care -termejä:
Valitaan totuustaulusta minimitermit (rivit, joiden totuusarvo on 1), jolloin saadaan tulojen summa -lauseke:
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 formula_2
Parista 1000 ja 1001 huomataan, että kaikki paitsi formula_3 säilyttää tilansa, jolloin se poistetaan ja jää formula_4
Minimoinnin jälkeen yhdistetään ryhmät takaisin yhdeksi tulojen summa -lausekkeeksi formula_5
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ä formula_6. Tutkimalla lauseketta huomataan, että formula_7 on ainoa, joka pitää tilansa. Lauseke supistuu siis muotoon formula_7.
Pienemmästä (vihreästä) alueesta saadaan formula_9 ja se supistuu muotoon formula_10, joten kokonainen lauseke on formula_11