Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Autobot (разговор | доприноси)
1.572.075 измена
м Робот: обликовање ISBN-а
Autobot (разговор | доприноси)
1.572.075 измена
м Робот: обликовање ISBN-а
Ред 1:
{{спајање|Еспресо истраживачки логички умањивач}}
{{РАФ102013}}
'''Еспресо логички минимизаторумањивач''' је компијутерскикомпјутерски прогампрограм који помоћукористи хеуристичкихспецифичне иалгоритме посебнихкако алогоритамаби се ефикасно смањујесмањила комплексност дигиталних електронских кола капија. <ref>{{Citation |first=J.P. |last=Hayes |title=Digital Logic Design |publisher=Addison Wesley |year=1993 |id=ISBN 978-0-201-15461-0}}</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. |journal=Memorandum No. UCB/ERL M86-65 |location=Berkeley}}</ref> Еспресо је утицао на развојинспирисао многихмноге производаизводе.
 
 
== Увод ==
Електронски уређаји се састоје од бројних блокова дигиталних кола, чијоми комбинациојомкомбинација секоји врше извршавазадати задатак. Ефикасна примена логичких функција у облику кола [[Логичка капија|логичких капијакола]] (тако да се не користи више логичких кола него што је потребно) омогућавапотребна је како би се минимизирали смањењетрошкови потрошњепроизводње и / или повећаваповећале учинакперформансе уређаја.▼
 
=== ДизајнИзрада дигиталних логичких кола ===▼
Сви дигитални системи се састојисастоје од две основне функције: меморија елемената за складиштење података, и [[КомбинационаЛогичка логикакапија|комбинационих кола]] која трансформишу ту информацију. СтатичнеМашине машинекоје мењају стања, као и бројачи, су комбинација меморијских елемената и комбинационих [[КомбинационаЛогичка логикакапија|комбинационих логичких кола]]. Пошто су меморијски елементи стандардна логичка кола, они су изабрани из ограниченог скупа алтернативних кола;, па се пројектовање дигиталних функција своди на пројектовање комбинационих кола капија и њиховоњихову повезивањеинтерконекцију.▼
 
ГенералноУ пробнапракси логичкаинстанцирање логичких кола на високом нивоу апстракције се називајуназива логичком[[Логичка синтезомСинтеза]], која се може радитиприменити ручно, али чешћеобично насе примењује неки формални начин који се примењује прекометод рачунара. У овом чланку су, методе за пројектовање комбинационих логичких кола су укратко сажете.▼
▲Електронски уређаји се састоје од бројних блокова дигиталних кола, чијом комбинациојом се извршава задатак. Ефикасна примена логичких функција у облику кола [[Логичка капија|логичких капија]] (тако да се не користи више логичких кола него што је потребно) омогућава смањење потрошње и / или повећава учинак уређаја.
 
Полазна тачка уза дизајнирањупројектовање дигиталних логичких кола је његовањена жељена Функционалностфункционалност, пошто је изведен из анализе система као једне целине, логичко коло је његовпостаје део тога. МожеОпис се описатиможе исказати у неком алгоритамском облику или логичкимпреко логичких једначинамаједначина, али може се такођеможе сажети записатии у облику табеле. Пример испод показује део такве табеле за 7-мо сегментни управљачки програм који преводи бинарни код за вредности децималних цифара у сигнале који осветљавајупроузрокују одговарајућеда сегментеодговарајући сегменти екрана засветле.▼
 
▲=== Дизајн дигиталних логичких кола ===
 
 
▲Сви дигитални системи се састоји од две основне функције: меморија елемената за складиштење података, и [[Комбинациона логика|комбинационих кола]] која трансформишу ту информацију. Статичне машине, као и бројачи, су комбинација меморијских елемената и [[Комбинациона логика|комбинационих логичких кола]]. Пошто су меморијски елементи стандардна логичка кола они су изабрани из ограниченог скупа алтернативних кола; па се пројектовање дигиталних функција своди на пројектовање комбинационих кола капија и њихово повезивање.
 
