Espreso istraživački logički umanjivač

Espreso logički minimizator je kompjuterski progam koji pomoću heurističkih i posebnih alogoritama efikasno smanjuje kompleksnost digitalnih elektronskih kola.^[1]Espreso je razvijen u IBM od strane Robert Brayton. Rudell je 1996 objavio varijantu Espresso-MV pod nazivom "Višestruki logički minimizator za PLA sintezu“.^[2] Espreso je uticao na razvoj mnogih proizvoda.

Uvod[uredi | uredi izvor]

Elektronski uređaji se sastoje od brojnih blokova digitalnih kola, čijom kombinaciojom se izvršava zadatak. Efikasna primena logičkih funkcija u obliku kola logičkih kapija (tako da se ne koristi više logičkih kola nego što je potrebno) omogućava smanjenje potrošnje i / ili povećava učinak uređaja.

Dizajn digitalnih logičkih kola[uredi | uredi izvor]

Svi digitalni sistemi se sastoji od dve osnovne funkcije: memorija elemenata za skladištenje podataka, i kombinacionih kola koja transformišu tu informaciju. Statične mašine, kao i brojači, su kombinacija memorijskih elemenata i kombinacionih logičkih kola. Pošto su memorijski elementi standardna logička kola oni su izabrani iz ograničenog skupa alternativnih kola; pa se projektovanje digitalnih funkcija svodi na projektovanje kombinacionih kola kapija i njihovo povezivanje.

Generalno probna logička kola na visokom nivou apstrakcije se nazivaju logičkom sintezom koja se može raditi ručno, ali češće na neki formalni način koji se primenjuje preko računara. U ovom članku su metode za projektovanje kombinacionih logičkih kola ukratko sažete.

Polazna tačka u dizajniranju digitalnih logičkih kola je njegova željena Funkcionalnost, pošto je izveden iz analize sistema kao celine, logičko kolo je njegov deo. Može se opisati u algoritamskom obliku ili logičkim jednačinama, ali može se takođe zapisati u obliku tabele. Primer ispod pokazuje deo takve tabele za 7-segmentni upravljački program koji prevodi binarni kod za vrednosti decimalnih cifara u signale koji osvetljavaju odgovarajuće segmente ekrana.

  Digit  Code        Segments
                   A B C D E F G
    0    0000      1 1 1 1 1 1 0          -A-
    1    0001      0 1 1 0 0 0 0         |   |
    2    0010      1 1 0 1 1 0 1         F   B
    3    0011      1 1 1 1 0 0 1         |   |
    4    0100      0 1 1 0 0 1 1          -G-
    5    0101      1 0 1 1 0 1 1         |   |
    6    0110      1 0 1 1 1 1 1         E   C
    7    0111      1 1 1 0 0 0 0         |   |
    8    1000      1 1 1 1 1 1 1          -D-
    9    1001      1 1 1 1 0 1 1

Proces implementacije počinje fazom 'logičke minimizacije', što će biti objašnjeno u daljem tekstu, u cilju pojednostavljenja tabele funkcija kombinovanjem posebnih uslova kako bi od većih sadržaja napravili sadržaj sa manje promenljivih. Dalje se minimizirani rezultat može podeliti na manje delove procedurom razlaganja i kasnije se mapira na osnovne logičke ćelije namenjene tehnologije. Ova operacija se obično naziva logička optimizacija.^[3]

Klasične metode minimizacije[uredi | uredi izvor]

Minimiziranje Bulovih funkcija ručno preko klasičnih karneovih mapa je naporan, dosadan i proces sklon greškama. Nije pogodan za više od 6 ulaznih promenljivih i praktičan je do 4 promenljive, dok je deljenje za više izlaznih funkcija još teže da sprovede.^[4]Štaviše, ovaj metod nije lak da se automatizuje u vidu kompjuterskog programa. Međutim, sa modernim logičkim funkcijama nismo ograničeni na tako mali broj promenljivih, dok je cena i rizik pravljenja greške za ručno implementaciju logičkih funkcija prevelika, zbog toga je upotreba računara postala neophodna.

Prvi alternativni metod koji je postao popularan je tabelarni metod koji su razvili Quine i McCluskey. Počevši od tablica istinitosti za skup logičkih funkcija, kombinujući minimalne vrednosti za koje su funkcije aktivirane -ON poklopac, ili vrednosti za koje je vrednost funkcija nebitna -Don't-Care poklopac ili - DC poklopac- koji čine set glavnih implikanata. Konačno sistematska procedura počinje u cilju pronalaženja najmanjeg skupa glavnih implikanata da bi izlazne funkcije mogle da se realizuju.^[5]^[6]

Iako je Kvajn–Maklaskijev algoritam pogodan da se realizuje u kompjuterskom programu, rezultat je još uvek daleko od efikasanog u smislu vremena obrade i korišćenja memorije. Dodavanje promenljivih u funkciji će otprilike udvostručiti oboje, zato što dužina tablice istinitosti eksponencijalno raste sa brojem promenljivih. Sličan problem se javlja kada se poveća broj izlaznih funkcija kombinacionog funkcionalnog bloka. Shodno tome Kvajn–Maklaskijev algoritam je praktičan metod samo za funkcije sa ograničenim brojem ulaznih promenljivih i izlaznih funkcija.

Espreso algoritam[uredi | uredi izvor]

