एस्प्रेसो ह्यूरिस्टिक लॉजिक मिनिमाइज़र

From alpha
Jump to navigation Jump to search

एस्प्रेसो लॉजिक मिनिमाइज़र एक कंप्यूटर प्रोग्राम है जो डिजिटल तर्क द्वार सर्किट की जटिलता को कुशलतापूर्वक कम करने के लिए अनुमानी और विशिष्ट कलन विधि का उपयोग करता है।[1]ESPRESSO-I को मूल रूप से IBM में रॉबर्ट के. ब्रेटन और अन्य द्वारा विकसित किया गया था। 1982 में.[2][3]और 1984 में एस्प्रेसो-II के रूप में सुधार किया गया।[4][5]रिचर्ड एल. रुडेल ने बाद में 1986 में एस्प्रेसो-एमवी संस्करण प्रकाशित किया[6]और 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 1 0 0 1 | |
   4 0100 0 1 1 0 0 1 1 -जी-
   5 0101 1 0 1 1 0 1 1 | |
   6 0110 1 0 1 1 1 1 1 ई सी
   7 0111 1 1 1 0 0 0 0 | |
   8 1000 1 1 1 1 1 1 1 1 -डी-
   9 1001 1 1 1 1 0 1 1

</पूर्व>

कार्यान्वयन प्रक्रिया एक तर्क न्यूनीकरण चरण के साथ शुरू होती है, जिसका वर्णन नीचे किया गया है, ताकि अलग-अलग शब्दों को कम चर वाले बड़े शब्दों में जोड़कर फ़ंक्शन तालिका को सरल बनाया जा सके।

इसके बाद, न्यूनतम परिणाम को कारकीकरण प्रक्रिया द्वारा छोटे भागों में विभाजित किया जा सकता है और अंततः लक्ष्य प्रौद्योगिकी के उपलब्ध बुनियादी तर्क कोशिकाओं पर मैप किया जाता है। इस ऑपरेशन को आमतौर पर तर्क अनुकूलन के रूप में जाना जाता है।[9]


शास्त्रीय न्यूनतमकरण विधियाँ

शास्त्रीय कर्णघ मानचित्रों का उपयोग करके हाथ से बूलियन कार्यों को कम करना एक श्रमसाध्य, थकाऊ और त्रुटि प्रवण प्रक्रिया है। यह छह से अधिक इनपुट वेरिएबल के लिए उपयुक्त नहीं है और केवल चार वेरिएबल तक के लिए व्यावहारिक है, जबकि कई आउटपुट फ़ंक्शंस के लिए उत्पाद शब्द साझा करना और भी कठिन है।[10]इसके अलावा, यह विधि स्वयं को कंप्यूटर प्रोग्राम के रूप में स्वचालित करने की अनुमति नहीं देती है। हालाँकि, चूंकि आधुनिक तर्क फ़ंक्शन आम तौर पर इतनी कम संख्या में चर तक सीमित नहीं होते हैं, जबकि लागत के साथ-साथ त्रुटियां करने का जोखिम तर्क कार्यों के मैन्युअल कार्यान्वयन के लिए निषेधात्मक है, कंप्यूटर का उपयोग अपरिहार्य हो गया है।

लोकप्रिय होने वाली पहली वैकल्पिक विधि विलार्ड वान ऑरमैन क्विन और एडवर्ड जे. मैक्लुस्की द्वारा विकसित सारणीबद्ध विधि थी। तर्क कार्यों के एक सेट के लिए सत्य तालिका से शुरू करना, उन न्यूनतम शब्दों को संयोजित करके जिनके लिए कार्य सक्रिय हैं (ऑन-कवर) या जिनके लिए फ़ंक्शन मान अप्रासंगिक है (परवाह न करें (तर्क)|नहीं करें -केयर-कवर या डीसी-कवर) प्रमुख निहितार्थों का एक सेट बनाया गया है। अंत में, प्रमुख निहितार्थों के सबसे छोटे सेट को खोजने के लिए एक व्यवस्थित प्रक्रिया का पालन किया जाता है जिसके साथ आउटपुट फ़ंक्शन को साकार किया जा सकता है।[11][12]

हालाँकि यह क्विन-मैक्लुस्की एल्गोरिदम कंप्यूटर प्रोग्राम में लागू करने के लिए बहुत उपयुक्त है, लेकिन प्रसंस्करण समय और मेमोरी उपयोग के मामले में परिणाम अभी भी कुशल नहीं है। फ़ंक्शन में एक वेरिएबल जोड़ने से वे दोनों लगभग दोगुना हो जाएंगे, क्योंकि सत्य तालिका की लंबाई चर की संख्या के साथ तेजी से बढ़ती है। एक समान समस्या तब उत्पन्न होती है जब संयोजन फ़ंक्शन ब्लॉक के आउटपुट फ़ंक्शंस की संख्या बढ़ जाती है। परिणामस्वरूप, क्विन-मैकक्लुस्की विधि केवल सीमित संख्या में इनपुट चर और आउटपुट फ़ंक्शन वाले कार्यों के लिए व्यावहारिक है।

