तर्क अनुकूलन

For other uses, see Minimisation.

लॉजिक ऑप्टिमाइज़ेशन एक या अधिक निर्दिष्ट बाधाओं के तहत निर्दिष्ट तर्क सर्किट के समतुल्य प्रतिनिधित्व को खोजने की एक प्रक्रिया है। यह प्रक्रिया डिजिटल इलेक्ट्रॉनिक्स और एकीकृत सर्किट डिजाइन में लागू तर्क संश्लेषण का एक हिस्सा है।

आम तौर पर, सर्किट एक पूर्वनिर्धारित प्रतिक्रिया विलंब को पूरा करने वाले न्यूनतम चिप क्षेत्र तक सीमित होता है। किसी दिए गए सर्किट के लॉजिक ऑप्टिमाइज़ेशन का लक्ष्य सबसे छोटा लॉजिक सर्किट प्राप्त करना है जो मूल के समान मानों का मूल्यांकन करता है।समान कार्य वाला छोटा सर्किट सस्ता है,कम जगह लेता है, बिजली दक्षता, कम विलंबता है, और एक एकीकृत सर्किट पर धातु संरचनाओं के नैनो-स्केल स्तर पर मौजूद अप्रत्याशित क्रॉसस्टॉक | क्रॉस-टॉक, खतरा (तर्क), और अन्य मुद्दों के जोखिम को कम करता है।

बूलियन बीजगणित के संदर्भ में, एक जटिल बूलियन अभिव्यक्ति का अनुकूलन एक सरल एक खोजने की प्रक्रिया है, जो मूल्यांकन पर अंततः मूल के समान परिणाम देगा।

प्रेरणा

एक जटिल विद्युत सर्किट (अर्थात् तर्क द्वार्स जैसे कई तत्वों के साथ एक) होने में समस्या यह है कि प्रत्येक तत्व इसके कार्यान्वयन में भौतिक स्थान लेता है और अपने आप में उत्पादन करने के लिए समय और पैसा खर्च करता है। एकीकृत परिपथों में जटिल तर्क के क्षेत्र को कम करने के लिए सर्किट न्यूनीकरण तर्क अनुकूलन का एक रूप हो सकता है।

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

तरीके

लॉजिक सर्किट सरलीकरण के तरीके #बूलियन एक्सप्रेशन मिनिमाइज़ेशन पर समान रूप से लागू होते हैं।

वर्गीकरण

आज, तर्क अनुकूलन को विभिन्न श्रेणियों में विभाजित किया गया है:

सर्किट प्रतिनिधित्व के आधार पर

दो-स्तरीय तर्क अनुकूलन

बहु-स्तरीय तर्क अनुकूलन

सर्किट विशेषताओं के आधार पर

अनुक्रमिक तर्क अनुकूलन

संयुक्त तर्क अनुकूलन

निष्पादन के प्रकार के आधार पर

ग्राफिकल अनुकूलन के तरीके

सारणीबद्ध अनुकूलन के तरीके

बीजगणितीय अनुकूलन के तरीके

चित्रमय तरीके

ग्राफ़िकल विधियाँ तर्क चर और फ़ंक्शन के मान का प्रतिनिधित्व करने वाले आरेख द्वारा आवश्यक तार्किक फ़ंक्शन का प्रतिनिधित्व करती हैं। आरेख में हेरफेर या निरीक्षण करके, बहुत कठिन गणना को समाप्त किया जा सकता है। दो-स्तरीय तर्क के लिए ग्राफिकल न्यूनीकरण विधियों में शामिल हैं:

• लियोनहार्ड पी. यूलर (1707-1783) द्वारा यूलर आरेख (उर्फ यूलेरियन सर्कल) (1768)

जॉन वेन द्वारा * वेन आरेख (1880) (1834-1923)

• मौरिस कर्णघ द्वारा कर्णघ नक्शा (1953)।

बूलियन अभिव्यक्ति न्यूनीकरण

नीचे सूचीबद्ध बूलियन एक्सप्रेशन न्यूनीकरण (सरलीकरण) के समान तरीकों को सर्किट अनुकूलन पर लागू किया जा सकता है।

