तर्क अनुकूलन

For other uses, see न्यूनीकरण.

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

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

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

प्रेरणा

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

तर्क संश्लेषण के आगमन के साथ, इलेक्ट्रॉनिक डिजाइन स्वचालन (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₂:

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

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

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

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

P = B + C

F₁ = AP + AD

F₂ = A'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.