Invertovani I-graf

Invertovani I-graf (eng. And-inverter graph, AIG) je direktan acikličan graf koji predstavlja strukturnu implementaciju logičke funkcije kola ili mreže. AIG se sastoji od dva ulazna čvora koji predstavljaju konjukciju, čvorova koji se označavaju imenima promenljivih, ivica koje potencijalno sadrže markere koji označavaju logičku negaciju. Ovaj vid reprezentacije logičke funkcije je retko efikasan za velika kola, i uglavnom se koristi za upravljanje buleanskim funkcijama.

Konverzija između mreže logičkih gejtova i AIG-ova je brza i skalabilna. Jedini uslov za konverziju je da se svaki gejt izrazi preko I-elemenata i invertera. Ona ne povećava zahteve za resursima u vidu vremena i prostora. Ovo čini AIG efikasnijom reprezentacijom funkcija u poređenju sa BDD-om (eng. Binary decision diagram) i DNF-om (eng. Disjunctive normal form). Interesovanje za AIG javlja se kasnih 50-ih^[1] i nastavlja se 70-ih godina 20. veka, kad se koristi u okviru sistema za verifikaciju radi ubrzanog generisanja formalnih dokaza ispravnosti.

AIG nedavno počinje ponovo da se pominje kao način reprezentacija funkcija za razne vrste verifikacije. Razlog za ovo je što su tekući načini reprezentacije došli do granice svojih skalabilnosti u mnogim aplikacijama.

AIG je pronašao svrhu i u EDA (eng. Electronic design automation) aplikacijama. Nedavne studije pokazuju da se efikasne tehnike kompresovanja kola mogu razviti korišćenjem AIG-a^[2]. Zbog svoje jednostavne strukture koja dozvoljava lake izmene, smatra se obećavajućim načinom reprezentacije funkcija.

Pored kombinatornih kola, AIG ima svoju primenu i u sekvencijalnim kolima. Postoji metoda strukturnog heširanja (tehnike koju je razvio IBM). Ona kombinuje AIG sa sekvencijalnim kolima (npr. D flip-flopom) u strukturu podataka koja se koristi za aplikacije koje služe za ritajming^[3] .

Implementacije

Logic Synthesis and Verification System ABC
AIGER
OpenAccess Gear

Reference

^ Hellerman, L. (jun 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. str. 42—49.
^ J. Baumgartner and A. Kuehlmann. „Min-area retiming on flexible circuit structures”. Proc. ICCAD'01. str. 176—182.

[1] Hellerman, L. (jun 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. str. 42—49.

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

[1]

[2]

[3]