موضوع مقاله: کمینه‌ساز منطق اکتشافی اسپرسو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کمینه‌ساز منطق اکتشافی اسپرسو | مقدمه: کمینه‌ساز منطق اکتشافی اسپرسو یک برنامهٔ رایانه‌ای برای کمینه‌سازی منطقی است که از الگوریتم‌های اکتشافی و تخصصی برای کاهش بهینهٔ پیچیدگی مدارهای دیجیتال متشکل از گیت‌های منطقی استفاده می‌کند. | ## بخش 1: کمینه‌ساز منطق اکتشافی اسپرسو | این ابزار الهام‌بخش ایجاد بسیاری از نسخه‌های مشتق‌شدهٔ دیگر نیز بوده است مقدمه دستگاه‌های الکترونیکی از مجموعه‌ای از بلوک‌های مدار دیجیتال تشکیل شده‌اند که ترکیب آن‌ها عملکرد خاصی را انجام می‌دهند. پیاده‌سازی کارآمد توابع منطقی به‌صورت مدارهای گیت منطقی (به‌گونه‌ای که از حداقل تعداد گیت‌های ممکن استفاده شود) برای کاهش هزینه‌های تولید و/یا افزایش عملکرد دستگاه ضروری است. طراحی مدارهای منطقی دیجیتال تمام سامانه‌های دیجیتال از دو کارکرد بنیادی ساخته می‌شوند: عناصر حافظه برای نگهداری اطلاعات و مدارهای ترکیبی که آن اطلاعات را تبدیل می‌کنند. ماشین‌های حالت، مثل شمارنده‌ها، ترکیبی از عناصر حافظه و مدارهای منطقی ترکیبی اند. از آنجا که عنصر های حافظه، خود مدار های منطقی استانداردی هستند که از میان مجموعه محدودی از مدار های جایگزین انتخاب می‌شوند، بنابراین طراحی توابع دیجیتال در نهایت به طراحی مدارهای گیت ترکیبی و نحوه اتصال آن‌ها به یکدیگر خلاصه می‌شود. کاری که می‌تواند به صورت دستی انجام شود، اما معمولاً از روش‌های رسمی و خودکار با کمک کامپیوتر استفاده می‌شود. نقطه شروع در طراحی یک مدار منطقی دیجیتال، تعیین عملکرد مورد انتظار آن است که پس از بررسی و تحلیل کل سیستم، مدار منطقی بخشی از آن محسوب می‌شود. عملکرد مدار می‌تواند به شکل الگوریتم، معادلات منطقی یا حتی به صورت جدول ارائه شود. به‌عنوان مثال، جدول زیر بخشی از یک راه‌انداز نمایشگر ۷‌ بخشی را نشان می‌دهد که اعداد دودویی را به سیگنال‌هایی تبدیل می‌کند که بخش‌های مرتبط را روشن کرده و مقادیر یک رقم ده‌دهی را نمایش می‌دهند. در این مرحله، جدول تابع با ترکیب عبارات جداگانه به عبارات بزرگ‌تر که شامل متغیرهای کمتری هستند، بهینه می‌شود. در مرحله بعد، نتیجه کمینه‌شده را می‌توان با استفاده از روش فاکتورگیری به بخش‌های کوچک‌تر تقسیم کرد و در نهایت آن را روی سلول‌های منطقی پایه موجود در فناوری هدف نگاشت نمود. | ## بخش 2: کمینه‌ساز منطق اکتشافی اسپرسو | روش‌های کمینه‌سازی کلاسیک کمینه‌سازی توابع بولی به صورت دستی با استفاده از نقشه‌های کلاسیک کارنو کاری زمان‌بر، خسته‌کننده و مستعد خطاست. این روش برای بیش از شش متغیر ورودی مناسب نیست و در عمل تنها برای حداکثر چهار متغیر قابل استفاده است، ضمن اینکه اشتراک‌گذاری عبارات حاصل‌ضرب برای چندین تابع خروجی حتی دشوارتر هم است. علاوه بر این، این روش به سادگی قابل خودکارسازی در قالب یک برنامه کامپیوتری نیست. از آنجا که توابع منطقی مدرن معمولا محدود به تعداد اندکی از متغیر‌ها نیستند و همچنین خطر بروز خطا پیاده سازی دستی توابع منطقی را ناموجه می کند، استفاده از رایانه‌ها برای این منظور ضروری شد. اولین روش جایگزینی که رایج شد، روش مبتنی بر جدول بود که توسط ویلارد کواین و ادوارد مک‌کلاسکی توسعه یافت. در این روش، با شروع از جدول ارزش برای مجموعه‌ای از توابع منطقی، مینترم‌هایی که برای آن‌ها تابع فعال است (پوشش ON) یا مقادیر تابع برای آن‌ها اهمیتی ندارد (پوشش Don't-Care یا DC) با هم ترکیب می‌شوند تا مجموعه‌ای از استلزامات اولیه شکل گیرد. در نهایت، یک فرآیند سیستماتیک برای یافتن کوچک‌ترین مجموعه استلزامات اولیه که بتوان با آن‌ها توابع خروجی را تحقق بخشید، اجرا می‌شود. اگرچه الگوریتم کواین-مک‌کلاسکی برای پیاده‌سازی در یک برنامه کامپیوتری مناسب است، اما همچنان از نظر زمان پردازش و مصرف حافظه کارآمد نیست. اضافه کردن یک متغیر به تابع تقریباً هر دو مورد را دو برابر می‌کند، زیرا طول جدول ارزش با تعداد متغیرها به صورت نمایی افزایش می‌یابد. بنابراین، روش کواین-مک‌کلاسکی تنها برای توابعی با تعداد محدودی از متغیرهای ورودی و توابع خروجی قابل استفاده و عملی است. الگوریتم اسپرسو رویکرد متفاوتی برای این مسئله در الگوریتم ESPRESSO دنبال می‌شود که توسط برایتون و همکارانش در دانشگاه کالیفرنیا، برکلی توسعه یافته است. | ## بخش 3: کمینه‌ساز منطق اکتشافی اسپرسو | این برنامه به جای گسترش یک تابع منطقی به مینترم‌ها، با “کیوب‌ها” کار می‌کند که نمایانگر عبارات حاصل‌ضرب در پوشش‌های روشن (ON)، بی اهمیت (Don't-Care یا DC) و خاموش (OFF) هستند و این کار به صورت تکراری انجام می‌شود. اگرچه تضمین نمی‌شود که نتیجه کمینه‌سازی همان کمینه‌ی سراسری باشد، اما در عمل این نتیجه معمولا بسیار به آن نزدیک است و راه حل همیشه عاری از افزونگی است. در مقایسه با روش‌های دیگر، این رویکرد به‌طور قابل توجهی کارآمدتر است و مصرف حافظه و زمان محاسبه را چندین برابر کاهش می‌دهد. [نیاز به توضیح بیشتر دارد] علاوه بر این، تقریباً هیچ محدودیتی برای تعداد متغیرها، توابع خروجی و عبارات حاصل‌ضرب در یک بلوک تابع ترکیبی وجود ندارد. به طور پیش‌فرض، عبارات حاصل‌ضرب تا حد امکان بین چندین تابع خروجی به اشتراک گذاشته می‌شوند، اما می‌توان برنامه را طوری تنظیم کرد که هر تابع خروجی را به‌‌صورت جداگانه پردازش کند. این قابلیت امکان پیاده‌سازی بهینه در آرایه‌های منطقی دو سطحی مانند PLA (آرایه منطقی قابل برنامه‌ریزی) یا PAL (آرایه منطقی برنامه‌پذیر) را فراهم می‌کند. الگوریتم ESPRESSO چنان کارآمد عمل کرد که به عنوان یک گام استاندارد برای کمینه‌سازی تابع منطقی در تقریباً همه ابزارهای سنتز منطقی مدرن مورد استفاده قرار می‌گیرد. برای پیاده‌سازی یک تابع در منطق چندسطحی، نتیجه کمینه‌سازی با فاکتورگیری بهینه می‌شود و سپس روی سلول‌های منطقی پایه‌ی موجود در فناوری هدف نگاشت می‌شود، چه این فناوری مربوط به FPGA (آرایه گیت قابل برنامه‌ریزی میدانی) باشد و چه ASIC (مدار مجتمع با کاربرد خاص). با استفاده از Logic Friday، کاربران می‌توانند یک تابع منطقی را به شکل جدول صحت، معادله یا نمودار گیت وارد کنند، آن را کمینه‌سازی کنند و نتایج را در سایر نمایش‌ها مشاهده نمایند. این برنامه قادر است یک پیاده‌سازی گیت دو سطحی برای یک بلوک تابع ترکیبی با حداکثر ۴۰ ورودی و خروجی یا یک ماشین حالت همزمان با حداکثر ۲۵۶ حالت ایجاد کند. این نسخه از تکنیک انتشار واحد به‌عنوان یک روش بهینه‌سازی اضافی برای الگوریتم‌های مختلف ESPRESSO-II که مبتنی بر الگوی بازگشتی یکتا هستند، استفاده می‌کند. | ## جمع‌بندی | یکی دیگر از امکانات اضافه شده، کنترل زمان فراخوانی لیترال‌ها است که می‌تواند برای کمینه‌سازی مؤثر توابع منطقی Kleene مورد بهره‌برداری قرار گیرد.