2016.10.15.
DIGITÁLIS TECHNIKA I Dr. Lovassy Rita Dr. Pődör Bálint Óbudai Egyetem KVK Mikroelektronikai és Technológia Intézet 6. ELŐADÁS
1
HÁZI FELADAT Arató Péter: Logikai rendszerek tervezése, Tankönyvkiadó, Budapest, Műegyetemi Kiadó, 55013 műegyetemi jegyzet
Beadási határidő: 2016. október 24.
Zsom Gyula: Digitális technika I és II, Műszaki Könyvkiadó, Budapest, (KVK 49-273/I és II)
1. Az alábbi logikai függvények közül válasszon ki egyet és Karnaugh táblázat segítségével határozza meg a legegyszerűbb kétszintű, hazárdmentes diszjunktív realizációt és valósítsa meg ÉS-VAGY kapus hálózattal hálózattal;, kétszintű ÉS-VAGY kapus, valamint a legegyszerűbb, kétszintű VAGY-ÉS kapus logikai vázlatát.
Rőmer Mária: Digitális rendszerek áramkörei, Műszaki Könyvkiadó, Budapest, (KVK 49-223) Rőmer Mária: Digitális technika példatár, KKMF 1105, Budapest Az előadás ezen könyvek megfelelő fejezetein alapszik.
4
HÁZI FELADAT
HÁZI FELADAT 2. Adja meg annak a 4 bemenetű (ABCD), 1 kimenetű (G) kombinációs hálózatnak a Karnaugh táblázatát, melyet az alábbi kétszintű hálózat valósít meg. Jelölje meg a hálózat által megvalósított prímimplikánsokat!
Példa az indexelt felírású logikai függvények felírására
5
6
1
2016.10.15.
HÁZI FELADAT
HÁZI FELADAT
4. Tervezze meg az alább leírt funkciókat megvalósító hálózatot.
3. Adja meg annak a 4 bemenetű (ABCD), 1 kimenetű (F) kombinációs hálózatnak a Karnaugh táblázatát, amelynek kimenete 1, ha: - A és B bemenete különböző értékű, amikor a C és D bemenet azonos értékű, vagy - B bemenete megegyezik a D bemenetével, amikor az A bemenete különbözik a C bemenettől. A táblázat felírásakor vegye figyelembe, hogy a bemeneten azon kombinációk nem fordulhatnak elő, ahol az összes bemenet azonos értékű! Az A változó a legmagasabb helyi értékű!
Egy vállalat igazgatótanácsának négy tagja van, a vezérigazgató és három helyettese. A tanács szótöbbséggel hozza meg döntéseit, szavazategyenlőség esetén azonban a vezérigazgató szava dönt. Realizálja a “szavazógépet” - a legegyszerűbb kétszintű NAND kapus, valamint - a legegyszerűbb kétszintű NOR kapus változatban is.
7
8
TERVEZÉSI GYAKORLAT (3)
TERVEZÉS (3): MEGOLDÁS
Egy kombinációs hálózat bemenetei A, B, C, D, kimenetei X, Y, Z. A bemenetet mint 2 db 2 bites számot értelmezve (AB, A a magasabb helyérték), illetve (CD, C a magasabb helyérték), a kimenet legyen a két bemenet összege, (XYZ, X a legmagasabb helyérték), XYZ = AB + CD. Pl. 101 = 11 + 10 (bináris összeadás). Adja meg a hálózat igazságtábláját. Adja meg a hálózat kimenetenként legegyszerűbb logikai függvényeit algebrai alakban.
A B C D
X Y Z
Például ha A B C D = 1 1 0 1 akkor X Y Z = 1 0 0 mivel
9
TERVEZÉS (3): MEGOLDÁS
AB +CD =XYZ
11 01 100
10
TERVEZÉS (3): IGAZSÁGTÁBLÁZAT
• A tervezés és megoldás első lépése a feladat megfogalmazása alapján a kimeneti függvényekre vonatkozó igazságtáblázat felírása. • Ebben az esetben három független kimeneti változó van, így mindhárom változóra el kell végezni a minimalizálást.
11
A
B
C
D
X
Y
Z
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
0
0
1
0
...
...
...
...
...
...
...
1
0
1
0
1
0
0
...
...
...
...
...
...
...
1
1
1
1
1
1
0
12
2
2016.10.15.
TERVEZÉS (3): LOGIKAI FÜGGVÉNYEK
X(A,B,C,D) MINIMALIZÁLÁSA
Az igazságtáblázatból a három logikai függvény könnyen kiolvasható
C A minimalizált függvény
4 X = Σ(7,10,11,13,14,15)
B
4 Y = Σ(2,3,5,6,8,9,12,15)
1
1
1
1
1
A
4 Z = Σ(1,3,4,6,9,11,12,14) D
13
14
TERVEZÉSI PÉLDA (4) NAPTÁR KIJELZŐ
TERVEZÉS (3): MINIMALIZÁLT, FÜGGVÉNYEK A Karnaugh táblából a három minimalizált függvény könnyen kiolvasható
Feladat: napok száma adott hónapban, karóra LCD kijelzője vezérléséhez
X =AC + B C D +AB D _ _ _ _ _ _ __ Y=AC D +AB C +AC D +AB C _ _ +ABCD+ABCD _ _ Z=BD+BD
Bemenetek: hónap, szökőév flag Kimenetek: napok száma, négy kimeneti vonal
16
FORMÁLIS MEGFOGALMAZÁS
NAPTÁR: 31 NAPOS HÓNAP
Kódolás: hónap: 4 bites bináris szám (m8,m4,m2,m1), szökőév: 1 bit, 4 vonal 28, 29, 30 és 31, egyszerre csak egy aktív
leap
28 29 30 31
integer number_of_days ( month, leap_year_flag) { switch (month) { case 1: return (31); case 2: if (leap_year_flag == 1) then return (29) else return (28); case 3: return (31); case 4: return (30); case 5: return (31); case 6: return (30); case 7: return (31); case 8: return (31); case 9: return (30); case 10: return (31); case 11: return (30); case 12: return (31); default: return (0); } }
15
(Esetleg XOR logika ?)
month
X =AC + B C D +AB D
1
month 0000 0001 0010 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 111–
leap – – 0 1 – – – – – – – – – – – –
28 – 0 1 0 0 0 0 0 0 0 0 0 0 0 – –
29 – 0 0 1 0 0 0 0 0 0 0 0 0 0 – –
30 – 0 0 0 0 1 0 1 0 0 1 0 1 0 – –
A színkóddal jelölt lefedés szerint
C
31 – 1 0 0 1 0 1 0 1 1 0 1 0 1 – –
17
-
1
1
0
—
—
F=AD+AD 0
1
1
0
1
-
-
-
1
0
0
1
A
D
B A közömbös kombinációk előnyösen kihasználhatók a függvény minimalizálásánál! 18
3
2016.10.15.
RELZÁLÁS: DISZKRÉT KAPUK
NAPTÁR: 30 NAPOS HÓNAP A lefedés szerint
C
•
Diszkrét kapuk
_ _ F=AD+ABD
1
month 0000 0001 0010 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 111–
– 28 = m8’ m4’ m2 m1’ leap’ – 29 = m8’ m4’ m2 m1’ leap
1
m8’ m4 m1’ + m8 m1
– 30 =
B -
-
1
1
– 31 = m8’ m1 + m8 m1’
-
A
D
c5 c4
c0 c6
A 0 0 0 0 0 0 0 0 1 1 1 1
• Megvalósítási technika megválasztása – Ha ROM, akkor kész – Don't care termek PAL/PLA előnyös lehet
c1 c2
• A kiválasztott technikától függően minimalizálás Karnaugh táblákon
BCD to 7–segment control signal decoder
1 1 -
A 1
1
D
A
1
0
X
1
0
1
X
1
C 1 1
1
X
X
1
X
X
D
1
X
1
1
0
X
1
C 1 1
1
X
X
0
X
X
-
C1 1 1 1 1 1 0 0 1 1 1 – –
C2 1 1 0 1 1 1 1 1 1 1 – –
C3 1 0 1 1 0 1 1 0 1 0 – –
C4 1 0 1 0 0 0 1 0 1 0 – –
C5 1 0 0 0 1 1 1 0 1 1 – –
C6 0 0 1 1 1 1 1 0 1 1 – –
1
X
1
0
1
X
1
C 0 0
0
X
X
X
X
B
23
A
1
1
X
1
1
1
X
1
C 1 0
1
X
X
1
X
X
B
D
A
1
0
X
1
0
1
X
0
C 1 1
0
X
X
1
X
X
1
0
X
1
0
0
X
0
C 0 1
0
X
X
1
X
X
D
B
D
B
A
1
1
D
B A
_ _ C0 = A + C + B D + B D
A
1
B
B -
C0 1 0 1 1 0 1 1 1 1 1 – –
• 15 term ha a kimeneteket külön-külön kezeljük A
-
D 0 1 0 1 0 1 0 1 0 1 – –
HÉT KIMENET FÜGGETLEN MINIMALIZÁLÁSA
C0
C
1
C 0 0 1 1 0 0 1 1 0 0 1 –
22
MINIMALIZÁLÁSI PÉLDA (C0)
1
B 0 0 0 0 1 1 1 1 0 0 0 1
(MSI változat: 7446, 7447, 7447, 7449) 21
A B C D
-
31 – 1 0 0 1 0 1 0 1 1 0 1 0 1 – –
A FELADAT ANALÍZISE
c0 c1 c2 c3 c4 c5 c6
1
30 – 0 0 0 0 1 0 1 0 0 1 0 1 0 – –
20
c3
0
29 – 0 0 1 0 0 0 0 0 0 0 0 0 0 – –
• Igazságtábla – don't care termek
• Bemenet : 4 bit BCD digit (A, B, C, D) • Kimenet : 7 szegmens vezérlőjele (C0-C6)
0
28 – 0 1 0 0 0 0 0 0 0 0 0 0 0 – –
19
TERVEZÉSI PÉLDA (5): BCD/7-SZEGMENSES KIJELZŐ DEKÓDOLÓ
1
leap – – 0 1 – – – – – – – – – – – –
D
0
1
X
1
0
1
X
1
C 1 1
0
X
X
X
X
1 B
D
C0 C1 C2 C3 C4 C5 C6
= = = = = = =
A + B D + C + B' D' C' D' + C D + B' B + C' + D B' D' + C D' + B C' D + B' C B' D' + C D' A + C' D' + B D' + B C' A + C D' + B C' + B' C
Don’t care termek: erős egyszerűsítések adódnak!
24
4
2016.10.15.
MINIMALIZÁLÁS KÖZÖS TERMEKKEL
PLA REALIZÁLÁS
• Jobb megoldás is van! A B C D
– 9 különböző szorzat tag (15 helyett) – Közös termek – Az egyes kimenetek nem szükségképen minimális
BC' B'C B'D
A
C2
A
1
1
X
1
1
1
X
1
C 1 0
1
X
X
1
X
X
C2 D
1
X
1
1
1
X
1
C 1 0
1
X
X
1
X
X
B
C0 C1 C2 C3 C4 C5 C6
= = = = = = =
BC'D
1
C'D' D
CD B'D'
B
A
C0 = B C' D + C D + B' D' + B C D' + A A + B D + C + B' D' C1 = B' D + C' D' + C D + B' D' C' D' + C D + B' C2 = B' D + B C' D + C' D' + C D + B C D' B + C' + D B' D' + C D' + B C' D + B' C C3 = B C' D + B' D + B' D' + B C D' C4 = B' D' + B C D' B' D' + C D' C5 = B C' D + C' D' + A + B C D' A + C' D' + B D' + B C' C6 = B' C + B C' + B C D' + A A + C D' + B C' + B' C
BCD'
C0 C1 C2 C3 C4 C5 C6 C7 25
A SZÁMJEGYES MINIMALIZÁLÁS ALAPJAI Quine-McCluskey módszer
26
MINTERMEK SZOMSZÉDOSSÁGA
Algoritimizálható, programozható.
A minimalizálás alapja a szomszédos mintermek megkeresése, egyszerűsítése, míg el nem jutunk a prímimplikánsokig.
Logikai függvényegyszerűsítéshez a Karnaugh-táblák használata korlátozott: – <5 változós függvények – Egyszerre egyetlen kimeneti függvény – Szubjektív megközelítés, különböző eredmények
Két minterm szomszédosságának szükséges és elégséges feltétele három állítással adható meg, melyeknek egyszerre kell, hogy teljesülniük. Lényeges, hogy e feltételek megfogalmazhatók kizárólag a mintermek alsó indexei értékeire alapozva.
Mintermek: alsó indexek egyértelműen megadják. Csupán ezek ismeretén alapuló minimalizálási eljárás: a végrehajthatóság nem függ a változók számától. 27
KÉT MINTERM SZOMSZÉDOSSÁGÁNAK FELTÉTELE (1) Két minterm szomszédos, ha decimális indexeik különbsége 2 egész számú hatványa. —
6 2 4
0110 0010
—
——
—
—
—
AB CD +AB CD →AC D
28
KÉT MINTERM SZOMSZÉDOSSÁGÁNAK FELTÉTELE (2) Két minterm szomszédos, ha bináris súlyaik (1-esek száma) különbsége 1. _ _ __ _ _ _ 6 0110 (2) AB CD +AB CD →AC D 2 0010 (1) 4 (1) Egyikük egyel és csakis egyel több 1-est tartalmaz bináris formájában. Ez is szükséges de nem elégséges feltétel, mivel pl. a 2 és 4 indexű mintermekre, bár a decimális különbség 2 hatványa, éppen ez a feltétel mely nem teljesül.
Ez szükséges de nem elégséges feltétel, mivel pl. a 2 és 4 indexű mintermekre is teljesül, de ezek nem szomszédosak.
29
30
5
2016.10.15.
KÉT MINTERM SZOMSZÉDOSSÁGÁNAK FELTÉTELE (3) A két minterm szomszédos, ha a nagyobb bináris súlyú mintermnek a decimális indexe is nagyobb a másikénál. _ _ __ _ _ _ 6 0110 (2) AB CD +AB CD →AC D 2 0010 (1) 4 (1)
QUINE-MCCLUSKEY ALGORITMUS Bizonyítható azonban, hogy ezen három feltétel egyidejű teljesülése már nemcsak szükséges hanem elégséges feltétele a két term szomszédosságának. Ezen alapul a Quine-McCluskey algoritmus.
6 > 2 és 2 > 1 Ez is szükséges de önmagában nem elégséges feltétel, mivel pl. a 7 és 9 indexű mintermekre, melyekre az első két feltétel áll, éppen ez nem teljesül, persze ezek nem szomszédosak. 31
32
QUINE-MCCLUSKEY MINIMALIZÁLÁS
QUINE-MCCLUSKEY ALGORITMUS
Minimalizálandó függvény: A számjegyes minimalizálás Quine-McCluskey féle algoritmusa ezen három feltétel alapján, kizárólag a mintermek indexeit vizsgálva válogatja párba a mintermeket, majd egyszerűsítés után a folyamatot addig ismétli míg el nem jut a prímimplikánsokig.
f (A,B,C,D) = Σm(0, 2, 3, 5, 7, 8,10,13,15) minterms = 0
Az algoritmus az összes prímimplikánst eredményezi így a második lépés az, hogy ki kell választani közülük a lényeges prímimplikánsokat. Az algoritmus gyakorlati alkalmazását egy példa mutatja be. 33
MINTERM TÁBLA Súly 0
1
⇒0
= 1 ⇒ 2, 8 = 2 ⇒ 3, 5,10 = 3 ⇒ 7,13 = 4 ⇒ 15 A mintermeket az indexeik bináris vagy Hamming súlya szerint csoportosítjuk http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
34
SZOMSZÉDOK MEGKERESÉSE…
Minterm
Súly
0
0 Két minterm szomszédos, ha decimális indexeik különbsége 2 egész számú hatványa.
2 8
1
Minterm 0 2 8
2
3 5 10
2
3 5 10
3
7 13
3
7 13
4
15
4
15
35
Párok 0,2 (2) 0,8 (8) Összevonás szomszédos csoportok között, ha az indexek különbsége 1, 2, 4, 8, stb. Felhasznált termek megjelölendők. Egy term több párban is szerepelhet.
36
6
2016.10.15.
AZ ÖSSZES SZOMSZÉDPÁR Súly
Minterm
NÉGYES CSOPORTOK
Pár Súly
0
0
2 8
1
0,2 (2) 0,8 (8)
3 5 10
3,7 (4) 5,7 (2) 5,13 (8)
3
7 13
7,15 (8) 13,15 (2)
4
15
2
Két minterm szomszédos, ha bináris súlyaik (1-esek száma) különbsége 1.
2,3 (1) 2,10 (8) 8,10 (2)
Ezután a párokat kell párosítani: 4-es csoportok
0,2 (2) 0,8 (8)
*
2 8
2,3 (1) 2,10 (8) 8,10 (2)
*
3 5 10
3,7 (4) 5,7 (2) 5,13 (8) 7,15 (8) 13,15 (2)
0
1
Pár
0
Kék csillag * : prímimplikáns
2
Ezek a tagok nem lettek összevonva
3
7 13
4
15
Négyes 0,2,8,10 (2,8)
5,7,13,15 (2,8)
37
PRÍMIMPLIKÁNS TÁBLA
Prímimplikánsok 0,2,8,10 (2,8) 5,7,13,15 (2,8)
Minterm
38
PRÍMIMPLIKÁNS TÁBLA Prímimplikánsok 0,2,8,10 (2,8) 5,7,13,15 (2,8)
Mintermek 0 2 3 5 7 8 10 13 15
2,3 (1) 3,7 (4)
2,3 (1) 3,7 (4)
Mintermek 0 2 3 5 7 8 10 13 15 X X X X X X X X X X X
X
Az m0 minterm csak egy sorban fordul elő, valamint, m8 és m10 is, ezért m(0,2,8,10) lényeges prímimplikáns. Ez lefedi majd az m2 mintermet is. 39
PRÍMIMPLIKÁNS TÁBLA Prímimplikánsok 0,2,8,10 (2,8) 5,7,13,15 (2,8) 2,3 (1) 3,7 (4)
MINTERMEK LEFEDÉSE
Mintermek 0 2 3 5 7 8 10 13 15 X X X X X X X X X X X
40
Primimplikánsok 0,2,8,10 (2,8) 5,7,13,15 (2,8) 2,3 (1) 3,7 (4)
X
√ √ √ √ √ √ √ √ 0 2 3 5 7 8 10 13 15 X X X X X X X X X X X
X
A két négyes prímimplikáns az m3 kivételével már lefedi az összes mintermet. 41
42
7
2016.10.15.
MEGOLDÁS A KARNAUGH TÁBLÁN
MINIMALIZÁLÁS EREDMÉNYE
f (A,B,C,D ) = 0,2,8,10(2,8) + 5,7,13,15(2,8) + 2,3(1)
0 2 8 10
=
X0X0
+
X1X1
+ 001X
=
BD
+
BD
+ AB C
5 7 13 15
0000 0010 1000 1010
0101 0111 1101 1111
2 3
1
1 1
1
1
1
X1X1
1
Redundás (nem lényeges) prímimplikáns) __ _ _ F(A,B,C,D) = B D + B D + A B C
B
0010 0011
A 1
X0X0
Lényeges prímimplikánsok
C
1
001X
D
43
QUINE-MCCLUSKEY ALGORITMUS PROGRAM
Kombinációs hálózatok
www.seattlerobotics.org/encoder/200106/qmccmin.htm
megvalósítása memóriaelemek
Példa: 64 változós függvény 64 mintermet tartalmazó alakjának minimalizálása
felhasználásával
45
46
MEMÓRIAELEM ELVI VÁZLATA
MEMÓRIAELEMEK TULAJDONSÁGAI Állandó tartalmú memóriák: Read Only Memory (ROM),
C1 C2 ...
D1 D2 ...
Cn E
Dm
tulajdonságaik alapján alkalmasak kombinációs hálózatok megvalósítására. A memóriaelemben tárolt adat egy bináris kombináció (D1, D2, ... Dm) , mely a cím megadásával, mely szintén bináris kombináció (C1, C2, ... Cn), válik hozzáférhetővé.
47
C – címbemenet D – adatkimenet E - (enable, engedélyező)
A C bemenetre érkező n-bites kombináció hatására a D kimeneten megjelenik a megfelelő cellában tárolt m-bites kombináció. Az E (enable, engedélyező) bemenetre adott jel letiltja vagy engedélyezi az adatkimenetet. Ennek révén, és a memória-elem áramköri kialakítása miatt több memóriaelem kimenetei huzalozott VAGY kapcsolat szerint közösíthetők. 48
8
2016.10.15.
MEMÓRIAELEM MINT KOMBINÁCIÓS HÁLÓZAT X1 X2
C1 C2 ...
D1 D2 ...
M-elem Xn
Cn E
Dm
F1 F2
ROM MINT UNIVERZÁLIS KOMBINÁCIÓS HÁLÓZAT
A memóriaelem egy n-változós és m kimeneti függvénnyel bíró kombinációs hálózatot valósít meg.
f1 = ABC + ABC + ABC
Az adatbeírás közvetlenül az igazságtáblázat alapján Fm végezhető el, nem szükséges a minimalizálás.
f 2 = AB + AC = ABC + ABC + ABC + ABC
Kombinációs hálózat
49
Mintermek: f1: 2, 4, 7, illetve f2: 0, 1, 5, 7
50
ROM MINT KOMBINÁCIÓS HÁLÓZAT A két 3-változós függvényhez egy 8x2 bites ROM elegendő, ilyen nincs forgalomban, 16x4 bitest alkalmazunk. A2, A1, A0 cím – A, B, C változók D0, D1 kimenet – f1, f2 függvény Igazságtábla előállítása és beprogramozása: A3 címbemenet fixen 0-ra kötve (csak a ROM alsó 8 szavát használjuk, a többi terület közömbös) D3, D2 – közömbös CS, OE fixen aktív szintre kötve, folyamatos engedélyezés
51
9
