DIGITÁLIS TECHNIKA I Dr. Kovács Balázs Dr. Lovassy Rita Dr. Pődör Bálint
Óbudai Egyetem KVK Mikroelektronikai és Technológia Intézet 6. ELŐADÁS
1
Arató Péter: Logikai rendszerek tervezése, Tankönyvkiadó, Budapest, Műegyetemi Kiadó, 55013 műegyetemi jegyzet Zsom Gyula: Digitális technika I és II, Műszaki Könyvkiadó, Budapest, (KVK 49-273/I és II) 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.
TERVEZÉSI GYAKORLAT (3) 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.
3
TERVEZÉS (3): MEGOLDÁS
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
AB +CD =XYZ
11 01 100
4
TERVEZÉS (3): MEGOLDÁS • 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.
5
TERVEZÉS (3): IGAZSÁGTÁBLÁZAT 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
6
TERVEZÉS (3): LOGIKAI FÜGGVÉNYEK Az igazságtáblázatból a három logikai függvény könnyen kiolvasható 4 X = S(7,10,11,13,14,15) 4 Y = S(2,3,5,6,8,9,12,15) 4 Z = S(1,3,4,6,9,11,12,14) 7
X(A,B,C,D) MINIMALIZÁLÁSA C
A minimalizált függvény X=AC+BCD+ABD
1 B A
1
D
1
1
1
1 8
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ó X=AC+BCD+ABD _ _ _ _ _ _ __ Y=ACD+ABC+ACD+ABC _ _ +ABCD+ABCD _ _ Z=BD+BD (Esetleg XOR logika ?)
9
TERVEZÉSI PÉLDA (4) NAPTÁR KIJELZŐ Feladat: napok száma adott hónapban, karóra LCD kijelzője vezérléséhez
Bemenetek: hónap, szökőév flag Kimenetek: napok száma, négy kimeneti vonal
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); } }
10
FORMÁLIS MEGFOGALMAZÁS 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
month
leap
28 29 30 31
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 – –
31 – 1 0 0 1 0 1 0 1 1 0 1 0 1 – – 11
NAPTÁR: 31 NAPOS HÓNAP A színkóddal jelölt lefedés szerint
C 0 A
1
1
1
1
0 0
1
-
-
-
1
0
0
1
D
—
—
F=AD+AD
B A közömbös kombinációk előnyösen kihasználhatók a függvény minimalizálásánál! 12
NAPTÁR: 30 NAPOS HÓNAP A lefedés szerint
C
_ _ F=AD+ABD
1
1 B
A
-
-
1
1 D
-
13
REALIZÁLÁS: DISZKRÉT KAPUK •
Diszkrét kapuk – 28 = m8’ m4’ m2 m1’ leap’ – 29 = m8’ m4’ m2 m1’ leap – 30 =
m8’ m4 m1’ + m8 m1
– 31 = m8’ m1 + m8 m1’
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 – –
31 – 1 0 0 1 0 1 0 1 1 0 1 0 1 – –
14
TERVEZÉSI PÉLDA (5): BCD/7-SZEGMENSES KIJELZŐ DEKÓDOLÓ • Bemenet : 4 bit BCD digit (A, B, C, D) • Kimenet : 7 szegmens vezérlőjele (C0-C6)
c5 c4
c0 c6
c1 c2
c3 c0 c1 c2 c3 c4 c5 c6
BCD to 7–segment control signal decoder A B C D
(MSI változat: 7446, 7447, 7447, 7449) 15
A FELADAT ANALÍZISE • Igazságtábla – don't care termek • Megvalósítási technika megválasztása – Ha ROM, akkor kész – Don't care termek PAL/PLA előnyös lehet • A kiválasztott technikától függően minimalizálás Karnaugh táblákon
A 0 0 0 0 0 0 0 0 1 1 1 1
B 0 0 0 0 1 1 1 1 0 0 0 1
C 0 0 1 1 0 0 1 1 0 0 1 –
D 0 1 0 1 0 1 0 1 0 1 – –
C0 1 0 1 1 0 1 1 1 1 1 – –
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 – –
16
MINIMALIZÁLÁSI PÉLDA (C0) C0
C 1
0
1
1
0
1
1
1 B
A
-
-
-
-
1
1
-
-
D
_ _ C0 = A + C + B D + B D
17
HÉT KIMENET FÜGGETLEN MINIMALIZÁLÁSA • 15 term ha a kimeneteket külön-külön kezeljük A
A
1
0
X
1
0
1
X
1
C 1 1
1
X
X
1
X
X
D
1
1
X
1
1
0
X
1
C 1 1
1
X
X
0
X
X
B
D
B
A
1
1
X
1
1
1
X
1
C 1 0
1
X
X
1
X
X
B
A
D
A
1
0
X
1
0
1
X
0
C 1 1
0
X
X
1
X
X
D
1
0
X
1
0
0
X
0
C 0 1
0
X
X
1
X
X
B
B
A
1
1
X
1
0
1
X
1
C 0 0
0
X
X
1
X
X
B
A
D
0
1
X
1
0
1
X
1
C 1 1
0
X
X
1
X
X
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!
18
D
MINIMALIZÁLÁS KÖZÖS TERMEKKEL • Jobb megoldás is van! – 9 különböző szorzat tag (15 helyett) – Közös termek – Az egyes kimenetek nem szükségképen minimális A
C2
A
1
1
X
1
1
1
X
1
C 1 0
1
X
X
1
X
X
C2 D
B
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
1
1
X
1
1
1
X
1
C 1 0
1
X
X
1
X
X
D
B
C0 C1 C2 C3 C4 C5 C6
= = = = = = =
B C' D + C D + B' D' + B C D' + A B' D + C' D' + C D + B' D' B' D + B C' D + C' D' + C D + B C D' B C' D + B' D + B' D' + B C D' B' D' + B C D' B C' D + C' D' + A + B C D' B' C + B C' + B C D' + A
19
PLA REALIZÁLÁS A B C D BC' B'C B'D BC'D C'D' CD B'D' A BCD'
C0 C1 C2 C3 C4 C5 C6 C7 20
A SZÁMJEGYES MINIMALIZÁLÁS ALAPJAI Quine-McCluskey módszer Algoritimizálható, programozható. 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 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. 21
MINTERMEK SZOMSZÉDOSSÁGA A minimalizálás alapja a szomszédos mintermek megkeresése, egyszerűsítése, míg el nem jutunk a prímimplikánsokig. 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.
22
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
—
—
——
—
—
—
ABCD+ABCD®ACD
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.
23
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) ABCD+ABCD®ACD 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. 24
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) ABCD+ABCD®ACD 2 0010 (1) 4 (1) 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. 25
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.
26
QUINE-MCCLUSKEY ALGORITMUS 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. 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. 27
QUINE-MCCLUSKEY MINIMALIZÁLÁS Minimalizálandó függvény:
f (A,B,C,D) = Sm(0, 2, 3, 5, 7, 8,10,13,15) minterms = 0
Þ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
28
MINTERM TÁBLA Súly 0
1
Minterm 0 2 8
2
3 5 10
3
7 13
4
15 29
SZOMSZÉDOK MEGKERESÉSE… Súly 0 Két minterm szomszédos, ha decimális indexeik különbsége 2 egész számú hatványa.
1
Minterm
Párok
ü0
0,2 (2) 0,8 (8)
ü2 ü8
2
3 5 10
3
7 13
4
15
Ö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.
30
AZ ÖSSZES SZOMSZÉDPÁR Súly
Minterm
Pár
ü0
0,2 (2) 0,8 (8)
ü2 ü8
2,3 (1) 2,10 (8) 8,10 (2)
2
ü3 ü5 ü10
3,7 (4) 5,7 (2) 5,13 (8)
3
ü7 ü13
7,15 (8) 13,15 (2)
4
ü15
0
1
Ezután a párokat kell párosítani: 4-es csoportok
31
NÉGYES CSOPORTOK Súly Két minterm szomszédos, ha bináris súlyaik (1-esek száma) különbsége 1.
Kék csillag * : prímimplikáns Ezek a tagok nem lettek összevonva
Minterm
Pár
Négyes
ü0
ü0,2 (2) ü0,8 (8)
0,2,8,10 (2,8)
*
ü2 ü8
2,3 (1) ü2,10 (8) ü8,10 (2)
*
ü3 ü5 ü10
3,7 (4) ü5,7 (2) ü5,13 (8)
3
ü7 ü13
ü7,15 (8) ü13,15 (2)
4
ü15
0
1
2
5,7,13,15 (2,8)
32
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)
33
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 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. 34
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 0 2 3 5 7 8 10 13 15 X X X X X X X X X X X
X
35
MINTERMEK LEFEDÉSE Primimplikánsok «0,2,8,10 (2,8) «5,7,13,15 (2,8) 2,3 (1) 3,7 (4)
√ √ √ √ √ √ √ √ 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. 36
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
0000 0010 1000 1010 X0X0
=
X0X0
+
X1X1
+ 001X
=
BD
+
BD
+ AB C
5 7 13 15
0101 0111 1101 1111 X1X1
2 3
0010 0011
001X 37
MEGOLDÁS A KARNAUGH TÁBLÁN Lényeges prímimplikánsok
C 1
1 1
1
1
Redundás (nem lényeges) prímimplikáns) __ _ _ F(A,B,C,D) = B D + B D + A B C
B 1
A
1
1
1 D
QUINE-MCCLUSKEY ALGORITMUS PROGRAM www.seattlerobotics.org/encoder/200106/qmccmin.htm Példa: 64 változós függvény 64 mintermet tartalmazó alakjának minimalizálása
39
Kombinációs hálózatok megvalósítása memóriaelemek felhasználásával
40
MEMÓRIAELEMEK TULAJDONSÁGAI Állandó tartalmú memóriák: Read Only Memory (ROM), 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é.
41
MEMÓRIAELEM ELVI VÁZLATA C1 C2 ...
D1 D2 ...
Cn E
Dm
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. 42
MEMÓRIAELEM MINT KOMBINÁCIÓS HÁLÓZAT X1 X2
C1 C2 ...
D1 D2 ...
M-elem Xn
Cn E
Dm
F1 F2
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.
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.
Kombinációs hálózat
43
ROM MINT UNIVERZÁLIS KOMBINÁCIÓS HÁLÓZAT f1 = ABC + ABC + ABC
f2 = AB + AC = ABC + ABC + ABC + ABC
Mintermek: f1: 2, 4, 7, illetve f2: 0, 1, 5, 7
44
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
45
