वालेस ट्री: Difference between revisions

Revision as of 09:39, 15 February 2023

14 आधा योजक (दो डॉट्स) और 38 पूर्ण योजक (थ्री डॉट्स) का उपयोग करते हुए 8x8 आंशिक उत्पाद मैट्रिक्स की 4 लेयर वालेस रिडक्शन। प्रत्येक कॉलम में डॉट्स समान वजन के बिट्स होते हैं।

वैलेस मल्टीप्लायर एक बाइनरी गुणक का कंप्यूटर हार्डवेयर कार्यान्वयन है, डिजिटल सर्किट जो दो पूर्णांकों को गुणा करता है। यह दो संख्याओं के बचे रहने तक चरणों में आंशिक उत्पादों का योग करने के लिए योजक (इलेक्ट्रॉनिक्स) (वालेस ट्री या वालेस रिडक्शन) के चयन का उपयोग करता है। वालेस गुणक प्रत्येक परत पर जितना संभव हो उतना कम करते हैं, जबकि दद्दा गुणक ऊपरी परतों में कमी को स्थगित करके गेट्स की आवश्यक संख्या को कम करने का प्रयास करते हैं।^[1] वैलेस गुणक 1964 में ऑस्ट्रेलियाई कंप्यूटर वैज्ञानिक क्रिस वालेस (कंप्यूटर वैज्ञानिक) द्वारा तैयार किए गए थे।^[2]

वालेस ट्री के तीन चरण हैं:

एक तर्क के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करें।
पूर्ण और आधे योजक (इलेक्ट्रॉनिक्स) की परतों द्वारा आंशिक उत्पादों की संख्या को घटाकर दो कर दें।
तारों को दो संख्याओं में समूहित करें, और उन्हें पारंपरिक योजक के साथ जोड़ें।^[3]

नियमित योजकों के साथ आंशिक उत्पादों को जोड़ने की तुलना में, वालेस ट्री का लाभ इसकी तेज गति है। यह है $O(\log n)$ कमी परतें, लेकिन प्रत्येक परत में केवल है $O(1)$ प्रचार देरी। आंशिक उत्पादों के भोले जोड़ की आवश्यकता होगी $O(\log ^{2}n)$ समय।

आंशिक उत्पाद बनाने के रूप में है $O(1)$ और अंतिम जोड़ है $O(\log n)$ , कुल गुणन है $O(\log n)$ जोड़ने से ज्यादा धीमा नहीं है। कम्प्यूटेशनल जटिलता सिद्धांत के दृष्टिकोण से, वालेस ट्री एल्गोरिथम गुणन को एनसी (जटिलता)|एनसी वर्ग में रखता है।^{1</उप>।}

^{आंशिक उत्पादों के भोले जोड़ की तुलना में वालेस ट्री का नकारात्मक पक्ष इसकी बहुत अधिक गेट काउंट है।}

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

वालेस के पेड़ को 3/2 या 4/2 योजक के पेड़ द्वारा भी दर्शाया जा सकता है।

इसे कभी-कभी बूथ एन्कोडिंग के साथ जोड़ दिया जाता है।^[4]^[5]

विस्तृत विवरण

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

पहला कदम, जैसा कि ऊपर कहा गया है, संख्या के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करना है, जिसे सरल AND गेट के रूप में पूरा किया जाता है, जिसके परिणामस्वरूप $n^{2}$ बिट्स; बिट्स का आंशिक उत्पाद $a_{m}$ द्वारा $b_{n}$ वजन है $2^{(m+n)}$

दूसरे चरण में, परिणामी बिट्स को दो संख्याओं में घटा दिया जाता है; यह निम्नानुसार पूरा किया जाता है:

जब तक समान भार वाले तीन या अधिक तार हों तब तक निम्नलिखित परत जोड़ें: -

समान भार वाले कोई भी तीन तार लें और उन्हें पूर्ण योजक में डालें। परिणाम एक ही वजन का आउटपुट तार होगा और प्रत्येक तीन इनपुट तारों के लिए उच्च वजन वाला आउटपुट तार होगा।
यदि समान वजन के दो तार बचे हैं, तो उन्हें आधे योजक में डालें।
अगर सिर्फ एक तार बचा है, तो उसे अगली परत से जोड़ दें।

तीसरे और अंतिम चरण में, दो परिणामी संख्याएँ एक योजक को खिलाई जाती हैं, जिससे अंतिम उत्पाद प्राप्त होता है।

उदाहरण

$n=4$ , गुणा करना $a_{3}a_{2}a_{1}a_{0}$ द्वारा $b_{3}b_{2}b_{1}b_{0}$ :

