4/3/2014
Optimizacija realizacije logičkih funkcija
Vanr.prof.dr.Lejla Banjanović‐
Mehmedović
Optimizacija logičke funkcije
 Booova algebra, Karnaughove mape i CAD (Computer Aided Design) su metode logičke simplifikacije.  Cilj logičke simplifikacije (optimizacije) je minimizacija troškova rješenja.
 Karnaughove mape reduciraju logičke funkcije brže i lakše u poređenju sa Boolovom algebrom.  Redukcija – broja gejtova i ulaza.
 Logička simplifikacija po najnižoj cijeni postiže se eliminacijom komponenti – najmanji broj logičkih kola i najmanji broj ulaza po logičkom kolu.
PLS_5
Optimalna realizacija logickih kola
1
4/3/2014
Minimizacija logičkih funkcija Karnaughovim mapama
j
g
j
 Grafičke metode minimizacije logičkih funkcija –
Veitchove ili Karnaughove mape.
 Ove dvije metode se razliku samo u redoslijedu označavanja pojedinih polja, ideja potekla od Veitch‐a, u literaturi oba naziva.
 Karnaughova metoda se zasniva na Karnaughovim mapama, odnosno grafičkom prikazu logičkih funkcija. 2n
Sadrže polja za n promjenljivih, tj. broj polja je jednak broju mintermi u tablici istine.
PLS_5
Optimalna realizacija logickih kola
Minimizacija logičkih funkcija Karnaughovim mapama
 Minterme u mapama su definisane algebarskim p
g
izrazima a poredane su tako da se susjedna polja razlikuju samo za jednu bit poziciju.
 Karnaughove mape za funkcije dvije promjenljive
PLS_5
Optimalna realizacija logickih kola
2
4/3/2014
Minimizacija logičkih funkcija Karnaughovim mapama
 Karnaughove mape crtamo tako da za svaku kombinaciju g
p
j
ulaznih promjenljivih, u odgovarajuće polje, upisujemo vrijednost funkcije za tu kombinaciju.
 U polja upisujemo samo vrijednost funkcije koje su jednake logičkoj 1, a u praznim poljima se podrazumjeva vrijednost 0 logičke funkcije.  Sažimanje se ona polja, koja su susjedna, formirajući par, Sažimanje se ona polja koja su susjedna formirajući par koji čini konturu od dvije jedinice ili nule. PLS_5
Optimalna realizacija logickih kola
Minimizacija logičkih funkcija Karnaughovim mapama
PLS_5
Optimalna realizacija logickih kola
3
4/3/2014
Minimizacija logičkih funkcija Karnaughovim mapama
Karnaughove mape za funkcije tri promjenljive
PLS_5
Optimalna realizacija logickih kola
Minimizacija logičkih funkcija Karnaughovim mapama
 Kontura koja obuhvata par jedinica (nula) u j
p j
(
)
Veitchovim dijagramima, iz analizičkog izraza funkcije elimiše jednu promjenljivu koja se pojavljuje u afirmaciji ili negaciji.
 Četvorka jedinica (nula) u Veitchovom dijagramu, iz analitičkog izraza funkcije eliminiše dvije promjenljive koje se pojavljuju u afirmaciji ili negaciji.
j
p j j j
f
j
g j
 Kontura od osam jedinica (nula) u Veitchovom dijagramu, iz analitičkog izraza funkcije eliminiše tri promjenljive koje se pojavljuju u afirmaciji ili negaciji.
PLS_5
Optimalna realizacija logickih kola
4
4/3/2014
Minimizacija logičkih funkcija Karnaughovim mapama
 Kada se u konturi Veitchovog dijagrama pojavljuje promjenljiva i u afirmaciji i u negaciji, tu promjenljivu treba eliminisati iz analitičkog izraza funkcije.  Promjenljiva koja je ista u svim poljima jedne konture, mora biti u kanačnom analitičkom ,
izrazu.
 Nedostatak metode: Teško formalizirati i nije pogodna za programiranje na računaru.
PLS_5
Optimalna realizacija logickih kola
Minimizacija logičkih funkcija Karnaughovim mapama
 Sve jedinice (nule) date logičke funkcije moraju biti prekrivene minimalnim brojem nakraćih konjukcija (disjunkcija) (prostih implikanti), odnosno što većim konturama. Pri tome isto polje smije biti pokriveno sa više kontura.  Konture mogu biti horizontalne ili vertikalne, mogu biti sa desne i lijeve strane, sa gornje i donje strane dijagrama, u četiri ugla dijagrama, ali nikada dijagonalne.
PLS_5
Optimalna realizacija logickih kola
5
4/3/2014
Primjeri kreiranja kontura za četiri promjenljive
PLS_5
Optimalna realizacija logickih kola
Primjeri logičke simplifikacije na dva načina
 Oba rješenja imaju isti minimalni trošak logičke realizacije
