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

Revision as of 20:58, 21 February 2023

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

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

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

प्रेरणा

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

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

तरीके

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

वर्गीकरण

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

जबकि सर्किट का दो-स्तरीय सर्किट प्रतिनिधित्व सख्ती से एसओपी (उत्पादों का योग) के संदर्भ में सर्किट के चपटा दृश्य को संदर्भित करता है - जो डिजाइन के प्रोग्राम करने योग्य तर्क सरणी कार्यान्वयन पर अधिक लागू होता है।^{[clarification needed]} - बहु-स्तरीय प्रतिनिधित्व मनमाने ढंग से जुड़े 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 है, उत्पाद शर्तों और शाब्दिकों की कुल संख्या कम हो जाती है^[quantify] B + C शब्द के बंटवारे के कारण।

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

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

उदाहरण

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

जबकि सर्किट को कम करने के कई तरीके हैं, यह उदाहरण है जो बूलियन फ़ंक्शन को कम करता है (या सरल करता है)। सर्किट द्वारा किया गया बूलियन फ़ंक्शन सीधे बीजगणितीय अभिव्यक्ति से संबंधित होता है जिससे फ़ंक्शन कार्यान्वित किया जाता है।^[7]प्रतिनिधित्व करने के लिए प्रयुक्त सर्किट पर विचार करें $(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

यह भी देखें

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

संदर्भ

↑ Maxfield, Clive "Max" (2008-01-01). "Chapter 5: "Traditional" Design Flows". In Maxfield, Clive "Max" (ed.). FPGAs. Instant Access. Burlington: Newnes / Elsevier Inc. pp. 75–106. doi:10.1016/B978-0-7506-8974-8.00005-3. ISBN 978-0-7506-8974-8. Retrieved 2021-10-04.{{cite book}}: CS1 maint: url-status (link)
↑ Balasanyan, Seyran; Aghagulyan, Mane; Wuttke, Heinz-Dietrich; Henke, Karsten (2018-05-16). "Digital Electronics" (PDF). Bachelor Embedded Systems - Year Group. Tempus. DesIRE. Archived (PDF) from the original on 2021-10-04. Retrieved 2021-10-04. (101 pages)
↑ Theobald, M.; Nowick, S. M. (November 1998). "Fast heuristic and exact algorithms for two-level hazard-free logic minimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 17 (11): 1130–1147. doi:10.1109/43.736186.
↑ Buchfuhrer, David; Umans, Christopher (January 2011). "The complexity of Boolean formula minimization" (PDF). Journal of Computer and System Sciences (JCSS). Computer Science Department, California Institute of Technology, Pasadena, California, USA: Elsevier Inc. 77 (1): 142–153. doi:10.1016/j.jcss.2010.06.011. This is an extended version of the conference paper: Buchfuhrer, David; Umans, Christopher (2008). "The Complexity of Boolean Formula Minimization". Proceedings of Automata, Languages and Programming (PDF). pp. 24–35. doi:10.1007/978-3-540-70575-8_3. ISBN 978-3-540-70574-1. Archived (PDF) from the original on 2018-01-14. Retrieved 2018-01-14. {{cite book}}: |work= ignored (help)
↑ Haaswijk, Winston. "SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism" (PDF). EPFL. Retrieved 7 December 2022.
↑ Haaswijk, Winston. "SAT-Based Exact Synthesis for Multi-Level Logic Networks" (PDF). EPFL. Retrieved 7 December 2022.
↑ Mano, M. Morris; Kime, Charles R. (2014). Logic and Computer Design Fundamentals (4th new international ed.). Pearson Education Limited. p. 54. ISBN 978-1-292-02468-4.

अग्रिम पठन

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.

[NB_Netlist-3] The netlist size can be used to measure simplicity.

[Maxfield_2008-1] Maxfield, Clive "Max" (2008-01-01). "Chapter 5: "Traditional" Design Flows". In Maxfield, Clive "Max" (ed.). FPGAs. Instant Access. Burlington: Newnes / Elsevier Inc. pp. 75–106. doi:10.1016/B978-0-7506-8974-8.00005-3. ISBN 978-0-7506-8974-8. Retrieved 2021-10-04.{{cite book}}: CS1 maint: url-status (link)

[Balasanyan-Aghagulyan-Wuttke-Henke_2018-2] Balasanyan, Seyran; Aghagulyan, Mane; Wuttke, Heinz-Dietrich; Henke, Karsten (2018-05-16). "Digital Electronics" (PDF). Bachelor Embedded Systems - Year Group. Tempus. DesIRE. Archived (PDF) from the original on 2021-10-04. Retrieved 2021-10-04. (101 pages)

[4] Theobald, M.; Nowick, S. M. (November 1998). "Fast heuristic and exact algorithms for two-level hazard-free logic minimization". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 17 (11): 1130–1147. doi:10.1109/43.736186.

[Buchfuhrer_2011-5] Buchfuhrer, David; Umans, Christopher (January 2011). "The complexity of Boolean formula minimization" (PDF). Journal of Computer and System Sciences (JCSS). Computer Science Department, California Institute of Technology, Pasadena, California, USA: Elsevier Inc. 77 (1): 142–153. doi:10.1016/j.jcss.2010.06.011. This is an extended version of the conference paper: Buchfuhrer, David; Umans, Christopher (2008). "The Complexity of Boolean Formula Minimization". Proceedings of Automata, Languages and Programming (PDF). pp. 24–35. doi:10.1007/978-3-540-70575-8_3. ISBN 978-3-540-70574-1. Archived (PDF) from the original on 2018-01-14. Retrieved 2018-01-14. {{cite book}}: |work= ignored (help)

[6] Haaswijk, Winston. "SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism" (PDF). EPFL. Retrieved 7 December 2022.

[7] Haaswijk, Winston. "SAT-Based Exact Synthesis for Multi-Level Logic Networks" (PDF). EPFL. Retrieved 7 December 2022.

[Mano_2014-8] Mano, M. Morris; Kime, Charles R. (2014). Logic and Computer Design Fundamentals (4th new international ed.). Pearson Education Limited. p. 54. ISBN 978-1-292-02468-4.

[1]

[2]

[nb 1]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
 {{short description|Process in digital electronics and integrated circuit design}}
 {{other uses|Minimisation (disambiguation){{!}}Minimisation}}
-लॉजिक ऑप्टिमाइज़ेशन एक या अधिक निर्दिष्ट बाधाओं के अनुसार निर्दिष्ट [[तर्क सर्किट]] के समतुल्य प्रतिनिधित्व को खोजने की एक प्रक्रिया है। यह प्रक्रिया [[डिजिटल इलेक्ट्रॉनिक्स]] और [[एकीकृत सर्किट डिजाइन]] में लागू [[तर्क संश्लेषण]] का एक हिस्सा है।
+लॉजिक ऑप्टिमाइज़ेशन या अधिक निर्दिष्ट बाधाओं के अनुसार निर्दिष्ट [[तर्क सर्किट]] के समतुल्य प्रतिनिधित्व को खोजने की प्रक्रिया है। यह प्रक्रिया [[डिजिटल इलेक्ट्रॉनिक्स]] और [[एकीकृत सर्किट डिजाइन]] में लागू [[तर्क संश्लेषण]] का हिस्सा है।
-सामान्यतः, सर्किट एक पूर्वनिर्धारित प्रतिक्रिया विलंब को पूरा करने वाले न्यूनतम चिप क्षेत्र तक सीमित होता है। किसी दिए गए सर्किट के लॉजिक ऑप्टिमाइज़ेशन का लक्ष्य सबसे छोटा लॉजिक सर्किट प्राप्त करना है जो मूल के समान मानों का मूल्यांकन करता है।<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>
@@ Line 42: / Line 42: @@
 नीचे सूचीबद्ध बूलियन एक्सप्रेशन न्यूनीकरण (सरलीकरण) के समान तरीकों को सर्किट अनुकूलन पर लागू किया जा सकता है।
-मामले के लिए जब बूलियन फ़ंक्शन एक सर्किट द्वारा निर्दिष्ट किया जाता है (अर्थात, हम न्यूनतम आकार के समतुल्य सर्किट को खोजना चाहते हैं), अनबाउंड सर्किट मिनिमाइज़ेशन समस्या बहुपद पदानुक्रम होने के लिए लंबे समय से अनुमानित थी।<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 से कम प्राथमिकता है। एसओपी और पीओएस दोनों फॉर्म सर्किट लॉजिक में अच्छी तरह से अनुवाद करते हैं।
+जबकि सर्किट का दो-स्तरीय सर्किट प्रतिनिधित्व सख्ती से एसओपी ([[उत्पादों का योग]]) के संदर्भ में सर्किट के चपटा दृश्य को संदर्भित करता है - जो डिजाइन के [[प्रोग्राम करने योग्य तर्क सरणी]] कार्यान्वयन पर अधिक लागू होता है।{{Clarify|date=February 2010}} - बहु-स्तरीय प्रतिनिधित्व मनमाने ढंग से जुड़े SOPs, POSs (उत्पाद-के-रकम), कारक रूप आदि के संदर्भ में सर्किट का अधिक सामान्य दृश्य है। तर्क अनुकूलन एल्गोरिदम सामान्यतः या तो संरचनात्मक (SOPs, कारक रूप) पर काम करते हैं या कार्यात्मक ([[द्विआधारी निर्णय आरेख]], बीजगणितीय निर्णय आरेख (ADDs)) सर्किट का प्रतिनिधित्व। सम-ऑफ़-प्रोडक्ट्स (SOP) फॉर्म में, AND गेट्स सबसे छोटी इकाई बनाते हैं और ORs का उपयोग करके साथ सिले होते हैं, जबकि [[योग का उत्पाद]] (POS) फॉर्म में यह विपरीत होता है। POS फॉर्म में AND गेट्स के अनुसार OR शब्दों को साथ समूहित करने के लिए कोष्ठक की आवश्यकता होती है, क्योंकि OR की AND से कम प्राथमिकता है। एसओपी और पीओएस दोनों फॉर्म सर्किट लॉजिक में अच्छी तरह से अनुवाद करते हैं।
 यदि हमारे पास दो कार्य हैं F<sub>1</sub> और एफ<sub>2</sub>:
@@ Line 80: / Line 80: @@
 == उदाहरण ==
-[[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;"
 |-

v t e डिजिटल इलेक्ट्रॉनिक्स
घटक	ट्रांजिस्टर प्रतिरोधक प्रारंभ करनेवाला संधारित्र मुद्रित इलेक्ट्रॉनिक्स मुद्रित सर्किट बोर्ड विद्युत सर्किट फ्लिप-फ्लॉप मेमोरी सेल संयुक्त तर्क अनुक्रमिक तर्क तर्क द्वार बूलियन सर्किट एकीकृत सर्किट (आईसी) हाइब्रिड इंटीग्रेटेड सर्किट (एचआईसी) मिश्रित सिग्नल एकीकृत सर्किट तीन आयामी एकीकृत सर्किट (3 डी आईसी) एमिटर-युग्मित तर्क (ईसीएल) इरेज़ेबल प्रोग्रामेबल लॉजिक डिवाइस (EPLD) मैक्रोसेल सरणी प्रोग्राम करने योग्य तर्क सरणी (पीएलए) प्रोग्रामेबल लॉजिक डिवाइस (पीएलडी) प्रोग्राम करने योग्य सरणी तर्क (पाल) जेनेरिक सरणी तर्क (जीएएल) कॉम्प्लेक्स प्रोग्रामेबल लॉजिक डिवाइस (CPLD) फील्ड प्रोग्रामेबल गेट ऐरे (FPGA) फील्ड-प्रोग्रामेबल ऑब्जेक्ट ऐरे (एफपीओए) एप्लिकेशन-विशिष्ट एकीकृत सर्किट (एएसआईसी) टेन्सर प्रोसेसिंग यूनिट (टीपीयू)
लिखित	डिजिटल सिग्नल बूलियन बीजगणित तर्क संश्लेषण कंप्यूटर विज्ञान में तर्क कंप्यूटर आर्किटेक्चर डिजिटल सिग्नल अंकीय संकेत प्रक्रिया सर्किट न्यूनीकरण स्विचिंग सर्किट सिद्धांत गेट समकक्ष
डिजाइन	तर्क संश्लेषण स्थान और मार्ग प्लेसमेंट रूटिंग रजिस्टर-ट्रांसफर लेवल हार्डवेयर विवरण भाषा उच्च स्तरीय संश्लेषण औपचारिक तुल्यता जाँच सिंक्रोनस लॉजिक एसिंक्रोनस लॉजिक परिमित अवस्था मशीन पदानुक्रमित राज्य मशीन
अनुप्रयोग	संगणक धातु सामग्री हार्डवेयर एक्सिलरेशन डिजिटल ऑडियो रेडियो डिजिटल फोटोग्राफी डिजिटल टेलीफोन डिजिटल वीडियो छायांकन टेलीविजन इलेक्ट्रॉनिक साहित्य
डिजाइन मुद्दों	मेटास्टेबिलिटी नाड़ी चलाएं

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 20:58, 21 February 2023

Contents

प्रेरणा