Инвертовани И-граф

Инвертовани И-граф (енг. And-inverter graph, AIG) је директан ацикличан граф који представља структурну имплементацију логичке функције кола или мреже. АИГ се састоји од два улазна чвора који представљају конјукцију, чворова који се означавају именима променљивих, ивица које потенцијално садрже маркере који означавају логичку негацију. Овај вид репрезентације логичке функције је ретко ефикасан за велика кола, и углавном се користи за управљање булеанским функцијама.

Конверзија између мреже логичких гејтова и АИГ-ова је брза и скалабилна. Једини услов за конверзију је да се сваки гејт изрази преко И-елемената и инвертера. Она не повећава захтеве за ресурсима у виду времена и простора. Ово чини АИГ ефикаснијом репрезентацијом функција у поређењу са БДД-ом (енг. Binary decision diagram) и ДНФ-ом (енг. Disjunctive normal form). Интересовање за АИГ јавља се касних 50-их^[1] и наставља се 70-их година 20. века, кад се користи у оквиру система за верификацију ради убрзаног генерисања формалних доказа исправности.

АИГ недавно почиње поново да се помиње као начин репрезентација функција за разне врсте верификације. Разлог за ово је што су текући начини репрезентације дошли до границе својих скалабилности у многим апликацијама.

АИГ је пронашао сврху и у ЕДА (енг. Electronic design automation) апликацијама. Недавне студије показују да се ефикасне технике компресовања кола могу развити коришћењем АИГ-а^[2]. Због своје једноставне структуре која дозвољава лаке измене, сматра се обећавајућим начином репрезентације функција.

Поред комбинаторних кола, АИГ има своју примену и у секвенцијалним колима. Постоји метода структурног хеширања (технике коју је развио IBM). Она комбинује АИГ са секвенцијалним колима (нпр. Д флип-флопом) у структуру података која се користи за апликације које служе за ритајминг^[3] .

Имплементације

Logic Synthesis and Verification System ABC
AIGER
OpenAccess Gear

Референце

^ Hellerman, L. (јун 1963). „A catalog of three-variable Or-Inverter and And-Inverter logical circuits”. IEEE Trans. Electron. Comput. EC-12 (3): 198—223. doi:10.1109/PGEC.1963.263531.
^ P. Bjesse and A. Boralv. „DAG-aware circuit compression for formal verification”. Proc. ICCAD '04. стр. 42—49.
^ J. Baumgartner and A. Kuehlmann. „Min-area retiming on flexible circuit structures”. Proc. ICCAD'01. стр. 176—182.

[1] Hellerman, L. (јун 1963). „A catalog of three-variable Or-Inverter and And-Inverter logical circuits”. IEEE Trans. Electron. Comput. EC-12 (3): 198—223. doi:10.1109/PGEC.1963.263531.

[2] P. Bjesse and A. Boralv. „DAG-aware circuit compression for formal verification”. Proc. ICCAD '04. стр. 42—49.

[3] J. Baumgartner and A. Kuehlmann. „Min-area retiming on flexible circuit structures”. Proc. ICCAD'01. стр. 176—182.

[1]

[2]

[3]