کمینه‌ساز منطق اکتشافی اسپرسو

**کمینه‌ساز منطق اکتشافی اسپرسو** یک برنامهٔ رایانه‌ای برای کمینه‌سازی منطقی است که از الگوریتم‌های اکتشافی و تخصصی برای کاهش بهینهٔ پیچیدگی مدارهای دیجیتال متشکل از گیت‌های منطقی استفاده می‌کند. نسخهٔ اولیهٔ آن به نام ESPRESSO-I در سال ۱۹۸۲ توسط رابرت ک. بریتون و همکارانش در شرکت آی‌بی‌ام توسعه داده شد. و سپس در سال ۱۹۸۴ به‌صورت ESPRESSO-II بهبود یافت. پس از آن، ریچارد ال. رودِل در سال ۱۹۸۶ نسخه‌ای چندمقداری به نام ESPRESSO-MV  و در سال ۱۹۸۷ نسخه‌ای دقیق به نام ESPRESSO-EXACT منتشر کرد. این ابزار الهام‌بخش ایجاد بسیاری از نسخه‌های مشتق‌شدهٔ دیگر نیز بوده است

## '''مقدمه'''
دستگاه‌های الکترونیکی از مجموعه‌ای از بلوک‌های مدار دیجیتال تشکیل شده‌اند که ترکیب آن‌ها عملکرد خاصی را انجام می‌دهند. پیاده‌سازی کارآمد توابع منطقی به‌صورت مدارهای گیت منطقی (به‌گونه‌ای که از حداقل تعداد گیت‌های ممکن استفاده شود) برای کاهش هزینه‌های تولید و/یا افزایش عملکرد دستگاه ضروری است.

## '''طراحی مدارهای منطقی دیجیتال'''
تمام سامانه‌های دیجیتال از دو کارکرد بنیادی ساخته می‌شوند: عناصر حافظه برای نگهداری اطلاعات و مدارهای ترکیبی که آن اطلاعات را تبدیل می‌کنند. ماشین‌های حالت، مثل شمارنده‌ها، ترکیبی از عناصر حافظه و مدارهای منطقی ترکیبی اند. از آنجا که عنصر های حافظه، خود مدار های منطقی استانداردی هستند که از میان مجموعه محدودی از مدار های جایگزین انتخاب می‌شوند، بنابراین طراحی توابع دیجیتال در نهایت به طراحی مدارهای گیت ترکیبی و نحوه اتصال آن‌ها به یکدیگر خلاصه می‌شود.

به‌طور کلی، تبدیل انتزاع های سطح بالا به مدار های منطقی را سنتز منطقی می‌نامند. کاری که  می‌تواند به صورت دستی انجام شود، اما معمولاً از روش‌های رسمی و خودکار با کمک کامپیوتر استفاده می‌شود. در این مقاله، روش‌های طراحی مدارهای منطقی ترکیبی به‌صورت مختصر بررسی شده‌اند.

نقطه شروع در طراحی یک مدار منطقی دیجیتال، تعیین عملکرد مورد انتظار آن است که پس از بررسی و تحلیل کل سیستم، مدار منطقی بخشی از آن محسوب می‌شود. عملکرد مدار می‌تواند به شکل الگوریتم، معادلات منطقی یا حتی به صورت جدول ارائه شود. به‌عنوان مثال، جدول زیر بخشی از یک راه‌انداز نمایشگر ۷‌ بخشی را نشان می‌دهد که اعداد دودویی را به سیگنال‌هایی تبدیل می‌کند که بخش‌های مرتبط را روشن کرده و مقادیر یک رقم ده‌دهی را نمایش می‌دهند.


```
Digit  Code        Segments
                   A B C D E F G
    0    0000      1 1 1 1 1 1 0          -A-
    1    0001      0 1 1 0 0 0 0         |   |
    2    0010      1 1 0 1 1 0 1         F   B
    3    0011      1 1 1 1 0 0 1         |   |
    4    0100      0 1 1 0 0 1 1          -G-
    5    0101      1 0 1 1 0 1 1         |   |
    6    0110      1 0 1 1 1 1 1         E   C
    7    0111      1 1 1 0 0 0 0         |   |
    8    1000      1 1 1 1 1 1 1          -D-
    9    1001      1 1 1 1 0 1 1
```


