वालेस ट्री

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

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

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

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

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

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

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

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

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

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

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

पहला चरण, जैसा कि ऊपर कहा गया है, संख्या के प्रत्येक बिट को दूसरे के प्रत्येक बिट से गुणा करना है, जिसे सरल 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. पहले हम हर बिट को हर बिट से गुणा करते हैं:
   • भार 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}$
2. परिवर्तन पटल 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 तार
3. परिवर्तन पटल 1 के उत्पादन में तार:
   • भार 1 - 1
   • भार 2 - 1
   • भार 4 - 2
   • भार 8 - 3
   • भार 16 - 2
   • भार 32 - 2
   • भार 64 - 2
4. परिवर्तन पटल 2:
   • भार 8 के लिए पूर्ण योजक जोड़ें, और भार 4, 16, 32, 64 के लिए आधा योजक जोड़ें
5. आउटपुट:
   • भार 1 - 1
   • भार 2 - 1
   • भार 4 - 1
   • भार 8 - 2
   • भार 16 - 2
   • भार 32 - 2
   • भार 64 - 2
   • भार 128 - 1
6. तारों को पूर्णांक की एक जोड़ी और उन्हें जोड़ने के लिए योजक में समूहित करें।

सी भी

• दद्दा वृक्ष

अग्रिम पठन

• 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.