PLS_5
 Oba rješenja imaju isti minimalni trošak logičke realizacije
Optimalna realizacija logickih kola
6
4/3/2014
Realizacija logičkih funkcija u TTL vs. CMOS logici
 Bolje rješenje zavisi od kompleksnosti i tipa korištene logičke familije.  SOP rješenje je obično bolje kada se koristi TTL logička familija pri čemu su NAND gejtovi bazne komponente, koje rade jako dobro u SOP implementaciji.  POS rješenje je prihvatljivije kada se koristi sa CMOS
logičkom familijom, pri čemu su sve forme NOR
gejtova raspoložive. PLS_5
Optimalna realizacija logickih kola
Procedura konstrukcije NAND‐NAND logike umjesto AND‐OR logike
1.
2.
3.
4.
5.
PLS_5
Formirati reducirani SOP logički dizajn.
g
j
Pri dizajniranju SOP dijagrama zamjeniti sve gejtove (i
AND i OR) sa NAND kolima.
Neiskorišteni ulazi trebaju biti povezani na logičku jedinicu.
Označiti pakete integrisanih kola sa U1, U2,.. itd.
P id ži i b j i
Pridružiti brojeve pinovima ulaza i izlaza svakog gejta.
i l i i l k j
Optimalna realizacija logickih kola
7
4/3/2014
Primjer 1:
PLS_5
Optimizirati logičku funkciju, kreirajući
rezultat u SOP i POS formi.
Optimalna realizacija logickih kola
Primjer 1:
PLS_5
Optimalna realizacija logickih kola
8
4/3/2014
Primjer 1: POS rješenje
PLS_5
Optimalna realizacija logickih kola
Primjer 1: SOP rješenje
PLS_5
Optimalna realizacija logickih kola
9
4/3/2014
Minimizacija nepotpuno definisanih logičkih funkcija
 Za neke logičke funkcije tablica istine sadrži kombinacije ulaznih promjenljivih za koje izlazni nivo nije bitan ili se nikada ne pojavljuje odnosno može imati vrijednost logičke 1 ili 0.
 Kod takvih funkcija neke kombinacije ulaznih signala se nikada ne pojavljuju, tako da nije definisan logički nivo izlaza, pa se njegova vrijednost može proizvoljno izabrati.
 Ovo su tzv. nepotpuno definisane logičke funkcije, a nedefinisane ulazne ili izlazne kombinacije nazivamo zabranjene kombinacije. Proizvoljnost izbora je ograničena konačnim ciljem, tj. realizacija najracionalnije strukture mreže u postupku minimizacije.
PLS_5
Optimalna realizacija logickih kola
Minimizacija nepotpuno definisanih logičkih funkcija
 U Karnoughovu mapu prvo upisujemo 1, zatim zabranjene kombinacije (x) i na kraju 0.
 Pri nalaženju MDNF polazimo od optimalnih kontura jedinica, uključujući u njih i zabranjene kombinacije, ako je potrebno. Konture gradimo dok ima nepokrivenih jedinica. Od preostalih zabranjenih kombinacija ne treba praviti nove b
j ih k
bi
ij t b iti konture.
 Sličan pristup za MKNF, ali konturama pokrivamo nule.
PLS_5
Optimalna realizacija logickih kola
10
4/3/2014
Primjer 2:
 Logika uključenja lampica za stacionarni bicikl u muzeju.
 Ako vozač uvećava brzinu pedaliranja, uključuju se lampice. Ako nema kretanja, ni jedna lampica nije uključena. Ako se brzina uvećava, prvo se pali L1, pa L1 i L2, potom L1, L2 i L3 itd., maksimalno može biti uključeno 5 lampica. Kada napon dodje do maksimuma, nema daljeg uvećanja iza ove granice.
PLS_5
Optimalna realizacija logickih kola
Primjer 2:
A
B
C
Y
Lampe
0
0
0
0
0
0
0
1
1
L1
0
1
0
1
L1 L2
0
1
1
1
L1 L2 L3
1
0
0
1
L1 L2 L3 L4
1
0
1
1
L1 L2 L3 L4 L5
1
1
0
*
*
1
1
1
*
*
Y  ABC  ABC  ABC  ABC  ABC..( SDNF )
Y  ( A  B  C )..( SKNF )
PLS_5
Optimalna realizacija logickih kola
11
4/3/2014
Primjer 2:
PLS_5
Optimalna realizacija logickih kola
Primjer 2:
PLS_5
Optimalna realizacija logickih kola
12
Download

Optimizacija logičke funkcije - Vanr.prof.dr. Lejla Banjanović