Еспресо истраживачки логички умањивач

Из Википедије, слободне енциклопедије

Еспресо логички умањивач је компјутерски програм који користи специфичне алгоритме како би се ефикасно смањила комплексност дигиталних електронских кола капија. [1] Еспресо је развио Роберт Брејтон у IBM-у. Rudell је касније објавио верзију Espresso-MV 1986. године која је названа "Multiple-Valued Logic Minimization for PLA Synthesis".[2] Еспресо је инспирисао многе изводе.

Увод[уреди]

Електронски уређаји се састоје од бројних блокова дигиталних кола и комбинација који врше задати задатак. Ефикасна примена логичких функција у облику логичких кола (тако да се не користи више логичких кола него што је потребно) потребна је како би се минимизирали трошкови производње и / или повећале перформансе уређаја.

Израда дигиталних логичких кола[уреди]

Сви дигитални системи се састоје од две основне функције: меморија елемената за складиштење података, и комбинационих кола која трансформишу ту информацију. Машине које мењају стања, као бројачи, су комбинација меморијских елемената и комбинационих логичких кола. Пошто су меморијски елементи стандардна логичка кола, они су изабрани из ограниченог скупа алтернативних кола, па се пројектовање дигиталних функција своди на пројектовање комбинационих кола капија и њихову интерконекцију.

У пракси инстанцирање логичких кола на високом нивоу апстракције се назива Логичка Синтеза, која се може применити ручно, али обично се примењује неки формални метод рачунара. У овом чланку, методе за пројектовање комбинационих логичких кола су укратко сажете.

Полазна тачка за пројектовање дигиталних логичких кола је њена жељена функционалност, пошто је изведен из анализе система као једне целине, логичко коло постаје део тога. Опис се може исказати у неком алгоритамском облику или преко логичких једначина, али се може сажети и у облику табеле. Пример испод показује део такве табеле за 7-мо сегментни програм који преводи бинарни код за вредности децималних цифара у сигнале који проузрокују да одговарајући сегменти екрана засветле.

  Цифра Код        Сегменти
                   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]

Класични методи минимизације[уреди]

Минимизирање Булових функција ручно, коришћењем Karnoovih mapa је напоран, досадан и склон грешкама процес. Није погодан за рад са више од 6 улазних променљивих, а практичан је само до 4 променљиве.[4] Штавише, овај метод се не може аутоматизовати у облику рачунарског програма. Међутим, пошто модерне логичке функције обично нису ограничене на тако мали број променљивих, док је цена, као и ризик од прављења грешки превисоки за мануелну имплементацију логичких функција, употреба рачунара је постала неопходна.

Први алтернативни метод који је постао популаран је табеларни метод кога су развили Квин и Мекласки. Почевши са таблицом истинитости за скуп логичких функција, комбинујући миничланове чије су функције активне-ОН-поклопац-или за које је вредност функције небитна—the Don't-Care-поклопац или DC-поклопац—скуп простих импликаната је направљен. Коначно, системска процедура почиње да налази најмањи скуп простих импликаната који одговарају излазној функцији.[5][6]

Иако је овај Quine-McCluskey алгоритам веома погодан за имплементацију у компјутерском програму, резултат је још увек далеко од задовољавајућег када причамо о времену обраде и употреби меморије. Додавање променљиве функцији их отприлике удвостручује обоје, зато што дужина таблица истинитости експоненцијално расте са бројем променљивих. Сличан проблем се јавља када се повећа број излазних функција једне комбинационе функције блока. Као резултат Квин-Мекласки метод је практичан само за функције са ограниченим бројем улазних променљивих и излазних функција.

Еспресо алгоритам[уреди]

Потпуно другачији приступ овом проблему је представљен у ESPRESSO алгоритму, кога је развио Брејтон e.a. на Универзитету Калифорније, Беркли.[7] Уместо ширења логичке функције у миничланове, програм манипулише "коцкама", представљајући производ у ON-DC- и OFF-поклопцу итеративно. Иако резултат минимизације није увек загарантован да буде глобални минимум, у пракси је то веома блиско усклађено, а решење никад не садржи логичку сувишност. У поређењу са другим методима, ово је доста ефикасније, смањујући употребу меморије и време извршења за неколико редова величине. Његово име одражава начин прављења инстант свеже кафе. Готово да нема ограничења што се тиче броја променљивих, излазних функција и услова производа комбинационих функција блока. У принципу, на пример десетине променљивих са десетинама излазних функција су лако решени.

Улаз за ESPRESSO је табела функција жељене функционалности, резултат је минимизирана табела, описујући било ON-поклопац или OFF-поклопац функције, у зависности од изабране опције. По дифолту услови производа ће се делити на што више могуће излазних функција, али програму може бити наложено да уради сваку од излазних функција посебно. Ово омогућава ефикасну имплементацију у два нивоа логичких низова као што су PLA (Programmable Logic Array) или PAL (Programmable Array Logic).

ESPRESSO алгоритам се показао толико успешан да је укључен као стандардни корак логичке минимизације у практично било ком алату логичке синтезе. За имплементирање функције у вишебазној логици, резултат минимизације је побољшан факторизацијом и приказан на слободним логичким ћелијама, било да се ово односи на FPGA (Field Programmable Gate Array) или ASIC (Application Specific Integrated Circuit).

Софтвер[уреди]

Минилог[уреди]

Минилог је логички програм за минимизацију који користи овај ESPRESSO алгоритам. У стању је да генерише имплементацију капије са 2 нивоа за комбинациони блок функције са 40 улаза и излаза или за асинхрону машину са више стања са 256 различитих стања. Део је образовног дизајн пакета Publicad , који се може скинути са сајта

  • Publicad - бесплатан Publicad скуп програма који укључује Минилог - логички програм за минимизацију.

Logic Friday[уреди]

Logic Friday је бесплатан Виндоус програм који обезбеђује графички интерфејс ESPRESSO-у, као и misII-у, још једном модулу у Беркли Октулс пакету. Са Logic Friday-ом корисници могу да унесу логичку функцију као таблицу истинитости, једначину, или дијаграм капија, минимизују функцију, и онда виде резултат у друге два програма. Logic Friday можете скинути са http://www.sontrak.com.

Espresso извори[уреди]

Извор оригиналног Espresso програма се може наћи на вебсајту Калифорниа Универзитета, Беркли, на Pubs/Downloads/Espresso. Верзија Espresso-a која је апдејтована за модерне POSIX системе се може наћи на [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“, 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