Tässä luvussa
esitetään perusteet lausekemuodossa esitettyjen kytkentäfunktioiden sieventämiselle
esitetään Karnaugh´n karttamenetelmä, jolla lausekkeita sievennetään mahdollisimman pienellä porttipiirimäärällä toteutettaviksi
käydään läpi kaksi esimerkkiä Karnaugh'n kartan käytöstä funktion mahdollisimman yksinkertaisen SOP-muotoisen lausekkeen etsimiseen
etsitään samojen funktioiden mahdollisimman yksinkertaiset POS-muotoiset lausekkeet Karnaugh'n karttamenetelmällä
esitetään epätäydellisesti määritellyt kytkentäfunktiot ja niiden sieventäminen Karnaugh'n karttamenetelmällä
Luku on melko teoreettinen, mutta oppimiseen käytetään käytännön esimerkkejä
Luvussa esitettäviä käsitteitä ja menettelyjä sovelletaan jatkossa, kun suunnitellaan käytännön digitaalipiirejä
Lausekkeiden sieventäminen
Pyritään piirin koon, hinnan ja tehonkulutuksen minimointiin
mahdollisimman pieni määrä portteja
mahdollisimman yksinkertaisia portteja
vähän tuloja
yksinkertainen sisäinen rakenne
Mitä yksinkertaisempi lauseke, sitä pienempi piiri
Kytkentäfunktion lauseke sievennetään (simplify, optimize) mahdollisimman yksinkertaiseen SOP- tai POS-muotoon
Kytkentäalgebran teoreemat (jos kaksi muuttujaa)
esimerkki: F = A (A + B) = A A + A B = 0 + A B = A B
Karnaugh´n karttamenetelmä (jos 3 - 6 muuttujaa)
Tietokoneella erikseen tehtävä sievennys
Quinen-McCluskeyn menetelmä
Espresso-menetelmä
Suunnittelutyökaluihin sisältyvät sievennys- ja sovitusalgoritmit
Lausekkeen sieventäminen SOP-muotoon
F(A, B, C) = B + A C A B C F
0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 Esimerkki: Usea tulotermi saa peittää saman ykkösen Jokainen SOP-lausekkeen tulotermi antaa funktiolle arvon 1 yhdellä tai usealla (2n) muuttujien arvoyhdistelmällä
sanotaan, että tulotermi peittää (cover) tietyn määrän funktion ykkösiä
mitä vähemmän muuttujia tulotermissä on, sitä useampia ykkösiä se peittää
Lausekkeen tulotermien tulee peittää funktion kaikki ykköset ja vain ne
Mahdollisimman yksinkertaisessa SOP-lausekkeessa on mahdollisimman vähän tulotermejä ja ne ovat mahdollisimman yksinkertaisia
Sievennyksen tehtävänä on löytää tällainen lauseke eli funktion SOP-minimipeitto
Lausekkeen sieventäminen POS-muotoon
Usea summa-
termi saa peittää saman nollan F(A, B, C) = (A + B) (B + C) A B C F
0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 Esimerkki: Jokainen POS-lausekkeen summatermi antaa funktiolle arvon 0 yhdellä tai usealla (2n) muuttujien arvoyhdistelmällä
sanotaan, että summatermi peittää tietyn määrän funktion nollia
mitä vähemmän muuttujia summatermissä on, sitä useampia nollia se peittää
Lausekkeen summatermien tulee peittää funktion kaikki nollat ja vain ne
Mahdollisimman yksinkertai- sessa POS-lausekkeessa on mahdollisimman vähän summatermejä ja ne ovat mahdollisimman yksinkertaisia
Sievennyksen tehtävänä on löytää tällainen lauseke eli funktion POS-minimipeitto
Karnaugh'n karttamenetelmä
K-MAP Esimerkki: G = A B C + A B C + A B = (A + A) B C + A B = B C + A B Karnaugh´n kartta on myös hyödyllinen kytkentäfunktioiden sievennyksen ja digitaalitekniikan käsitteiden ymmärtämisen apuväline Funktion POS-minimipeitto löydetään vastaavasti soveltamalla visuaalisesti teoreemaa
(K + F(A, B, C…)) · (K + F(A, B, C…)) = (K · K) + F(A, B, C…) = F(A, B, C…) Manuaalinen sievennysmenetelmä
Soveltuu 3 - 6:lle muuttujalle
Helppo 3 - 4:lle muuttujalle
Perustuu kytkentäfunktion totuustaulun piirtämiseen muotoon, jossa voidaan visuaalisesti soveltaa kytkentäalgebran teoreemaa K · F(A, B, C…) + K · F(A, B, C…) = (K + K) · F(A, B, C…) = F(A, B, C…) jopa useita kertoja yhtä aikaa ja löytää näin funktion SOP-minimipeitto
Karnaugh'n kartta
K-MAP Karnaugh'n kartan (Karnaugh map) kukin ruutu vastaa yhtä totuustaulun riviä
Ruutujen lukumäärä vastaa rivien lukumäärää
Muuttujia Ruutuja
3 8 4 16 5 2 x 16 6 4 x 16
Kuhunkin ruutuun merkitään sitä vastaavalla totuustaulun rivillä oleva funktion arvo
Kartassa yhden muuttujan suhteen erilaisia rivejä vastaavat ruudut ovat vierekkäin
Vierekkäisyys tulkitaan siten, että reunimmaiset ruudut ovat myös keskenään vierekkäisiä
Kolmen muuttujan Karnaugh´n kartta
1 0 1 1 1 0 0 1 Funktion arvot
totuustaulusta
(sivu 4) 3 Vierekkäiset rivit C B A C:n
ykkös-
alue A:n ykkösalue B:n ykkösalue A C B 1 0 0 1 0 1 1 Piirretään yleensä yksinkertaistettuna: 1 F C A B 1 0 0 1 0 1 1 1 F U-sääntö C
0
1 AB
00 01 11 10 F Nimet (F,A,B,C) 0 2 6 4 1 3 7 5 Totuustaulun rivin numero Kolmen muuttujan kartta esitettynä kaikkine merkintöineen
Neljän muuttujan Karnaugh´n kartta
Vierekkäiset rivit Vierekkäiset rivit 4 C D A B 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 F Silmukkasääntö D A B C F 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 Kuvassa yksinkertainen esitystapa
Huomaa vierekkäisyydet
Viiden muuttujan Karnaugh´n kartta
A = 0 A = 1 Vierekkäiset
ruudut 5 D E B C D E B C F F Lisä Kaksi erillistä karttaa, jotka ajatellaan asetetuiksi päällekkäin
Vierekkäisyys kuten neljän muuttujan kartassa, lisäksi päällekkäiset ruudut ovat vierekkäisiä
Karnaugh’n kartan käyttö, tulojen summa (SOP)
SOP Laaditaan toteutettavan funktion totuustaulu
Piirretään muuttujien määrän mukainen Karnaugh’n kartta
Siirretään totuustaulusta nollat ja ykköset karttaan
Muodostetaan vierekkäisistä ykkösistä kaikki mahdollisimman suuret 1:n, 2:n, 4:n tai 8:n ykkösen ryhmät; tietty ykkönen saa kuulua useaan ryhmään
Valitaan muodostettuja ryhmiä, kunnes kaikki ykköset ovat ainakin yhdessä ryhmässä: joskus on valittava kaikki ryhmät, joskus vain osa ryhmistä
Kutakin ryhmää vastaa tulotermi, jossa ovat mukana ne muuttujat
sellaisinaan, joiden ykkösalueella kaikki ryhmän ykköset ovat
invertoituina, joiden 1-alueen ulkopuolella kaikki ryhmän ykköset ovat
Muodostetaan valittuja ryhmiä vastaavien tulotermien looginen summa
se on yksinkertaisin totuustaulua vastaava tulojen summa (SOP) -muotoinen lauseke eli SOP-minimipeitto
Esimerkkejä ryhmistä ja vastaavista tulotermeistä
?
1 0 1 1 C D A B 0 0 1 1 0 1 1 1 1 1 1 1 1 B C 1 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 C D A B D B 0 0 1 C D A B 1 1 1 1 1 0 0 1 0 0 0 1 0 A C A B C D 1 0 1 1 1 0 0 1 0 0 0 0 1 0 1 1 C B A D B D A D B C 0 0 1 C D A B 1 1 0 0 0 1 0 1 0 0 0 0 0 A C D A B D A B C D 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 C A D B A B C D B C D A B D
Perustermit ja olennaiset perustermit
?
2 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 C A B F D B C D Ei perus-
termi! F = B + C D + C D + A C tai F = B + C D + C D + A D Olennaiset
perustermit B C D C D Muut
perustermit A D A C Tulotermiä, joka vastaa mahdollisimman suuren määrän ykkösiä sisältävää ryhmää, nimitetään perustermiksi (prime implicant)
Perustermiä, jota vastaava ryhmä ainoana peittää ainakin yhden ykkösen, nimitetään olennaiseksi perustermiksi (essential prime implicant)
Mikäli yksinkertaisin lauseke voidaan muodostaa pelkästään olennaisista perustermeistä, se on yksikäsitteinen
Mikäli tarvitaan lisäksi muita perustermejä, on useita yhtä yksinkertaisia lausekkeita
Esimerkki 1: SOP-muotoinen lauseke, 3 muuttujaa
?
3 SOP Molemmat tulotermit
olennaisia perustermejä Huom!
Järjestyksen vaihto A B C F
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0 C A B F 1 1 1 0 0 0 1 1 F = B + A C 1 0 1 A B 1 1 0 0 1 F C
Esimerkki 2: SOP-muotoinen lauseke, 4 muuttujaa
Vain B D ja
B D olennaisia
perustermejä SOP A B C D F
0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 0 1 1 1
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 1
1 0 0 0 1
1 0 0 1 0
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 0
1 1 1 1 1 1
0
1
1 1
1
1
0 1
0
1
1 0
1
1
0 1 0 1 1 0 1 1 0 D 1 1 0 C A B 1 0 1 1 0 1 1 1 1 1 0 0 1 F Vaihto-
ehtoinen
perustermi A C D B C F = B D + B D + C D + A B C D C A B F Huom!
Järjestyksen vaihto 1 0 1 1 1 1 1 0
Karnaugh’n kartan käyttö, summien tulo (POS)
POS A A:n nolla-alue Laaditaan toteutettavan funktion totuustaulu
Piirretään muuttujien määrän mukainen Karnaugh’n kartta
Siirretään totuustaulusta nollat ja ykköset karttaan
Muodostetaan vierekkäisistä nollista kaikki mahdollisimman suuret 1:n, 2:n, 4:n tai 8:n nollan ryhmät; tietty nolla saa kuulua useaan ryhmään
Valitaan muodostettuja ryhmiä, kunnes kaikki nollat ovat ainakin yhdessä ryhmässä: joskus on valittava kaikki ryhmät, joskus vain osa ryhmistä
Kutakin ryhmää vastaa summatermi, jossa ovat mukana ne muuttujat
sellaisinaan, joiden nolla-alueella kaikki ryhmän nollat ovat
invertoituina, joiden nolla-alueen ulkopuolella kaikki ryhmän nollat ovat
nolla-alue on muuttujan ykkösalueen ulkopuolinen alue
Muodostetaan valittuja ryhmiä vastaavien summatermien looginen tulo; se on yksinkertaisin totuustaulua vastaava summien tulo (POS) -muotoinen lauseke eli POS-minimipeitto
Esimerkki 1: POS-muotoinen lauseke, 3 muuttujaa
Molemmat summatermit
olennaisia perustermejä B 1 0 1 C A 1 1 0 0 1 F POS (B + C) Huom!
Järjestyksen vaihto A B C F
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0 C A B F 1 1 1 0 0 0 1 1 F = (A + B)
Esimerkki 2: POS-muotoinen lauseke, 4 muuttujaa
?
4 Kaikki
summatermit
olennaisia
perustermejä C B 1 1 0 D A 1 0 1 1 0 1 1 1 1 1 0 0 1 F POS F = (A + B + D) (B + C + D) (B + C + D) Esittele
Karnaugh'n
karttaohjelma A B C D F
0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 0 1 1 1
0 1 0 0 1
0 1 0 1 1
0 1 1 0 0
0 1 1 1 1
1 0 0 0 1
1 0 0 1 0
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 0
1 1 1 1 1 1
0
1
1 1
1
1
0 1
0
1
1 0
1
1
0 1 0 1 1 0 1 1 0 D C A B F Huom!
Järjestyksen vaihto 1 0 1 1 1 1 1 0
Epätäydellisesti määritellyt kytkentäfunktiot
Don't Care! A B C F
0 0 0 1
0 0 1 X
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 X
1 1 0 1
1 1 1 0 Hälläväliä-termit Esimerkki:
F(A, B, C) = m (0, 2, 3, 6); d (A, B, C) = m (1, 5)
F(A, B, C) = M (4, 7); d (A, B, C) = M (1, 5)
Toisinaan kytkentäfunktion arvolla tietyllä tai tietyillä muuttujien arvoyhdistelmillä ei ole merkitystä
yhdistelmä ei koskaan voi esiintyä: esimerkiksi kolmiasentoinen kytkin
arvolla ei muutoin ole merkitystä: esimerkiksi lyhytaikainen virhekoodi
Vastaavaa funktion arvoa nimitetään hälläväliä-arvoksi (don't care)
Tällöin arvo voidaan jättää määrittelemättä: sanotaan, että kytkentäfunktio on epätäydellisesti määritelty (incompletely specified)
Totuustauluun kyseiseen kohtaan merkitään X
Jos kytkentäfunktio määritellään minimi- tai maksimi- termien avulla, määritellään erikseen hälläväliä-termit
Hälläväliä-arvot sieventämisessä
Don´t care! Hälläväliä-arvot merkitään Karnaugh’n karttaan X:llä
Arvot tulkitaan kukin erikseen 0:ksi tai 1:ksi sen mukaan, kumpi johtaa yksinkertaisempaan lausekkeeseen
Lausekkeena määritelty kytkentäfunktio on aina täysin määritelty: funktiolla on aina joko arvo 1 tai 0
Comments