Еспресо истраживачки логички умањивач
Еспресо логички минимизатор је компјутерски прогам који помоћу хеуристичких и посебних алогоритама ефикасно смањује комплексност дигиталних електронских кола.[1]Еспресо је развијен у IBM од стране Robert Brayton. Rudell је 1996 објавио варијанту Еспрессо-МВ под називом "Вишеструки логички минимизатор за ПЛА синтезу“.[2] Еспресо је утицао на развој многих производа.
Увод[уреди | уреди извор]
Електронски уређаји се састоје од бројних блокова дигиталних кола, чијом комбинациојом се извршава задатак. Ефикасна примена логичких функција у облику кола логичких капија (тако да се не користи више логичких кола него што је потребно) омогућава смањење потрошње и / или повећава учинак уређаја.
Дизајн дигиталних логичких кола[уреди | уреди извор]
Сви дигитални системи се састоји од две основне функције: меморија елемената за складиштење података, и комбинационих кола која трансформишу ту информацију. Статичне машине, као и бројачи, су комбинација меморијских елемената и комбинационих логичких кола. Пошто су меморијски елементи стандардна логичка кола они су изабрани из ограниченог скупа алтернативних кола; па се пројектовање дигиталних функција своди на пројектовање комбинационих кола капија и њихово повезивање.
Генерално пробна логичка кола на високом нивоу апстракције се називају логичком синтезом која се може радити ручно, али чешће на неки формални начин који се примењује преко рачунара. У овом чланку су методе за пројектовање комбинационих логичких кола укратко сажете.
Полазна тачка у дизајнирању дигиталних логичких кола је његова жељена Функционалност, пошто је изведен из анализе система као целине, логичко коло је његов део. Може се описати у алгоритамском облику или логичким једначинама, али може се такође записати у облику табеле. Пример испод показује део такве табеле за 7-сегментни управљачки програм који преводи бинарни код за вредности децималних цифара у сигнале који осветљавају одговарајуће сегменте екрана.
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
Процес имплементације почиње фазом 'логичке минимизације', што ће бити објашњено у даљем тексту, у циљу поједностављења табеле функција комбиновањем посебних услова како би од већих садржаја направили садржај са мање променљивих. Даље се минимизирани резултат може поделити на мање делове процедуром разлагања и касније се мапира на основне логичке ћелије намењене технологије. Ова операција се обично назива логичка оптимизација.[3]
Класичне методе минимизације[уреди | уреди извор]
Минимизирање Булових функција ручно преко класичних карнеових мапа је напоран, досадан и процес склон грешкама. Није погодан за више од 6 улазних променљивих и практичан је до 4 променљиве, док је дељење за више излазних функција још теже да спроведе.[4]Штавише, овај метод није лак да се аутоматизује у виду компјутерског програма. Међутим, са модерним логичким функцијама нисмо ограничени на тако мали број променљивих, док је цена и ризик прављења грешке за ручно имплементацију логичких функција превелика, због тога је употреба рачунара постала неопходна.
Први алтернативни метод који је постао популаран је табеларни метод који су развили Quine и McCluskey. Почевши од таблица истинитости за скуп логичких функција, комбинујући минималне вредности за које су функције активиране -ON поклопац, или вредности за које је вредност функција небитна -Don't-Care поклопац или - DC поклопац- који чине сет главних импликаната. Коначно систематска процедура почиње у циљу проналажења најмањег скупа главних импликаната да би излазне функције могле да се реализују.[5][6]
Иако је Квајн–Макласкијев алгоритам погодан да се реализује у компјутерском програму, резултат је још увек далеко од ефикасаног у смислу времена обраде и коришћења меморије. Додавање променљивих у функцији ће отприлике удвостручити обоје, зато што дужина таблице истинитости експоненцијално расте са бројем променљивих. Сличан проблем се јавља када се повећа број излазних функција комбинационог функционалног блока. Сходно томе Квајн–Макласкијев алгоритам је практичан метод само за функције са ограниченим бројем улазних променљивих и излазних функција.
Еспресо алгоритам[уреди | уреди извор]
Радикално другачији приступ овом питању је ЕСПРЕСО алгоритам који је развио Brayton e.a. на Универзитету Беркли у Калифорнији.[7] Уместо проширивања логичке функције преко минималних вредности, програм ради са "коцкама ", које представљају производ услова у ON-, DC- and OFF-поклопац итеративно. Иако резултат минимизације није гарантовано глобални минимум, у пракси то је веома блиско усаглашено, а решење је увек без логичког вишка. У односу на друге методе, ова је занчајно ефикаснија, јер смањује коришћење меморије и време обраде до неколико редова величине. Име Еспресо и потиче из сличности са брзим начином прављења кафе. Готово да нема ограничења за број променљивих, излазних функција и производа на основу услова комбинационих функција блока. У принципу, десетине варијабли са десетинама излазних функција су лако решиви.
Улазне вредности за еспресо се записују у табели функција да би добили жељену функционалност; Резултат је минимизиран табела, која описује било ON-cover или OFF-cover функције, у зависности од изабраних опција. Подразумевано термини производа ће се делити што више од стране неколико излазних функција, али програму може бити наложено да рукује сваком од излазних функција посебно. Ово омогућава ефикасно спровођење у два нивоа логичких низова, као што су ПЛА (Програмабилно логичко поље) или ПАЛ (Програмабилна логика поља).
ЕСПРЕСО алгоритам показао се толико успешан да је регистрован као стандардни корак минимизације логичких функција у свим савременим алатима за логичку синтезу. За спровођење функције у више нивоа логике, резултат минимизације је оптимизовано разлагање и мапирање на расположивим основним логичким ћелијама у циљној технологији, било да се то тичеFPGA (engl.Field Programmable Gate Array) FPGA или ASIC(Апликационо специфично интегрисано коло).
Софтвер[уреди | уреди извор]
Minilog[уреди | уреди извор]
'Минилог' је програма за логичку минимизације који користи ЕСПРЕСО алгоритам. Она је у стању да генерише капије са два нивоа имплементације за комбинационе функције блока са до 40 улаза и излаза или синхроне машине стања са до 256 стања. Он спада у Publicad едукациони пакет, који може да се скине са сајта Publicad[мртва веза] - бесплатни Publicad алат који укључује Минилог програма за логичку минимизацију.
Logic Friday[уреди | уреди извор]
Logic Friday је Виндоусов (Windows) бесплатни програм који омогућава графички интерфејс за ЕСПРЕСО, такође и за misII, други метод развијен у Беркли пакету са алатима. Овим програмом корисници могу унети логичку функцију као таблицу истинитости, једначину, дијаграм или капију, минимизирају функцију, а затим видете резултат у оба облика. Logic Friday је доступан на http://www.sontrak.com.
Еспресо извори[уреди | уреди извор]
Извор оригиналног Еспресо програма је доступан на сајту Универзитета у Калифорнији, Беркли Pubs/Downloads/Espresso. Верзија Еспресо која је ажурирана на савременим POSIX системима је доступан на [1][мртва веза]
Референце[уреди | уреди извор]
- ^ 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