वालेस ट्री: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Efficient hardware implementation of a digital multiplier}} | {{short description|Efficient hardware implementation of a digital multiplier}} | ||
[[File:Wallace tree 8x8 (corrected).svg|alt=|thumb|14 [[आधा योजक]] (दो डॉट्स) और 38 [[पूर्ण योजक]] (थ्री डॉट्स) का उपयोग करते हुए 8x8 आंशिक उत्पाद मैट्रिक्स की 4 लेयर वालेस रिडक्शन। प्रत्येक कॉलम में डॉट्स समान | [[File:Wallace tree 8x8 (corrected).svg|alt=|thumb|14 [[आधा योजक]] (दो डॉट्स) और 38 [[पूर्ण योजक]] (थ्री डॉट्स) का उपयोग करते हुए 8x8 आंशिक उत्पाद मैट्रिक्स की 4 लेयर वालेस रिडक्शन। प्रत्येक कॉलम में डॉट्स समान भार के बिट्स होते हैं।]]वैलेस गुणक एक [[बाइनरी गुणक]] का [[कंप्यूटर हार्डवेयर]] कार्यान्वयन है, डिजिटल परिपथ जो दो पूर्णांकों को गुणा करता है। यह दो संख्याओं के बचे रहने तक चरणों में आंशिक उत्पादों का योग करने के लिए [[योजक (इलेक्ट्रॉनिक्स)]] (वालेस ट्री या वालेस रिडक्शन) के चयन का उपयोग करता है। वालेस गुणक प्रत्येक पटल पर जितना संभव हो उतना कम करते हैं, जबकि दद्दा गुणक ऊपरी पटलों में परिवर्तन को स्थगित करके गेट्स की आवश्यक संख्या को कम करने का प्रयास करते हैं।<ref>{{Cite journal|last=Townsend|first=Whitney J.|last2=Swartzlander|first2=Earl E.|last3=Abraham|first3=Jacob A.|date=2003|title=A comparison of Dadda and Wallace multiplier delays|url=https://ui.adsabs.harvard.edu/abs/2003SPIE.5205..552T/abstract|journal=Advanced Signal Processing Algorithms, Architectures, and Implementations XIII|language=en|volume=5205|pages=552–560|doi=10.1117/12.507012|issn=0277-786X}}</ref> वैलेस गुणक 1964 में ऑस्ट्रेलियाई कंप्यूटर वैज्ञानिक [[क्रिस वालेस (कंप्यूटर वैज्ञानिक)]] द्वारा तैयार किए गए थे।<ref name="Wallace_1964" /> | ||
वालेस ट्री के तीन चरण हैं: | वालेस ट्री के तीन चरण हैं: | ||
# एक तर्क के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करें। | # एक तर्क के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करें। | ||
# पूर्ण और आधे योजक (इलेक्ट्रॉनिक्स) की | # पूर्ण और आधे योजक (इलेक्ट्रॉनिक्स) की पटलों द्वारा आंशिक उत्पादों की संख्या को घटाकर दो कर दें। | ||
# तारों को दो संख्याओं में समूहित करें, और उन्हें पारंपरिक योजक के साथ जोड़ें।<ref name="Bohsali_2010"/> | # तारों को दो संख्याओं में समूहित करें, और उन्हें पारंपरिक योजक के साथ जोड़ें।<ref name="Bohsali_2010"/> | ||
नियमित योजकों के साथ आंशिक उत्पादों को जोड़ने की तुलना में, वालेस ट्री का लाभ इसकी तेज गति है। यह है <math>O(\log n)</math> | नियमित योजकों के साथ आंशिक उत्पादों को जोड़ने की तुलना में, वालेस ट्री का लाभ इसकी तेज गति है। यह है <math>O(\log n)</math> परिवर्तन पटलें, लेकिन प्रत्येक पटल में केवल है <math>O(1)</math> प्रचार देरी। आंशिक उत्पादों के भोले जोड़ की आवश्यकता होगी <math>O(\log^2n)</math> समय। | ||
आंशिक उत्पाद बनाने के रूप में है <math>O(1)</math> और अंतिम जोड़ है <math>O(\log n)</math>, कुल गुणन है <math>O(\log n)</math>जोड़ने से ज्यादा धीमा नहीं है। [[कम्प्यूटेशनल जटिलता सिद्धांत]] के दृष्टिकोण से, वालेस ट्री एल्गोरिथम गुणन को | आंशिक उत्पाद बनाने के रूप में है <math>O(1)</math> और अंतिम जोड़ है <math>O(\log n)</math>, कुल गुणन है <math>O(\log n)</math>जोड़ने से ज्यादा धीमा नहीं है। [[कम्प्यूटेशनल जटिलता सिद्धांत]] के दृष्टिकोण से, वालेस ट्री एल्गोरिथम गुणन को NC<sup>1</sup> वर्ग में रखता है। वालेस ट्री का नकारात्मक पक्ष, आंशिक उत्पादों के साधारण जोड़ की तुलना में बहुत अधिक गेट काउंट है। | ||
ये संगणनाएँ केवल [[गेट देरी]] पर विचार करती हैं और वायर विलंब से निपटती नहीं हैं, जो बहुत महत्वपूर्ण भी हो सकता है। | ये संगणनाएँ केवल [[गेट देरी]] पर विचार करती हैं और वायर विलंब से निपटती नहीं हैं, जो बहुत महत्वपूर्ण भी हो सकता है। | ||
| Line 21: | Line 19: | ||
== विस्तृत विवरण == | == विस्तृत विवरण == | ||
वालेस ट्री लंबे गुणन का रूप है। पहला | वालेस ट्री लंबे गुणन का रूप है। पहला चरण कारक के प्रत्येक अंक (प्रत्येक बिट) को दूसरे के प्रत्येक अंक से गुणा करना है। इस आंशिक उत्पाद में से प्रत्येक का भार इसके कारकों के उत्पाद के बराबर है। अंतिम उत्पाद की गणना इन सभी आंशिक उत्पादों के भारित योग से की जाती है। | ||
पहला | पहला चरण, जैसा कि ऊपर कहा गया है, संख्या के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करना है, जिसे सरल AND गेट के रूप में पूरा किया जाता है, जिसके परिणामस्वरूप <math>n^2</math> बिट्स; बिट्स का आंशिक उत्पाद <math>a_m</math> द्वारा <math>b_n</math> भार है <math>2^{(m+n)}</math> | ||
दूसरे चरण में, परिणामी बिट्स को दो संख्याओं में घटा दिया जाता है; यह निम्नानुसार पूरा किया जाता है: | दूसरे चरण में, परिणामी बिट्स को दो संख्याओं में घटा दिया जाता है; यह निम्नानुसार पूरा किया जाता है: | ||
जब तक समान भार वाले तीन या अधिक तार हों तब तक निम्नलिखित | जब तक समान भार वाले तीन या अधिक तार हों तब तक निम्नलिखित पटल जोड़ें: - | ||
* समान भार वाले कोई भी तीन तार लें और उन्हें पूर्ण योजक में डालें। परिणाम एक ही | * समान भार वाले कोई भी तीन तार लें और उन्हें पूर्ण योजक में डालें। परिणाम एक ही भार का आउटपुट तार होगा और प्रत्येक तीन इनपुट तारों के लिए उच्च भार वाला आउटपुट तार होगा। | ||
* यदि समान | * यदि समान भार के दो तार बचे हैं, तो उन्हें आधे योजक में डालें। | ||
* अगर सिर्फ एक तार बचा है, तो उसे अगली | * अगर सिर्फ एक तार बचा है, तो उसे अगली पटल से जोड़ दें। | ||
तीसरे और अंतिम चरण में, दो परिणामी संख्याएँ एक योजक को खिलाई जाती हैं, जिससे अंतिम उत्पाद प्राप्त होता है। | तीसरे और अंतिम चरण में, दो परिणामी संख्याएँ एक योजक को खिलाई जाती हैं, जिससे अंतिम उत्पाद प्राप्त होता है। | ||
| Line 38: | Line 36: | ||
# पहले हम हर बिट को हर बिट से गुणा करते हैं: | # पहले हम हर बिट को हर बिट से गुणा करते हैं: | ||
#* | #* भार 1 – <math>a_0b_0</math> | ||
#* | #* भार 2 – <math>a_0b_1</math>, <math>a_1b_0</math> | ||
#* | #* भार 4 – <math>a_0b_2</math>, <math>a_1b_1</math>, <math>a_2b_0</math> | ||
#* | #* भार 8 – <math>a_0b_3</math>, <math>a_1b_2</math>, <math>a_2b_1</math>, <math>a_3b_0</math> | ||
#* | #* भार 16 – <math>a_1b_3</math>, <math>a_2b_2</math>, <math>a_3b_1</math> | ||
#* | #* भार 32 – <math>a_2b_3</math>, <math>a_3b_2</math> | ||
#* | #* भार 64 – <math>a_3b_3</math> | ||
# | # परिवर्तन पटल 1: | ||
#* केवल | #* केवल भार -1 तार से गुजरें, आउटपुट: 1 भार -1 तार | ||
#* | #* भार 2 के लिए आधा योजक जोड़ें, आउटपुट: 1 भार-2 तार, 1 भार-4 तार | ||
#* | #* भार 4 के लिए पूर्ण योजक जोड़ें, आउटपुट: 1 भार-4 तार, 1 भार-8 तार | ||
#* | #* भार 8 के लिए पूर्ण योजक जोड़ें, और शेष तार को आउटपुट के माध्यम से पास करें: 2 भार-8 तार, 1 भार-16 तार | ||
#* | #* भार 16 के लिए पूर्ण योजक जोड़ें, आउटपुट: 1 भार-16 तार, 1 भार-32 तार | ||
#* | #* भार 32 के लिए आधा योजक जोड़ें, आउटपुट: 1 भार-32 तार, 1 भार-64 तार | ||
#* केवल | #* केवल भार-64 तार से गुजरें, आउटपुट: 1 भार-64 तार | ||
# | # परिवर्तन पटल 1 के उत्पादन में तार: | ||
#* | #* भार 1 - 1 | ||
#* | #* भार 2 - 1 | ||
#* | #* भार 4 - 2 | ||
#* | #* भार 8 - 3 | ||
#* | #* भार 16 - 2 | ||
#* | #* भार 32 - 2 | ||
#* | #* भार 64 - 2 | ||
# | # परिवर्तन पटल 2: | ||
#* | #* भार 8 के लिए पूर्ण योजक जोड़ें, और भार 4, 16, 32, 64 के लिए आधा योजक जोड़ें | ||
# आउटपुट: | # आउटपुट: | ||
#* | #* भार 1 - 1 | ||
#* | #* भार 2 - 1 | ||
#* | #* भार 4 - 1 | ||
#* | #* भार 8 - 2 | ||
#* | #* भार 16 - 2 | ||
#* | #* भार 32 - 2 | ||
#* | #* भार 64 - 2 | ||
#* | #* भार 128 - 1 | ||
# तारों को पूर्णांक की एक जोड़ी और उन्हें जोड़ने के लिए योजक में समूहित करें। | # तारों को पूर्णांक की एक जोड़ी और उन्हें जोड़ने के लिए योजक में समूहित करें। | ||
Revision as of 10:09, 15 February 2023
.svg)
14 आधा योजक (दो डॉट्स) और 38 पूर्ण योजक (थ्री डॉट्स) का उपयोग करते हुए 8x8 आंशिक उत्पाद मैट्रिक्स की 4 लेयर वालेस रिडक्शन। प्रत्येक कॉलम में डॉट्स समान भार के बिट्स होते हैं।
वैलेस गुणक एक बाइनरी गुणक का कंप्यूटर हार्डवेयर कार्यान्वयन है, डिजिटल परिपथ जो दो पूर्णांकों को गुणा करता है। यह दो संख्याओं के बचे रहने तक चरणों में आंशिक उत्पादों का योग करने के लिए योजक (इलेक्ट्रॉनिक्स) (वालेस ट्री या वालेस रिडक्शन) के चयन का उपयोग करता है। वालेस गुणक प्रत्येक पटल पर जितना संभव हो उतना कम करते हैं, जबकि दद्दा गुणक ऊपरी पटलों में परिवर्तन को स्थगित करके गेट्स की आवश्यक संख्या को कम करने का प्रयास करते हैं।[1] वैलेस गुणक 1964 में ऑस्ट्रेलियाई कंप्यूटर वैज्ञानिक क्रिस वालेस (कंप्यूटर वैज्ञानिक) द्वारा तैयार किए गए थे।[2]
वालेस ट्री के तीन चरण हैं:
- एक तर्क के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करें।
- पूर्ण और आधे योजक (इलेक्ट्रॉनिक्स) की पटलों द्वारा आंशिक उत्पादों की संख्या को घटाकर दो कर दें।
- तारों को दो संख्याओं में समूहित करें, और उन्हें पारंपरिक योजक के साथ जोड़ें।[3]
नियमित योजकों के साथ आंशिक उत्पादों को जोड़ने की तुलना में, वालेस ट्री का लाभ इसकी तेज गति है। यह है परिवर्तन पटलें, लेकिन प्रत्येक पटल में केवल है प्रचार देरी। आंशिक उत्पादों के भोले जोड़ की आवश्यकता होगी समय।
आंशिक उत्पाद बनाने के रूप में है और अंतिम जोड़ है , कुल गुणन है जोड़ने से ज्यादा धीमा नहीं है। कम्प्यूटेशनल जटिलता सिद्धांत के दृष्टिकोण से, वालेस ट्री एल्गोरिथम गुणन को NC1 वर्ग में रखता है। वालेस ट्री का नकारात्मक पक्ष, आंशिक उत्पादों के साधारण जोड़ की तुलना में बहुत अधिक गेट काउंट है।
ये संगणनाएँ केवल गेट देरी पर विचार करती हैं और वायर विलंब से निपटती नहीं हैं, जो बहुत महत्वपूर्ण भी हो सकता है।
वालेस के पेड़ को 3/2 या 4/2 योजक के पेड़ द्वारा भी दर्शाया जा सकता है।
इसे कभी-कभी बूथ एन्कोडिंग के साथ जोड़ दिया जाता है।[4][5]
विस्तृत विवरण
वालेस ट्री लंबे गुणन का रूप है। पहला चरण कारक के प्रत्येक अंक (प्रत्येक बिट) को दूसरे के प्रत्येक अंक से गुणा करना है। इस आंशिक उत्पाद में से प्रत्येक का भार इसके कारकों के उत्पाद के बराबर है। अंतिम उत्पाद की गणना इन सभी आंशिक उत्पादों के भारित योग से की जाती है।
पहला चरण, जैसा कि ऊपर कहा गया है, संख्या के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करना है, जिसे सरल AND गेट के रूप में पूरा किया जाता है, जिसके परिणामस्वरूप बिट्स; बिट्स का आंशिक उत्पाद द्वारा भार है
दूसरे चरण में, परिणामी बिट्स को दो संख्याओं में घटा दिया जाता है; यह निम्नानुसार पूरा किया जाता है:
जब तक समान भार वाले तीन या अधिक तार हों तब तक निम्नलिखित पटल जोड़ें: -
- समान भार वाले कोई भी तीन तार लें और उन्हें पूर्ण योजक में डालें। परिणाम एक ही भार का आउटपुट तार होगा और प्रत्येक तीन इनपुट तारों के लिए उच्च भार वाला आउटपुट तार होगा।
- यदि समान भार के दो तार बचे हैं, तो उन्हें आधे योजक में डालें।
- अगर सिर्फ एक तार बचा है, तो उसे अगली पटल से जोड़ दें।
तीसरे और अंतिम चरण में, दो परिणामी संख्याएँ एक योजक को खिलाई जाती हैं, जिससे अंतिम उत्पाद प्राप्त होता है।
उदाहरण
, गुणा करना द्वारा :
- पहले हम हर बिट को हर बिट से गुणा करते हैं:
- भार 1 –
- भार 2 – ,
- भार 4 – , ,
- भार 8 – , , ,
- भार 16 – , ,
- भार 32 – ,
- भार 64 –
- परिवर्तन पटल 1:
- केवल भार -1 तार से गुजरें, आउटपुट: 1 भार -1 तार
- भार 2 के लिए आधा योजक जोड़ें, आउटपुट: 1 भार-2 तार, 1 भार-4 तार
- भार 4 के लिए पूर्ण योजक जोड़ें, आउटपुट: 1 भार-4 तार, 1 भार-8 तार
- भार 8 के लिए पूर्ण योजक जोड़ें, और शेष तार को आउटपुट के माध्यम से पास करें: 2 भार-8 तार, 1 भार-16 तार
- भार 16 के लिए पूर्ण योजक जोड़ें, आउटपुट: 1 भार-16 तार, 1 भार-32 तार
- भार 32 के लिए आधा योजक जोड़ें, आउटपुट: 1 भार-32 तार, 1 भार-64 तार
- केवल भार-64 तार से गुजरें, आउटपुट: 1 भार-64 तार
- परिवर्तन पटल 1 के उत्पादन में तार:
- भार 1 - 1
- भार 2 - 1
- भार 4 - 2
- भार 8 - 3
- भार 16 - 2
- भार 32 - 2
- भार 64 - 2
- परिवर्तन पटल 2:
- भार 8 के लिए पूर्ण योजक जोड़ें, और भार 4, 16, 32, 64 के लिए आधा योजक जोड़ें
- आउटपुट:
- भार 1 - 1
- भार 2 - 1
- भार 4 - 1
- भार 8 - 2
- भार 16 - 2
- भार 32 - 2
- भार 64 - 2
- भार 128 - 1
- तारों को पूर्णांक की एक जोड़ी और उन्हें जोड़ने के लिए योजक में समूहित करें।
सी भी
- दद्दा वृक्ष
संदर्भ
- ↑ Townsend, Whitney J.; Swartzlander, Earl E.; Abraham, Jacob A. (2003). "A comparison of Dadda and Wallace multiplier delays". Advanced Signal Processing Algorithms, Architectures, and Implementations XIII (in English). 5205: 552–560. doi:10.1117/12.507012. ISSN 0277-786X.
- ↑ Wallace, Christopher Stewart (February 1964). "A suggestion for a fast multiplier" (PDF). IEEE Transactions on Electronic Computers. EC-13 (1): 14–17. doi:10.1109/PGEC.1964.263830.
- ↑ Bohsali, Mounir; Doan, Michael (2010). "Rectangular Styled Wallace Tree Multipliers" (PDF). Archived from the original (PDF) on 2010-02-15.
- ↑ "Introduction". 8x8 Booth Encoded Wallace-tree multiplier. Tufts university. 2007. Archived from the original on 2010-06-17.
- ↑ Weems Jr., Charles C. (2001) [1995]. "CmpSci 535 Discussion 7: Number Representations". Amherst: University of Massachusetts. Archived from the original on 2011-02-06.
अग्रिम पठन
- Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.