मामले के लिए जब बूलियन फ़ंक्शन एक सर्किट द्वारा निर्दिष्ट किया जाता है (अर्थात, हम न्यूनतम आकार के समतुल्य सर्किट को खोजना चाहते हैं), अनबाउंड सर्किट मिनिमाइज़ेशन समस्या बहुपद पदानुक्रम होने के लिए लंबे समय से अनुमानित थी।$\Sigma _{2}^{P}$समय की जटिलता में पूर्ण (निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में नियतात्मक ट्यूरिंग मशीन पर हल किया जा सकता है), एक परिणाम अंततः 2008 में सिद्ध हुआ,लेकिन कर्णघ मानचित्र और क्विन-मैक्लुस्की एल्गोरिथम जैसे प्रभावी अनुमान हैं जो प्रक्रिया को सुविधाजनक बनाते हैं।

बूलियन फ़ंक्शन को कम करने के तरीकों में शामिल हैं:

• क्विन-मैक्लुस्की एल्गोरिथम
• पेट्रिक की विधि

इष्टतम बहु-स्तरीय विधियां

बूलियन कार्यों के इष्टतम सर्किट प्रस्तुतियों को खोजने वाली विधियों को अक्सर साहित्य में सटीक संश्लेषण के रूप में संदर्भित किया जाता है। कम्प्यूटेशनल जटिलता के कारण, सटीक संश्लेषण केवल छोटे बूलियन कार्यों के लिए ट्रैक्टेबल है। हालिया दृष्टिकोण अनुकूलन समस्या को एक संतुष्टि समस्या के लिए मानचित्रित करते हैं। यह SAT सॉल्वर का उपयोग करके इष्टतम सर्किट अभ्यावेदन खोजने की अनुमति देता है।

अनुमानी तरीके

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

दो-स्तरीय बनाम बहु-स्तरीय प्रतिनिधित्व

जबकि सर्किट का दो-स्तरीय सर्किट प्रतिनिधित्व सख्ती से एसओपी (उत्पादों का योग) के संदर्भ में सर्किट के चपटा दृश्य को संदर्भित करता है - जो डिजाइन के प्रोग्राम करने योग्य तर्क सरणी कार्यान्वयन पर अधिक लागू होता है। - एक बहु-स्तरीय प्रतिनिधित्व मनमाने ढंग से जुड़े SOPs, POSs (उत्पाद-के-रकम), कारक रूप आदि के संदर्भ में सर्किट का अधिक सामान्य दृश्य है। तर्क अनुकूलन एल्गोरिदम आमतौर पर या तो संरचनात्मक (SOPs, कारक रूप) पर काम करते हैं या कार्यात्मक (द्विआधारी निर्णय आरेख, बीजगणितीय निर्णय आरेख (ADDs)) सर्किट का प्रतिनिधित्व। सम-ऑफ़-प्रोडक्ट्स (SOP) फॉर्म में, AND गेट्स सबसे छोटी इकाई बनाते हैं और ORs का उपयोग करके एक साथ सिले होते हैं, जबकि योग का उत्पाद (POS) फॉर्म में यह विपरीत होता है। POS फॉर्म में AND गेट्स के तहत OR शब्दों को एक साथ समूहित करने के लिए कोष्ठक की आवश्यकता होती है, क्योंकि OR की AND से कम प्राथमिकता है। एसओपी और पीओएस दोनों फॉर्म सर्किट लॉजिक में अच्छी तरह से अनुवाद करते हैं।

यदि हमारे पास दो कार्य हैं F₁ और एफ₂:

$F_{1}=AB+AC+AD,\,$

$F_{2}=A'B+A'C+A'E.\,$

उपरोक्त 2-स्तरीय प्रतिनिधित्व में सीएमओएस प्रतिनिधि में छह उत्पाद शब्द और 24 ट्रांजिस्टर लगते हैं।

बहुस्तरीय में कार्यात्मक रूप से समतुल्य प्रतिनिधित्व हो सकता है:

पी = बी + सी।

एफ₁ = एपी + एडी।

एफ₂ = ए'P + A'E.

जबकि यहां स्तरों की संख्या 3 है, उत्पाद शर्तों और शाब्दिकों की कुल संख्या कम हो जाती है B + C शब्द के बंटवारे के कारण।

इसी तरह, हम अनुक्रमिक तर्क और संयोजन तर्क के बीच अंतर करते हैं, जिनके व्यवहार को क्रमशः परिमित-राज्य मशीन राज्य तालिकाओं/आरेखों या बूलियन कार्यों और संबंधों द्वारा वर्णित किया जा सकता है। कॉम्बिनेशन सर्किट को उस समय स्वतंत्र सर्किट के रूप में परिभाषित किया जाता है जो किसी भी आउटपुट को उत्पन्न करने के लिए पिछले इनपुट पर निर्भर नहीं करता है जिसे कॉम्बिनेशन सर्किट कहा जाता है। उदाहरण - प्राथमिकता एनकोडर, बाइनरी डिकोडर, [[डिबहुसंकेतक]], डेमल्टीप्लेक्सर।

