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. | 0 | 0 | 0 | 0 | 1 |
1. | 0 | 0 | 0 | 1 | 1 |
2. | 0 | 0 | 1 | 0 | 0 |
3. | 0 | 0 | 1 | 1 | 1 |
4. | 0 | 1 | 0 | 0 | 1 |
5. | 0 | 1 | 0 | 1 | 1 |
6. | 0 | 1 | 1 | 0 | 0 |
7. | 0 | 1 | 1 | 1 | 1 |
8. | 1 | 0 | 0 | 0 | 0 |
9. | 1 | 0 | 0 | 1 | 1 |
10. | 1 | 0 | 1 | 0 | 1 |
11. | 1 | 0 | 1 | 1 | 1 |
12. | 1 | 1 | 0 | 0 | 0 |
13. | 1 | 1 | 0 | 1 | 1 |
14. | 1 | 1 | 1 | 0 | 0 |
15. | 1 | 1 | 1 | 1 | 1 |
|
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.
|
|
|
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 + ..
|
|
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'.
|
|
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.
|
|
Näin ollen funktion lausekkeeksi saadaan F = D + A'C' + AB'C.
|