Radikalno drugačiji pristup ovom pitanju je ESPRESO algoritam koji je razvio Brayton e.a. na Univerzitetu Berkli u Kaliforniji.^[7] Umesto proširivanja logičke funkcije preko minimalnih vrednosti, program radi sa "kockama ", koje predstavljaju proizvod uslova u ON-, DC- and OFF-poklopac iterativno. Iako rezultat minimizacije nije garantovano globalni minimum, u praksi to je veoma blisko usaglašeno, a rešenje je uvek bez logičkog viška. U odnosu na druge metode, ova je zančajno efikasnija, jer smanjuje korišćenje memorije i vreme obrade do nekoliko redova veličine. Ime Espreso i potiče iz sličnosti sa brzim načinom pravljenja kafe. Gotovo da nema ograničenja za broj promenljivih, izlaznih funkcija i proizvoda na osnovu uslova kombinacionih funkcija bloka. U principu, desetine varijabli sa desetinama izlaznih funkcija su lako rešivi.

Ulazne vrednosti za espreso se zapisuju u tabeli funkcija da bi dobili željenu funkcionalnost; Rezultat je minimiziran tabela, koja opisuje bilo ON-cover ili OFF-cover funkcije, u zavisnosti od izabranih opcija. Podrazumevano termini proizvoda će se deliti što više od strane nekoliko izlaznih funkcija, ali programu može biti naloženo da rukuje svakom od izlaznih funkcija posebno. Ovo omogućava efikasno sprovođenje u dva nivoa logičkih nizova, kao što su PLA (Programabilno logičko polje) ili PAL (Programabilna logika polja).

ESPRESO algoritam pokazao se toliko uspešan da je registrovan kao standardni korak minimizacije logičkih funkcija u svim savremenim alatima za logičku sintezu. Za sprovođenje funkcije u više nivoa logike, rezultat minimizacije je optimizovano razlaganje i mapiranje na raspoloživim osnovnim logičkim ćelijama u ciljnoj tehnologiji, bilo da se to tičeFPGA (engl.Field Programmable Gate Array) FPGA ili ASIC(Aplikaciono specifično integrisano kolo).

Softver[uredi | uredi izvor]

Minilog[uredi | uredi izvor]

'Minilog' je programa za logičku minimizacije koji koristi ESPRESO algoritam. Ona je u stanju da generiše kapije sa dva nivoa implementacije za kombinacione funkcije bloka sa do 40 ulaza i izlaza ili sinhrone mašine stanja sa do 256 stanja. On spada u Publicad edukacioni paket, koji može da se skine sa sajta Publicad^{[mrtva veza]} - besplatni Publicad alat koji uključuje Minilog programa za logičku minimizaciju.

Logic Friday[uredi | uredi izvor]

Logic Friday je Vindousov (Windows) besplatni program koji omogućava grafički interfejs za ESPRESO, takođe i za misII, drugi metod razvijen u Berkli paketu sa alatima. Ovim programom korisnici mogu uneti logičku funkciju kao tablicu istinitosti, jednačinu, dijagram ili kapiju, minimiziraju funkciju, a zatim videte rezultat u oba oblika. Logic Friday je dostupan na http://www.sontrak.com.

Espreso izvori[uredi | uredi izvor]

Izvor originalnog Espreso programa je dostupan na sajtu Univerziteta u Kaliforniji, Berkli Pubs/Downloads/Espresso. Verzija Espreso koja je ažurirana na savremenim POSIX sistemima je dostupan na [1]^{[mrtva veza]}

Reference[uredi | uredi izvor]

^ Hayes, J.P. (1993), Digital Logic Design, Addison Wesley, ISBN 978-0-201-15461-0
^ Rudell, Richard L. (5. 6. 1986), „Multiple-Valued Logic Minimization for PLA Synthesis” (PDF), Memorandum No. UCB/ERL M86-65, Berkeley
^ De Micheli, Giovanni (1994), Synthesis and Optimization of Digital Circuits, McGraw-Hill Science Engineering, ISBN 978-0-07-016333-1
^ Lewin, Douglas (1985), Design of Logic Systems, Van Nostrand (UK), ISBN 978-0-442-30606-9
^ Katz, Randy H.; Borriello, Gaetano (1994), Contemporary Logic Design, The Benjamin/Cummings Publishing Company, ISBN 978-0-8053-2703-8
^ Lala, Parag K. (1996), Practical Digital Logic Design and Testing, Prentice Hall, ISBN 978-0-02-367171-5
^ Brayton, Robert King; Hachtel, Gary D.; McMullen, Curtis T.; Sangiovanni-Vincentelli, Alberto L.. (1984), Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, ISBN 978-0-89838-164-1

[1] Hayes, J.P. (1993), Digital Logic Design, Addison Wesley, ISBN 978-0-201-15461-0

[2] Rudell, Richard L. (5. 6. 1986), „Multiple-Valued Logic Minimization for PLA Synthesis” (PDF), Memorandum No. UCB/ERL M86-65, Berkeley

[3] De Micheli, Giovanni (1994), Synthesis and Optimization of Digital Circuits, McGraw-Hill Science Engineering, ISBN 978-0-07-016333-1

[4] Lewin, Douglas (1985), Design of Logic Systems, Van Nostrand (UK), ISBN 978-0-442-30606-9

[5] Katz, Randy H.; Borriello, Gaetano (1994), Contemporary Logic Design, The Benjamin/Cummings Publishing Company, ISBN 978-0-8053-2703-8

[6] Lala, Parag K. (1996), Practical Digital Logic Design and Testing, Prentice Hall, ISBN 978-0-02-367171-5

[7] Brayton, Robert King; Hachtel, Gary D.; McMullen, Curtis T.; Sangiovanni-Vincentelli, Alberto L.. (1984), Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, ISBN 978-0-89838-164-1

[1]

[2]

[3]

[4]

[5]

[6]

[7]