अनुक्रमिक सर्किट वे होते हैं जो घड़ी चक्र पर निर्भर होते हैं और किसी भी आउटपुट को उत्पन्न करने के लिए वर्तमान के साथ-साथ पिछले इनपुट पर निर्भर करते हैं। उदाहरण – फ्लिप फ्लॉप, काउंटर (डिजिटल)।

उदाहरण

मूल और सरलीकृत उदाहरण सर्किट

जबकि एक सर्किट को कम करने के कई तरीके हैं, यह एक उदाहरण है जो बूलियन फ़ंक्शन को कम करता है (या सरल करता है)। सर्किट द्वारा किया गया बूलियन फ़ंक्शन सीधे बीजगणितीय अभिव्यक्ति से संबंधित होता है जिससे फ़ंक्शन कार्यान्वित किया जाता है।प्रतिनिधित्व करने के लिए प्रयुक्त सर्किट पर विचार करें $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)$. यह स्पष्ट है कि इस कथन में दो निषेध, दो संयुग्मन और एक वियोग का उपयोग किया गया है। इसका मतलब है कि सर्किट बनाने के लिए दो इन्वर्टर (लॉजिक गेट), दो AND गेट्स और एक OR गेट की आवश्यकता होगी।

बूलियन बीजगणित के नियमों को लागू करके या अंतर्ज्ञान का उपयोग करके सर्किट को सरल (न्यूनतम) किया जा सकता है। चूंकि उदाहरण बताता है कि $A$ सच है जब $B$ झूठा है और इसके विपरीत, कोई यह निष्कर्ष निकाल सकता है कि इसका सीधा सा मतलब है $A\neq B$. तार्किक द्वारों के संदर्भ में, असमानता (गणित) का अर्थ केवल एक XOR द्वार (अनन्य या) है। इसलिए, $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B$. फिर नीचे दिखाए गए दो सर्किट समतुल्य हैं, जैसा कि सत्य तालिका का उपयोग करके जांचा जा सकता है:

A	B		(A	∧	B)	∨	(A	∧	B)		A	≠	B
F	F		F	F	T	F	T	F	F		F	F	F
F	T		F	F	F	T	T	T	T		F	T	T
T	F		T	T	T	T	F	F	F		T	T	F
T	T		T	F	F	F	F	F	T		T	F	T

यह भी देखें

• बाइनरी निर्णय आरेख (बीडीडी)
• परवाह न करने की स्थिति
• प्रधान आरोपित
• सर्किट जटिलता - सर्किट जटिलता के अनुमान पर
• समारोह रचना
• समारोह अपघटन
• गेट का कम उपयोग
• तर्क अतिरेक
• हार्वर्ड न्यूनतम चार्ट :विकीवर्सिटी:हार्वर्ड चार्ट मेथड|(विकीवर्सिटी) :विकीबुक्स:हार्वर्ड चार्ट मेथड|(विकीबुक्स)

अग्रिम पठन

• Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). Analysis and Design of Sequential Digital Systems. Macmillan Press. ISBN 0-33319266-4. (146 pages)
• De Micheli, Giovanni (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill. ISBN 0-07-016333-2. (NB. Chapters 7–9 cover combinatorial two-level, combinatorial multi-level, and respectively sequential circuit optimization.)
• Hachtel, Gary D.; Somenzi, Fabio (2006) [1996]. Logic Synthesis and Verification Algorithms. Springer Science & Business Media. ISBN 978-0-387-31005-3.
• Kohavi, Zvi; Jha, Niraj K. (2009). "4–6". Switching and Finite Automata Theory (3rd ed.). Cambridge University Press. ISBN 978-0-521-85748-2.
• Rutenbar, Rob A. Multi-level minimization, Part I: Models & Methods (PDF) (lecture slides). Carnegie Mellon University (CMU). Lecture 7. Archived (PDF) from the original on 2018-01-15. Retrieved 2018-01-15; Rutenbar, Rob A. Multi-level minimization, Part II: Cube/Cokernel Extract (PDF) (lecture slides). Carnegie Mellon University (CMU). Lecture 8. Archived (PDF) from the original on 2018-01-15. Retrieved 2018-01-15.