2016.02.21.
DIGITÁLIS TECHNIKA
IRODALOM Arató Péter: Logikai rendszerek tervezése, Tankönyvkiadó, Budapest, 1990, Műegyetemi Kiadó 2004, 55013 műegyetemi jegyzet
Dr. Lovassy Rita Dr. Pődör Bálint Óbudai Egyetem KVK Mikroelektronikai és Technológia Intézet
Zsom Gyula: Digitális technika I és II, Műszaki Könyvkiadó, Budapest, 2000, (KVK 49-273/I és II)
3. ELŐADÁS: LOGIKAI (BOOLE) FÜGGVÉNYEK ÉS ALKALMAZÁSAIK
Rőmer Mária: Digitális rendszerek áramkörei, Műszaki Könyvkiadó, Budapest, 1989, (KVK 49-223) Rőmer Mária: Digitális technika példatár, KKMF 1105, Budapest 1999 Az előadások ezen könyvek megfelelő fejezetein alapulnak. 1
LOGIKAI MŰVELETEK ÉS DUALITÁS
2
LOGIKAI ÁRAMKÖRÖK KIALAKÍTÁSA
Röviden áttekintjük a logikai alapműveletek közötti kapcsolatot melyet a dualitás fejez ki és lényegében a De Morgan tételeken alapul.
Tetszőleges logikai összefüggés, vagy logikai függvény is előállítható a NEM-ÉS vagy NEM-VAGY alapművelet párokkal. Vagyis tetszőleges logikai áramkör kialakítható csupán NEM-ÉS, vagy csupán NEM-VAGY kapuk alkalmazásával. A NAND és az NOR univerzális műveletek. Elvileg elég csak NAND vagy csak NOR kapukat tartatni, azokból bármilyen logikai áramkör felépíthető. Gyakorlati jelentőség: az elektronikus erősítők általában invertáló jellegűek (180 fokos fázistolás). Ezért a gyakorlatban a NEM-ÉS (NAND) és a NEM-VAGY (NOR) a szokásos alapelem.
A kétargumentumos műveletek közül kettőt-kettőt alapművelet-párokként választhatunk. (Egyiket vagy a másikat, de nem mindkettőt.) Ezek a művelet-párok a következők: ÉS ( szorzás) — VAGY (összeadás: +) NEM-ÉS (NAND) — NEM-VAGY (NOR) A műveletpárok egyik tagja a másik un. duális párja. A duális műveletpárokat De Morgan tételek kapcsolják össze. A duális művelet-párokkal (és a negációval) kifejezhetjük bármelyik másik műveletet.
Végső soron mindez a De Morgan tételeken alapul!
CSAK NAND ILLETVE NOR KAPUS MEGVALÓSÍTÁSOK
KOMBINCIÓS HÁLÓZATOK A GYAKORLATBAN Egy kétszintű ÉS-VAGY hálózat (szorzatok összege, sum-ofproducts) megvalósítható kétszintű NEM-ÉS/NEM-ÉS (NAND-NAND) hálózattal. Egy kétszintű VAGY-ÉS hálózat (összegek szorzata, productof-sums) megvalósítható kétszintű NEM-VAGY/NEM-VAGY (NOR-NOR) hálózattal. Mindez a De Morgan tételeken alapul. 5
6
1
2016.02.21.
LOGIKAI KIFEJEZÉSEK ALGEBRAI ÁTALAKÍTÁSA
LOGIKAI ALGEBRAI ÁTALAKÍTÁS (1) Hozzuk egyszerűbb alakra az alábbi kifejezést _ _ Y = AB + AB + ABCD
A következőkben néhány példával illusztráljuk a logikai függvények algebrai átalakítását. Hangsúlyozni kell, hogy a logikai algebra műveleti szabályai eltérnek a szokásos algebra szabályaitól!
Az A változó kiemelhető, utána a zárójelben lévő kifejezés fokozatosan egyszerűsíthető _ _ _ Y = A(B + B + BCD) = A(1 + BCD) = A Válasz: Y = A
NAND KAPUS REALIZÁLÁS
LOGIKAI ALGEBRAI ÁTALAKÍTÁS (2) Hozzuk egyszerűbb alakra az alábbi kifejezést ____ ________ Y = ABC + A + B + C
A kétszintű NAND kapus realizálás az alábbi átalakításon alapul (De Morgan szabályok!) ________ ___ ___ _ _ – – Y(A,B,C) = AC + BC = (AC) (BC)
Alkalmazzuk a De Morgan azonosságokat! _ _ _ ___ _ __ _ _ Y = A + B + C + A B C = A(1 + B C) + B + C =
A _ C
_ _ _ =A+B+C
B _ C
KÉTVÁLTOZÓS FÜGGVÉNYEK: ANTIVALENCIA, EKVIVALENCIA
AND, OR, NAND, NOR
A•B, A+B, A•B, A+B
——
—
X
&
Z
Y
Y
X
&
Z
Y
XOR (A ⊕ B ),
A, A, B, B
—
Z
Antivalencia (más neve kizáró vagy)
—
Egyváltozós függvények
XOR (A⊕B ), XNOR (A B)
& Y
ANTIVALENCIA ÉS EKVIVALENCIA
Függvény neve f(A,B) —————————————————————— Logikai konstansok 0, 1 —
X
Ekvivalencia
———
XNOR (A
——
A B+A B, A B+A B Angolul:
INHIBÍCIÓ (TILTÁS) A ⊃ B, B ⊃ A IMPLIKÁCIÓ (KÖVETKEZTETÉS) A → B, B → A 11
B)
antivalency (exclusive-or) equivalency vagy coincidence
12
2
2016.02.21.
ANTIVALENCIA (XOR) XNOR EKVIVALENCIA (XNOR) A B f62 f92 —————— 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 ——————
ANTIVALENCIA, EXCLUSIVE-OR A B f62 ———— _ _ 0 0 0 f62 = A B + A B 0 1 1 1 0 1 szokásos jelölése: 1 1 0 ———— f62 = A ⊕ B
A két függvény egymás ellentettje (negáltja) ____ A⊕B = A B —
—
XOR
f62 = A⊕B = A B+A B,
XNOR
f92 = A B = A B+A B
——
ANTIVALENCIA más néven KIZÁRÓ-VAGY (EXCLUSIVEOR), a függvény akkor 1, ha vagy az egyik, vagy a másik változó 1, és 0, ha mindkét változó egyszerre 0 vagy 1. 13
14
ANTIVALENCIA
EKVIVALENCIA, EXCLUSIVE-NOR A B f92 ———— __ 0 0 1 f92 = AB + AB 0 1 0 1 0 0 szokásos jelölése: 1 1 1 ———— f92 = A B
A B f62 ————— 0 0 0 0 1 1 1 0 1 1 1 0 —————
EKVIVALENCIA (EXCLUSIVE-NOR), a függvény akkor 1, ha mindkét változó egyszerre 0 vagy 1, és akkor 0 ha az egyik, vagy a másik változó 1.
Az igazságtáblázat szerint a f62 = A ⊕ B művelet egyben megvalósítja a két bites maradéknélküli bináris összeadás aritmetikai műveletét (”fél összeadó”).
Az antivalencia kapu felfogható egy-bites ”digitális komparátor”-nak is, ha a bemenetére érkező két bit azonos értékű, a kimeneten 0 jelet ad, ha eltérő, akkor 1-et. 16
15
EXCLUSIVE-OR, ANTIVALENCIA —
KIZÁRÓ-VAGY
—
A⊕B = A B+A B, ⇒ Az XOR megvalósítja két bit átvitel nélküli összeadását (fél-összeadó). ⇒ Funkcionál mint vezérelt inverter (vezérlőjel: A, feldolgozandó jel: B). ⇒ Funkcionál mint ”páratlanság-vizsgáló”: ha páratlan számú bemeneten van 1, akkor a kimenet 1, ellenkező esetben 0. Itt már implikáltuk az XOR kiterjesztését több bementre (értelmezés az MSz szerint, részletes magyarázat Zsom I, 76-77 old.!) 17
Az EXCLUSIVE-OR megvalósítása történhet a definiáló Boole algebrai egyenlet alapján NEM, ÉS és VAGY kapukkal, vagy megfelelő átalakítás után NAND kapukkal mint univerzális elemmel. Az TTL és CMOS áramköri családokban van külön kész EXCLUSIVE-OR kapu is.
18
3
2016.02.21.
EXCLUSIVE-OR NEM, ÉS, VAGY KAPUS MEGVALÓSÍTÁSA
EXCLUSIVE-OR (ANTIVALENCIA) NAND KAPUS MEGVALÓSÍTÁSA
——————— —— —— — — — — A⊕B = A B+A B = (A B)•(A B)
1. Az XOR a Boole-egyenlet szerint megvalósítása. 2. Az XOR szabványos rajzjele. 3. Az XOR régebbi rajzjele. 19
Itt feltételezzük, hogy a negált változók rendelkezésre állnak. 20
EKVIVALENCIA (XNOR) NEM, ÉS, VAGY KAPUS MEGVALÓSÍTÁSA
EXCLUSIVE-NOR: EKVIVALENCIA ——
A B = A B+A B Az igazságtáblázat szerint az XNOR az XOR negáltja. Több változóra való kiterjesztéskor az XNOR függvénynek többféle értelmezése is előfordul! Pl. az MSZ szerint három változó esetén a függvény értéke csak a 0 0 0 és az 1 1 1 bemeneti kombinációkra 1, az összes többire 0. A másik szokásos értelmezés esetén a függvény értéke akkor 1, ha a változók között páros számú 1 van.
1. Az XNOR a Boole-egyenlet szerinti megvalósítása. 2. Az XNOR (EKVIVALENCIA) szabványos rajzjele. 3. Az XNOR régebbi rajzjele.
21
EXCLUSIVE-NOR (EKVIVALENCIA) NAND KAPUS MEGVALÓSÍTÁSA
22
NOR KAPUS REALIZÁLÁSOK Természetesen mind az ANTIVALENCIA (XOR) mind az EKVIVALENCIA (XNOR) megvalósítható kizárólag NOR kapuk felhasználásával.
A NAND kapus realizálás a De Morgan azonosságok felhasználásával végzett átalakítások eredménye. 23
24
4
2016.02.21.
LOGIKAI FÜGGVÉNY MEGADÁSA IGAZSÁGTÁBLÁZATTAL ILLETVE ALGEBRAI ALAKBAN
LOGIKAI FÜGGVÉNYEK MEGADÁSI MÓDJAI A logikai függvény többféle módon megadható, illetve ábrázolható. Az alábbi módokat fogjuk alkalmazni.
i A B C Y _________________ 0 0 0 0 0 1 0 0 1 0 2 0 1 0 1 3 0 1 1 0 4 1 0 0 1 5 1 0 1 0 6 1 1 0 1 7 1 1 1 0 _________________
1. Igazságtáblázat 2. Algebrai alak 3. Grafikus ábrázolás 4. Szimbolikus jelölés
– – –– – Y(A,B,C) = ABC + ABC + ABC Egy logikai függvény egyértelmű megadása: a független változók összes lehetséges kombinációjához megadjuk a függvénykapcsolat által előírt függvényértéket. Ez az ún. igazságtáblázat. Az ilyen függvénydefiníció egyértelmű.
25
FÜGGVÉNY MEGADÁSA ALGEBRAI ALAKBAN: KANONIKUS ALAK
26
GRAFIKUS ÁBRÁZOLÁS A logikai függvény értékei pl. az igazságtáblázat segítségével grafikusan is szemléltethetők ún. függvénytáblázatokon
A logikai függvény megadható oly módon, hogy a logikai műveletek szimbólumaival (ÉS, VAGY és NEM) definiáljuk a logikai függvényt.
(Karnaugh-táblázatok, ill. Veitch-diagramok). Ez az ábrázolási mód korlátozott független változó szám esetén igen szemléletes, és az ún. függvény-minimalizáláskor jól felhasználható.
A kombinációs hálózatok tervezésének kiindulási lépése a logikai függvény felírása a megoldandó feladat alapján. Általában az algebrai alak használatos. Egyazon függvény többféle algebrai alakban is megadható. Közöttük kitüntetett szerepük van az ún. normalizált vagy kanonikus alakoknak. 27
KOMBINÁCIÓS HÁLÓZAT ÉS LOGIKAI FÜGGVÉNY
28
LOGIKAI FÜGGVÉNYEK KANONIKUS ALAKJAI A most következő anyagot egy háromváltozós, teljesen határozott logikai függvény igazságtáblázata fogja illusztrálni, az új fogalmakat ennek alapján vezetjük be, és az elméletet is ez alapján építjük fel.
Egy kombinációs hálózatban egyetlen kimeneti pont esetén minden logikai feladat megadható egyetlen logikai függvénnyel. Az egyes bemeneti-változó kombinációkhoz tartozó függvényérték a hálózat kimeneti változójának logikai értékével azonos.
A tárgyalásmód Arató Péter (ajánlott) könyvét (Logikai rendszerek tervezése) követi.
29
30
5
2016.02.21.
TELJESEN HATÁROZOTT LOGIKAI FÜGGVÉNY (LOGIKAI FELADAT) A B C F ————— 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0 —————
LOGIKAI FÜGGVÉNYEK KANONIKUS ALAKJAI
Teljesen határozott logikai függvény megadható azon változókombinációk felsorolásával,amelyekhez F = 1, vagy azokéval amihez F = 0 tartozik. —
—
—
——
A kombinációs hálózatok tervezésénél célszerű az algebrai alakból kiindulni. Mivel egy logikai függvénynek több algebrai alakja is van, olyan speciális tulajdonságú alakot kell keresni, mely olyan, hogy a logikai függvényhez más, ilyen tulajdonságú algebrai alak nem rendelhető. Az ilyen alak a logikai függvény normál vagy kanonikus
—
F(ABC) = ABC + ABC + ABC + ABC vagy ————
———
——
—
alakja.
F(ABC) = A B C + A BC + ABC + ABC —
F és F egyaránt logikai szorzatok VAGY kapcsolataként adható meg. 31
DISZJUNKTÍV KANONIKUS ALAK (EXTENDED SUM-OF-PRODUCTS)
MINTERM (DEFINICIÓ) A diszjunktív kanonikus alak tagjai neve minterm
A logikai szorzatok logikai összegeként (ÉS-VAGY) képzett algebrai alak kanonikus vagy normál alak. A példa szerinti függvényalak tulajdonságai: — —
—
——
32
—
m in
itt n a független változók száma,
i a független változók adott kombinációjának megfelelő bináris szám decimális értéke.
F(ABC) = ABC + ABC + ABC + ABC
— —
- mindegyik szorzat egy olyan független-változó kombináció, melyhez F = 1 tartozik; - mindegyik szorzatban az összes független változó szerepel ponált vagy negált alakban. A teljesen határozott függvénynek csak egy ilyen algebrai alakja van a diszjunktív kanonikus alak.
—
——
A B C F ————— 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0
—
F(ABC) = ABC + ABC + ABC + ABC (emlékeztető: (2) (3) (4) (6) ) F(ABC) = m23 + m33 + m43 + m63 más jelölés: 3 F = Σ (2,3,4,6)
33
KONJUNKTÍV KANONIKUS ALAK
KONJUNKTÍV KANONIKUS ALAK (2)
A negált függvény ————
———
——
—
F(ABC)= A B C + A B C + A B C + A B C ————
F(ABC) = m03 + m13 + m53 + m73 A függvény negáltja azokat a mintermeket tartalmazza, melyeket a függvény nem tartalmaz (ez csak a teljesen határozott logikai függvényekre igaz!)
34
A B C F ————— 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 0
35
A De Morgan képletek felhasználásával elvégzett átalakításokkal előállítható az F függvény konjunktív kanonikus alakja, mely az un. maxterm-ek szorzataként adható meg ————
————————————————————
————
———
——
—
A B C F —————
F(ABC) = F(ABC) = A B C + A B C + A B C + A B C = 0 0 0 0 —
—
—
—
—
—
(A + B + C) (A + B + C) (A + B + C) (A + B + C)
F(ABC) = M73M63M23M03
0 0 0 1 1 1 1
0 1 1 0 0 1 1
1 0 1 0 1 0 1
0 1 1 1 0 1 0 36
6
2016.02.21.
MINTERMEK ÉS MAXTERMEK KAPCSOLATA
ELVI LOGIKAI RAJZ Minden logikai függvény megadható ÉS, VAGY, NEM műveletekkel. Eltekintve a bemeneti változók negáltját adó NEM kapuktól (INVERTER), a két kanonikus alak kétszintű ÉS-VAGY illetve VAGY-ÉS kapuhálózattal realizálható.
Eredeti függvény, diszjunktív normálalak F(ABC) = m23 + m33 + m43 + m63 Negált függvény, diszjunktív normálalak (index i)
Mivel az ÉS, VAGY és NEM műveletek akár kizárólag NAND akár kizárólag NOR kapukkal megvalósíthatók, ezért a diszjunktív normálalakból kiindulva bármely logikai függvény realizálható kétszintű NAND kapus vagy NOR kapus hálózattal.
————
F(ABC) = m03 + m13 + m53 + m73 Eredeti függvény, konjunktív normálalak (index I) F(ABC) = M73M63M23M03 37
38
— —
—
&
F(ABC) = ABC + ABC —
——
+ ABC + ABC
& 1
& & o
Az ÉS kapuk bementeire értelemszerűen az egyes ponált vagy negált változók kerülnek.
& o
& 39
AZ F(A,B,C) KÉTSZINTŰ VAGY-ÉS KAPUS REALIZÁLÁSA — —
— —
A NAND kapuk bemene-teire értelemszerűen az egyes ponált vagy negált változók kerülnek.
40
AZ F(A,B,C) KÉTSZINTŰ NOR KAPUS REALIZÁLÁSA —
—
— —
F(ABC) = (A+B+C)(A+B+C)(A+B+C)(A+B+C)
1
o
1
1
o
1
o
1
o
&
1
Az ÉS kapuk bementeire értelemszerűen az egyes ponált vagy negált változók kerülnek.
1 41
— —
—
—
F(ABC) = (A+B+C)(A+B+C)(A+B+C)(A+B+C)
1
1
—
+ ABC + ABC
o
&
&
—
o
——
— —
F(ABC) = ABC + ABC
o
&
AZ F(A,B,C) KÉTSZINTŰ NAND KAPUS REALIZÁLÁSA o
AZ F(A,B,C) KÉTSZINTŰ ÉS-VAGY KAPUS REALIZÁLÁSA
A NAND kapuk bemene-teire értelemszerűen az egyes ponált vagy negált változók kerülnek.
42
7
2016.02.21.
LOGIKAI FÜGGVÉNY EGYSZERŰSÍTÉSE: MINIMALIZÁLÁS Logikai hálózat tervének gazdaságossága: 1. Felhasznált kapuk számának csökkentése; 2. Összekötetések számának csökkentése; 3. Kapukat megvalósító építőelem-fajták optimális kiválasztása.
LOGIKAI FÜGGVÉNY EGYSZERŰSÍTÉSE: ILLUSZTRÁCIÓ — —
—
Az optimalizálás (minimalizálás) bizonyos korlátokkal, mint a kapubementek számának csökkentése (minimalizálása) is megfogalmazható. 43
EGYSZERŰSÍTETT FÜGGVÉNY ÉS-VAGY KAPUS REALIZÁLÁSA
—
—
— —
o
Az eredmény egy jóval egyszerűbb algebrai alak melyet realizálva mind a kapuk, mind az összekötetések száma jelentősen csökken. 44
LOGIKAI FÜGGVÉNYEK MINIMALIZÁLÁSA
& —
o
—
——
—
m 23 + m 33 + m 43 + m 63
mintermek
1 1
—
F(ABC) = ABC + ABC + ABC + ABC
B C
—
= AB(C + C) + AC(B + B) = AB + AC
— —
1
—
”kiemelések” alkalmazásával
A 3. pontbeli feladat megoldására nincs általános módszer, az 1. és 2. pontbeli feladatokra adhatók használható eljárások.
A
——
F(ABC) = ABC + ABC + ABC + ABC
—
— —
—
—
= AB(C + C) + AC(B + B) = AB + AC
&
—
Az összevonható mintermek egy helyértékben és csakis egyben térnek el egymástól:
—
F(A,B,C) = AB + AC
(010) és (011), illetve (100) és (110) 45
SZOMSZÉDOS MINTERMEK, MINIMALIZÁLÁS
Ez az összevonások és a minimalizálás kulcsa!
46
MINIMALIZÁLÁS, PRÍMIMPLIKÁNSOK
Szomszédos mintermek: egy logikai változó ponált illetve negált, a többi azonos. A minimalizálás menete: 1. A szomszédos mintermeket összevonják, a megfelelő változó kiesik. 2. Az új alakban az esetleges szomszédos termeket megint összevonják. 3. Az eljárást addig folytatják míg olyan szorzatok összegét kapjuk, melyekből már egy változó sem hagyható el. Az így kapott szorzatok, termek a prímimplikáns-ok. 47
A logikai függvény minimalizált (diszjunktív) alakja tehát prímimplikáns-ok összege. — —
—
——
—
F(ABC) = ABC + ABC + ABC + ABC —
—
F(ABC) = AB + AC —
—
itt a prímimplikánsok AB és AC A logikai függvényt egyszerűsítő eljárások célja a prímimplikánsok megkeresése. Egy függvénynek több ekvivalens legegyszerűbb alakja is lehet!
48
8