فرآیند پیاده‌سازی با مرحله‌ای به نام کمینه‌سازی منطقی آغاز می‌شود، که در ادامه به آن پرداخته خواهد شد. در این مرحله، جدول تابع با ترکیب عبارات جداگانه به عبارات بزرگ‌تر که شامل متغیرهای کمتری هستند، بهینه می‌شود.

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

## '''روش‌های کمینه‌سازی کلاسیک'''
کمینه‌سازی توابع بولی به صورت دستی با استفاده از نقشه‌های کلاسیک کارنو کاری زمان‌بر، خسته‌کننده و مستعد خطاست. این روش برای بیش از شش متغیر ورودی مناسب نیست و در عمل تنها برای حداکثر چهار متغیر قابل استفاده است، ضمن اینکه اشتراک‌گذاری عبارات حاصل‌ضرب برای چندین تابع خروجی حتی دشوارتر هم است. علاوه بر این، این روش به سادگی قابل خودکارسازی در قالب یک برنامه کامپیوتری نیست. از آنجا که توابع منطقی مدرن معمولا محدود به تعداد اندکی از متغیر‌ها نیستند و همچنین خطر بروز خطا پیاده سازی دستی توابع منطقی را ناموجه می کند، استفاده از رایانه‌ها برای این منظور ضروری شد.

