مُقلِّل المنطق الاستدلالي للإسبريسو
مُقلِّل منطق ESPRESSO هو برنامج كمبيوتر يستخدم خوارزميات استدلالية ومحددة لتقليل تعقيد دوائر البوابات المنطقية الرقمية بكفاءة . [1] تم تطوير ESPRESSO-I في الأصل في IBM بواسطة Robert K. Brayton وآخرون في عام 1982. [2] [3] وتم تحسينه كـ ESPRESSO-II في عام 1984. [4] [5] نشر ريتشارد إل. روديل لاحقًا متغير ESPRESSO-MV في عام 1986 [6] وESPRESSO-EXACT في عام 1987. [7] [8] [5] ألهمت الإسبريسو العديد من المشتقات.
مقدمة
تتكون الأجهزة الإلكترونية من كتل عديدة من الدوائر الرقمية، والتي يؤدي تركيبها معًا المهمة المطلوبة. إن التنفيذ الفعّال للوظائف المنطقية في هيئة دوائر بوابات منطقية (بحيث لا يتم استخدام بوابات منطقية أكثر مما هو ضروري) ضروري لتقليل تكاليف الإنتاج، و/أو تعظيم أداء الجهاز.
تصميم الدوائر المنطقية الرقمية
تتكون جميع الأنظمة الرقمية من وظيفتين أساسيتين: عناصر الذاكرة لتخزين المعلومات، والدوائر التوليفية التي تحول تلك المعلومات. آلات الحالة ، مثل العدادات، هي مزيج من عناصر الذاكرة والدوائر المنطقية التوليفية . نظرًا لأن عناصر الذاكرة عبارة عن دوائر منطقية قياسية، يتم اختيارها من مجموعة محدودة من الدوائر البديلة؛ لذا فإن تصميم الوظائف الرقمية يتلخص في تصميم دوائر البوابة التوليفية وربطها ببعضها البعض.
بشكل عام، يُشار إلى إنشاء الدوائر المنطقية من التجريد عالي المستوى باسم التوليف المنطقي ، والذي يمكن تنفيذه يدويًا، ولكن عادةً ما يتم تطبيق بعض الطرق الرسمية بواسطة الكمبيوتر. في هذه المقالة، تم تلخيص طرق تصميم الدوائر المنطقية المركبة بإيجاز.
نقطة البداية لتصميم دائرة منطقية رقمية هي الوظيفة المطلوبة، والتي يتم الحصول عليها من تحليل النظام ككل، والتي من المفترض أن تكون الدائرة المنطقية جزءًا منها. يمكن صياغة الوصف في شكل خوارزمي أو معادلات منطقية، ولكن يمكن تلخيصه في شكل جدول أيضًا. يوضح المثال أدناه جزءًا من مثل هذا الجدول لبرنامج تشغيل شاشة مكونة من 7 أجزاء يترجم الكود الثنائي لقيم رقم عشري إلى إشارات تتسبب في إضاءة الأجزاء المعنية من الشاشة.
أجزاء رمز الرقم
أ ب ج د هـ
0 0000 1 1 1 1 1 1 0 -أ-
1 0001 0 1 1 0 0 0 0 | |
2 0010 1 1 0 1 1 0 1 فيسبوك
3 0011 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 -د-
9 1001 1 1 1 1 0 1 1
تبدأ عملية التنفيذ بمرحلة تقليل المنطق ، والتي سيتم وصفها أدناه، من أجل تبسيط جدول الوظائف عن طريق الجمع بين المصطلحات المنفصلة في مصطلحات أكبر تحتوي على متغيرات أقل.
بعد ذلك، يمكن تقسيم النتيجة المصغرة إلى أجزاء أصغر من خلال إجراء التحليل إلى عوامل ثم يتم تعيينها في النهاية على الخلايا المنطقية الأساسية المتاحة للتكنولوجيا المستهدفة. يشار إلى هذه العملية عادةً باسم تحسين المنطق . [9]
طرق التقليل الكلاسيكية
إن تقليل الدوال المنطقية يدويًا باستخدام خرائط كارنو الكلاسيكية هي عملية شاقة ومملة وعرضة للخطأ. فهي غير مناسبة لأكثر من ستة متغيرات إدخال وعملية فقط لما يصل إلى أربعة متغيرات، في حين أن مشاركة مصطلح المنتج لوظائف الإخراج المتعددة أصعب في التنفيذ. [10] علاوة على ذلك، فإن هذه الطريقة لا تصلح للأتمتة في شكل برنامج كمبيوتر. ومع ذلك، نظرًا لأن الدوال المنطقية الحديثة لا تقتصر عمومًا على مثل هذا العدد الصغير من المتغيرات، في حين أن التكلفة وكذلك خطر ارتكاب الأخطاء أمر محظور للتنفيذ اليدوي للوظائف المنطقية، فقد أصبح استخدام أجهزة الكمبيوتر أمرًا لا غنى عنه.
كانت الطريقة البديلة الأولى التي أصبحت شائعة هي الطريقة الجدولية التي طورها ويلارد كوين وإدوارد ماكلوسكي . بدءًا من جدول الحقيقة لمجموعة من الدوال المنطقية، من خلال الجمع بين الحدود الدنيا التي تكون الدوال نشطة فيها (غطاء ON) أو التي تكون قيمة الدالة غير ذات صلة بها ( غطاء Don't-Care أو غطاء DC) يتم تكوين مجموعة من المضمنات الأولية . أخيرًا، يتم اتباع إجراء منهجي للعثور على أصغر مجموعة من المضمنات الأولية التي يمكن تحقيق الدوال الناتجة بها. [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 الحديثة، بتنسيق ملف توزيع Debian Linux ( .deb ) بالإضافة إلى كود المصدر C. وكان آخر إصدار هو الإصدار 9.0 بتاريخ 2008. [15] وتم نقل متوافق مع Windows وC++20 إلى GitHub في عام 2020. [16]
المنطق يوم الجمعة
Logic Friday هو برنامج مجاني يعمل بنظام Windows يوفر واجهة رسومية لبرنامج Espresso، بالإضافة إلى misII، وهي وحدة أخرى في حزمة Berkeley Octtools. باستخدام Logic Friday، يمكن للمستخدمين إدخال دالة منطقية كجدول حقيقة أو معادلة أو رسم بياني للبوابة، وتقليص الدالة، ثم عرض النتائج في كل من التمثيلين الآخرين. كان الإصدار الأخير هو الإصدار 1.1.4 بتاريخ 2012. [17]
ميني لوج
Minilog هو برنامج مجاني يعمل بنظام Windows يوفر تقليلًا منطقيًا من خلال استغلال خوارزمية Espresso هذه. وهو قادر على إنشاء تنفيذ بوابة من مستويين لكتلة دالة تركيبية تحتوي على ما يصل إلى 40 مدخلًا ومخرجًا أو آلة حالة متزامنة تحتوي على ما يصل إلى 256 حالة. وهو جزء من حزمة التصميم التعليمي Publicad .
إسبريسو-IISOJS
ESPRESSO-IISOJS هو تنفيذ JavaScript لـ ESPRESSO-II لوظائف الإخراج الفردية. إنه يستخدم انتشار الوحدة كتقنية تحسين إضافية للخوارزميات المختلفة في ESPRESSO-II التي تعتمد على النموذج التكراري unate. إضافة أخرى هي السماح بالتحكم في متى يمكن رفع القيم الحرفية والتي يمكن استغلالها لتقليل وظائف منطق Kleene بشكل فعال . [18]
مراجع
- ^ هايز، جون باتريك (1993). التصميم المنطقي الرقمي . أديسون ويسلي . ISBN 0-201-15461-7.
- ^ برايتون، روبرت كينج؛ هاتشتيل، جاري د؛ هيماشاندرا، لين أ؛ نيوتن، أ. ريتشارد؛ سانجيوفاني فينسنتيلي، ألبرتو لويجي م. (1982). "مقارنة بين استراتيجيات تقليل المنطق باستخدام ESPRESSO: حزمة برنامج APL لمحاكاة المنطق المجزأ". وقائع ندوة معهد مهندسي الكهرباء والإلكترونيات الدولية حول الدوائر والأنظمة، 1982. نيويورك، نيويورك، الولايات المتحدة الأمريكية: معهد مهندسي الكهرباء والإلكترونيات : 42-48.
- ^ "روبرت ك. برايتون؛ أستاذ فخري، أستاذ في كلية الدراسات العليا". جامعة كاليفورنيا، بيركلي . 2018-09-23. مؤرشف من الأصل في 2018-09-23 . تم الاسترجاع في 2018-09-23 .
- ^ ab Brayton, Robert King; Hachtel, Gary D.; McMullen, Curtis Tracy ; Sangiovanni-Vincentelli, Alberto Luigi M. (1984). Logic Minimization Algorithms for VLSI Synthesis (الطبعة التاسعة 2000، الطبعة الأولى). بوسطن، ماساتشوستس، الولايات المتحدة الأمريكية: Kluwer Academic Publishers . ISBN 0-89838-164-9.
- ^ ab Bolton, Martin (1990). "4.3.3 ESPRESSO-II". كتب في جامعة بريستول، بريستول، المملكة المتحدة. في Dagless, Erik L. (محرر). تصميم الأنظمة الرقمية باستخدام المنطق القابل للبرمجة. سلسلة هندسة الأنظمة الإلكترونية (طبعة واحدة). ووكينجهام، المملكة المتحدة: Addison-Wesley Publishers Ltd. ص 112، 115-116. ISBN 0-201-14545-6. LCCN 90000007. ISBN 978-0-201-14545-8 ark:/13960/t2f83p38r . تم الاسترجاع في 2021-04-17 .
- ^ Rudell, Richard L. (1986-06-05). "Multiple-Valued Logic Minimization for PLA Synthesis" (PDF) . مذكرة رقم UCB/ERL M86-65 . بيركلي، الولايات المتحدة الأمريكية.
- ^ Rudell, Richard L.; Sangiovanni-Vincentelli, Alberto Luigi M. (سبتمبر 1987). "تقليل القيمة المنطقية المتعددة لتحسين PLA". معاملات معهد مهندسي الكهرباء والإلكترونيات للتصميم بمساعدة الكمبيوتر . 6 (5): 727–750. doi :10.1109/TCAD.1987.1270318. S2CID 13525177.
- ^ Rudell, Richard L. (أبريل 1989). Logic Synthesis for VLSI Design (أطروحة دكتوراه). بيركلي: جامعة كاليفورنيا .(إسبرسو-إكساكت)
- ^ دي ميشيلي، جيوفاني (1994). تركيب وتحسين الدوائر الرقمية . ماكجرو هيل للعلوم والهندسة . رقم ISBN 0-07-016333-2.
- ^ لوين، دوغلاس (1985). تصميم الأنظمة المنطقية . فان نوستراند (المملكة المتحدة). رقم ISBN 0-442-30606-7.
- ^ كاتز، راندي هوارد ؛ بوريلو، جيتانو (1994). التصميم المنطقي المعاصر. شركة بنيامين/كومينجز للنشر . رقم ISBN 0-8053-2703-7.
- ^ لالا، باراج ك. (1996). التصميم العملي للمنطق الرقمي والاختبار. برنتيس هول . رقم ISBN 0-02-367171-8.
- ^ ثيوبالد، مايكل؛ نوفيك، ستيفن م. (1998). خوارزميات سريعة ودقيقة لتقليل المخاطر على المستويين. جامعة كولومبيا (تقرير). doi : 10.7916/D8N58V58 . تم الاسترجاع في 2021-10-04 .
- ^ "Espresso C source code (1988)". جامعة كاليفورنيا، بيركلي . 2018-09-21. مؤرشف من الأصل في 2018-09-21 . تم الاسترجاع في 2018-09-21 .
- ^ "Espresso-eb / eqntott C source code and program (2008)". Google Code . 2018-09-21. مؤرشف من الأصل في 2018-09-21 . تم الاسترجاع 2018-09-21 .
- ^ "مصدر برنامج Espresso heuristic logic reduction في نظام التشغيل Windows C++20". GitHub .
- ^ "برنامج الجمعة المنطقية (2012)". سونتراك . 2018-09-21. مؤرشف من الأصل في 2013-10-22 . استرجاع 2018-09-21 .
- ^ "Espresso-IISOJS". GitHub .
قراءة إضافية
- إيشيرمان ، بيرنهارد (مايو 1993). Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken [ التصميم الوظيفي للدوائر الرقمية - الأساليب وتقنيات CAD ]. سبرينغر ليهربوخ (في المانيا). سبرينغر-فيرلاغ . ص 136-137، 140-141. رقم ISBN 9-783540-56788-2. ISBN 3-540-56788-7 .
