مُقلِّل منطق الاستدلال في الإسبريسو

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
الموسوعة الحرة

برنامج ESPRESSO لتقليل تعقيد الدوائر المنطقية الرقمية هو برنامج حاسوبي يستخدم خوارزميات استدلالية ومحددة لتقليل تعقيد هذه الدوائر بكفاءة . [ 1 ] طُوّر برنامج ESPRESSO-I في الأصل في شركة IBM على يد روبرت ك. برايتون وآخرين عام 1982. [ 2 ] [ 3 ] ثم جرى تحسينه ليصبح ESPRESSO-II عام 1984. [ 4 ] [ 5 ] وفي وقت لاحق، نشر ريتشارد ل. روديل النسخة المعدلة ESPRESSO-MV عام 1986 [ 6 ] وESPRESSO-EXACT عام 1987. [ 7 ] [ 8 ] [ 5 ] وقد ألهم برنامج Espresso العديد من البرامج المشتقة.

مقدمة

تتكون الأجهزة الإلكترونية من العديد من الدوائر الرقمية، التي يؤدي تركيبها معًا مهمة محددة. ويُعدّ التنفيذ الفعال للوظائف المنطقية في شكل دوائر البوابات المنطقية (بحيث لا يُستخدم عدد من البوابات المنطقية أكثر من اللازم) ضروريًا لتقليل تكاليف الإنتاج، و/أو لزيادة أداء الجهاز إلى أقصى حد.

تصميم الدوائر المنطقية الرقمية

تتألف جميع الأنظمة الرقمية من وظيفتين أساسيتين: عناصر الذاكرة لتخزين المعلومات، والدوائر المنطقية التوافقية التي تحوّل تلك المعلومات. تُعدّ آلات الحالة ، مثل العدادات، مزيجًا من عناصر الذاكرة والدوائر المنطقية التوافقية . وبما أن عناصر الذاكرة عبارة عن دوائر منطقية قياسية، فإنها تُختار من بين مجموعة محدودة من الدوائر البديلة؛ لذا فإن تصميم الوظائف الرقمية يقتصر على تصميم دوائر البوابات المنطقية التوافقية وربطها ببعضها.

يُشار عمومًا إلى عملية إنشاء الدوائر المنطقية انطلاقًا من تجريد عالي المستوى باسم توليف المنطق ، والذي يمكن تنفيذه يدويًا، ولكن عادةً ما تُطبق طريقة رسمية باستخدام الحاسوب. في هذه المقالة، نلخص بإيجاز طرق تصميم الدوائر المنطقية التوافقية.

تنطلق عملية تصميم الدوائر المنطقية الرقمية من وظيفتها المطلوبة، والتي تُستمد من تحليل النظام ككل الذي ستُشكّل الدائرة جزءًا منه. يمكن وصف هذه الوظيفة بصيغة خوارزمية أو باستخدام معادلات منطقية، كما يمكن تلخيصها في جدول. يوضح المثال التالي جزءًا من هذا الجدول الخاص ببرنامج تشغيل شاشة عرض سباعية الأجزاء ، والذي يُترجم الشفرة الثنائية لقيم الأرقام العشرية إلى إشارات تُضيء أجزاء الشاشة المعنية.

 أجزاء رمز الرقم ABCDEFG 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 FB 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 EC 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

تبدأ عملية التنفيذ بمرحلة تقليل المنطق ، والتي سيتم وصفها أدناه، من أجل تبسيط جدول الوظائف عن طريق دمج المصطلحات المنفصلة في مصطلحات أكبر تحتوي على عدد أقل من المتغيرات.

بعد ذلك، يمكن تقسيم النتيجة المُصغّرة إلى أجزاء أصغر من خلال عملية تحليل، ثم يتم ربطها في النهاية بخلايا المنطق الأساسية المتاحة في التقنية المستهدفة. تُعرف هذه العملية عادةً باسم تحسين المنطق . [ 9 ]

أساليب التصغير الكلاسيكية

