Еспресо истраживачки логички умањивач — разлика између измена
Садржај обрисан Садржај додат
м Преусмерење на Еспресо истраживачки логички умањивач |
мНема описа измене |
||
Ред 1:
'''Еспресо логички умањивач''' је компјутерски програм који користи специфичне алгоритме како би се ефикасно смањила комплексност дигиталних електронских кола капија. <ref>{{Citation |first=J.P. |last=Hayes |title=Digital Logic Design |publisher=Addison Wesley |year=1993 |isbn=0-201-15461-7}}</ref> Еспресо је развио [[Robert Brayton (computer scientist)|Роберт Брејтон]] у IBM-у. Rudell је касније објавио верзију Espresso-MV 1986. године која је названа "-{Multiple-Valued Logic Minimization for PLA Synthesis}-".<ref>{{Citation |url=http://www.eecs.berkeley.edu/Pubs/TechRpts/1986/ERL-86-65.pdf |title=Multiple-Valued Logic Minimization for PLA Synthesis |first=Richard L. |last=Rudell |date = 5. 6. 1986. |journal=Memorandum No. UCB/ERL M86-65 |location=Berkeley}}</ref> Еспресо је инспирисао многе изводе.
== Увод ==
Електронски уређаји се састоје од бројних блокова дигиталних кола и комбинација који врше задати задатак. Ефикасна примена логичких функција у облику [[Логичка капија|логичких кола]] (тако да се не користи више логичких кола него што је потребно) потребна је како би се минимизирали трошкови производње и / или повећале перформансе уређаја.
=== Израда дигиталних логичких кола ===
Сви дигитални системи се састоје од две основне функције: меморија елемената за складиштење података, и [[Логичка капија|комбинационих кола]] која трансформишу ту информацију. Машине које мењају стања, као бројачи, су комбинација меморијских елемената и комбинационих [[Логичка капија|логичких кола]]. Пошто су меморијски елементи стандардна логичка кола, они су изабрани из ограниченог скупа алтернативних кола, па се пројектовање дигиталних функција своди на пројектовање комбинационих кола капија и њихову интерконекцију.
У пракси инстанцирање логичких кола на високом нивоу апстракције се назива [[Логичка Синтеза]], која се може применити ручно, али обично се примењује неки формални метод рачунара. У овом чланку, методе за пројектовање комбинационих логичких кола су укратко сажете.
Полазна тачка за пројектовање дигиталних логичких кола је њена жељена функционалност, пошто је изведен из анализе система као једне целине, логичко коло постаје део тога. Опис се може исказати у неком алгоритамском облику или преко логичких једначина, али се може сажети и у облику табеле. Пример испод показује део такве табеле за 7-мо сегментни програм који преводи бинарни код за вредности децималних цифара у сигнале који проузрокују да одговарајући сегменти екрана засветле.
<pre>
Цифра Код Сегменти
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
</pre>
Процес имплементације почиње са фазом '''логичке минимизације''', која ће бити описана даље у тексту, у циљу поједностављења функција табеле комбиновањем одвојених израза у оне веће који садрже мање променљивих.
Даље, умањени резултат може се поделити на мање делове процедуром разлагања и који се на крају може видети у слободним логичким ћелијама. Ова операција се обично назива [[Логичка оптимизација|Логичка Оптимизација]].<ref>{{Citation |first=Giovanni |last=De Micheli |title=Synthesis and Optimization of Digital Circuits |publisher=McGraw-Hill Science Engineering |year=1994 |isbn=0-07-016333-2}}</ref>
=== Класични методи минимизације ===
Минимизирање Булових функција ручно, коришћењем [[Карноова карта|Karnoovih mapa]] је напоран, досадан и склон грешкама процес. Није погодан за рад са више од 6 улазних променљивих, а практичан је само до 4 променљиве.<ref>{{Citation |first=Douglas |last=Lewin |title=Design of Logic Systems |publisher=Van Nostrand (UK) |year=1985 |isbn=0-442-30606-7}}</ref> Штавише, овај метод се не може аутоматизовати у облику рачунарског програма. Међутим, пошто модерне логичке функције обично нису ограничене на тако мали број променљивих, док је цена, као и ризик од прављења грешки превисоки за мануелну имплементацију логичких функција, употреба рачунара је постала неопходна.
Први алтернативни метод који је постао популаран је табеларни метод кога су развили Квин и Мекласки. Почевши са таблицом истинитости за скуп логичких функција, комбинујући миничланове чије су функције активне-ОН-поклопац-или за које је вредност функције небитна—the Don't-Care-поклопац или DC-поклопац—скуп [[Импликант|простих импликаната]] је направљен. Коначно, системска процедура почиње да налази најмањи скуп простих импликаната који одговарају излазној функцији.<ref>{{Citation |first1=Randy H. |last1=Katz |first2=Gaetano |last2=Borriello |title=Contemporary Logic Design |publisher=The Benjamin/Cummings Publishing Company |year=1994 |isbn=0-8053-2703-7}}</ref><ref>{{Citation |first=Parag K. |last=Lala |title=Practical Digital Logic Design and Testing |publisher=Prentice Hall |year=1996 |isbn=0-02-367171-8}}</ref>
Иако је овај [[Quine–McCluskey алгоритам]] веома погодан за имплементацију у компјутерском програму, резултат је још увек далеко од задовољавајућег када причамо о времену обраде и употреби меморије. Додавање променљиве функцији их отприлике удвостручује обоје, зато што дужина таблица истинитости експоненцијално расте са бројем променљивих. Сличан проблем се јавља када се повећа број излазних функција једне комбинационе функције блока. Као резултат Квин–Мекласки метод је практичан само за функције са ограниченим бројем улазних променљивих и излазних функција.
== Еспресо алгоритам ==
Потпуно другачији приступ овом проблему је представљен у ESPRESSO алгоритму, кога је развио Брејтон e.a. на Универзитету Калифорније, Беркли.<ref>{{Citation |first1=Robert King |last1=Brayton |first2=Gary D. |last2=Hachtel |first3=Curtis T. |last3=McMullen |first4=Alberto L.. |last4=Sangiovanni-Vincentelli |url=http://portal.acm.org/citation.cfm?id=577427 |title=Logic Minimization Algorithms for VLSI Synthesis |publisher=Kluwer Academic Publishers |year=1984 |isbn=0-89838-164-9}}</ref> Уместо ширења логичке функције у миничланове, програм манипулише "коцкама", представљајући производ у ON-DC- и OFF-поклопцу итеративно. Иако резултат минимизације није увек загарантован да буде глобални минимум, у пракси је то веома блиско усклађено, а решење никад не садржи логичку сувишност. У поређењу са другим методима, ово је доста ефикасније, смањујући употребу меморије и време извршења за неколико редова величине. Његово име одражава начин прављења инстант свеже кафе. Готово да нема ограничења што се тиче броја променљивих, излазних функција и услова производа комбинационих функција блока. У принципу, на пример десетине променљивих са десетинама излазних функција су лако решени.
Улаз за ESPRESSO је табела функција жељене функционалности, резултат је минимизирана табела, описујући било ON-поклопац или OFF-поклопац функције, у зависности од изабране опције. По дифолту услови производа ће се делити на што више могуће излазних функција, али програму може бити наложено да уради сваку од излазних функција посебно. Ово омогућава ефикасну имплементацију у два нивоа логичких низова као што су [[Programmable Logic Array|PLA]] (Programmable Logic Array) или [[Programmable Array Logic|PAL]] (Programmable Array Logic).
ESPRESSO алгоритам се показао толико успешан да је укључен као стандардни корак логичке минимизације у практично било ком алату логичке синтезе. За имплементирање функције у вишебазној логици, резултат минимизације је побољшан факторизацијом и приказан на слободним логичким ћелијама, било да се ово односи на [[Field-programmable gate array|FPGA (Field Programmable Gate Array)]] или [[Application-specific integrated circuit|ASIC (Application Specific Integrated Circuit)]].
=== Софтвер ===
==== Минилог ====
''' Минилог ''' је логички програм за минимизацију који користи овај ESPRESSO алгоритам. У стању је да генерише имплементацију капије са 2 нивоа за комбинациони блок функције са 40 улаза и излаза или за асинхрону машину са више стања са 256 различитих стања. Део је образовног дизајн пакета ''' Publicad ''', који се може скинути са сајта
[http://cid-b7034765ca89b294.skydrive.live.com/browse.aspx/Quick-Install Publicad] - бесплатан Publicad скуп програма који укључује Минилог - логички програм за минимизацију.
==== Logic Friday ====
''' Logic Friday ''' је бесплатан Виндоус програм који обезбеђује графички интерфејс ESPRESSO-у, као и misII-у, још једном модулу у Беркли Октулс пакету. Са Logic Friday-ом корисници могу да унесу логичку функцију као таблицу истинитости, једначину, или дијаграм капија, минимизују функцију, и онда виде резултат у друге два програма. Logic Friday можете скинути са http://www.sontrak.com.
==== Espresso извори ====
Извор оригиналног Espresso програма се може наћи на вебсајту Калифорниа Универзитета, Беркли, на [http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/index.htm Pubs/Downloads/Espresso].
Верзија Espresso-a која је апдејтована за модерне POSIX системе се може наћи на [ftp://ftp.cs.man.ac.uk/pub/amulet/balsa/other-software/espresso-ab-1.0.tar.gz]
== Референце ==
{{reflist}}
== Литература ==
{{DEFAULTSORT:Espresso Heuristic Logic Minimizer}}
[[Категорија:Електронска оптимизација]]
| |||