एस्प्रेसो एल्गोरिथ्म

ब्रेटन एट अल द्वारा विकसित एस्प्रेसो एल्गोरिदम में इस मुद्दे पर एक अलग दृष्टिकोण अपनाया गया है। कैलिफोर्निया विश्वविद्यालय, बर्कले में।[4][3]यह एक संसाधन और प्रदर्शन कुशल एल्गोरिदम है जिसका उद्देश्य अनुमानी खतरा (तर्क) मुक्त दो-स्तरीय तर्क न्यूनीकरण समस्या को हल करना है।[13]

लॉजिक फ़ंक्शन को मिंटर्म्स में विस्तारित करने के बजाय, प्रोग्राम क्यूब्स में हेरफेर करता है, जो ON-, DC- और OFF- कवर में उत्पाद शर्तों को पुनरावृत्त रूप से दर्शाता है। हालाँकि न्यूनतमकरण परिणाम के वैश्विक न्यूनतम होने की गारंटी नहीं है, व्यवहार में यह बहुत बारीकी से अनुमानित है, जबकि समाधान हमेशा तर्क अतिरेक से मुक्त होता है। अन्य तरीकों की तुलना में, यह अनिवार्य रूप से अधिक कुशल है, जो मेमोरी उपयोग और गणना समय को परिमाण के कई क्रमों तक कम कर देता है। इसका नाम तुरंत एक कप ताज़ी कॉफ़ी बनाने के तरीके को दर्शाता है। संयोजन फ़ंक्शन ब्लॉक के चर, आउटपुट फ़ंक्शंस और उत्पाद शर्तों की संख्या पर शायद ही कोई प्रतिबंध है। सामान्य तौर पर, उदा. दसियों आउटपुट फ़ंक्शंस वाले दसियों वेरिएबल्स को आसानी से निपटाया जाता है।

एस्प्रेसो के लिए इनपुट वांछित कार्यक्षमता की एक फ़ंक्शन तालिका है; परिणाम एक न्यूनतम तालिका है, जो चयनित विकल्पों के आधार पर फ़ंक्शन के ऑन-कवर या ऑफ-कवर का वर्णन करती है। डिफ़ॉल्ट रूप से, उत्पाद शर्तों को कई आउटपुट फ़ंक्शंस द्वारा यथासंभव साझा किया जाएगा, लेकिन प्रोग्राम को प्रत्येक आउटपुट फ़ंक्शंस को अलग से संभालने का निर्देश दिया जा सकता है। यह प्रोग्रामयोग्य तर्क सारणी (प्रोग्रामेबल लॉजिक एरे) या प्रोग्रामयोग्य ऐरे लॉजिक (प्रोग्रामेबल एरे लॉजिक) जैसे दो-स्तरीय लॉजिक एरे में कुशल कार्यान्वयन की अनुमति देता है।

ESPRESSO एल्गोरिथ्म इतना सफल साबित हुआ कि इसे वस्तुतः किसी भी समकालीन तर्क संश्लेषण उपकरण में एक मानक तर्क फ़ंक्शन न्यूनतमकरण चरण के रूप में शामिल किया गया है। बहु-स्तरीय तर्क में एक फ़ंक्शन को लागू करने के लिए, न्यूनतमकरण परिणाम को कारकीकरण द्वारा अनुकूलित किया जाता है और लक्ष्य प्रौद्योगिकी में उपलब्ध बुनियादी तर्क कोशिकाओं पर मैप किया जाता है, चाहे यह क्षेत्र में प्रोग्राम की जा सकने वाली द्वार श्रंखला (एफपीजीए) या एप्लिकेशन-विशिष्ट एकीकृत सर्किट से संबंधित हो ( एएसआईसी)।

सॉफ्टवेयर

एस्प्रेसो

मूल एस्प्रेसो प्रोग्राम कैलिफोर्निया विश्वविद्यालय, बर्कले की वेबसाइट पर सी (प्रोग्रामिंग भाषा) स्रोत कोड के रूप में उपलब्ध है। अंतिम रिलीज़ संस्करण 2.3 दिनांक 1988 था।[14] ESPRESSO-AB और EQNTOTT (सच्चाई तालिका के लिए समीकरण) प्रोग्राम, आधुनिक POSIX सिस्टम के लिए ESPRESSO का एक अद्यतन संस्करण, डेबियन लिनक्स वितरण (.deb) फ़ाइल प्रारूप के साथ-साथ C स्रोत कोड में भी उपलब्ध है। अंतिम रिलीज़ संस्करण 9.0 दिनांक 2008 था।[15]Windows और C++20 संगत को 2020 में GitHub पर पोर्ट किया गया था।[16]


तर्क शुक्रवार