يُعدّ تبسيط الدوال المنطقية يدويًا باستخدام خرائط كارنو الكلاسيكية عمليةً شاقةً ومملةً وعرضةً للأخطاء. فهي غير مناسبة لأكثر من ستة متغيرات إدخال، وعملية فقط لأربعة متغيرات كحد أقصى، بينما يُعدّ تقاسم حدود الضرب لدوال إخراج متعددة أكثر صعوبةً. [ 10 ] علاوةً على ذلك، لا يُمكن أتمتة هذه الطريقة باستخدام برنامج حاسوبي. مع ذلك، ولأنّ الدوال المنطقية الحديثة لا تقتصر عمومًا على هذا العدد القليل من المتغيرات، ولأنّ تكلفة التنفيذ اليدوي للدوال المنطقية ومخاطر ارتكاب الأخطاء باهظة، فقد أصبح استخدام الحواسيب ضروريًا.

كانت الطريقة الجدولية، التي طورها ويلارد كواين وإدوارد ماكلوسكي ، أول طريقة بديلة شائعة . تبدأ هذه الطريقة بجدول الحقيقة لمجموعة من الدوال المنطقية، ومن خلال دمج الحدود الدنيا التي تكون فيها الدوال فعالة (غطاء التشغيل) أو التي تكون فيها قيمة الدالة غير ذات صلة ( غطاء عدم الاكتراث )، يتم تكوين مجموعة من المُضمَّنات الأولية . وأخيرًا، يتم اتباع إجراء منهجي لإيجاد أصغر مجموعة من المُضمَّنات الأولية التي يمكن من خلالها تحقيق دوال الإخراج. [ 11 ] [ 12 ]

على الرغم من أن خوارزمية كوين-ماكلوسكي مناسبة جدًا للتطبيق في برامج الحاسوب، إلا أن نتائجها لا تزال غير فعالة من حيث وقت المعالجة واستهلاك الذاكرة. فإضافة متغير إلى الدالة تُضاعف تقريبًا كليهما، لأن طول جدول الحقيقة يزداد أُسّيًا مع عدد المتغيرات. وتظهر مشكلة مماثلة عند زيادة عدد دوال الإخراج في وحدة الدوال التوافقية. ونتيجةً لذلك، فإن طريقة كوين - ماكلوسكي عملية فقط للدوال ذات عدد محدود من متغيرات الإدخال ودوال الإخراج.

خوارزمية الإسبريسو

يتبع خوارزمية ESPRESSO، التي طورها برايتون وآخرون في جامعة كاليفورنيا، بيركلي ، نهجًا مختلفًا لهذه المسألة. [ 4 ] [ 3 ] وهي خوارزمية فعالة من حيث الموارد والأداء، تهدف إلى حل مشكلة تقليل المنطق ثنائي المستوى الخالية من المخاطر الاستدلالية. [ 13 ]

بدلاً من توسيع دالة منطقية إلى حدود دنيا، يتعامل البرنامج مع "مكعبات" تمثل حدود الضرب في أغطية التشغيل (ON) والتيار المستمر (DC) والإيقاف (OFF) بشكل تكراري. على الرغم من أن نتيجة التصغير ليست مضمونة لتكون الحد الأدنى العالمي ، إلا أنها تُقارب ذلك بدقة عالية عمليًا، مع ضمان خلو الحل دائمًا من التكرار . بالمقارنة مع الطرق الأخرى، تُعد هذه الطريقة أكثر كفاءة بشكل ملحوظ، حيث تُقلل من استخدام الذاكرة ووقت الحساب بشكل كبير. يعكس اسمها طريقة تحضير فنجان قهوة طازجة على الفور. لا توجد قيود تُذكر على عدد المتغيرات ودوال الإخراج وحدود الضرب في كتلة دالة توافقية. بشكل عام، يمكن التعامل بسهولة مع عشرات المتغيرات وعشرات دوال الإخراج.

يُدخل برنامج ESPRESSO جدول وظائف يحدد الوظائف المطلوبة؛ والنتيجة هي جدول مُصغّر يصف إما تشغيل الغطاء أو إيقافه، وذلك حسب الخيارات المُحددة. افتراضيًا، تُشارك حدود الضرب قدر الإمكان بين وظائف الإخراج المختلفة، ولكن يُمكن توجيه البرنامج للتعامل مع كل وظيفة إخراج على حدة. يُتيح ذلك تنفيذًا فعالًا في مصفوفات منطقية ثنائية المستوى مثل مصفوفة المنطق القابلة للبرمجة ( PLA ) أو مصفوفة المنطق القابلة للبرمجة ( PAL ).