اولین روش جایگزینی که رایج شد، روش مبتنی بر جدول بود که توسط ویلارد کواین و ادوارد مک‌کلاسکی توسعه یافت. در این روش، با شروع از جدول ارزش برای مجموعه‌ای از توابع منطقی، مینترم‌هایی که برای آن‌ها تابع فعال است (پوشش ON) یا مقادیر تابع برای آن‌ها اهمیتی ندارد (پوشش Don't-Care یا DC) با هم ترکیب می‌شوند تا مجموعه‌ای از استلزامات اولیه شکل گیرد. در نهایت، یک فرآیند سیستماتیک برای یافتن کوچک‌ترین مجموعه استلزامات اولیه که بتوان با آن‌ها توابع خروجی را تحقق بخشید، اجرا می‌شود.

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

## '''الگوریتم اسپرسو'''
رویکرد متفاوتی برای این مسئله در الگوریتم ESPRESSO دنبال می‌شود که توسط برایتون و همکارانش در دانشگاه کالیفرنیا، برکلی توسعه یافته است. این الگوریتم، از نظر مصرف منابع و کارایی بسیار موثر است و با هدف حل مسئله کمینه‌سازی منطقی دو سطحی بدون ریسک به صورت اکتشافی طراحی شده است. 

این برنامه به جای گسترش یک تابع منطقی به مینترم‌ها، با “کیوب‌ها” کار می‌کند که نمایانگر عبارات حاصل‌ضرب در پوشش‌های روشن (ON)، بی اهمیت (Don't-Care یا DC) و خاموش (OFF) هستند و این کار به صورت تکراری انجام می‌شود. اگرچه تضمین نمی‌شود که نتیجه کمینه‌سازی همان کمینه‌ی سراسری باشد، اما در عمل این نتیجه معمولا بسیار به آن نزدیک است و راه حل همیشه عاری از افزونگی است.

در مقایسه با روش‌های دیگر، این رویکرد به‌طور قابل توجهی کارآمدتر است و مصرف حافظه و زمان محاسبه را چندین برابر کاهش می‌دهد. نام الگوریتم از روش تهیه سریع یک فنجان قهوه (Espresso) گرفته شده است. [نیاز به توضیح بیشتر دارد]

علاوه بر این، تقریباً هیچ محدودیتی برای تعداد متغیرها، توابع خروجی و عبارات حاصل‌ضرب در یک بلوک تابع ترکیبی وجود ندارد. به طور کلی، حتی ده‌ها متغیر و ده‌ها تابع خروجی به راحتی قابل مدیریت هستند.

ورودی الگوریتم ESPRESSO، یک جدول تابع برای کارکرد مورد نظر است؛ خروجی آن یک جدول کمینه‌شده است که بسته به گزینه‌های انتخاب شده، پوشش روشن (ON-cover) یا پوشش خاموش (OFF-cover) تابع را توصیف می‌کند. به طور پیش‌فرض، عبارات حاصل‌ضرب تا حد امکان بین چندین تابع خروجی به اشتراک گذاشته می‌شوند، اما می‌توان برنامه را طوری تنظیم کرد که هر تابع خروجی را به‌‌صورت جداگانه پردازش کند. این قابلیت امکان پیاده‌سازی بهینه در آرایه‌های منطقی دو سطحی مانند PLA (آرایه منطقی قابل برنامه‌ریزی) یا PAL (آرایه منطقی برنامه‌پذیر) را فراهم می‌کند.

الگوریتم ESPRESSO چنان کارآمد عمل کرد که به عنوان یک گام استاندارد برای کمینه‌سازی تابع منطقی در تقریباً همه ابزارهای سنتز منطقی مدرن مورد استفاده قرار می‌گیرد. برای پیاده‌سازی یک تابع در منطق چندسطحی، نتیجه کمینه‌سازی با فاکتورگیری بهینه می‌شود و سپس روی سلول‌های منطقی پایه‌ی موجود در فناوری هدف نگاشت می‌شود، چه این فناوری مربوط به FPGA (آرایه گیت قابل برنامه‌ریزی میدانی) باشد و چه ASIC (مدار مجتمع با کاربرد خاص).

## '''نرم‌افزار'''

### اسپرسو
نسخه اصلی برنامه ESPRESSO به‌صورت کد منبع C از وب‌سایت دانشگاه کالیفرنیا، برکلی در دسترس است. آخرین نسخه رسمی آن، نسخه ۲.۳، مربوط به سال ۱۹۸۸ بود. نسخه‌های جدیدتر شامل ESPRESSO-AB و EQNTOTT (جدول تبدیل معادله به جدول صحت)، که برای سیستم‌های مدرن POSIX به‌روز شده‌اند، هم به صورت فایل توزیع لینوکس دبیان (.deb) و هم به صورت کد منبع C در دسترس هستند. آخرین نسخه این مجموعه، نسخه ۹.۰، مربوط به سال ۲۰۰۸ است. علاوه بر این، یک نسخه سازگار با ویندوز و C++20 در سال ۲۰۲۰ در GitHub منتشر شد.

## '''Logic Friday'''
Logic Friday یک برنامه رایگان برای ویندوز است که یک رابط گرافیکی برای الگوریتم Espresso و همچنین misII، ماژول دیگری از بسته Octtools دانشگاه برکلی، فراهم می‌کند. با استفاده از Logic Friday، کاربران می‌توانند یک تابع منطقی را به شکل جدول صحت، معادله یا نمودار گیت وارد کنند، آن را کمینه‌سازی کنند و نتایج را در سایر نمایش‌ها مشاهده نمایند. آخرین نسخه این برنامه، نسخه ۱.۱.۴، مربوط به سال ۲۰۱۲ است.

## '''مینی‌لاگ'''
Minilog یک برنامه رایگان برای ویندوز است که با استفاده از الگوریتم Espresso امکان کمینه‌سازی توابع منطقی را فراهم می‌کند. این برنامه قادر است یک پیاده‌سازی گیت دو سطحی برای یک بلوک تابع ترکیبی با حداکثر ۴۰ ورودی و خروجی یا یک ماشین حالت همزمان با حداکثر ۲۵۶ حالت ایجاد کند. Minilog بخشی از بسته آموزشی Publicad برای طراحی مدارهای دیجیتال است.

## '''اسپرسو-IISOJS'''
ESPRESSO-IISOJS یک پیاده‌سازی جاوااسکریپت از ESPRESSO-II برای توابع با خروجی تک‌گانه است. این نسخه از تکنیک انتشار واحد به‌عنوان یک روش بهینه‌سازی اضافی برای الگوریتم‌های مختلف ESPRESSO-II که مبتنی بر الگوی بازگشتی یکتا هستند، استفاده می‌کند. یکی دیگر از امکانات اضافه شده، کنترل زمان فراخوانی لیترال‌ها است که می‌تواند برای کمینه‌سازی مؤثر توابع منطقی Kleene مورد بهره‌برداری قرار گیرد.

## منابع

## '''مطالعه بیشتر'''

* 

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

رده:بهینه‌سازی الکترونیکی
رده:نرم‌افزارهای شبیه‌سازی آزاد