1. Az adott kifejezést egyszerűsítse és rajzolja le a lehető legkevesebb elemmel, a legegyszerűbben. F = A ⋅ B + B ⋅ C ⋅ D + A ⋅ C ⋅ D (A függvény 4 változós.) MEGOLDÁS: A legegyszerűbb alak megtalálása valamilyen egyszerűsítéssel lehetséges (algebrai, Karnaugh, Quine stb.). Célszerű négy változó esetén a grafikus egyszerűsítést alkalmazni (Karnaugh). Ehhez ismerni kell a függvény teljes normál diszjunktív akját (TDNA). Két módon juthatunk hozzá: •
minden kapu kimenetén felírjuk a függvény értékét, így legvégül megkapjuk F teljes alakját, az így kapott implikánsokkal leírt függvényt kibővítjük TDNA-ra.
F = A ⋅ B + B ⋅ C ⋅ D + A ⋅ C ⋅ D = A ⋅ B ⋅ (C + C ) + B ⋅ C ⋅ D + A ⋅ C ⋅ D = A⋅ B ⋅C + A⋅ B ⋅C + B ⋅C ⋅ D + A⋅C ⋅ D = A ⋅ B ⋅ C ⋅ ( D + D) + A ⋅ B ⋅ C ⋅ ( D + D) + ( A + A) ⋅ B ⋅ C ⋅ D + A ⋅ ( B + B) ⋅ C ⋅ D = A⋅ B ⋅C ⋅ D + A⋅ B ⋅C ⋅ D + A⋅ B ⋅C ⋅ D + A⋅ B⋅C ⋅ D + A⋅ B ⋅C ⋅ D + A⋅ B ⋅C ⋅ D + A ⋅ B ⋅ C ⋅ D + A ⋅ B ⋅ C ⋅ D = m7 + m6 + m5 + m 4 + m10 + m 2 + m13 + m9.
A Karnaugh tábla (1. ábra): 1. ábra: Karnaugh tábla
Az egyszerűsített függvény: F = A ⋅ B + A ⋅ C ⋅ D + B ⋅ C ⋅ D , vagyis valójában nem lehetett tovább egyszerűsíteni. A kapcsolás rajza (2. ábra):
2. ábra: A kapcsolási rajz
1
•
másik lehetőség, kitöltjük a négyváltozós igazságtáblát, majd minden kombinációra megadjuk a függvény kimenetét. Ahol logikai 1-est kapunk, ott már megkaptuk a mintermet is. Ez a módszer eléggé hosszadalmas, de sokszor valamelyik változó több kombinációnál is azonnal megadja a helyes értéket.
2. Egy négytagú zsűri egyszerre szavaz, a kijelző akkor gyullad ki, ha legalább 4 pontos volt a szavazás. Az elnök (E) 3, a helyttes (H) 2 és a tagog (T1 és T2) szavazatai 1 – 1 pontot érnek. Rajzolja le a kapcsolást kizárólag 2 bemenetű NAND kapukkal. MEGOLDÁS: Kitöltjük az igazságtáblázatot. A „PONT” oszlopba kerülnek be az egyes szavazások pontértékei, ha bármelyik legalább 4 pontot ér, a függvény kimenete F = 1 lesz (F oszlop). 1. táblázat: a 2. példa igazságtáblázata pont 3 2 1 1 sorszám E H T1 T2 PONT 0. 0 0 0 0 0 1. 0 0 0 1 1 2. 0 0 1 0 1 3. 0 0 1 1 2 4. 0 1 0 0 2 5. 0 1 0 1 3 6. 0 1 1 0 3 7. 0 1 1 1 4 8. 1 0 0 0 3 9. 1 0 0 1 4 10. 1 0 1 0 4 11. 1 0 1 1 5 12. 1 1 0 0 5 13. 1 1 0 1 6 14. 1 1 1 0 6 15. 1 1 1 1 7
F 0 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1
A Karnauhh tábla (3. ábra): 3. ábra: A példa egyszerűsítése Karnaugh táblával
2
Az egyszerűsített függvény: F = E ⋅ H + E ⋅ T2 + E ⋅ T1 + H ⋅ T1 ⋅ T2 . Felhasználva a De Morgan azonosságot és figyelembe véve azt a feltételt, hogy minden NAND kapu csak két bemenetű, a következő átalakításokat kell végrehajtani:
F = E ⋅ H + E ⋅ T2 + E ⋅ T1 + H ⋅ T1 ⋅ T2 = E ⋅ H ⋅ E ⋅ T2 ⋅ E ⋅ T1 ⋅ H ⋅ T1 ⋅ T2 Ha X = E ⋅ H ⋅ E ⋅ T2 és Y = E ⋅ T1 ⋅ H ⋅ T1 ⋅ T2 , valamint Z = T1 ⋅ T2 , akkor írhatjuk, hogy:
F = X ⋅ Y , Z = T1 ⋅ T2 , X = E ⋅ H ⋅ E ⋅ T2 és Y = E ⋅ T1 ⋅ H ⋅ Z . A teljes kapcsolás, kizárólag 2 bemenetű NAND kapukkal (4. ábra):
4. ábra: A példa megoldása 2 bemenetű NAND kapukkal
a) b) c) d)
1. Az F(ABCDE)= Σ(0,1,2,3,4,5,6,7)+Σx(8,9,10,18,19,20,22,23,24,30,31) ötváltozós függvényt: egyszerűsítse a Quine-Mc Cluskey-féle numerikus módszer segítségével, rajzolja le a kapcsolást tetszőleges logikai kapukkal, rajzolja le a kapcsolást tetszőleges logikai kapukkal, mindegyik kapu 3 bemenetű, rajzolja le a kapcsolást 2 bemenetű NOR logikai kapukkal.
MEGOLDÁS A Quine egyszerűsítésnél az x-szel jelölt határozatlan kombinációkat is be kell vonni, töltsük ki a mintermeknek megfelelő bináris táblázatot (3. táblázat): 3. táblázat: a mintermek bináris alakban A B C D E 0. 0 0 0 0 0 √ 1. 0 0 0 0 1 √ 2. 0 0 0 1 0 √ 3. 0 0 0 1 1 √
3
4. 5. 6. 7. 8. 9. 10. 18. 19. 20. 22. 23. 24. 30. 31.
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 1 1 1 0 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 0 1 1 1 0 1 1
0 0 1 1 0 0 1 1 1 0 1 1 0 1 1
0 1 0 1 0 1 0 0 1 0 0 1 0 0 1
√ √ √ √ √ √ √ √ √ √ √ √ √ √ √
Mivel egyszerűsíteni mindig csak a szomszédos mintermek között lehet, ezért rendezzük át a táblázatot úgy, hogy egy-egy csoportban ugyanannyi számú egyes legyen, a már átvitt mintermet pedig jelöljük meg √ jellel (4. táblázat). 4. táblázat: a mintermek bináris alakban, átrendezve az egyesek száma szerint A B C D E 0. 0 0 0 0 0 √ 1. 2. 4. 8.
0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
√ √ √ √
3. 6. 9. 10. 18. 20. 24.
0 0 0 0 1 1 1
0 0 1 1 0 0 1
1 1 0 0 0 1 0
0 1 0 1 1 0 0
1 0 1 0 0 0 0
√ √ √ √ √ √ √
7. 19. 22.
0 1 1
0 0 0
1 0 1
1 1 1
1 1 0
√ √ √
23. 30.
1 1
0 1
1 1
1 1
1 0
√ √
31.
1
1
1
1
1
√
4
Egyszerűsíteni csak a szomszédos csoportok között kell, azokkal a mintermekkel, melyek között egy változó a különbség (a változó az egyik mintermben ponált, a másikban negált) ( 5. táblázat). 5. táblázat: az egyszerűsítés első lépése A B C D E 0,1 0 0 0 0 √ 0,2 0 0 0 0 √ 0,4 0 0 0 0 √ 0,8 0 0 0 0 √ 1,3 1,5 1,9 2,3 2,6 2,10 2,18 4,5 4,6 4,20 8,9 8,10 8,24
0 0 0 0 0 0 0 0 0 0 -
0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 1 0 0 0
0 0 1 1 1 1 0 0 0 0
1 1 1 0 0 0 0 0 0 0
√ √ √ √ √ ← √ √ √ √ √ √ ←
3,7 3,19 5,7 6,7 6,22 18,19 18,22 20,22
0 0 0 1 1 1
0 0 0 0 0 0 0 0
0 1 1 1 0 1
1 1 1 1 1 1 -
1 1 1 0 0 0
√ √ √ √ √ √ √ √
7,23 19,23 22,23 22,30
1 1 1
0 0 0 -
1 1 1
1 1 1 1
1 1 0
√ √ √ √
23,31 1 30,30 1
1
1 1
1 1
1 -
√ √
Az 5. táblázatban keletkezett implikánsokat tovább lehet egyszerűsíteni (6. táblázat). 6. táblázat: az egyszerűsítés második lépése A B C D E 0,1,2,3 0 0 0 √ 0,1,4,5 0 0 0 √ 0,1,8,9 0 0 0 ← 5
0,2,4,6 0,2,8,10
0 0
0 -
0
-
0 0
√ ←
1,3,5,7 2,3,18,19 2,3,6,7 2,6,18,22 4,5,6,7 4,6,20.22
0 0 0 -
0 0 0 0 0 0
0 1 1
1 1 1 -
1 0 0
√ √ √ √ √ ←
3,7,19,23 6,7,22,23 18,19,22,23 22,23,30,31
1 1
0 0 0 -
1 1
1 1 1 1
1 -
√ √ √ ←
A 6. táblázatban keletkezett implikánsokat tovább lehet egyszerűsíteni (7. táblázat). 7. táblázat: az egyszerűsítés harmadik lépése A B C 0,1,2,3,4,5,6,7 0 0 2,3,6,7,18,19,22,23 0 -
D 1
E -
← ←
A 3. – 7. táblázatban a ← jel azt jelenti, hogy az adott implikáns nem vonható már össze semelyik más implikánssal sem (nem lehet tovább egyszerűsíteni), a √ jel azokat az implikánsokat jelenti, melyek tovább egyszerűsíthetők. A nem egyszerűsíthető implikánsok bekerülnek a 8. táblázatba (Quine – McKaluskey táblázat), ahol az eredeti mintermekkel hozzuk azokat kapcsolatba.
8. táblázat: Quine – McKaluskey táblázat 0 A⋅C ⋅ D⋅ E B⋅C ⋅ D⋅ E A⋅C ⋅ D B⋅C ⋅ E A⋅C ⋅ D A⋅ B B⋅D
1
2 3 □
4
5
6
7
x 8
x 9
□ □ □
□ □ □
x x x x x x x x x 10 18 19 20 22 23 24 30 31 □ □
□
■ ■ ■ ■ ■ ■ ■ ■ □ □ □ □
□
□
□
□ □
□
□
□
□
□
A 8. táblázatba került imlikánsokhoz azokat a mintermeket kapcsoljuk, amelyekből erednek, ide egy □ jelet teszünk. Ezután megkeressük azokat az oszlopokat, melyekben csak egy □ jel van, ezt és a vele egy sorban levő összes □ jelet átalakítjuk ■ jellé. A határozatlan 6
kombinációhoz tartozó □ jelet nem tekintjük ilyenkor egyesnek ( a példában a 24. minterm). Ha egy oszlopban (mintermnél) több □ jel van, azt választjuk ki, amelyik vízszintesen a lehető legtöbb mintermet fedi le. A kimaradt implikánsokat a továbbiakban nem vesszük figyelembe (a példában B ⋅ C ⋅ D ⋅ E ). A kapott megoldás:
F = A⋅ B 4. a) írja fel az RS tároló átmeneti tábláját, majd annak alpján tervezze meg a tárolót és rajzolja le tetszőleges elemekkel, b) (2 pont) rajzolja le a tárololó szinkron változatát. MEGOLDÁS: Az R/S flip flop működését leíró igazság táblázat az 5. ábrán látható. A táblázat utolsó két sorában tiltott kombinációt találunk (ezt X –szel jelöljük). Mostani Következő állapot állapot Qt Qt+1
Leírás
R
S
0
0
0
0
HOLD
0
0
1
1
HOLD
0
1
0
1
SET
0
1
1
1
SET
1
0
0
0
RESET
1
0
1
0
RESET
1
1
0
X
tiltott állapot
1
1
1
X
tiltott állapot
5. ábra: az R/S flip flop igazság táblázata Ha az igazság táblázatból kiindulva elvégezzük a minimalizálást (6. ábra), akkor megkapjuk a tároló analitikus alakját: Qt +1 = S + R ⋅ Qt
6. ábra: az R/S flip flop egyszerűsítése Karnaugh módszerével
7
A Qt +1 és Qt jelölés valójában ugyanazt a kimenetet jelöli, de a t + 1 index a következő állapotra (az órajel utáni) utal, míg a t index az előző állapotot adja (az órajel elötti állapot). Az R/S flip flop-nak két bemenete (R és S) van, valójában azonban a memória müködésére még a kimenet mostani állapota is kihat, így gyakorlatilag a kapu 3 bemenettel rendelkezik (R, S és Qt ), ami azt jelenti, hogy a kombinációk száma n = 2 3 = 8 (7. ábra).
7. ábra: az aszinkron R/S flip flop kapcsolási rajza tetszőleges elemekkel Az aszinkron R/S tároló (11.11. ábra) a CLK szinkronizáló jel, valamint két ÉS kapu hozzáadásával könnyen átalakítható szinkron R/S tárolóvá (8. ábra). A flip flop állapota csak a szinkronizáló jel megjelenésekor változik meg (CLK = 1).
8. ábra: szinkron R/S flip flop
8