أثبتت خوارزمية ESPRESSO نجاحًا باهرًا لدرجة أنها أُدمجت كخطوة قياسية لتقليل حجم الدوال المنطقية في جميع أدوات توليف المنطق الحديثة تقريبًا . ولتنفيذ دالة في منطق متعدد المستويات، تُحسَّن نتيجة التقليل عن طريق التحليل إلى عوامل، ثم تُسقط على خلايا المنطق الأساسية المتاحة في التقنية المستهدفة، سواءً كانت مصفوفة بوابات قابلة للبرمجة ميدانيًا (FPGA) أو دائرة متكاملة خاصة بالتطبيقات (ASIC).

برمجة

إسبريسو

يتوفر برنامج ESPRESSO الأصلي كشفرة مصدرية بلغة C على موقع جامعة كاليفورنيا، بيركلي . وكان آخر إصدار له هو الإصدار 2.3 بتاريخ 1988. [ 14 ] أما برنامج ESPRESSO-AB و EQNTOTT (تحويل المعادلة إلى جدول الحقيقة)، وهو نسخة محدثة من ESPRESSO لأنظمة POSIX الحديثة ، فيتوفر بصيغة ملف توزيعة دبيان لينكس (.deb) بالإضافة إلى الشفرة المصدرية بلغة C. وكان آخر إصدار له هو الإصدار 9.0 بتاريخ 2008. [ 15 ] وقد تم نقل نسخة متوافقة مع نظام ويندوز ولغة C++20 إلى منصة GitHub في عام 2020. [ 16 ]

منطق الجمعة

Logic Friday هو برنامج مجاني لنظام ويندوز يوفر واجهة رسومية لبرنامج Espresso، بالإضافة إلى misII ، وهي وحدة أخرى ضمن حزمة Berkeley Octtools. يُمكّن Logic Friday المستخدمين من إدخال دالة منطقية على شكل جدول حقيقة، أو معادلة، أو مخطط بوابات، ثم تبسيط الدالة، وعرض النتائج في كلا التمثيلين الآخرين. آخر إصدار كان الإصدار 1.1.4 بتاريخ 2012. [ 17 ]

مدونة مصغرة

Minilog هو برنامج مجاني لنظام ويندوز يوفر تبسيط الدوائر المنطقية باستخدام خوارزمية Espresso. يستطيع البرنامج إنشاء تصميم بوابة ثنائية المستوى لوحدة وظائف توافقية تصل إلى 40 مدخلاً ومخرجاً، أو لآلة حالة متزامنة تصل إلى 256 حالة. وهو جزء من حزمة تصميم Publicad التعليمية.

إسبريسو-IISOJS

ESPRESSO-IISOJS هي تطبيق جافا سكريبت لـ ESPRESSO-II للدوال ذات المخرج الواحد. تستخدم هذه المكتبة تقنية نشر الوحدة كتقنية تحسين إضافية لمختلف الخوارزميات في ESPRESSO-II القائمة على نموذج التكرار الأحادي. ومن الإضافات الأخرى إمكانية التحكم في وقت رفع القيم الحرفية، وهو ما يمكن استغلاله لتقليل دوال منطق كلين بشكل فعال . [ 18 ]

باي إي دي إيه

Python EDA هي مكتبة بايثون لأتمتة تصميم الإلكترونيات، وتتضمن روابط لتقنية تقليل منطق Espresso. [ 19 ]

