بهینه‌سازی منطقی کیست؟ توضیح بده.
بهینه‌سازی منطقی فرآیندی است که در آن یک نمایش معادل از یک مدار منطقی مشخص شده، تحت یک یا چند محدودیت مشخص، پیدا می‌شود. این فرایند بخشی از سنتز منطقی است که در الکترونیک دیجیتال و طراحی مدارهای مجتمع کاربرد دارد.به‌طور کلی، مدار به یک مساحت حداقل تراشه محدود می‌شود که یک تأخیر پاسخ از پیش تعریف شده را برآورده می‌کند. هدف بهینه‌سازی منطقی یک مدار معین، به دست آوردن کوچک‌ترین مدار منطقی است که همان مقادیر مدار اصلی را ارزیابی می‌کند. معمولاً، مدار کوچکتر با همان عملکرد ارزان‌تر است، فضای کمتری را اشغال می‌کند، ، دارای تأخیر کمتری است و خطرات تداخل غیرمنتظره، و سایر مسائل موجود در سطح نانو ساختارهای فلزی را بر روی یک مدار مجتمع به حداقل می‌رساند.از نظر جبر بولی، بهینه‌سازی یک عبارت بولی پیچیده فرایند پیدا کردن یک عبارت ساده‌تر است که هنگام ارزیابی، در نهایت نتایج مشابهی با عبارت اصلی تولید می‌کند.انگیزه.مشکل داشتن یک مدار پیچیده (یعنی مداری با عناصر متعدد مانند دروازه‌های منطقی) این است که هر عنصر فضای فیزیکی اشغال می‌کند و تولید آن زمان و هزینه می‌برد. مینیمم‌سازی مدار می‌تواند یکی از اشکال بهینه‌سازی منطقی باشد که برای کاهش مساحت منطق پیچیده در مدارهای مجتمع استفاده می‌شود.با ظهور سنتز منطقی، یکی از بزرگ‌ترین چالش‌های صنعت خودکارسازی طراحی الکترونیک (EDA) یافتن ساده‌ترین نمایش مدار از توصیف طراحی داده شده بود. در حالی که به شکل الگوریتم کوین-مک کلاسکی و بعداً به دنبال آن وجود داشت، تراکم تراشه‌های در حال بهبود سریع و پذیرش گسترده زبان‌های توصیف سخت‌افزار برای توصیف مدار، حوزه بهینه‌سازی منطقی را همان‌طور که امروز وجود دارد، رسمی کرد، از جمله ، Minilog و ESPRESSO-IISOJS (منطق چند ارزشی).روش‌ها.روش‌های ساده‌سازی مدار منطقی به یک اندازه برای قابل استفاده هستند.طبقه‌بندی.امروزه، بهینه‌سازی منطقی به دسته‌های مختلفی تقسیم می‌شود:بر اساس نمایش مداربر اساس ویژگی‌های مداربر اساس نوع اجراروش‌های گرافیکی.روش‌های گرافیکی، تابع منطقی مورد نیاز را با استفاده از یک نمودار که متغیرهای منطقی و مقدار تابع را نشان می‌دهد، نمایش می‌دهند. با دستکاری یا بررسی یک نمودار، می‌توان از بسیاری از محاسبات خسته‌کننده جلوگیری کرد. روش‌های کمینه‌سازی گرافیکی برای منطق دو سطحی شامل:بهینه‌سازی (ساده‌سازی) عبارات بولی.همان روش‌های ساده‌سازی عبارات بولی که در زیر فهرست شده‌اند، ممکن است برای بهینه‌سازی مدار اعمال شوند.در حالتی که تابع بولی توسط یک مدار مشخص شده باشد (یعنی می‌خواهیم یک مدار معادل با حداقل اندازه ممکن پیدا کنیم)، مشکل ساده‌سازی مدار نامحدود، برای مدت طولانی حدس زده می‌شد که در پیچیدگی زمانی Σ2P- باشد، نتیجه‌ای که در نهایت در سال ۲۰۰۸ ثابت شد، اما برخی از روش‌های ابتکاری مؤثر مانند جدول‌های کارنو و الگوریتم کواین-مک‌کلاسی وجود دارند که این فرایند را تسهیل می‌کنند.روش‌های کمینه‌سازی تابع بولی عبارتند از:روش‌های چندسطحی بهینه.روش‌هایی که نمایش‌های مدار بهینه برای توابع بولی پیدا می‌کنند، اغلب در ادبیات به عنوان سنتز دقیق شناخته می‌شوند. به دلیل پیچیدگی محاسباتی، سنتز دقیق تنها برای توابع بولی کوچک قابل حل است. رویکردهای اخیر مسئله بهینه‌سازی را به یک مسئله نگاشت می‌کنند. این امکان را فراهم می‌کند تا با استفاده از یک ، نمایش‌های مدار بهینه را پیدا کرد.روش‌های اکتشافی.یک روش ابتکاری از قوانین مشخصی استفاده می‌کند که زیرمجموعه‌ای عملی و مفید از مجموعه بسیار بزرگ‌تر مشکلات ممکن را حل می‌کند. روش ابتکاری ممکن است بهینه‌ترین راه‌حل نظری را تولید نکند، اما اگر مفید باشد، بیشتر بهینه‌سازی مورد نظر را با حداقل تلاش فراهم می‌کند. یک مثال از یک سیستم کامپیوتری که از روش‌های ابتکاری برای بهینه‌سازی منطق استفاده می‌کند، است.نمایش‌های دو سطحی در مقابل نمایش‌های چندسطحی.در حالی که یک نمایش دو سطحی مدار به‌طور دقیق به نمای مسطح مدار از نظر مجموع حاصلضرب‌ها (SOP) اشاره دارد - که بیشتر برای پیاده‌سازی PLA طراحی قابل اجرا است [نیازمند توضیح] - یک نمایش چندسطحی یک دید کلی‌تر از مدار از نظر SOPهای به هم پیوسته دلخواه، POSهای ()، فرم فاکتور شده و غیره است. الگوریتم‌های بهینه‌سازی منطق معمولاً روی نمایش ساختاری (SOPها، فرم فاکتور شده) یا نمایش عملکردی (، ) مدار کار می‌کنند. در فرم مجموع حاصلضرب (SOP)، دروازه‌های AND کوچک‌ترین واحد را تشکیل می‌دهند و با استفاده از ORها به هم متصل می‌شوند، در حالی که در فرم حاصلضرب مجموع (POS) برعکس است. فرم POS برای گروه‌بندی اصطلاحات OR تحت دروازه‌های AND به پرانتز نیاز دارد، زیرا OR اولویت کمتری نسبت به AND دارد. هر دو فرم SOP و POS به خوبی به منطق مدار ترجمه می‌شوند.اگر دو تابع F1 و F2 داشته باشیم:F1=AB+AC+ADF2=A′B+A′C+A′Eنمایش دو سطحی بالا از شش جمله حاصلضرب و ۲۴ ترانزیستور در پیاده‌سازی CMOS استفاده می‌کند.یک نمایش چندسطحی معادل از نظر عملکردی می‌تواند باشد:P = B + CF1 = AP + ADF2 = A'P + A'Eبا وجود اینکه تعداد سطوح در اینجا ۳ است، اما تعداد کل جملات حاصلضرب و متغیرها به دلیل اشتراک‌گذاری جمله B + C، به‌طور قابل توجهی کاهش می‌یابد.به‌طور مشابه، بین مدارهای ترکیبی و مدارهای ترتیبی تمایز قائل می‌شویم. مدارهای ترکیبی خروجی خود را تنها بر اساس ورودی‌های فعلی تولید می‌کنند. آنها می‌توانند با بولی نمایش داده شوند. برخی از مثال‌ها عبارتند از کدگذار اولویت‌دار، رمزگشا (کدگشا) دودویی، مالتی‌پلکسر و دمالتی‌پلکسر.مدارهای ترتیبی خروجی خود را بر اساس ورودی‌های فعلی و گذشته تولید می‌کنند، و برای تشخیص ورودی‌های قبلی از ورودی‌های فعلی به سیگنال ساعت وابسته هستند. آن‌ها می‌توانند با ماشین‌های حالت متناهی نمایش داده شوند. برخی از مثال‌ها عبارتند از فلیپ‌فلاپ‌ها و شمارنده‌ها.مثال.در حالی که روش‌های بسیاری برای ساده‌سازی یک مدار وجود دارد، این یک مثال ساده‌سازی یک تابع بولی است. تابع بولی که توسط مدار انجام می‌شود، به‌طور مستقیم به عبارت جبری مرتبط است که تابع از آن پیاده‌سازی شده است. به مدار مورد استفاده برای نمایش ('A ∧ B) ∨ (A' ∧ B)توجه کنید. مشخص است که از دو نفی، دو الحاق و یک فصل مشترک در این عبارت استفاده شده است. این بدان معناست که برای ساخت مدار، به دو گیت NOT، دو دروازه AND و یک دروازه OR نیاز داریم.این مدار را می‌توان با استفاده از قوانین جبر بولی یا با استفاده از شهود ساده کرد (مینیمایز کرد). از آنجایی که مثال بیان می‌کند که A زمانی درست است که B نادرست باشد و برعکس، می‌توان نتیجه گرفت که این به سادگی به معنای A ≠ B است. از نظر دروازه‌های منطقی، نابرابری به سادگی به معنای یک دروازه XOR (یا انحصاری) است؛ بنابراین،('A ∧ B) ∨ (A' ∧ B) ⟺ A ≠ B. سپس دو مدار نشان داده شده در زیر معادل هستند، همان‌طور که می‌توان با استفاده از جدول درستی بررسی کرد: