گراف عطف-وارونگر

**گراف عطف-وارون‌گر** یک گراف جهت‌دارِ بدون دور است که پیاده‌سازی ساختاری عملکرد منطقی یک مدار یا شبکه را نمایش می‌دهد. یک گراف عطف-وارون‌گر از گره‌هایی با دو ورودی برای نمایش عطف منطقی، گره‌های پایانی با برچسب نام متغیرها، و یال‌هایی که می‌توانند شامل نشانگر نفی منطقی باشند، تشکیل شده‌است. اگرچه این شیوهٔ نمایش تابع منطقی برای مدارهای بزرگ همواره بهینه نیست، اما در دست‌کاری و پردازش توابع بولی بسیار کارآمد است. معمولاً این گراف‌ها به صورت یک ساختار داده در نرم‌افزار پیاده‌سازی می‌شوند.

بندانگشتی|چپ|دو گراف عطف-وارون‌گر متفاوت برای تابع بولی f(x1, x2, x3) = x2 * (x1 + x3)|380x380px

تبدیل شبکه‌ای از گیت‌های منطقی به گراف‌های عطف-وارون‌گر فرایندی سریع و مقیاس‌پذیر است؛ زیرا تنها کافی است تمامی گیت‌های مدار با گیت‌های عطف (AND) و وارون‌گر (Inverter) بازنویسی شوند. برخلاف برخی روش‌های دیگر، این تبدیل موجب افزایش غیرقابل‌پیش‌بینی در مصرف حافظه یا زمان اجرا نمی‌شود.

این ویژگی، گراف عطف-وارون‌گر را در مقایسه با روش‌هایی نظیر نمودار تصمیم‌گیری دودویی (BDD) یا فرم «جمع حاصل‌ضرب‌ها» (ΣoΠ) که همان فرم نرمال دیسجانکتیو (DNF) است، نمایشی کارآمد می‌سازد.

اگرچه می‌توان BDD و DNF را نیز نوعی مدار در نظر گرفت، اما این ساختارها محدودیت‌های صوری دارند که مانع مقیاس‌پذیری مناسب آن‌ها می‌شود. برای نمونه، مدارهای ΣoΠ حداکثر دارای دو سطح منطقی‌اند و نمودارهای BDD ساختاری یکتا (Canonical) دارند؛ یعنی ترتیب ارزیابی متغیرها در تمام مسیرهای گراف باید یکسان باشد.

پژوهش دربارهٔ مدارهای ساخته‌شده از گیت‌های ساده – از جمله گراف‌های عطف-وارون‌گر – سابقه‌ای طولانی دارد. جرقهٔ اولیهٔ توجه به گراف‌های عطف-وارون‌گر با مقالهٔ بنیادین آلن تورینگ در سال ۱۹۴۸ دربارهٔ شبکه‌های عصبی زده شد؛ او در این مقاله شبکه‌ای تصادفی و آموزش‌پذیر از گیت‌های NAND را توصیف کرده بود.

این روند در اواخر دههٔ ۱۹۵۰ و دههٔ ۱۹۷۰ با توسعهٔ تبدیل‌های محلی (Local Transformations) ادامه یافت. این تبدیل‌ها بعدها در سیستم‌های متعددی برای سنتز و بازبینی منطقی – از جمله کارهای دارینگر و همکاران و اسمیت و همکاران – به کار رفت.

یکی از تکنیک‌های کلیدی که در شرکت آی‌بی‌ام توسعه یافت، «درهم‌سازی ساختاری» (Structural Hashing) بود که بر ترکیب و استفادهٔ مجدد از زیرعبارت‌های منطقی تکیه دارد.

از دههٔ ۲۰۰۰ به بعد، با کاهش کارایی روش‌های دههٔ ۱۹۹۰ – مانند BDDها – در مقیاس‌های بزرگ، گراف‌های عطف-وارون‌گر دوباره مورد توجه قرار گرفتند. 

تحول مهم بعدی، ظهور حل‌کننده‌های بسیار کارآمد مسائل «ارضای‌پذیری بولی» (SAT Solvers) بود. ترکیب این حل‌کننده‌ها با AIGها باعث افزایش چشمگیر سرعت در حل بسیاری از مسائل بولی شد. 

گراف‌های عطف-وارون‌گر امروزه در بسیاری از کاربردهای اتوماسیون طراحی الکترونیکی (EDA) با موفقیت استفاده می‌شوند. ترکیب AIG با حل‌پذیری بولی تأثیر قابل‌توجهی بر حوزهٔ راستی‌آزمایی صوری، به‌ویژه وارسی مدل و وارسی هم‌ارزی داشته است.

همچنین پژوهش‌های اخیر نشان می‌دهند که می‌توان روش‌های کارآمدی برای فشرده‌سازی مدار با استفاده از AIGها توسعه داد.

از دیگر کاربردهای مهم AIGها بررسی ویژگی‌های تابعی مانند تقارن‌ها و همچنین محاسبهٔ انعطاف‌پذیری‌های گره – شامل Don’t-cares و SPFDها – است.

گسترش AIG برای پشتیبانی از منطق ترتیبی – شامل مدارهای دارای فلیپ‌فلاپ – منجر به ایجاد ساختار داده‌ای ویژه برای باززمان‌بندی (Retiming) شد.

در سال‌های اخیر تلاش‌های بسیاری برای ساخت سامانه‌ای مدرن برای سنتز منطقی بر پایهٔ AIG انجام شده‌است. نمونهٔ اولیهٔ این سامانه – ABC – شامل یک بستهٔ اختصاصی برای AIGها، مجموعه‌ای از روش‌های سنتز و وارسی هم‌ارزی مبتنی بر AIG و نیز پیاده‌سازی آزمایشی برای سنتز ترتیبی است.

یکی از ایده‌های مهم در این حوزه، ترکیب نگاشت تکنولوژی و باززمان‌بندی در یک گام بهینه‌سازی است. گرچه این روش‌ها را می‌توان با هر نوع گیت دلخواه به‌کار برد، اما استفاده از عطف-وارون‌گرها باعث افزایش مقیاس‌پذیری و سادگی پیاده‌سازی می‌شود.

## پیاده‌سازی‌ها
* ABC: سامانهٔ سنتز و راستی‌آزمایی منطقی  
* AIGER: مجموعه ابزارهای کاربردی برای AIGها  
* OpenAccess Gear: ابزارهای مبتنی بر استاندارد OpenAccess  
* Gini logic library: کتابخانهٔ منطقی Gini  

## منابع

رده:مدارهای الکتریکی
رده:خودکارسازی طراحی الکترونیکی
رده:روش‌های صوری
رده:نمودارها
رده:گراف‌های با کاربرد ویژه