مراجع

  1. ↑ هايز، جون باتريك (1993). تصميم المنطق الرقمي . أديسون ويسلي . ISBN 0-201-15461-7.
  2. ↑ برايتون، روبرت كينغ؛ هاكتل، غاري د.؛ هيماشاندرا، لين أ.؛ نيوتن، أ. ريتشارد؛ سانجيوفاني-فينسنتيلي، ألبرتو لويجي م. (1982). "مقارنة استراتيجيات تبسيط المنطق باستخدام ESPRESSO: حزمة برامج APL لمحاكاة المنطق المجزأ". وقائع ندوة IEEE الدولية للدوائر والأنظمة، 1982. نيويورك، نيويورك، الولايات المتحدة الأمريكية: IEEE : 42-48 .
  3. ١ ٢ "روبرت ك. برايتون؛ أستاذ فخري، أستاذ في كلية الدراسات العليا" . جامعة كاليفورنيا، بيركلي . ٢٠١٨-٠٩-٢٣. مؤرشف من الأصل في ٢٠١٨-٠٩-٢٣ . تم الاسترجاع في ٢٠١٨-٠٩-٢٣ .
  4. 1 2 برايتون، روبرت كينج؛ هاكتل، جاري د.؛ ماكمولين، كورتيس تريسي ؛ سانجيوفاني-فينسنتيلي، ألبرتو لويجي م. (1984). خوارزميات تبسيط المنطق لتوليف الدوائر المتكاملة واسعة النطاق (الطبعة التاسعة، 2000، الطبعة الأولى). بوسطن، ماساتشوستس، الولايات المتحدة الأمريكية: دار نشر كلوير الأكاديمية . ISBN  0-89838-164-9.
  5. 1 2 بولتون، مارتن (1990). "4.3.3 ESPRESSO-II". كُتب في جامعة بريستول، بريستول، المملكة المتحدة. في داغليس، إريك ل. (محرر). تصميم الأنظمة الرقمية باستخدام المنطق القابل للبرمجة . سلسلة هندسة الأنظمة الإلكترونية (الطبعة الأولى ). ووكينغهام، المملكة المتحدة: دار نشر أديسون-ويسلي المحدودة. الصفحات 112، 115-116 . ISBN   0-201-14545-6LCCN 90000007 . ISBN​  978-0-201-14545-8ark:/13960/t2f83p38r . تم الاطلاع عليه بتاريخ 17 أبريل 2021 .
  6. ↑ روديل، ريتشارد ل. (5 يونيو 1986). "تقليل قيم المنطق المتعدد لتوليف PLA" (ملف PDF) . مذكرة رقم UCB/ERL M86-65 . بيركلي، الولايات المتحدة الأمريكية.
  7. ↑ روديل، ريتشارد ل.؛ سانجيوفاني-فينسنتيلي، ألبرتو لويجي م. (سبتمبر 1987). "تقليل منطق القيم المتعددة لتحسين مصفوفة المنطق القابلة للبرمجة". معاملات IEEE في التصميم بمساعدة الحاسوب . 6 (5): 727-750 . doi : 10.1109/TCAD.1987.1270318 . S2CID 13525177 . 
  8. ↑ روديل، ريتشارد ل. (أبريل 1989). توليف المنطق لتصميم الدوائر المتكاملة واسعة النطاق (أطروحة دكتوراه). بيركلي: جامعة كاليفورنيا .(إسبريسو-إكزاكت)
  9. ↑De Micheli, Giovanni (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill Science Engineering. ISBN 0-07-016333-2.
  10. ↑Lewin, Douglas (1985). Design of Logic Systems. Van Nostrand (UK). ISBN 0-442-30606-7.
  11. ↑Katz, Randy Howard; Borriello, Gaetano (1994). Contemporary Logic Design. The Benjamin/Cummings Publishing Company. ISBN 0-8053-2703-7.
  12. ↑Lala, Parag K. (1996). Practical Digital Logic Design and Testing. Prentice Hall. ISBN 0-02-367171-8.
  13. ↑Theobald, Michael; Nowick, Steven M. (1998). Fast Heuristic and Exact Algorithms for Two-Level Hazard-Free Logic Minimization. Columbia University (Report). doi:10.7916/D8N58V58. Retrieved 2021-10-04.
  14. ↑"Espresso C source code (1988)". University of California, Berkeley. 2018-09-21. Archived from the original on 2018-09-21. Retrieved 2018-09-21.
  15. ↑"Espresso-eb / eqntott C source code and program (2008)". Google Code. 2018-09-21. Archived from the original on 2018-09-21. Retrieved 2018-09-21.
  16. ↑"Espresso heuristic logic minimizer C++20 Windows source". GitHub.
  17. ↑"Logic Friday program (2012)". sontrak. 2018-09-21. Archived from the original on 2013-10-22. Retrieved 2018-09-21.
  18. ↑"Espresso-IISOJS". GitHub.
  19. ↑"Python library for electronic design automation". Read the Docs.

Further reading

  • Eschermann, Bernhard (May 1993). Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken[Functional design of digital circuits - Methods and CAD techniques]. Springer-Lehrbuch (in German). Springer-Verlag. pp. 136–137, 140–141. ISBN 9-783540-56788-2. ISBN 3-540-56788-7.