Логичка оптимизација

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

Логичка оптимизација, део логичке синтезе, је процес налажења еквивалентне репрезентације одређених тј, задатих логичких кола под једним или више задатих услова. Генерално, коло је условњено самом, минимално задатом, величином чипа као и унапред прецизираним кашњењем.

Увод[уреди]

Са појавом логичке синтезе, један од највећих изазова пред EDA индистријом је била да пронађе најбољу netlist репрезентацију датог описа дизајна. Netlist представња стандард за описивање повезаности у електронском дизајну. EDA поставља стандарде у индустрији аутомизације електронског дизајна.

Док је логичка оптимизација другог степена постојала као форма Квајн–Макласкијевог алгоритма, у даљем развоју добијено је Еспресо истраживачки логички умањивач, убрзан напредак на густини чипа, и широко прихватање хардверског описног језика (HDL) за опис кола, сто је довело до формализовања домена логичке оптимизације какав постоји данас.

Логичка оптимизација је данас подељена у разне категорије базиране на ова два критеријума:

Базирана на репрезентацији кола

  • Логичку оптимизацију другог степена
  • Логичку репрезентацију вишег нивоа

Базирана на карактеристикама чипа

  • Низовна логичка репрезентација
  • Комбинована логичка оптимизација

Док чиповна репрезентација другог нивоа стриктно користи упрошћен поглед на чипове у смислу SOP што је много примењеније на PLA имплементацију дизајна, при чему је

  • PLA - Програмибилни логички низ
  • SOP - збир продукта, канонска форма у боолеан алгебри
  • POS - продукт сума у боолеан алгебри

Репрезентација вишег нивоа је више генерички поглед на чип у смислу арбитрарно побезаних SOP, POS, фактор форма идр. Алгоритми у логичкој оптимизацији генерално раде или на структуралним (SOP, фактор форма) или функционалним (BDD, ADD) репрезентацијама чипа.

Упоређивање репрезентација другог и виших нивоа[уреди]

Ако имамо две функције F1 и F2:

F_1 = AB + AC + AD,\,
F_2 = A'B + A'C + A'E.\,

Горе наведеној репрезентацији другог нивоа је потребно шест израза и 24 танзистора у CMOS репрезентацији.

Функционална репрезентација вишег нивоа би била:

P = B + C.
F1 = AP + AD.
F2 = A'P + A'E.

Док је број нивоа овде 3, укупан број израза и литерала се смањује због дељења израза B + C.

Слично томе можемо разликовати између секвенциалних и комбинованих кола, чије понашање се може описати у облику таблица стања.

Види још[уреди]

Литература[уреди]

  • Synthesis and Optimization of Digital Circuits, by Giovanni De Micheli, ISBN 0-07-016333-2.