तर्क अनुकूलन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Process in digital electronics and integrated circuit design}}
{{short description|Process in digital electronics and integrated circuit design}}
{{other uses|Minimisation (disambiguation){{!}}Minimisation}}
{{other uses|न्यूनीकरण (बहुविकल्पी){{!}}न्यूनीकरण}}
लॉजिक ऑप्टिमाइज़ेशन या अधिक निर्दिष्ट बाधाओं के अनुसार निर्दिष्ट [[तर्क सर्किट]] के समतुल्य प्रतिनिधित्व को खोजने की प्रक्रिया है। यह प्रक्रिया [[डिजिटल इलेक्ट्रॉनिक्स]] और [[एकीकृत सर्किट डिजाइन]] में लागू [[तर्क संश्लेषण]] का हिस्सा है।


सामान्यतः, सर्किट पूर्वनिर्धारित प्रतिक्रिया विलंब को पूरा करने वाले न्यूनतम चिप क्षेत्र तक सीमित होता है। किसी दिए गए सर्किट के लॉजिक ऑप्टिमाइज़ेशन का लक्ष्य सबसे छोटा लॉजिक सर्किट प्राप्त करना है जो मूल के समान मानों का मूल्यांकन करता है।<ref name="Maxfield_2008"/>समान कार्य वाला छोटा सर्किट सस्ता है,<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018"/>कम जगह लेता है, बिजली दक्षता, कम विलंबता है, और एकीकृत सर्किट पर धातु संरचनाओं के नैनो-स्केल स्तर पर मौजूद अप्रत्याशित [[क्रॉसस्टॉक]] | क्रॉस-टॉक, [[खतरा (तर्क)]], और अन्य मुद्दों के जोखिम को कम करता है।
'''तर्क अनुकूलन''' या अधिक निर्दिष्ट बाधाओं के अनुसार निर्दिष्ट [[तर्क सर्किट|तर्क परिपथ]] के समतुल्य प्रतिनिधित्व को खोजने की प्रक्रिया है। यह प्रक्रिया [[डिजिटल इलेक्ट्रॉनिक्स]] और [[एकीकृत सर्किट डिजाइन|एकीकृत परिपथ डिजाइन]] में लागू की जाने वाली [[तर्क संश्लेषण]] का विशिष्ट भाग है।


[[बूलियन बीजगणित]] के संदर्भ में, जटिल [[बूलियन अभिव्यक्ति]] का अनुकूलन सरल खोजने की प्रक्रिया है, जो मूल्यांकन पर अंततः मूल के समान परिणाम देगा।
सामान्यतः परिपथ पूर्वनिर्धारित प्रतिक्रिया के विलंब को पूरा करने वाले न्यूनतम चिप क्षेत्र तक सीमित होता है। किसी दिए गए परिपथ के तर्क अनुकूलन का लक्ष्य उसके सबसे छोटे तार्किक परिपथ को प्राप्त करना है जो मूल के समान मानों का मूल्यांकन करता है।<ref name="Maxfield_2008"/> समान कार्य वाले छोटे परिपथ सस्ते होते हैं,<ref name="Balasanyan-Aghagulyan-Wuttke-Henke_2018"/> तथा कम जगह भी लेते हैं, इनमें बिजली दक्षता तथा विलंबता भी कम होती हैं, इस प्रकार एकीकृत परिपथ पर धातु संरचनाओं के नैनो-स्केल के लिए इसके स्तर पर निहित अप्रत्याशित [[क्रॉसस्टॉक]] या क्रॉस-टॉक, [[खतरा (तर्क)|तार्किक खतरा]], और अन्य विवादों के खतरे को कम करता है।
 
[[बूलियन बीजगणित]] के संदर्भ में, जटिल [[बूलियन अभिव्यक्ति]] का अनुकूलन सरल खोजने की प्रक्रिया पर निर्भर करता हैं, जो मूल्यांकन पर अंततः इसके मौलिक मान के समान परिणाम देता हैं।