पहले हम हर बिट को हर बिट से गुणा करते हैं:
- वज़न 1 – $a_{0}b_{0}$
- वज़न 2 – $a_{0}b_{1}$ , $a_{1}b_{0}$
- वजन 4 – $a_{0}b_{2}$ , $a_{1}b_{1}$ , $a_{2}b_{0}$
- वजन 8 – $a_{0}b_{3}$ , $a_{1}b_{2}$ , $a_{2}b_{1}$ , $a_{3}b_{0}$
- वजन 16 – $a_{1}b_{3}$ , $a_{2}b_{2}$ , $a_{3}b_{1}$
- वजन 32 – $a_{2}b_{3}$ , $a_{3}b_{2}$
- वजन 64 – $a_{3}b_{3}$
कमी परत 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.

बाहरी संबंध

Generic VHDL Implementation of Wallace Tree Multiplier.

[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_1964-2] 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_2010-3] Bohsali, Mounir; Doan, Michael (2010). "Rectangular Styled Wallace Tree Multipliers" (PDF). Archived from the original (PDF) on 2010-02-15.

[tufts_2007-4] "Introduction". 8x8 Booth Encoded Wallace-tree multiplier. Tufts university. 2007. Archived from the original on 2010-06-17.

[Weems_2001-5] Weems Jr., Charles C. (2001) [1995]. "CmpSci 535 Discussion 7: Number Representations". Amherst: University of Massachusetts. Archived from the original on 2011-02-06.

[1]

[2]

[3]

[4]

[5]

@@ Line 1: / Line 1: @@
 {{short description|Efficient hardware implementation of a digital multiplier}}
