Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
мНема описа измене
м Поништена измена 8547795 корисника Milicevic01
Ред 1:
{{спајање|Еспресо истраживачки логички умањивач}}
{{РАФ102013}}
'''Еспресо логички умањивачминимизатор''' је компјутерскикомпијутерски програмпрогам који користипомоћу специфичнехеуристичких алгоритмеи какопосебних би сеалогоритама ефикасно смањиласмањује комплексност дигиталних електронских кола капија. <ref>{{Citation |first=J.P. |last=Hayes |title=Digital Logic Design |publisher=Addison Wesley |year=1993 |isbn=0-201-15461-7}}</ref> Еспресо је развиоразвијен у IBM од стране [[Robert Brayton (computer scientist)|РобертRobert БрејтонBrayton]] у IBM-у. Rudell је касније1996 објавио верзијуваријанту 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.-06-05 |journal=Memorandum No. UCB/ERL M86-65 |location=Berkeley}}</ref> Еспресо је инспирисаоутицао на развој многемногих изводепроизвода.
 
 
== Увод ==
Електронски уређаји се састоје од бројних блокова дигиталних кола и комбинација који врше задати задатак. Ефикасна примена логичких функција у облику [[Логичка капија|логичких кола]] (тако да се не користи више логичких кола него што је потребно) потребна је како би се минимизирали трошкови производње и / или повећале перформансе уређаја.▼
 
=== Израда дигиталних логичких кола ===▼
Сви дигитални системи се састоје од две основне функције: меморија елемената за складиштење података, и [[Логичка капија|комбинационих кола]] која трансформишу ту информацију. Машине које мењају стања, као бројачи, су комбинација меморијских елемената и комбинационих [[Логичка капија|логичких кола]]. Пошто су меморијски елементи стандардна логичка кола, они су изабрани из ограниченог скупа алтернативних кола, па се пројектовање дигиталних функција своди на пројектовање комбинационих кола капија и њихову интерконекцију.▼
 
▲Електронски уређаји се састоје од бројних блокова дигиталних кола, ичијом комбинацијакомбинациојом који вршесе задатиизвршава задатак. Ефикасна примена логичких функција у облику кола [[Логичка капија|логичких колакапија]] (тако да се не користи више логичких кола него што је потребно) потребна је како би се минимизиралиомогућава трошковисмањење производњепотрошње и / или повећалеповећава перформансеучинак уређаја.
У пракси инстанцирање логичких кола на високом нивоу апстракције се назива [[Логичка Синтеза]], која се може применити ручно, али обично се примењује неки формални метод рачунара. У овом чланку, методе за пројектовање комбинационих логичких кола су укратко сажете.▼
 
 
Полазна тачка за пројектовање дигиталних логичких кола је њена жељена функционалност, пошто је изведен из анализе система као једне целине, логичко коло постаје део тога. Опис се може исказати у неком алгоритамском облику или преко логичких једначина, али се може сажети и у облику табеле. Пример испод показује део такве табеле за 7-мо сегментни програм који преводи бинарни код за вредности децималних цифара у сигнале који проузрокују да одговарајући сегменти екрана засветле.▼
▲=== ИзрадаДизајн дигиталних логичких кола ===
 
 
▲Сви дигитални системи се састојесастоји од две основне функције: меморија елемената за складиштење података, и [[ЛогичкаКомбинациона капијалогика|комбинационих кола]] која трансформишу ту информацију. МашинеСтатичне које мењају стањамашине, као и бројачи, су комбинација меморијских елемената и комбинационих [[ЛогичкаКомбинациона капијалогика|комбинационих логичких кола]]. Пошто су меморијски елементи стандардна логичка кола, они су изабрани из ограниченог скупа алтернативних кола,; па се пројектовање дигиталних функција своди на пројектовање комбинационих кола капија и њиховуњихово интерконекцијуповезивање.
 
▲УГенерално праксипробнa инстанцирање логичкихлогичка кола на високом нивоу апстракције се називаназивају [[Логичкалогичком Синтеза]],синтезом која се може применитирадити ручно, али обичночешће се примењујена неки формални методначин који се примењује преко рачунара. У овом чланку, су методе за пројектовање комбинационих логичких кола су укратко сажете.
 
▲Полазна тачка зау пројектовањедизајнирању дигиталних логичких кола је њенањегова жељена функционалностФункционалност, пошто је изведен из анализе система као једне целине, логичко коло постајеје деоњегов тогадео. ОписМоже се може исказатиописати у неком алгоритамском облику или преко логичкихлогичким једначинаједначинама, али се може сажетисе такође изаписати у облику табеле. Пример испод показује део такве табеле за 7-мо сегментни управљачки програм који преводи бинарни код за вредности децималних цифара у сигнале који проузрокујуосветљавају даодговарајуће одговарајући сегментисегменте екрана засветле.
 
<pre>
ЦифраDigit Код Code Сегменти Segments
A B C D E F G
0 0000 1 1 1 1 1 1 0 -A-
Линија 27 ⟶ 33:
</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>
 
Даље, умањени резултат може се поделити на мање делове процедуром разлагања и који се на крају може видети у слободним логичким ћелијама. Ова операција се обично назива [[Логичка оптимизација|Логичка Оптимизација]].<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> Штавише, овај метод се не може аутоматизовати у облику рачунарског програма. Међутим, пошто модерне логичке функције обично нису ограничене на тако мали број променљивих, док је цена, као и ризик од прављења грешки превисоки за мануелну имплементацију логичких функција, употреба рачунара је постала неопходна.▼
 