== प्रेरणा ==
== प्रेरणा ==
एक जटिल [[विद्युत सर्किट]] (अर्थात् [[तर्क द्वार]]्स जैसे कई तत्वों के साथ एक) होने में समस्या यह है कि प्रत्येक तत्व इसके कार्यान्वयन में भौतिक स्थान लेता है और अपने आप में उत्पादन करने के लिए समय और पैसा खर्च करता है। एकीकृत परिपथों में जटिल तर्क के क्षेत्र को कम करने के लिए सर्किट न्यूनीकरण तर्क अनुकूलन का रूप हो सकता है।
जटिल [[विद्युत सर्किट|विद्युत परिपथ]] (अर्थात् [[तर्क द्वार|तर्क]] जैसे कई तत्वों के साथ) होने में समस्या यह है कि प्रत्येक तत्व इसके कार्यान्वयन में भौतिक स्थान लेता है और अपने आप में उत्पादन करने के लिए समय और पैसा खर्च करता है। एकीकृत परिपथों में जटिल तर्क के क्षेत्र को कम करने के लिए परिपथ न्यूनीकरण तर्क अनुकूलन का रूप हो सकता है।
 
तर्क संश्लेषण के आगमन के साथ, [[इलेक्ट्रॉनिक डिजाइन स्वचालन]] (EDA) उद्योग द्वारा सामना की जाने वाली सबसे बड़ी चुनौतियों में से दिए गए डिज़ाइन विवरण का सबसे सरल सर्किट प्रतिनिधित्व खोजना था।<ref group="nb" name="NB_Netlist"/> जबकि दो-स्तरीय लॉजिक ऑप्टिमाइज़ेशन क्विन-मैकक्लुस्की एल्गोरिथम के रूप में लंबे समय से मौजूद था, बाद में [[एस्प्रेसो हेयुरिस्टिक लॉजिक मिनिमाइज़र]], तेजी से सुधार चिप घनत्व, और सर्किट विवरण के लिए [[हार्डवेयर विवरण भाषा]]ओं को व्यापक रूप से अपनाते हुए[[दो-स्तरीय तर्क अनुकूलन]] को औपचारिक रूप दिया। [[तर्क शुक्रवार]] (ग्राफ़िकल इंटरफ़ेस), मिनिलॉग और ESPRESSO-IISOJS (बहु-मूल्यवान लॉजिक) सहित डोमेन आज भी मौजूद है।<ref>{{Cite journal |last=Theobald |first=M. |last2=Nowick |first2=S. M. |date=November 1998 |title=Fast heuristic and exact algorithms for two-level hazard-free logic minimization |url=https://academiccommons.columbia.edu/doi/10.7916/D8N58V58/download |journal=IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |volume=17 |issue=11 |pages=1130–1147 |doi=10.1109/43.736186}}</ref>
 


== तरीके ==
तर्क संश्लेषण के आगमन के साथ, [[इलेक्ट्रॉनिक डिजाइन स्वचालन]] (EDA) उद्योग द्वारा इनके विरुद्ध सबसे बड़ी चुनौतियों के रूप में सामने आने वाली डिज़ाइन के विवरण का सबसे सरल परिपथ प्रतिनिधित्व खोजना था।<ref group="nb" name="NB_Netlist"/> जबकि दो-स्तरीय तर्क अनुकूलन क्विन-मैकक्लुस्की एल्गोरिथम के रूप में लंबे समय से निहित था, बाद में [[एस्प्रेसो हेयुरिस्टिक लॉजिक मिनिमाइज़र|एस्प्रेसो हेयुरिस्टिक तार्किक न्यूनीकरण]] विधि के कारण तेजी से सुधार के फलस्वरूप चिप घनत्व, और परिपथ विवरण के लिए [[हार्डवेयर विवरण भाषा|हार्डवेयर विवरण भाषाओं]] को व्यापक रूप से निहित करते हुए [[दो-स्तरीय तर्क अनुकूलन]] को औपचारिक रूप दिया गया। [[तर्क शुक्रवार|तार्किक ग्राफिकल इंटरफेस]] , मिनिलॉग और ईएसपीआरईएसएसओ-आईआईएसओजेएस (ESPRESSO-IISOJS) (बहु-मूल्यवान तर्क) सहित इसकी डोमेन को आज भी निहित किया जाता है।<ref>{{Cite journal |last=Theobald |first=M. |last2=Nowick |first2=S. M. |date=November 1998 |title=Fast heuristic and exact algorithms for two-level hazard-free logic minimization |url=https://academiccommons.columbia.edu/doi/10.7916/D8N58V58/download |journal=IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems |volume=17 |issue=11 |pages=1130–1147 |doi=10.1109/43.736186}}</ref>
लॉजिक सर्किट सरलीकरण के तरीके #बूलियन एक्सप्रेशन मिनिमाइज़ेशन पर समान रूप से लागू होते हैं।
== विधि ==
तार्किक परिपथ सरलीकरण की विधियाँ बूलियन एक्सप्रेशन न्यूनीकरण पर समान रूप से लागू होती हैं।


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


सर्किट प्रतिनिधित्व के आधार पर
'''परिपथ प्रतिनिधित्व के आधार पर'''
: दो-स्तरीय तर्क अनुकूलन
: दो-स्तरीय तर्क अनुकूलन
: बहु-स्तरीय तर्क अनुकूलन
: बहु-स्तरीय तर्क अनुकूलन


सर्किट विशेषताओं के आधार पर
'''परिपथ विशेषताओं के आधार पर'''
: अनुक्रमिक तर्क अनुकूलन
: अनुक्रमिक तर्क अनुकूलन
: संयुक्त तर्क अनुकूलन
: संयुक्त तर्क अनुकूलन


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


=== चित्रमय तरीके ===
ग्राफ़िकल विधियाँ तर्क चर और फ़ंक्शन के मान का प्रतिनिधित्व करने वाले आरेख द्वारा आवश्यक तार्किक फ़ंक्शन का प्रतिनिधित्व करती हैं। आरेख में हेरफेर या निरीक्षण करके, बहुत कठिन गणना को समाप्त किया जा सकता है।
दो-स्तरीय तर्क के लिए ग्राफिकल न्यूनीकरण विधियों में सम्मलित हैं:
दो-स्तरीय तर्क के लिए ग्राफिकल न्यूनीकरण विधियों में सम्मलित हैं:
* लियोनहार्ड पी. यूलर (1707-1783) द्वारा [[यूलर आरेख]] (उर्फ यूलेरियन सर्कल) (1768)
* लियोनहार्ड पी. यूलर (1707-1783) द्वारा [[यूलर आरेख]] (उर्फ यूलेरियन सर्कल) (1768)
Line 40: Line 40:


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


मामले के लिए जब बूलियन फ़ंक्शन सर्किट द्वारा निर्दिष्ट किया जाता है (अर्थात, हम न्यूनतम आकार के समतुल्य सर्किट को खोजना चाहते हैं), अनबाउंड सर्किट मिनिमाइज़ेशन समस्या बहुपद पदानुक्रम होने के लिए लंबे समय से अनुमानित थी।<math>\Sigma_2^P</math>समय की जटिलता में पूर्ण (निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में नियतात्मक ट्यूरिंग मशीन पर हल किया जा सकता है), परिणाम अंततः 2008 में सिद्ध हुआ,<ref name="Buchfuhrer_2011"/>किन्तु कर्णघ मानचित्र और क्विन-मैक्लुस्की एल्गोरिथम जैसे प्रभावी अनुमान हैं जो प्रक्रिया को सुविधाजनक बनाते हैं।
इस विवाद पर जब बूलियन फ़ंक्शन परिपथ द्वारा निर्दिष्ट किया जाता है (अर्थात, हम न्यूनतम आकार के समतुल्य परिपथ को खोजना चाहते हैं), इस स्थिति में अनबाउंड परिपथ न्यूनीकरण समस्या बहुपद <math>\Sigma_2^P</math> पर इ के पदानुक्रम होने के लिए लंबे समय से अनुमानित की गई थी। इस प्रकार समय की जटिलता में पूर्ण (निर्णय समस्याओं की जटिलता वर्ग जिसे बहुपद समय में नियतात्मक ट्यूरिंग मशीन पर हल किया जाता है), इस परिणाम को अंततः 2008 में सिद्ध किया गया हैं,<ref name="Buchfuhrer_2011"/> किन्तु कर्णघ मानचित्र और क्विन-मैक्लुस्की एल्गोरिथम जैसे प्रभावी अनुमान हैं जो प्रक्रिया को सुविधाजनक बनाते हैं।


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


* क्विन-मैक्लुस्की एल्गोरिथम
* क्विन-मैक्लुस्की एल्गोरिथम
Line 50: Line 50:


=== इष्टतम बहु-स्तरीय विधियां ===
=== इष्टतम बहु-स्तरीय विधियां ===
बूलियन कार्यों के इष्टतम सर्किट प्रस्तुतियों को खोजने वाली विधियों को अधिकांशतः साहित्य में त्रुटिहीन संश्लेषण के रूप में संदर्भित किया जाता है। कम्प्यूटेशनल जटिलता के कारण, त्रुटिहीन संश्लेषण केवल छोटे बूलियन कार्यों के लिए ट्रैक्टेबल है। हालिया दृष्टिकोण अनुकूलन समस्या को [[संतुष्टि]] समस्या के लिए मानचित्रित करते हैं।<ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism |url=https://si2.epfl.ch/~demichel/publications/archive/2020/winston-exact.pdf |website=EPFL |access-date=7 December 2022}}</ref><ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis for Multi-Level Logic Networks |url=https://si2.epfl.ch/~demichel/graduates/theses/winston.pdf |website=EPFL |access-date=7 December 2022}}</ref> यह SAT सॉल्वर का उपयोग करके इष्टतम सर्किट अभ्यावेदन खोजने की अनुमति देता है।
बूलियन कार्यों के इष्टतम परिपथ प्रस्तुतियों को खोजने वाली विधियों को अधिकांशतः साहित्य में त्रुटिहीन संश्लेषण के रूप में संदर्भित किया जाता है। कम्प्यूटरीकृत जटिलता के कारण, त्रुटिहीन संश्लेषण केवल छोटे बूलियन कार्यों के लिए ट्रैक्टेबल है। वर्तमान दृष्टिकोण अनुकूलन समस्या को [[संतुष्टि]] समस्या के लिए मानचित्रित किया जाता हैं।<ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism |url=https://si2.epfl.ch/~demichel/publications/archive/2020/winston-exact.pdf |website=EPFL |access-date=7 December 2022}}</ref><ref>{{cite web |last1=Haaswijk |first1=Winston |title=SAT-Based Exact Synthesis for Multi-Level Logic Networks |url=https://si2.epfl.ch/~demichel/graduates/theses/winston.pdf |website=EPFL |access-date=7 December 2022}}</ref> यह SAT सॉल्वर का उपयोग करके इष्टतम परिपथ अभ्यावेदन खोजने की अनुमति देता है।


=== [[अनुमानी]] तरीके ===
=== [[अनुमानी]] विधि ===


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


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


यदि हमारे पास दो कार्य हैं F<sub>1</sub> और एफ<sub>2</sub>:
यदि हमारे पास दो कार्य हैं F<sub>1</sub> और F<sub>2</sub>:
: <math>F_1 = AB + AC + AD,\,</math>
: <math>F_1 = AB + AC + AD,\,</math>
: <math>F_2 = A'B + A'C + A'E.\,</math>
: <math>F_2 = A'B + A'C + A'E.\,</math>
Line 66: Line 66:
बहुस्तरीय में कार्यात्मक रूप से समतुल्य प्रतिनिधित्व हो सकता है:
बहुस्तरीय में कार्यात्मक रूप से समतुल्य प्रतिनिधित्व हो सकता है:


: पी = बी + सी।
:: ''P'' = ''B'' + ''C''
:: ''F''<sub>1</sub> = ''AP'' + ''AD''
:: ''F''<sub>2</sub> = ''A'P'' + ''A'E''


: एफ<sub>1</sub> = एपी + एडी।
जबकि यहां स्तरों की संख्या 3 होती हैं, उत्पाद शर्तों और शाब्दिकों की कुल संख्या इस प्रकार  B + C शब्द के बंटवारे के कारण कम हो जाती है।


: एफ<sub>2</sub> = ए<nowiki>'</nowiki>P + A<nowiki>'</nowiki>E.
इस प्रकार हम [[अनुक्रमिक तर्क]] और [[संयोजन तर्क]] के बीच अंतर करते हैं, जिनके व्यवहार को क्रमशः परिमित स्थिति मशीन स्थिति तालिकाओं/आरेखों या बूलियन कार्यों और संबंधों द्वारा वर्णित किया जा सकता है।कॉम्बिनेशन परिपथ को उस समय स्वतंत्र परिपथ के रूप में परिभाषित किया जाता है जो किसी भी आउटपुट को उत्पन्न करने के लिए पिछले इनपुट पर निर्भर नहीं करता है जिसे कॉम्बिनेशन परिपथ कहा जाता है। उदाहरण - [[प्राथमिकता एनकोडर]], [[बाइनरी डिकोडर]], [[डि[[बहुसंकेतक]]]], डेमल्टीप्लेक्सर इत्यादि।


जबकि यहां स्तरों की संख्या 3 है, उत्पाद शर्तों और शाब्दिकों की कुल संख्या कम हो जाती है {{Quantify|date=February 2010}} B + C शब्द के बंटवारे के कारण।
अनुक्रमिक परिपथ वे होते हैं जो घड़ी चक्र पर निर्भर होते हैं और किसी भी आउटपुट को उत्पन्न करने के लिए वर्तमान के साथ-साथ पिछले इनपुट पर निर्भर करते हैं। उदाहरण – [[फ्लिप फ्लॉप]], [[काउंटर (डिजिटल)]] इत्यादि।
 
इसी तरह, हम [[अनुक्रमिक तर्क]] और [[संयोजन तर्क]] के बीच अंतर करते हैं, जिनके व्यवहार को क्रमशः परिमित-राज्य मशीन राज्य तालिकाओं/आरेखों या बूलियन कार्यों और संबंधों द्वारा वर्णित किया जा सकता है।
कॉम्बिनेशन सर्किट को उस समय स्वतंत्र सर्किट के रूप में परिभाषित किया जाता है जो किसी भी आउटपुट को उत्पन्न करने के लिए पिछले इनपुट पर निर्भर नहीं करता है जिसे कॉम्बिनेशन सर्किट कहा जाता है। उदाहरण - [[प्राथमिकता एनकोडर]], [[बाइनरी डिकोडर]], [[डि[[बहुसंकेतक]]]], डेमल्टीप्लेक्सर।
 
अनुक्रमिक सर्किट वे होते हैं जो घड़ी चक्र पर निर्भर होते हैं और किसी भी आउटपुट को उत्पन्न करने के लिए वर्तमान के साथ-साथ पिछले इनपुट पर निर्भर करते हैं। उदाहरण – [[फ्लिप फ्लॉप]], [[काउंटर (डिजिटल)]]।


== उदाहरण ==
== उदाहरण ==
[[File:Circuit-minimization.svg|thumb|300px|मूल और सरलीकृत उदाहरण सर्किट]]जबकि सर्किट को कम करने के कई तरीके हैं, यह उदाहरण है जो बूलियन फ़ंक्शन को कम करता है (या सरल करता है)। सर्किट द्वारा किया गया बूलियन फ़ंक्शन सीधे बीजगणितीय अभिव्यक्ति से संबंधित होता है जिससे फ़ंक्शन कार्यान्वित किया जाता है।<ref name="Mano_2014"/>प्रतिनिधित्व करने के लिए प्रयुक्त सर्किट पर विचार करें <math>(A \wedge \bar{B}) \vee (\bar{A} \wedge B)</math>. यह स्पष्ट है कि इस कथन में दो निषेध, दो संयुग्मन और वियोग का उपयोग किया गया है। इसका मतलब है कि सर्किट बनाने के लिए दो [[इन्वर्टर (लॉजिक गेट)]], दो AND गेट्स और OR गेट की आवश्यकता होगी।
[[File:Circuit-minimization.svg|thumb|300px|मूल और सरलीकृत उदाहरण परिपथ]]जबकि परिपथ को कम करने के कई विधि हैं, यह उदाहरण है जो बूलियन फ़ंक्शन को कम करता है (या सरल करता है)। परिपथ द्वारा किया गया बूलियन फ़ंक्शन सीधे बीजगणितीय अभिव्यक्ति से संबंधित होता है जिससे फ़ंक्शन कार्यान्वित किया जाता है।<ref name="Mano_2014"/> प्रतिनिधित्व करने के लिए प्रयुक्त परिपथ पर विचार करें <math>(A \wedge \bar{B}) \vee (\bar{A} \wedge B)</math>. यह स्पष्ट है कि इस कथन में दो निषेध, दो संयुग्मन और वियोग का उपयोग किया गया है। इसका तात्पर्य है कि परिपथ बनाने के लिए दो [[इन्वर्टर (लॉजिक गेट)|इन्वर्टर (तार्किक गेट)]], दो AND गेट्स और OR गेट की आवश्यकता होती हैं।


बूलियन बीजगणित के नियमों को लागू करके या अंतर्ज्ञान का उपयोग करके सर्किट को सरल (न्यूनतम) किया जा सकता है। चूंकि उदाहरण बताता है कि <math>A</math> सच है जब <math>B</math> झूठा है और इसके विपरीत, कोई यह निष्कर्ष निकाल सकता है कि इसका सीधा सा मतलब है <math>A \neq B</math>. तार्किक द्वारों के संदर्भ में, [[असमानता (गणित)]] का अर्थ केवल XOR द्वार (अनन्य या) है। इसलिए, <math>(A \wedge \bar{B}) \vee (\bar{A} \wedge B) \iff A \neq B</math>. फिर नीचे दिखाए गए दो सर्किट समतुल्य हैं, जैसा कि सत्य तालिका का उपयोग करके जांचा जा सकता है:
बूलियन बीजगणित के नियमों को लागू करके या अंतर्ज्ञान का उपयोग करके परिपथ को सरल (न्यूनतम) किया जा सकता है। चूंकि उदाहरण बताता है कि <math>A</math> ट्रुथ है जब <math>B</math> फाल्स होता है और इसके विपरीत, कोई यह निष्कर्ष निकाल सकता है कि इसका तात्पर्य <math>A \neq B</math> से होता है। तार्किक गेट के संदर्भ में, [[असमानता (गणित)]] का अर्थ केवल XOR गेट के लिए होता है। इसलिए, <math>(A \wedge \bar{B}) \vee (\bar{A} \wedge B) \iff A \neq B</math>. फिर नीचे दिखाए गए दो परिपथ समतुल्य माना जाता हैं, जैसा कि सत्य तालिका का उपयोग करके जांचा जाता है:
{| class=wikitable style=" float: left;"
{| class=wikitable style=" float: left;"
|-
|-
Line 95: Line 92:
| '''T''' || '''T''' || ||  T || F || F              || ''F'' || F              || F || T  || || T || ''F'' || T
| '''T''' || '''T''' || ||  T || F || F              || ''F'' || F              || F || T  || || T || ''F'' || T
|}
|}




Line 103: Line 101:
== यह भी देखें ==
== यह भी देखें ==
* बाइनरी निर्णय आरेख (बीडीडी)
* बाइनरी निर्णय आरेख (बीडीडी)
* परवाह न करने की स्थिति
* जाँच न करने की स्थिति
* प्रधान आरोपित
* मुख् आरोप
* [[सर्किट जटिलता]] - सर्किट जटिलता के अनुमान पर
* [[सर्किट जटिलता|परिपथ जटिलता]] - परिपथ जटिलता के अनुमान पर
* [[समारोह रचना]]
* [[समारोह रचना|फंक्शन रचना]]
* [[समारोह अपघटन]]
* [[समारोह अपघटन|फंक्शन अपघटन]]
* [[गेट का कम उपयोग]]
* [[गेट का कम उपयोग]]
* [[तर्क अतिरेक]]
* [[तर्क अतिरेक]]
* [[हार्वर्ड न्यूनतम चार्ट]] :विकीवर्सिटी:हार्वर्ड चार्ट मेथड|(विकीवर्सिटी) :विकीबुक्स:हार्वर्ड चार्ट मेथड|(विकीबुक्स)
* [[हार्वर्ड न्यूनतम चार्ट]] , हार्वर्ड चार्ट विधि।


== टिप्पणियाँ ==
== टिप्पणियाँ ==

Revision as of 21:25, 21 February 2023

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

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

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

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

प्रेरणा

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

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

विधि

तार्किक परिपथ सरलीकरण की विधियाँ बूलियन एक्सप्रेशन न्यूनीकरण पर समान रूप से लागू होती हैं।

वर्गीकरण

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

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

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

परिपथ विशेषताओं के आधार पर

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

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

ग्राफिकल अनुकूलन की विधियाँ
सारणीबद्ध अनुकूलन की विधियाँ
बीजगणितीय अनुकूलन की विधियाँ

चित्रमय विधि

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

दो-स्तरीय तर्क के लिए ग्राफिकल न्यूनीकरण विधियों में सम्मलित हैं:

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

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

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

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

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