-{{Refimprove|date=December 2009}}
+[[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" />
-<!-- [[Image:Binary tree.svg|thumb | Would be used in reverse order]]
-[[Image:Full-adder.svg|thumb | Full adder, would in this case use only XOR]] -->[[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" />
 वालेस ट्री के तीन चरण हैं:
@@ Line 9: / Line 7: @@
 # तारों को दो संख्याओं में समूहित करें, और उन्हें पारंपरिक योजक के साथ जोड़ें।<ref name="Bohsali_2010"/>
-नियमित योजकों के साथ आंशिक उत्पादों को जोड़ने की तुलना में, वालेस ट्री का लाभ इसकी तेज गति है। यह है <math>O(\log n)</math> कमी परतें, लेकिन प्रत्येक परत में केवल है <math>O(1)</math> प्रचार देरी। आंशिक उत्पादों के एक भोले जोड़ की आवश्यकता होगी <math>O(\log^2n)</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>जोड़ने से ज्यादा धीमा नहीं है। [[कम्प्यूटेशनल जटिलता सिद्धांत]] के दृष्टिकोण से, वालेस ट्री एल्गोरिथम गुणन को एनसी (जटिलता)|एनसी वर्ग में रखता है।<sup>1</उप>।
-आंशिक उत्पादों के भोले जोड़ की तुलना में वालेस ट्री का नकारात्मक पक्ष इसकी बहुत अधिक गेट काउंट है।
+<sup>आंशिक उत्पादों के भोले जोड़ की तुलना में वालेस ट्री का नकारात्मक पक्ष इसकी बहुत अधिक गेट काउंट है।
 ये संगणनाएँ केवल [[गेट देरी]] पर विचार करती हैं और वायर विलंब से निपटती नहीं हैं, जो बहुत महत्वपूर्ण भी हो सकता है।
@@ Line 21: / Line 21: @@
 == विस्तृत विवरण ==
-वालेस ट्री लंबे गुणन का एक रूप है। पहला कदम एक कारक के प्रत्येक अंक (प्रत्येक बिट) को दूसरे के प्रत्येक अंक से गुणा करना है। इस आंशिक उत्पाद में से प्रत्येक का वजन इसके कारकों के उत्पाद के बराबर है। अंतिम उत्पाद की गणना इन सभी आंशिक उत्पादों के भारित योग से की जाती है।
+वालेस ट्री लंबे गुणन का रूप है। पहला कदम कारक के प्रत्येक अंक (प्रत्येक बिट) को दूसरे के प्रत्येक अंक से गुणा करना है। इस आंशिक उत्पाद में से प्रत्येक का वजन इसके कारकों के उत्पाद के बराबर है। अंतिम उत्पाद की गणना इन सभी आंशिक उत्पादों के भारित योग से की जाती है।
+पहला कदम, जैसा कि ऊपर कहा गया है, संख्या के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करना है, जिसे सरल AND गेट के रूप में पूरा किया जाता है, जिसके परिणामस्वरूप <math>n^2</math> बिट्स; बिट्स का आंशिक उत्पाद <math>a_m</math> द्वारा <math>b_n</math> वजन है <math>2^{(m+n)}</math>
-पहला कदम, जैसा कि ऊपर कहा गया है, एक संख्या के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करना है, जिसे एक सरल AND गेट के रूप में पूरा किया जाता है, जिसके परिणामस्वरूप <math>n^2</math> बिट्स; बिट्स का आंशिक उत्पाद <math>a_m</math> द्वारा <math>b_n</math> वजन है <math>2^{(m+n)}</math>
 दूसरे चरण में, परिणामी बिट्स को दो संख्याओं में घटा दिया जाता है; यह निम्नानुसार पूरा किया जाता है:
 जब तक समान भार वाले तीन या अधिक तार हों तब तक निम्नलिखित परत जोड़ें: -
-* समान भार वाले कोई भी तीन तार लें और उन्हें एक पूर्ण योजक में डालें। परिणाम एक ही वजन का एक आउटपुट तार होगा और प्रत्येक तीन इनपुट तारों के लिए एक उच्च वजन वाला एक आउटपुट तार होगा।
+* समान भार वाले कोई भी तीन तार लें और उन्हें पूर्ण योजक में डालें। परिणाम एक ही वजन का आउटपुट तार होगा और प्रत्येक तीन इनपुट तारों के लिए उच्च वजन वाला आउटपुट तार होगा।
 * यदि समान वजन के दो तार बचे हैं, तो उन्हें आधे योजक में डालें।
 * अगर सिर्फ एक तार बचा है, तो उसे अगली परत से जोड़ दें।
@@ Line 46: / Line 48: @@
 #* केवल वजन -1 तार से गुजरें, आउटपुट: 1 वजन -1 तार
 #* वजन 2 के लिए आधा योजक जोड़ें, आउटपुट: 1 वजन-2 तार, 1 वजन-4 तार
-#* वजन 4 के लिए एक पूर्ण योजक जोड़ें, आउटपुट: 1 वजन-4 तार, 1 वजन-8 तार
+#* वजन 4 के लिए पूर्ण योजक जोड़ें, आउटपुट: 1 वजन-4 तार, 1 वजन-8 तार
-#* वजन 8 के लिए एक पूर्ण योजक जोड़ें, और शेष तार को आउटपुट के माध्यम से पास करें: 2 वजन-8 तार, 1 वजन-16 तार
+#* वजन 8 के लिए पूर्ण योजक जोड़ें, और शेष तार को आउटपुट के माध्यम से पास करें: 2 वजन-8 तार, 1 वजन-16 तार
-#* वजन 16 के लिए एक पूर्ण योजक जोड़ें, आउटपुट: 1 वजन-16 तार, 1 वजन-32 तार
+#* वजन 16 के लिए पूर्ण योजक जोड़ें, आउटपुट: 1 वजन-16 तार, 1 वजन-32 तार
 #* वजन 32 के लिए आधा योजक जोड़ें, आउटपुट: 1 वजन-32 तार, 1 वजन-64 तार
 #* केवल वजन-64 तार से गुजरें, आउटपुट: 1 वजन-64 तार
@@ Line 60: / Line 62: @@
 #* वजन 64 - 2
 # कमी परत 2:
-#* वजन 8 के लिए एक पूर्ण योजक जोड़ें, और वजन 4, 16, 32, 64 के लिए आधा योजक जोड़ें
+#* वजन 8 के लिए पूर्ण योजक जोड़ें, और वजन 4, 16, 32, 64 के लिए आधा योजक जोड़ें
 # आउटपुट:
 #* वज़न 1 - 1
@@ Line 70: / Line 72: @@
 #* वजन 64 - 2
 #* वजन 128 - 1
-# तारों को पूर्णांक की एक जोड़ी और उन्हें जोड़ने के लिए एक योजक में समूहित करें।
+# तारों को पूर्णांक की एक जोड़ी और उन्हें जोड़ने के लिए योजक में समूहित करें।
 == सी भी ==

Anonymous

Search

वालेस ट्री: Difference between revisions

Namespaces

More

Page actions

Revision as of 09:39, 15 February 2023

Contents

विस्तृत विवरण

उदाहरण

सी भी

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

वालेस ट्री: Difference between revisions

Revision as of 09:39, 15 February 2023

विस्तृत विवरण

उदाहरण

सी भी

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories