5. ELİADÁS
DIGITÁLIS TECHNIKA I
1. Karnaugh táblázat programok
Dr. Pıdör Bálint BMF KVK Mikroelektronikai és Technológia Intézet
2. Nem teljesen határozott logikai függvények
5. ELİADÁS
3. Karnaugh táblázat, logikai tervezési példák 4. A számjegyes minimalizálás (Quine-McCluskey módszer) alapjai
2008/2009 tanév 1. félév 1
KARNAUGH TÁBLA, K-MAP
2
KARNAUGH TÁBLA PROGRAMOK
A Karnaugh tábla (Karnaugh map) mint Veitch diagram is ismert (röviden K-map, vagy KV-map). Elsı leírója Maurice Karnaugh (Bell Labs, 1950), illetve Edward W. Veitch (1952). Edward W. Veitch, A chart method for simplifying truth functions, May 1952, Proc. Assoc. for Computing Machinery, Pittsburgh Maurice Karnaugh, The map method for synthesis of combinational logic circuits, Trans. AIEE, pt. I, 72(9), 553599, November 1953. A nem túl nagy változószámú függvények gyors szemléletes minimalizálása mellett alkalmas a potenciális hazárd3 jelenségek azonosítására és eliminálására, melyeket csupán a Boole algebrai egyenletek alapján nem lehet elvégezni.
kmap12.exe
www.puz.com/sw/karnaugh/
kmin.zip
karnaugh.shuriksoft.com/
KMapSimulator.zip members.cox.net/cyclone1980/ KMapSimulation10Embedded.htm A Karnaugh map programok általában mindkét kanonikus alakot kezelik. SOP: sum-of-products, diszjunktív algebrai alak. POS: product-of-sums, konjunktív algebrai alak.
4
PÉLDA: ÖT-VÁLTOZÓS MINIMALIZÁLÁS
PÉLDA: ÖT-VÁLTOZÓS MINIMALIZÁLÁS
F(A,B,C,D,E) = Σ5 (2,6,8,10,12,14,17,19, 21,23,26,27,30,31)
F(A,B,C,D,E) = Σ5 (2,6,8,10,12,14,17,19, 21,23,26,27,30,31)
5
_ ABE
ABD
_ _ ADE
_ _ ABE
6
PÉLDA: HATVÁLTOZÓS MINIMALIZÁLÁS
PÉLDA: HATVÁLTOZÓS MINIMALIZÁLÁS F(A,B,C,D,E,F) = Σ6(0,2,6,9,14,18,21,23,25,27,32,34,41,49,53,55,57,61,62)
7
8
LEGEGYSZERŐBB KONJUNKTÍV FÜGGVÉNYALAK
PÉLDA A LEGEGYSZERŐBB KONJUNKTÍV ALAK KÉPZÉSÉRE
•Eddig mindig a legegyszerőbb diszjunktív alakot írtuk fel a Karnaugh tábla alapján.
C
• A legegyszerőbb konjunktív algebrai alak is könnyen kiolvasható a K-táblából, ekkor a tagadott függvény mintermjeit kell hurkokkal lefedni, ez megadja a függvény negáltjának legegyszerőbb diszjunktív algebrai alakját.
1
1
1
1
1
A • Ebbıl a DeMorgan azonosság alapján rögtön adódik a ponált függvény legegyszerőbb konjunktív alakja.
—
——
—
——
—
—
1
Pl. a felsı sorbeli négyes hurok (a peremeken ellentétesnek kell venni a B változókat!) (A + B)
1 D
9
LEGEGYSZERŐBB KONJUNKTÍV ALGEBRAI ALAK
Három négyes és két kettes hurok jelölhetı ki.
10
NEM TELJESEN HATÁROZOTT LOGIKAI FÜGGVÉNY Az összevonás során a nem rögzített függvényértéket tetszılegesen választhatjuk 1-nek vagy 0-nak, attól függıen, hogy melyik adja a legkedvezıbb megoldást.
—
F=AB+BD+ACD+ACD+BC
Bejegyzések a Karnaugh táblán (háromféle!) —
—
—
—
F = (A+B)(B+D)(A+C+D)(A+C+D)(B+C) Természetesen ugyanez olvasható ki a Karnaugh táblázatból is. 11
1 0 X
a minterm szerepel a függvényben, a minterm nem szerepel a függvényben, a minterm értéke közömbös.
(A 0 bejegyzés helyett sokszor üresen marad a cella.) 12
NEM TELJESEN HATÁROZOTT LOGIKAI FÜGGVÉNY A B C F ————— 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 —————
NEM TELJESEN HATÁROZOTT FÜGGVÉNYEK
3
Nem teljesen határozott logikai függvényeknél elıfordulhat, hogy a közömbös értékeket máskép célszerő rögzíteni a legegyszerőbb konjunktív alak képzésekor, mint ahogy azt a legegyszerőbb diszjunktív alaknál tennénk. Ekkor a két elvi logikai rajzon a kapubementek száma különbözı lehet! A megvalósításkor, ha szabadon választhatunk a két alak között, azaz nincs megkötés az ÉS és VAGY szintek sorrendjére, akkor a legkevesebb kapubemenetet igénylı megoldást a két függvényalak további, 14 heurisztikus elemzésével kaphatjuk csak meg.
F = Σ ((0,2,3,7) + (4,6)) C Optimális lefedés két 4-es hurok: 1 — F=B+C 1 1 B Itt a közömbös függX 1 vényértékeket 1-nek A X tekintjük. 13
PÉLDA A KÖZÖMBÖS FÜGGVÉNYÉRTÉK ELTÉRİ RÖGZÍTÉSÉRE C 1
1
-
-
1
1
1
1
A 1
1
1
LEGEGYSZERŐBB ALGEBRAI ALAKOK
A színkóddal jelölt cella értékét a diszjunktív alak keresésénél célszerő 1-nek rögzíteni, a B konjunktív alak keresésénél pedig 0-nak!
—
—
— —
Fk = (A+B)(B+C+D)(B+C+D) A változók negáltjait elıállító invertereket is figyelembe véve a diszjkunktív alak realizálásnál 11, a konjunktív alakénál pedig 14 kapubementre van szükség!
1
D
—
Fd = B + C D + A C D
15
16
TERVEZÉS (1): MEGOLDÁS (ÉS-VAGY)
TERVEZÉSI GYAKORLAT (1 ÉS 2) Tervezzen 4 bemenető (ABCD), 1 kimenető (F) kombinációs hálózatot, amelynek F kimenete 1, ha a bemenetre adott bináris számok (legmagasabb helyérték A) maradék nélkül oszthatók 3-mal vagy 4-el. Rajzolja fel a Karnaugh tábláját, és az elvi logikai rajzot.
3-al osztható: 0,3,6,9,12,15 4-el osztható: 0,4,8,12
C 1
1
1
1 B
Rajzolja fel az F Karnaugh tábláját és az elvi logikai rajzot, ha a bemenetre csak binárisan kódolt decimális számok (BCD 8-4-2-1 súlyozás) érkezhetnek. 17
1
1
A 1
A megvalósítandó logikai függvény 4 F = Σ(0,3,4,6,8,9,12,15)
1 D
18
TERVEZÉS (1): MEGOLDÁS (ÉS-VAGY) Az egyszerősített alak
C 1
__ _ _ __ F=CD+ABD+ABC
1
1
1 B
1
1
A
_ _ + ABCD+ABCD (Esetleg XOR logika ?)
1
1 D
19
TERVEZÉS (1): MEGOLDÁS (VAGY-ÉS)
TERVEZÉSI PÉLDA (1): MEGOLDÁS Az elvi logikai rajz:
1 db két-bemenető ÉS 2 db három-bemenető ÉS 2 db négy-bemenető ÉS 1 db 5 bemenető VAGY kapu. A minimalizált hálózatban 21 kapubement van. Realizálás: 1/4 7400 (4x2 bemenető NAND) 2 7420 (2x4 bemenető NAND) 1 7430 (1x8 bemenető NAND) A teljes diszjunktív kanonikus alak realizálása 8x4 + 1x8 = 40 kapubementet igényelne.
TERVEZÉS (1): MEGOLDÁS (VAGY-ÉS)
C 1 1
1 B
1
Az elvi logikai rajz (VAGY-ÉS):
_ _ A+B+D
1
6 db három-bemenető VAGY kaput és 1 db 6 bemenető ÉS kaput tartalmaz.
stb., hat hasonló szerkezető tényezı
A minimalizált hálózatban 24 kapubement van.
1
A teljes konjunktív kanonikus alak realizálása 8x4 + 1x8 = 40 kapubementet igényelne.
A 1
1 D
21
22
TERVEZÉS (2): MEGOLDÁS
1
1
1 B
X
X
X
X
A 1
1
X D
TERVEZÉSI PÉLDA (2): MEGOLDÁS
3-al osztható: 0,3,6,9 (12,15 kizárva!) 4-el osztható: 0,4,8 (12 kizárva!)
C 1
20
X
1
_ _ _ _ F=A+CD+BD+BCD
1
1
A megvalósítandó logikai függvény
1 B
X
X
X
X
1
1
X
X
A
4 F = Σ((0,3,4,6,8,9) +(10-15))
A minimalizált függvény
C
23
D
24
TERVEZÉSI PÉLDA (2): MEGOLDÁS Az elvi logikai rajz : 1 db közvetlen összekötetést, 2 db két-bemenető, 1 db három-bemenető ÉS kaput és 1 db 4 bemenető VAGY kaput tartalmaz. A minimalizált hálózatban 12 kapubement van. Realizálás: 3/4 7400 (4x2 bemenető NAND) 1 7420 (2x4 bemenető NAND) A teljes diszjunktív kanonikus alak realizálása 6x4 + 1x6 = 30 kapubementet igényelne. Megjegyzés: ebben az esetben a VAGY-ÉS elrendezés némileg egyszerőbb lenne, csak 11 kapubement szükséges hozzá.
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).
25
TERVEZÉS (3): MEGOLDÁS
A B C D
• 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.
Például ha A B C D = 1 1 0 1 akkor X Y Z = 1 1 0 AB +CD =XYZ
Adja meg a hálózat igazságtábláját. Adja meg a hálózat kimenetenként legegyszerőbb 26 logikai függvényeit algebrai alakban.
TERVEZÉS (3): MEGOLDÁS
X Y Z
mivel
TERVEZÉSI GYAKORLAT (3)
11 01 110
27
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
28
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 = Σ(7,10,11,12-15) 4 Y = Σ(2,3,5,6,8,9,12,14) 4 Z = Σ(1,3,4,6,9,11,12,14)
29
30
TERVEZÉS (3): MINIMALIZÁLT, FÜGGVÉNYEK
X(A,B,C,D) MINIMALIZÁLÁSA
A Karnaugh táblából a három minimalizált függvény könnyen kiolvasható
C A minimalizált függvény
X=AC+BCD+ABD _ _ _ _ _ _ __ Y=ACD+ABC+ACD+ABC _ _ +ABCD+ABCD _ _ Z=BD+BD
X=AC+BCD+ABD
1 B 1
1
1
1
1
A
D
31
NAPTÁR KIJELZİ
FORMÁLIS MEGFOGALMAZÁS
Determine number of days in a month (to control watch display) Used in controlling the display of a wrist-watch LCD screen
•
Feladat: napok száma adott hónapban, karóra LCD kijelzıje vezérléséhez 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); }
Inputs: month, leap year flag Outputs: number of days Bemenetek: hónap, szökıév flag Kimenetek: napok száma, négy kimeneti vonal
Use software implementation to help understand the problem
•
Encoding: – Binary number for month: 4 bits – 4 wires for 28, 29, 30, and 31 one-hot – only one true at any time Block diagram:
month
1
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 – –
NAPTÁR: 30 NAPOS HÓNAP
A színkóddal jelölt lefedés szerint 0
leap – – 0 1 – – – – – – – – – – – –
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 34
NAPTÁR: 31 NAPOS HÓNAP
-
leap
month 0000 0001 0010 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 111–
28 29 30 31
}
33
C
32
(Esetleg XOR logika ?)
A lefedés szerint
C
_ _ F=AD+ABD
-
—
F=AD+AD 0 1
1
1
-
-
0 -
A 1
0
0 D
1
1 B A közömbös kombinációk elınyösen kihasználhatók a függvény minimalizálásánál! 35
1 B -
-
1
1
-
A
D
36
BINÁRISAN KÓDOLT DECIMÁLIS SZÁMOK
RELZÁLÁS: DISZKRÉT KAPUK •
Diszkrét kapuk
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 – 30 =
m8’ m4 m1’ + m8 m1
– 31 = m8’ m1 + m8 m1’ •
Can translate to S-o-P or P-o-S
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 – –
Egy fontos eset a nem teljesen határozott logikai függvények alkalmazására, amikor binárisan kódolt decimális (BCD) számokkal kell valamilyen mőveletet, kódolást, dekódolást, stb. elvégezni. A BCD kód, és a vele rokon kódok (pl. a 3 többletes kód) a lehetséges 16 négy-bites kódszóból csak tízet használ. Jó gyakorló feladat: BCD - 7 szegmenses számjegykijelzı illesztı kombinációs hálózata. 37
38
PÉLDA: BCD/7-SZEGMENSES KIJELZİ DEKÓDOLÓ
A FELADAT ANALÍZISE • Igazságtábla – don't care termek
• Bemenet : 4 bit BCD digit (A, B, C, D) • Kimenet : 7 szegmens vezérlıjele (C0-C6) c5 c4
c0
• Megvalósítási technika megválasztása – Ha ROM, akkor kész – Don't care termek PAL/PLA elınyös lehet
c1
c6
c2
c3 c0 c1 c2 c3 c4 c5 c6
• A kiválasztott technikától függıen minimalizálás Karnaugh táblákon
BCD to 7–segment control signal decoder A B C D
39
HÉT KIMENET FÜGGETLEN MINIMALIZÁLÁSA
A
A
0
X
1
0
1
X
1
C 1
1
X
1
1
X
1
X
1
1
0
X
1
X
C 1
1
X
X
1
0
X
D
B
A
1
1
X
1
1
1
X
1
X
C 1
1
X
X
0
1
X
D
B
0
X
1
0
1
X
0
X
C 1
0
X
X
1
1
X
D
0
X
1
0
0
X
0
X
C 0
0
X
X
X
1
1
X
X
B
D
1
X
1
0
1
X
1
0
1
X
1
0
1
X
1
C 0
0
X
X
C 1
0
X
X
0
1
X
X
1
1
X
X
D
B
D
C0 C1 C2 C3 C4 C5 C6
= = = = = = =
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 – –
40
A
C2
B
A
1
D 0 1 0 1 0 1 0 1 0 1 – –
– 9 különbözı szorzat tag (15 helyett) – Közös termek – Az egyes kimenetek nem szükségképen minimális
1 D
C 0 0 1 1 0 0 1 1 0 0 1 –
• Jobb megoldás is van! A
1
B
A
B
A
1
B 0 0 0 0 1 1 1 1 0 0 0 1
MINIMALIZÁLÁS KÖZÖS TERMEKKEL
• 15 term ha a kimeneteket külön-külön kezeljük
1
A 0 0 0 0 0 0 0 0 1 1 1 1
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!41
A
1
1
X
1
1
1
X
1
C 1
1
X
X
0
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
1
X
X
0
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
42
A SZÁMJEGYES MINIMALIZÁLÁS ALAPJAI
PLA REALIZÁLÁS A B C D
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.
BC' B'C B'D BC'D C'D'
Algoritimizálható, programozható.
CD B'D' A
Quine-McCluskey módszer.
BCD'
C0 C1 C2 C3 C4 C5 C6 C7 43
44
KÉT MINTERM SZOMSZÉDOSSÁGÁNAK FELTÉTELE (1)
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édos, ha decimális indexeik különbsége 2 egész számú hatványa. —
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.
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.
45
46
KÉT MINTERM SZOMSZÉDOSSÁGÁNAK FELTÉTELE (2)
KÉT MINTERM SZOMSZÉDOSSÁGÁNAK FELTÉTELE (3)
Két minterm szomszédos, ha bináris súlyaik (1-esek száma) különbsége 1. _ _ __ _ _ _ 6 0110 (2) A B C D + A B C D → A C D 2 0010 (1) 4 (1)
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 48 teljesül, persze ezek nem szomszédosak.
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, 47 éppen ez a feltétel mely nem teljesül.
QUINE-MCCLUSKEY ALGORITMUS
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.
A számjegyes minimalizálás Quine-McClsukey 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.
Ezen alapul a Quine-McCluskey algoritmus.
49
50
MINTERM TÁBLA
QUINE-MCCLUSKEY MINIMALIZÁLÁS Minimalizálandó függvény:
Súly
f (A,B,C,D) = Σm(0, 2, 3, 5, 7, 8,10,13,15) minterms = 0
0
⇒0 1
= 1 ⇒ 2, 8 = 2 ⇒ 3, 5,10 = 3 ⇒ 7,13 = 4 ⇒ 15 A mintermeket az indexeik bináris vagy Hamming 51 súlya szerint csoportosítjuk
SZOMSZÉDOK MEGKERESÉSE…
0
1
Minterm
Párok
0
0,2 (2) 0,8 (8)
2 8
2
3 5 10
3
7 13
4
15
0 2 8
2
3 5 10
3
7 13
4
15 52
AZ ÖSSZES SZOMSZÉDPÁR Súly
Súly
Minterm
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
Ö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. 53
Ezután a párokat kell párosítani: 4-es csoportok
54
NÉGYES CSOPORTOK Súly 0
Minterm
Pár
Négyes
0
0,2 (2) 0,8 (8)
0,2,8,10 (2,8)
2 8
*
2
3 5 10
*
3
7 13
4
15
1
PRÍMIMPLIKÁNS TÁBLA Prímimplikánsok 0,2,8,10 (2,8) 5,7,13,15 (2,8)
2,3 (1) 2,10 (8) 8,10 (2) 3,7 (4) 5,7 (2) 5,13 (8)
2,3 (1) 3,7 (4)
5,7,13,15 (2,8)
7,15 (8) 13,15 (2)
Kék csillag * : prímimplikáns 55
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)
X X X
Prímimplikánsok 0,2,8,10 (2,8) 5,7,13,15 (2,8) 2,3 (1) 3,7 (4)
X
X X X
X
58
REDUKÁLT LEFEDÉSI TÁBLA
√ √ √ √ √ √ √ √ 0 2 3 5 7 8 10 13 15 X X X X X X X X X X X
Mintermsek 0 2 3 5 7 8 10 13 15 X X X X X X X X
57
MINTERMEK LEFEDÉSE
2,3 (1) 3,7 (4)
56
PRÍMIMPLIKÁNS TÁBLA
Minterms 0 2 3 5 7 8 10 13 15 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.
Primimplikánsok 0,2,8,10 (2,8) 5,7,13,15 (2,8)
Mintermek 0 2 3 5 7 8 10 13 15
X
A két négyes prímimplikáns az m3 kivételével már lefedi az összes mintermet. 59
Prímimplikánsok
3
2,3 (1) 3,7 (4)
X X
Mintermek
A fennmaradt m3 minterm lefedése bármelyik kettes prímimlpikánssal megoldható, itt m(2,3) a választás. Így m(2,3) a harmadik lényeges 60 prímimplikáns, m(3,7) pedig redundás.
MEGOLDÁS A KARNAUGH TÁBLÁN
MINIMALIZÁLÁS EREDMÉNYE
Lényeges prímimplikánsok
C
f (A,B,C,D ) = 0,2,8,10(2,8) + 5,7,13,15(2,8) + 2,3(1) =
X0X0
+
X1X1
+ 001X
=
BD
+
BD
+ AB C
1
1 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 A 1
61
1 D
QUINE-MCCLUSKEY ALGORITMUS PROGRAM Boolean function`s minimalisation software based on the Quine-McCluskey method www.seattlerobotics.org/encoder/200106/qmccmin. htm
VÉGE
Példa: 64 változós függvény 64 mintermet tartalmazó alakjának minimalizálása
63
64