▲Минимизирање Булових функција ручно, коришћењемпреко класичних [[Карноова карта|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. Почевши саод таблицомтаблица истинитости за скуп логичких функција, комбинујући миничлановеминималне чијевредности за које су функције активне-ОНактивиране -ON поклопац- ,или вредности за које је вредност функцијефункција небитна—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&ndash;McCluskey алгоритам]] веома погодан за имплементацију у компјутерском програму, резултат је још увек далеко од задовољавајућег када причамо о времену обраде и употреби меморије. Додавање променљиве функцији их отприлике удвостручује обоје, зато што дужина таблица истинитости експоненцијално расте са бројем променљивих. Сличан проблем се јавља када се повећа број излазних функција једне комбинационе функције блока. Као резултат Квин&ndash;Мекласки метод је практичан само за функције са ограниченим бројем улазних променљивих и излазних функција.▼
 
▲Иако је овај [[Quine&ndash;McCluskeyКвајн–Макласкијев алгоритам]] веома погодан зада се имплементацијуреализује у компјутерском програму, резултат је још увек далеко од задовољавајућегефикасаног када причамоу осмислу временувремена обраде и употребикоришћења меморије. Додавање променљивепроменљивих у функцији ихће отприлике удвостручујеудвостручити обоје, зато што дужина таблицатаблице истинитости експоненцијално расте са бројем променљивих. Сличан проблем се јавља када се повећа број излазних функција једнекомбинационог комбинационе функцијефункционалног блока. КаоСходно резултаттоме Квин&ndash;МекласкиКвајн–Макласкијев методалгоритам је практичан метод само за функције са ограниченим бројем улазних променљивих и излазних функција.
== Еспресо алгоритам ==▼
Потпуно другачији приступ овом проблему је представљен у 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 алгоритму,алгоритам когакоји је развио БрејтонBrayton 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- иand OFF-поклопцупоклопац итеративно. Иако резултат минимизације није увек загарантован да будегарантовано глобални минимум, у пракси је то је веома блиско усклађеноусаглашено, а решење никадје неувек садржибез логичкулогичког сувишноствишка. У поређењуодносу сана другимдруге методимаметоде, овоова је достазанчајно ефикаснијеефикаснија, смањујућијер употребусмањује коришћење меморије и време извршењаобраде задо неколико редова величине. ЊеговоИме имеЕспресо одражаваи начинпотиче прављењаиз инстантсличности свежеса брзим начином прављења кафе. Готово да нема ограничења што се тичеза бројаброј променљивих, излазних функција и производа на основу услова производа комбинационих функција блока. У принципу, на пример десетине променљивихваријабли са десетинама излазних функција су лако решенирешиви.
 
▲УлазУлазне вредности за ESPRESSOеспресо јесе табелазаписују у табели функција жељенеда функционалности,би добили жељену функционалност; резултатРезултат је минимизиранаминимизиран табела, описујућикоја описује било ON-поклопацcover или OFF-поклопацcover функције, у зависности од изабранеизабраних опцијеопција. ПоПодразумевано дифолту условитермини производа ће се делити на што више могућеод стране неколико излазних функција, али програму може бити наложено да урадирукује свакусваком од излазних функција посебно. Ово омогућава ефикаснуефикасно имплементацијуспровођење у два нивоа логичких низова, као што су [[ProgrammableПрограмабилно Logicлогичко Arrayпоље|PLA ПЛА]] (ProgrammableПрограмабилно Logicлогичко Arrayпоље) или [[ProgrammableПрограмабилна Arrayлогика Logicпоља|PAL ПАЛ]] (ProgrammableПрограмабилна Arrayлогика Logicпоља).
 
ЕСПРЕСО алгоритам показао се толико успешан да је регистрован као стандардни корак минимизације логичких функција у свим савременим алатима за логичку синтезу. За спровођење функције у више нивоа логике, резултат минимизације је оптимизовано разлагање и мапирање на расположивим основним логичким ћелијама у циљној технологији, било да се то тиче[[ FPGA|FPGA (engl.Field Programmable Gate Array)]] FPGA или ASIC(Апликационо специфично интегрисано коло).
 
 
=== Софтвер ===
==== МинилогMinilog ====
 
''' Минилог ''' је логички програм за минимизацију који користи овај ESPRESSO алгоритам. У стању је да генерише имплементацију капије са 2 нивоа за комбинациони блок функције са 40 улаза и излаза или за асинхрону машину са више стања са 256 различитих стања. Део је образовног дизајн пакета ''' Publicad ''', који се може скинути са сајта
'' 'Минилог''' је програма за логичку минимизације који користи ЕСПРЕСО алгоритам. Она је у стању да генерише капије са два нивоа имплементације за комбинационе функције блока са до 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.▼
 
▲''' Logic Friday ''' је бесплатанВиндовсов(Windows) Виндоусбесплатни програм који обезбеђујеомогућава графички интерфејс 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Еспресо извори ====
Верзија Espresso-a која је апдејтована за модерне POSIX системе се може наћи на [ftp://ftp.cs.man.ac.uk/pub/amulet/balsa/other-software/espresso-ab-1.0.tar.gz]▼
▲Извор оригиналног 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}}
 
▲== Референце ==
{{Reflist}}
 
{{DEFAULTSORT:Espresso Heuristic Logic Minimizer}}
[[Категорија:Електронска оптимизација]]
Преузето из „https://sr.wikipedia.org/wiki/Еспресо_истраживачки_логички_умањивач”