▲Генерално пробна логичка кола на високом нивоу апстракције се називају логичком синтезом која се може радити ручно, али чешће на неки формални начин који се примењује преко рачунара. У овом чланку су методе за пројектовање комбинационих логичких кола укратко сажете.
 
▲Полазна тачка у дизајнирању дигиталних логичких кола је његова жељена Функционалност, пошто је изведен из анализе система као целине, логичко коло је његов део. Може се описати у алгоритамском облику или логичким једначинама, али може се такође записати у облику табеле. Пример испод показује део такве табеле за 7-сегментни управљачки програм који преводи бинарни код за вредности децималних цифара у сигнале који осветљавају одговарајуће сегменте екрана.
 
<pre>
DigitЦифра Код Code SegmentsСегменти
A B C D E F G
0 0000 1 1 1 1 1 1 0 -A-
Линија 34 ⟶ 27:
</pre>
 
Процес имплементације почиње са фазом '' 'логичке минимизације''', штокоја ће бити објашњеноописана удаље даљему тексту, у циљу поједностављења табеле функција табеле комбиновањем посебниходвојених условаизраза какоу бионе одвеће већихкоји садржаја направили садржај сасадрже мање променљивих. Даље се минимизирани резултат може поделити на мање делове процедуром разлагања и касније се мапира на основне логичке ћелије намењене технологије. Ова операција се обично назива [[логичка оптимизација]].<ref>{{Citation |first=Giovanni |last=De Micheli |title=Synthesis and Optimization of Digital Circuits |publisher=McGraw-Hill Science Engineering |year=1994 |id=ISBN 978-0-07-016333-1}}</ref>
 
Даље, умањени резултат може се поделити на мање делове процедуром разлагања и који се на крају може видети у слободним логичким ћелијама. Ова операција се обично назива [[Логичка оптимизација|Логичка Оптимизација]].<ref>{{Citation |first=Giovanni |last=De Micheli |title=Synthesis and Optimization of Digital Circuits |publisher=McGraw-Hill Science Engineering |year=1994 |id=ISBN 978-0-07-016333-1}}</ref>
 
=== КласичнеКласични методеметоди минимизације ===▼
 
Минимизирање Булових функција ручно, преко класичнихкоришћењем [[Карноова карта|карнеовихKarnoovih мапаmapa]] је напоран, досадан и процес склон грешкама процес. Није погодан за рад са више од 6 улазних променљивих, иа практичан је само до 4 променљиве, док је дељење за више излазних функција још теже да спроведе.<ref>{{Citation |first=Douglas |last=Lewin |title=Design of Logic Systems |publisher=Van Nostrand (UK) |year=1985 |id=ISBN 978-0-442-30606-9}}</ref> Штавише, овај метод нијесе лакне даможе се аутоматизујеаутоматизовати у видуоблику компјутерскограчунарског програма. Међутим, сапошто модерниммодерне логичкимлогичке функцијамафункције нисмообично ограниченинису ограничене на тако мали број променљивих, док је цена, као и ризик од прављења грешкегрешки превисоки за ручномануелну имплементацију логичких функција превелика, збогупотреба тогарачунара је употреба рачунара постала неопходна. ▼
▲=== Класичне методе минимизације ===
 
▲Минимизирање Булових функција ручно преко класичних [[Карноова карта|карнеових мапа]] је напоран, досадан и процес склон грешкама. Није погодан за више од 6 улазних променљивих и практичан је до 4 променљиве, док је дељење за више излазних функција још теже да спроведе.<ref>{{Citation |first=Douglas |last=Lewin |title=Design of Logic Systems |publisher=Van Nostrand (UK) |year=1985 |id=ISBN 978-0-442-30606-9}}</ref>Штавише, овај метод није лак да се аутоматизује у виду компјутерског програма. Међутим, са модерним логичким функцијама нисмо ограничени на тако мали број променљивих, док је цена и ризик прављења грешке за ручно имплементацију логичких функција превелика, због тога је употреба рачунара постала неопходна.
 