लॉजिक फ्राइडे एक निःशुल्क माइक्रोसॉफ़्ट विंडोज़ प्रोग्राम है जो एस्प्रेसो के साथ-साथ बर्कले ऑक्टटूल्स पैकेज के एक अन्य मॉड्यूल मिसआईआई को एक ग्राफिकल इंटरफ़ेस प्रदान करता है। लॉजिक फ्राइडे के साथ उपयोगकर्ता एक तर्क फ़ंक्शन को सत्य तालिका, समीकरण या गेट आरेख के रूप में दर्ज कर सकते हैं, फ़ंक्शन को छोटा कर सकते हैं, और फिर अन्य दो अभ्यावेदन में परिणाम देख सकते हैं। अंतिम रिलीज़ संस्करण 1.1.4 दिनांक 2012 था।[17]


मिनीलॉग

मिनीलॉग एक निःशुल्क विंडोज़ प्रोग्राम है जो इस एस्प्रेसो एल्गोरिथम का उपयोग करके तर्क न्यूनीकरण प्रदान करता है। यह 40 इनपुट और आउटपुट या 256 राज्यों तक की परिमित-राज्य मशीन के साथ संयोजन फ़ंक्शन ब्लॉक के लिए दो-स्तरीय गेट कार्यान्वयन उत्पन्न करने में सक्षम है। यह Publicad शैक्षिक डिज़ाइन पैकेज का हिस्सा है।

एस्प्रेसो-आईआईएसओजेएस

ESPRESSO-IISOJS एकल आउटपुट फ़ंक्शंस के लिए ESPRESSO-II का जावास्क्रिप्ट कार्यान्वयन है। यह ESPRESSO-II में विभिन्न एल्गोरिदम के लिए एक अतिरिक्त अनुकूलन तकनीक के रूप में इकाई प्रसार को नियोजित करता है जो कि यूनेट रिकर्सिव प्रतिमान पर आधारित हैं। एक और अतिरिक्त यह नियंत्रण की अनुमति दे रहा है कि अक्षर कब बढ़ाए जा सकते हैं जिसका उपयोग तीन-मूल्यवान तर्क#क्लीन और प्रीस्ट तर्क कार्यों को प्रभावी ढंग से कम करने के लिए किया जा सकता है।[18]


संदर्भ

  1. ↑ Hayes, John Patrick (1993). Digital Logic Design. Addison Wesley. ISBN 0-201-15461-7.
  2. ↑ Brayton, Robert King; Hachtel, Gary D.; Hemachandra, Lane A.; Newton, A. Richard; Sangiovanni-Vincentelli, Alberto Luigi M. (1982). "A comparison of logic minimization strategies using ESPRESSO: an APL program package for partitioned logic simulation". Proceedings of the IEEE International Symposium on Circuits and Systems, 1982. New York, New York, USA: IEEE: 42–48.
  3. ↑ 3.0 3.1 "Robert K. Brayton; Professor Emeritus, Professor in the Graduate School". University of California, Berkeley. 2018-09-23. Archived from the original on 2018-09-23. Retrieved 2018-09-23.
  4. ↑ 4.0 4.1 Brayton, Robert King; Hachtel, Gary D.; McMullen, Curtis Tracy; Sangiovanni-Vincentelli, Alberto Luigi M. (1984). Logic Minimization Algorithms for VLSI Synthesis (9th printing 2000, 1st ed.). Boston, Massachusetts, USA: Kluwer Academic Publishers. ISBN 0-89838-164-9.
  5. ↑ 5.0 5.1 Bolton, Martin (1990). "4.3.3 ESPRESSO-II". Written at University of Bristol, Bristol, UK. In Dagless, Erik L. (ed.). Digital Systems Design with Programmable Logic. Electronic Systems Engineering Series (1 ed.). Wokingham, UK: Addison-Wesley Publishers Ltd. pp. 112, 115–116. ISBN 0-201-14545-6. LCCN 90000007. ISBN 978-0-201-14545-8 ark:/13960/t2f83p38r. Retrieved 2021-04-17.
  6. ↑ Rudell, Richard L. (1986-06-05). "Multiple-Valued Logic Minimization for PLA Synthesis" (PDF). Memorandum No. UCB/ERL M86-65. Berkeley, USA.
  7. ↑ Rudell, Richard L.; Sangiovanni-Vincentelli, Alberto Luigi M. (September 1987). "Multiple-valued logic minimization for PLA optimization". IEEE Transactions on Computer-Aided Design. 6 (5): 727–750. doi:10.1109/TCAD.1987.1270318. S2CID 13525177.
  8. ↑ Rudell, Richard L. (April 1989). Logic Synthesis for VLSI Design (PhD thesis). Berkeley: University of California. (ESPRESSO-EXACT)
  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.


अग्रिम पठन

  • Eschermann, Bernhard (May 1993). Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken [Functional design of digital circuits - Methods and CAD techniques]. Springer-Lehrbuch (in Deutsch). Springer-Verlag. pp. 136–137, 140–141. ISBN 9-783540-56788-2. ISBN 3-540-56788-7.
Retrieved from "https://alpha.indicwiki.in/index.php?title=एस्प्रेसो_ह्यूरिस्टिक_लॉजिक_मिनिमाइज़र&oldid=275948"