موضوع مقاله: بهینه‌سازی منطقی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بهینه‌سازی منطقی | مقدمه: بهینه‌سازی منطقی فرآیندی است که در آن یک نمایش معادل از یک مدار منطقی مشخص شده، تحت یک یا چند محدودیت مشخص، پیدا می‌شود. | ## بخش 1: بهینه‌سازی منطقی | این فرایند بخشی از سنتز منطقی است که در الکترونیک دیجیتال و طراحی مدارهای مجتمع کاربرد دارد. به‌طور کلی، مدار به یک مساحت حداقل تراشه محدود می‌شود که یک تأخیر پاسخ از پیش تعریف شده را برآورده می‌کند. هدف بهینه‌سازی منطقی یک مدار معین، به دست آوردن کوچک‌ترین مدار منطقی است که همان مقادیر مدار اصلی را ارزیابی می‌کند. معمولاً، مدار کوچکتر با همان عملکرد ارزان‌تر است، فضای کمتری را اشغال می‌کند، مصرف انرژی کمتری دارد، دارای تأخیر کمتری است و خطرات تداخل غیرمنتظره، خطر پردازش سیگنال تأخیری و سایر مسائل موجود در سطح نانو ساختارهای فلزی را بر روی یک مدار مجتمع به حداقل می‌رساند. از نظر جبر بولی، بهینه‌سازی یک عبارت بولی پیچیده فرایند پیدا کردن یک عبارت ساده‌تر است که هنگام ارزیابی، در نهایت نتایج مشابهی با عبارت اصلی تولید می‌کند. انگیزه مشکل داشتن یک مدار پیچیده (یعنی مداری با عناصر متعدد مانند دروازه‌های منطقی) این است که هر عنصر فضای فیزیکی اشغال می‌کند و تولید آن زمان و هزینه می‌برد. مینیمم‌سازی مدار می‌تواند یکی از اشکال بهینه‌سازی منطقی باشد که برای کاهش مساحت منطق پیچیده در مدارهای مجتمع استفاده می‌شود. با ظهور سنتز منطقی، یکی از بزرگ‌ترین چالش‌های صنعت خودکارسازی طراحی الکترونیک (EDA) یافتن ساده‌ترین نمایش مدار از توصیف طراحی داده شده بود. روش‌ها روش‌های ساده‌سازی مدار منطقی به یک اندازه برای مینیمم‌سازی عبارت‌های بولی قابل استفاده هستند. | ## بخش 2: بهینه‌سازی منطقی | طبقه‌بندی امروزه، بهینه‌سازی منطقی به دسته‌های مختلفی تقسیم می‌شود: بر اساس نمایش مدار بهینه‌سازی منطقی دو سطحی بهینه‌سازی منطقی چندسطحی بر اساس ویژگی‌های مدار بهینه‌سازی منطق ترتیبی بهینه‌سازی منطق ترکیبی بر اساس نوع اجرا روش‌های بهینه‌سازی گرافیکی روش‌های بهینه‌سازی جدولی روش‌های بهینه‌سازی جبری روش‌های گرافیکی روش‌های گرافیکی، تابع منطقی مورد نیاز را با استفاده از یک نمودار که متغیرهای منطقی و مقدار تابع را نشان می‌دهد، نمایش می‌دهند. با دستکاری یا بررسی یک نمودار، می‌توان از بسیاری از محاسبات خسته‌کننده جلوگیری کرد. روش‌های کمینه‌سازی گرافیکی برای منطق دو سطحی شامل: نمودار اویلر (یا دایره اویلری) (۱۷۶۸) توسط لئونارد اویلر (۱۷۰۷–۱۷۸۳) نمودار ون (۱۸۸۰) توسط جان ون (۱۸۳۴–۱۹۲۳) جدول کارنو (۱۹۵۳) توسط موریس کارنو بهینه‌سازی (ساده‌سازی) عبارات بولی همان روش‌های ساده‌سازی عبارات بولی که در زیر فهرست شده‌اند، ممکن است برای بهینه‌سازی مدار اعمال شوند. در حالتی که تابع بولی توسط یک مدار مشخص شده باشد (یعنی می‌خواهیم یک مدار معادل با حداقل اندازه ممکن پیدا کنیم)، مشکل ساده‌سازی مدار نامحدود، برای مدت طولانی حدس زده می‌شد که در پیچیدگی زمانی Σ2P- کامل باشد، نتیجه‌ای که در نهایت در سال ۲۰۰۸ ثابت شد، اما برخی از روش‌های ابتکاری مؤثر مانند جدول‌های کارنو و الگوریتم کواین-مک‌کلاسی وجود دارند که این فرایند را تسهیل می‌کنند. روش‌های کمینه‌سازی تابع بولی عبارتند از: الگوریتم کواین-مک کلاسکی روش پتریک روش‌های چندسطحی بهینه روش‌هایی که نمایش‌های مدار بهینه برای توابع بولی پیدا می‌کنند، اغلب در ادبیات به عنوان سنتز دقیق شناخته می‌شوند. این امکان را فراهم می‌کند تا با استفاده از یک حل‌کننده SAT، نمایش‌های مدار بهینه را پیدا کرد. روش‌های اکتشافی یک روش ابتکاری از قوانین مشخصی استفاده می‌کند که زیرمجموعه‌ای عملی و مفید از مجموعه بسیار بزرگ‌تر مشکلات ممکن را حل می‌کند. روش ابتکاری ممکن است بهینه‌ترین راه‌حل نظری را تولید نکند، اما اگر مفید باشد، بیشتر بهینه‌سازی مورد نظر را با حداقل تلاش فراهم می‌کند. یک مثال از یک سیستم کامپیوتری که از روش‌های ابتکاری برای بهینه‌سازی منطق استفاده می‌کند، بهینه‌ساز منطق ابتکاری Espresso است. | ## بخش 3: بهینه‌سازی منطقی | نمایش‌های دو سطحی در مقابل نمایش‌های چندسطحی در حالی که یک نمایش دو سطحی مدار به‌طور دقیق به نمای مسطح مدار از نظر مجموع حاصلضرب‌ها (SOP) اشاره دارد - که بیشتر برای پیاده‌سازی PLA طراحی قابل اجرا است [نیازمند توضیح] - یک نمایش چندسطحی یک دید کلی‌تر از مدار از نظر SOPهای به هم پیوسته دلخواه، POSهای (حاصلضرب مجموع)، فرم فاکتور شده و غیره است. الگوریتم‌های بهینه‌سازی منطق معمولاً روی نمایش ساختاری (SOPها، فرم فاکتور شده) یا نمایش عملکردی (نمودارهای تصمیم دودویی، نمودارهای تصمیم جبری) مدار کار می‌کنند. در فرم مجموع حاصلضرب (SOP)، دروازه‌های AND کوچک‌ترین واحد را تشکیل می‌دهند و با استفاده از ORها به هم متصل می‌شوند، در حالی که در فرم حاصلضرب مجموع (POS) برعکس است. یک نمایش چندسطحی معادل از نظر عملکردی می‌تواند باشد: P = B + C F1 = AP + AD F2 = A'P + A'E با وجود اینکه تعداد سطوح در اینجا ۳ است، اما تعداد کل جملات حاصلضرب و متغیرها به دلیل اشتراک‌گذاری جمله B + C، به‌طور قابل توجهی کاهش می‌یابد. برخی از مثال‌ها عبارتند از کدگذار اولویت‌دار، رمزگشا (کدگشا) دودویی، مالتی‌پلکسر و دمالتی‌پلکسر. مدارهای ترتیبی خروجی خود را بر اساس ورودی‌های فعلی و گذشته تولید می‌کنند، و برای تشخیص ورودی‌های قبلی از ورودی‌های فعلی به سیگنال ساعت وابسته هستند. تابع بولی که توسط مدار انجام می‌شود، به‌طور مستقیم به عبارت جبری مرتبط است که تابع از آن پیاده‌سازی شده است. این مدار را می‌توان با استفاده از قوانین جبر بولی یا با استفاده از شهود ساده کرد (مینیمایز کرد). از آنجایی که مثال بیان می‌کند که A زمانی درست است که B نادرست باشد و برعکس، می‌توان نتیجه گرفت که این به سادگی به معنای A ≠ B است. | ## جمع‌بندی | از نظر دروازه‌های منطقی، نابرابری به سادگی به معنای یک دروازه XOR (یا انحصاری) است؛ بنابراین، ('A ∧ B) ∨ (A' ∧ B) ⟺ A ≠ B.