Први алтернативни метод који је постао популаран је табеларни метод који су развили Quine и McCluskey. Почевши од таблица истинитости за скуп логичких функција, комбинујући минималне вредности за које су функције активиране -ON поклопац , или вредности за које је вредност функција небитна -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 |id=ISBN 978-0-8053-2703-8}}</ref><ref>{{Citation |first=Parag K. |last=Lala |title=Practical Digital Logic Design and Testing |publisher=Prentice Hall |year=1996 |id=ISBN 978-0-02-367171-5}}</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 |id=ISBN 978-0-8053-2703-8}}</ref><ref>{{Citation |first=Parag K. |last=Lala |title=Practical Digital Logic Design and Testing |publisher=Prentice Hall |year=1996 |id=ISBN 978-0-02-367171-5}}</ref>
 
▲Иако је овај [[Квајн–МакласкијевQuine-McCluskey алгоритам]] веома погодан да сеза реализујеимплементацију у компјутерском програму, резултат је још увек далеко од ефикасаногзадовољавајућег укада причамо смислуо временавремену обраде и коришћењаупотреби меморије. Додавање променљивих упроменљиве функцији ћеих отприлике удвостручитиудвостручује обоје, зато што дужина таблицетаблица истинитости експоненцијално расте са бројем променљивих. Сличан проблем се јавља када се повећа број излазних функција комбинационогједне функционалногкомбинационе функције блока. СходноКао томерезултат Квајн–МакласкијевКвин-Мекласки алгоритамметод је практичан метод само за функције са ограниченим бројем улазних променљивих и излазних функција.
 
== Еспресо алгоритам ==
РадикалноПотпуно другачији приступ овом питањупроблему је ЕСПРЕСОпредстављен алгоритаму 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 |id=ISBN 978-0-89838-164-1}}</ref> Уместо проширивањаширења логичке функицјефункције преко минималниху вредностиминичланове, програм ради саманипулише "коцкама ", које представљајупредстављајући производ услова у ON-, DC- andи OFF-поклопацпоклопцу итеративно. Иако резултат минимизације није гарантованоувек загарантован да буде глобални минимум, у пракси то је то веома блиско усаглашеноусклађено, а решење јеникад увекне безсадржи логичкоглогичку вишкасувишност. У односупоређењу наса другедругим методеметодима, оваово је занчајнодоста ефикаснијаефикасније, јерсмањујући смањује коришћењеупотребу меморије и време обрадеизвршења доза неколико редова величине. ИмеЊегово Еспресоиме иодражава потиченачин изправљења сличностиинстант са брзим начином прављењасвеже кафе. Готово да нема ограничења зашто се тиче бројброја променљивих, излазних функција и производа на основу услова производа комбинационих функција блока. У принципу, на пример десетине варијаблипроменљивих са десетинама излазних функција су лако решивирешени.▼
 
Улазне вредностиУлаз за еспресоESPRESSO сеје записују у табелитабела функција дажељене бифункционалности, добили жељену функционалност; Резултатрезултат је минимизиранминимизирана табела, која описујеописујући било ON-coverпоклопац или OFF-coverпоклопац функције, у зависности од изабранихизабране опцијаопције. ПодразумеваноПо терминидифолту услови производа ће се делити на што више од стране неколикомогуће излазних функција, али програму може бити наложено да рукујеуради свакомсваку од излазних функција посебно. Ово омогућава ефикасноефикасну спровођењеимплементацију у два нивоа логичких низова, као што су [[ПрограмабилноProgrammable логичкоLogic пољеArray|ПЛАPLA]] (ПрограмабилноProgrammable логичкоLogic пољеArray) или [[ПрограмабилнаProgrammable логикаArray пољаLogic|ПАЛPAL]] (ПрограмабилнаProgrammable логикаArray пољаLogic).▼
▲Радикално другачији приступ овом питању је ЕСПРЕСО алгоритам који је развио 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 |id=ISBN 978-0-89838-164-1}}</ref> Уместо проширивања логичке функицје преко минималних вредности, програм ради са "коцкама ", које представљају производ услова у ON-, DC- and OFF-поклопац итеративно. Иако резултат минимизације није гарантовано глобални минимум, у пракси то је веома блиско усаглашено, а решење је увек без логичког вишка. У односу на друге методе, ова је занчајно ефикаснија, јер смањује коришћење меморије и време обраде до неколико редова величине. Име Еспресо и потиче из сличности са брзим начином прављења кафе. Готово да нема ограничења за број променљивих, излазних функција и производа на основу услова комбинационих функција блока. У принципу, десетине варијабли са десетинама излазних функција су лако решиви.
 
