موضوع مقاله: گراف AND-NOT | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # گراف AND-NOT | مقدمه: به طور معمول، این گراف انتزاعی به عنوان یک ساختار داده در نرم‌افزار نمایش داده می‌شود. | ## بخش 1: گراف AND-NOT | این ویژگی AIG را به یک نمایش کارآمد در مقایسه با نمودار تصمیم دودویی (BDD) یا فرم «مجموع حاصل‌ضرب‌ها» (ΣoΠ) تبدیل می‌کند، که همان فرم متعارف در جبر بولی است و با نام فرم نرمال فصلی (DNF) شناخته می‌شود . BDD و DNF را نیز می‌توان به عنوان مدار مشاهده کرد، اما آن‌ها شامل محدودیت‌های رسمی هستند که مقیاس‌پذیری آن‌ها را کاهش می‌دهند. برای مثال، ΣoΠها مدارهایی با حداکثر دو سطح هستند، در حالی که BDDها متعارف هستند، به این معنی که لازم است متغیرهای ورودی در تمام مسیرها به ترتیب یکسانی ارزیابی شوند. تاریخچه مدارهایی که از گیت‌های ساده تشکیل شده‌اند، از جمله AIGها، موضوعی «قدیمی» در تحقیقات هستند. علاقه به AIGها با مقاله پیشگامانه آلن تورینگ در سال ۱۹۴۸ [۱] در مورد شبکه‌های عصبی آغاز شد، که در آن او یک شبکه آموزش‌پذیر تصادفی از گیت‌های NAND را توصیف کرد. این علاقه در اواخر دهه ۱۹۵۰ [۲] و سپس در دهه ۱۹۷۰ که تبدیل‌های محلی مختلفی توسعه یافتند، ادامه پیدا کرد. این سیستم‌ها مدارها را برای بهبود سطح و تأخیر در طول سنتز، یا برای تسریع در بررسی هم‌ارزی صوری، کاهش می‌دهند. | ## بخش 2: گراف AND-NOT | اخیراً علاقه مجددی به AIGها به عنوان یک نمایشگر تابعی برای کارهای مختلف در سنتز و تأیید به وجود آمده است. دلیل این امر این است که نمایش‌های محبوبی که در دهه ۱۹۹۰ رایج بودند (مانند BDDها)، در بسیاری از کاربردهای خود به محدودیت‌های مقیاس‌پذیری رسیده‌اند . هنگامی که این حل‌کننده‌ها با AIGها به عنوان نمایش مدار ترکیب می‌شوند، منجر به سرعت‌های قابل توجهی در حل طیف گسترده‌ای از مسائل بولی می‌شوند . کاربردها AIGها کاربرد موفقی در کاربردهای متنوع اتوماسیون طراحی الکترونیک (EDA) پیدا کرده‌اند. یک کار اخیر دیگر نشان می‌دهد که می‌توان از AIGها برای توسعه تکنیک‌های فشرده‌سازی کارآمد مدار استفاده کرد [۶]. در حال حاضر این درک رو به رشد وجود دارد که مسائل سنتز منطقی و فیزیکی را می‌توان با استفاده از شبیه‌سازی و ارضاپذیری بولی برای محاسبه خواص تابعی (مانند تقارن‌ها) [۷] و انعطاف‌پذیری گره (مانند عبارات بی‌اهمیت، جایگزینی‌های مجدد و SPFDها) [۸] [۹] [۱۰] حل کرد. این امر تا حد زیادی به دلیل ساختار ساده و یکنواخت AIGها است که به بازنویسی، شبیه‌سازی، نگاشت، جایابی و تأیید اجازه می‌دهد تا از یک ساختار داده مشترک استفاده کنند. | ## بخش 3: گراف AND-NOT | منطق ترتیبی علاوه بر منطق ترکیبی، AIGها در مورد منطق ترتیبی و تبدیل‌های ترتیبی نیز به کار گرفته شده‌اند. به طور خاص، روش درهم‌سازی ساختاری توسعه یافت تا برای AIGهایی با عناصر حافظه (مانند فلیپ‌فلاپ‌های نوع D با یک حالت اولیه، که به طور کلی می‌تواند نامشخص باشد) کار کند، که در نتیجه یک ساختار داده‌ای ایجاد شده که به طور خاص برای کاربردهای مرتبط با زمان‌بندی مجدد (retiming) [۱۱] تنظیم شده است. تحقیقات جاری تحقیقات جاری شامل پیاده‌سازی یک سیستم سنتز منطقی مدرن است که به طور کامل بر پایه AIGها بنا شده باشد. نمونه اولیه این سیستم که **ABC** نامیده می‌شود، شامل یک بسته AIG، چندین تکنیک سنتز و بررسی هم‌ارزی مبتنی بر AIG، و همچنین یک پیاده‌سازی آزمایشی از سنتز ترتیبی است. یکی از این تکنیک‌ها، نگاشت فناوری و زمان‌بندی مجدد را در یک مرحله بهینه‌سازی واحد ترکیب می‌کند. | ## جمع‌بندی | این بهینه‌سازی‌ها را می‌توان با استفاده از شبکه‌های متشکل از گیت‌های دلخواه نیز پیاده‌سازی کرد، اما استفاده از AIGها آن‌ها را مقیاس‌پذیرتر و پیاده‌سازی‌شان را آسان‌تر می‌سازد.