Quine-McCluskey Módszer ECE-331, Digital Design Prof. Hintz Electrical and Computer Engineering Fordította: Szikora Zsolt, 2000 11/16/00
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
1
Quine-McCluskey Egyszerűsítés (Tabular Method)
Logikai függvényegyszerűsítéshez a Karnaugh-táblák hazsnálata korlátozott: – –
Kis függvények (<5változó) Egyszerre egyetlen kimeneti függvény
Nem implementálhatók számítógéppel Szubjektív megközelítés, különböző eredmények Q-M megoldja ezeket a problémákat!!
11/16/00
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
2
Alap definíciók
Benne-van viszony (“g benne van f-ben”) g ( x1 ,x2 ,K,xn ) ≤ f ( x1 ,x2 ,K,xn ) ha az x1 ,x2 ,K,xn változók ∀ olyan kombinációjához, amikor g(x) értéke 1, f(x) is = 1 - gyel.
Implikáns –
11/16/00
Egy term, mely benne van egy függvényben Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
3
Alap definíciók
Egy függvény Prím-implikánsa –
Kiváló egy-cella –
11/16/00
Egy olyan implikáns, amelyiknek megvan az a tulajdonsága is, hogy ha egyetlen változóját eltávolítjuk, többé már nem lesz benne a függvényben Egy minterm, melyet csupán egyetlen prím implikáns fed le Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
4
Alap definíciók
Lényeges prím imlikáns –
Teljes összeg – –
11/16/00
Egy prím implikáns, amelyik kiváló egy-cellát tartalmaz Egy függvény MINDEN lehetséges prímimlikánst tartalmazó reprezentációja Nem feltétlenül irredundáns
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
5
Alap definíciók
Irredundáns összeg –
11/16/00
Egy függvény megadása a PI-ok egy olyan összegével, amelyből a PI-ok bármelyikének eltávolítása megváltoztatja a függvény értékét néhány bemeneti érték kombináció esetén
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
6
Alap definíciók
Költség függvény –
Digitális tervezés költség függvényei – –
11/16/00
Valaminek a megvalósításához vagy egy feladat teljesítéséhez társuló erőfeszítés vagy hardver mértéke Termek száma A változók előfordulási száma (nem a különböző változók száma) Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
7
Quine-McCluskey módszer 1.Készítsd el a minterm számok bináris megfelelőinek egy „méret” szerint növekvő sorba rendezett táblázatát. –
11/16/00
A „méret” a bináris minterm-sorszámban lévő egyesek száma.
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
8
Quine-McCluskey módszer 2.Válaszd ki az első lépés táblázatából a azokat a termeket, melyek egységnyi Hamming-távolságra vannak egymástól és pipáld ki őket. –
11/16/00
A pipa jelzi, hogy a minterm egy „nagyobb” termben lesz benne a következő lépésben
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
9
Quine-McCluskey módszer 3.Helyezd a 2. Lépés párjait egy, az elsőhöz hasonló új táblázatba. –
11/16/00
Ennek az új táblázatnak minden sora bal oldalon tartalmazza a kiválasztott párok decimális minterm számait; jobb oldalon a pár bináris megfelelőjét, a két termben különbséget okozó bitet egy „-” jelre cserélve.
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
10
Quine-McCluskey módszer 4.Az új táblázatból válassz egységnyi távolságra lévő párokat, jelöld meg őket és menj vissza a 3. lépéshez – –
11/16/00
Ha nincsenek egységnyi távolságra lévő párok a harmadik lépés táblázatában, fezed be. Mikor az algoritmus befejeződik, azok a termek, amelyek a táblázatok egyikében sem megjelöltek, PI-ok.
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
11
Q-M, példa 1. lépés f (w,x, y ,z )=Σ1 (0,2,3,5,7,8, A,D,F ) mintermek = 0 =1 =2 =3 =4 11/16/00
0 2,8 3,5, A 7,D F
* Karim-Johnson, p. 59
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
12
Q-M, példa 1. és 2. lépés Méret minterm 0 0 1 2 1 8 2 3 2 5 2 A 3 7 3 D 4 F
11/16/00
W 0 0 1 0 0 1 0 1 1
X 0 0 0 0 1 0 1 1 1
Y 0 1 0 1 0 1 1 0 1
Z 0 0 0 1 1 0 1 1 1
Jelölve
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
13
Q-M, példa 1. és 2. lépés Méret minterm 0 0 1 2
W X Y Z 0 0 0 0 0 0 1 0
Jelölve
... 0
11/16/00
(0,2) ...
0 0 - 0
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
14
Q-M, példa 3. és 4. lépés méret 0 0 1 1 1 2 2 2 3 3 11/16/00
minterm (0,2) (0,8) (2,3) (2,A) (8,A) (3,7) (5,7) (5,D) (7,F) (D,F)
W 0 0 1 0 0 1
X 0 0 0 0 0 1 1 1 1
Y 0 1 1 1 0 1 -
Z Jelölve 0 0 PI-1 0 0 1 PI-2 1 1 1 1
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
15
Q-M, példa 3. és 4. lépés méret
minterm
W X Y Z
2 3
... (5,7) (D,F)
0 1 - 1 1 1 - 1
Jelölve
... 2
11/16/00
(5, 7, D, F)
- 1 - 1
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
16
Q-M, példa 5. lépés size 0 0 1 1
A) A) F) F)
W -
X 0 0 1 1
Y -
Z 0 0 1 1
Checked PI-3 same PI-4 same
Eredmény PI-ok – – – –
11/16/00
minterm (0, 2, 8, (0, 8, 2, (5, 7, D, (5, 7, D,
( 2, 3 ) ( 3, 7 ) ( 0, 2, 8, A ) ( 5, 7, D, F ) Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
17
Prím implikáns tábla
A táblázatos módszer megtalál minden PI-t, de sajnos redundáns lefedést eredményezhet A PI táblázat megtalálja az összegnek egy irredundáns összegét, a hazárdokra való tekintet nélkül –
–
11/16/00
A hazárdok logikai függvények olyan áramköri megvalósításai, amiknek 1-ben (0-ban) kellene maradniuk, amikor egy bemeneti érték megváltozik, de nem ez történik velük A hazárdokat az ECE-332 lab. ismerteti! (http://cpe.gmu.edu/courses/) Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
18
PI tábla módszer 1. Építsd fel a táblázatot – – –
Mintermekkel felül sorban Prím implikánsokkal bal oldalaon egymás alatt X-ekkel a PI sor és az ő mintermjei metszéspontjaiban
2. Karikázd be azokat a mintermeket, amiknek az oszlopában csak egyetlen X van –
11/16/00
Ezek a mintermek kiváló oszlopokat alkotnak, mert ők a kiváló egy-cellák
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
19
PI tábla módszer 3.Tégy csillagot minden olyan sor jobb szélére, amelyik a kiváló oszlopokban lévő mintermeket tartalmaz –
Ezek a lényeges sorok (lényeges PI-ok)
4. Húzz ki minden oszlopot, amelyik Xeket tartalmaz a lényeges sorokban 5.Rajzold újra a táblázatot a lényeges sorok és kihúzott oszlopok nélkül 11/16/00
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
20
PI tábla módszer 6.Távolítsd el az uralkodó sorokat és oszlopokat 7.Alkalmazd a költség-függvényt, hogy válassz a megmaradó PI-ok közül.
11/16/00
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
21
PI tábla módszer, példa Kiváló egy-cellák PI 1 2 3 4
0
X
2 X
5
7
8
A
X
X
D
F
LPI
X
* *
X
X X
PI 1 2 11/16/00
3 X X
3 X X
X
X
2dik LPI Akármelyik okay
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
22
Összefoglalás Q-M PI tábla LPI 2dik LPI Gyakorló feladat!! F=Σ(0,1,2,3,4,7,12,13,15,14) OKAY – Jöhet a Pascal program!
11/16/00
Forrás = http://cpe.gmu.edu/courses/ece331/lectures/331_8/index.htm
23