▲Улазне вредности за еспресо се записују у табели функција да би добили жељену функционалност; Резултат је минимизиран табела, која описује било ON-cover или OFF-cover функције, у зависности од изабраних опција. Подразумевано термини производа ће се делити што више од стране неколико излазних функција, али програму може бити наложено да рукује сваком од излазних функција посебно. Ово омогућава ефикасно спровођење у два нивоа логичких низова, као што су [[Програмабилно логичко поље|ПЛА]] (Програмабилно логичко поље) или [[Програмабилна логика поља|ПАЛ]] (Програмабилна логика поља).
 
ЕСПРЕСО алгоритам показао се толико успешан да је регистрован као стандардни корак минимизације логичких функција у свим савременим алатима за логичку синтезу. За спровођење функције у више нивоа логике, резултат минимизације је оптимизовано разлагање и мапирање на расположивим основним логичким ћелијама у циљној технологији, било да се то тиче[[FPGA|FPGA (engl.Field Programmable Gate Array)]] FPGA или ASIC(Апликационо специфично интегрисано коло).
 
ESPRESSO алгоритам се показао толико успешан да је укључен као стандардни корак логичке минимизације у практично било ком алату логичке синтезе. За имплементирање функције у вишебазној логици, резултат минимизације је побољшан факторизацијом и приказан на слободним логичким ћелијама, било да се ово односи на [[Field-programmable gate array|FPGA (Field Programmable Gate Array)]] или [[Application-specific integrated circuit|ASIC (Application Specific Integrated Circuit)]].
 
=== Софтвер ===
==== 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 ''' је Виндовсов(Windows)бесплатан бесплатниВиндоус програм који омогућаваобезбеђује графички интерфејс за ЕСПРЕСОESPRESSO-у, такођекао и за misII-у, другијош методједном развијенмодулу у Беркли пакетуОктулс са алатимапакету. Са Logic Friday-ом корисници могу унетида унесу логичку функцију као таблицу истинитости, једначину, дијаграм или капијудијаграм капија, минимизирајуминимизују функцију, аи затимонда видетевиде резултат у обадруге обликадва програма. Logic Friday јеможете доступанскинути наса http://www.sontrak.com.▼
 
==== ЕспресоEspresso извори ====▼
▲''' Logic Friday ''' је Виндовсов(Windows) бесплатни програм који омогућава графички интерфејс за ЕСПРЕСО, такође и за misII, други метод развијен у Беркли пакету са алатима. Са Logic Friday корисници могу унети логичку функцију као таблицу истинитости, једначину, дијаграм или капију, минимизирају функцију, а затим видете резултат у оба облика. Logic Friday је доступан на http://www.sontrak.com.
Извор оригиналног Еспресо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}}
▲Извор оригиналног Еспресо програма је доступан на сајту Универзитета у Калифорнији, Беркли [http://embedded.eecs.berkeley.edu/pubs/downloads/espresso/index.htm Pubs/Downloads/Espresso].
▲Верзија Еспресо која је ажурирана на савременим POSIX системима је доступан на [ftp://ftp.cs.man.ac.uk/pub/amulet/balsa/other-software/espresso-ab-1.0.tar.gz]
 
 
{{DEFAULTSORT:Espresso Heuristic Logic Minimizer}}
 
▲== Референце ==
{{Reflist}}
 
[[Категорија:Електронска оптимизација]]
Преузето из „https://sr.wikipedia.org/wiki/Еспресо_истраживачки_логички_умањивач”