वालेस ट्री

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)$जोड़ने से ज्यादा धीमा नहीं है। कम्प्यूटेशनल जटिलता सिद्धांत के दृष्टिकोण से, वालेस ट्री एल्गोरिथम गुणन को एनसी (जटिलता)|एनसी वर्ग में रखता है।^{1</उप>।}

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

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

वालेस के पेड़ को 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.