Signaalinkäsittelytekniikan laboratorio
Digitaalitekniikan perusteet

Luennot
Sivukartta
Sanasto
Laskuharjoitukset

Karnaugh'n kartan käyttö esimerkin avulla

Kartalla pyritään täsmälleen samaan kuin totuustaulun suhteen: muodostamaan mahdollisimman yksinkertainen lauseke, jolla pystytään määrittelemään funktion arvo. Kartasta katsomalla siis haetaan yksinkertaisia ehtoja muuttujille, jotta funktion arvo on haluttu kaikilla mahdollisilla muuttujakombinaatioilla. Kartta toimii siis oikopolkuna totuustaulusta yksinkertaiseen funktion määrittelevään lausekkeeseen.

Käytännössä tämä tapahtuu kalastamalla kartasta alueita, jotka voidaan määritellä yhdellä tai useammalla muuttujalla tai näiden komplementeilla.

Tutkitaan kartan käyttöä neljällä muuttujalla. Otetaan esimerkkifunktio F, joka riippuu neljästä muuttujasta A,B,C ja D ja jolle on määritelty seuraavanlainen totuustaulu:

rivi-
nro
Input
A
Input
B
Input
C
Input
D
Output
F
0.00001
1.00011
2.00100
3.00111
4.01001
5.01011
6.01100
7.01111
8.10000
9.10011
10.10101
11.10111
12.11000
13.11011
14.11100
15.11111

Ensimmäiseksi sijoitetaan funktion arvot Karnaugh'n karttaan. Muistin virkistämiseksi vasemalla alla esitetään mikä totuustaulun rivi tulee mihinkin ruutuun. (Sääntö: muuten vasemmalta oikealle, ylhäältä alas; paitsi kaksi oikeanpuoleista saraketta sekä kaksi alinta riviä vaihtavat keskenään.

! HUOM ! Edellä mainittu sääntö rivien sijoittamisesta ruutuihin pätee ainoastaan, mikäli muuttujat (nyt A,B,C ja D) määrittävät juuri ne alueet kuin esimerkeissä on näytetty. Toisinsanoen, mikäli menet vaihtamaan Karnaugh'n kartassa esim. B:n ja C:n alueiden paikkoja, ei edellämainittu sijoittelusääntö enää päde.)

Oikeanpuolimmaisessa kuvassa funktion arvot on sijoitettu paikoilleen.

kahvia kahvia

Tarkastellaan karttaa ja etsitään lauseketta funktiolle. Perussääntö on, että mitä suurempi yhtenäinen alue voidaan saavuttaa, sen parempi, sillä sitä enemmän lauseke yksinkertaistuu. Nähdään, että funktio saa arvon 1 kahdella pystyrivillä. Näillä muuttuja D saa myös arvon 1. Voidaan valita rivit suoraan, jolloin saadaan funktion ensimmäinen termi: F = D + ..

kahvia

Jatketaan vaikka vasemman yläkulman ykkösillä. Kaksi ykköstä voisi valita yksinään, mutta se ei ole kannattavaa: mitä suurempi alue saadaan valittua, sitä vähemmän muuttujia tarvitaan termiin. (Mitä vähemmän muuttujia sitä yksinkertaisempi toteutus.) Toisaalta samoja ruutuja voi valita uudelleen. (Ei siis haittaa, jos funktio saa arvon yksi useammalla kuin yhdellä perusteella.) Näillä perustein voidaan ryhmitellä neljä vasemman yläreunan ruutua alueeksi ja antaa näille peruste A'C'.

kahvia

Jäljelle jää enää siis yksi kiusallinen ykkösruutu oikeaan alanurkkaan. Jos tähän viitataan yksinään, vaatii se kaikkien neljän muuttujan käytön: AB'CD'. (Voi helposti todeta, että termi on juuri tuo esim. rengastamalla alueet A, B', C, D' ja katsomalla, että ruutu jäi ulkopuolelle.) Kannattaa yhdistää ruutu viereisen kanssa, jolloin saadaan kolmen muuttujan termi: AB'C.

kahvia

Näin ollen funktion lausekkeeksi saadaan F = D + A'C' + AB'C.

Lisätietoja:


Tämän sivun sisällöstä vastaa aura@wooster.hut.fi
URL: http://signal.hut.fi/digis/luento4/kaytto.html
Sivua on viimeksi päivitetty 12.08.2003.