दद्दा मल्टीप्लायर

दद्दा मल्टीप्लायर एक हार्डवेयर द्विआधारी गुणक डिज़ाइन है जिसका आविष्कार कंप्यूटर वैज्ञानिक लुइगी दद्दा ने 1965 में किया था।यह आंशिक उत्पादों को चरणों (दद्दा वृक्ष या दद्दा कमी) में तब तक जोड़ने के लिए योजक (इलेक्ट्रॉनिक्स) के चयन का उपयोग करता है जब तक कि दो संख्याएँ शेष न रह जाएँ। डिज़ाइन वालेस गुणक के समान है, लेकिन अलग-अलग रिडक्शन ट्री तर्क द्वार की आवश्यक संख्या को कम कर देता है (छोटे ऑपरेंड आकारों को छोड़कर सभी के लिए) और इसे थोड़ा तेज़ बनाता है (सभी ऑपरेंड आकारों के लिए)। दद्दा और वालेस मल्टीप्लायरों में दो बिट स्ट्रिंग के लिए समान तीन चरण होते हैं $w_{1}$ और $w_{2}$ लंबाई का $\ell _{1}$ और $\ell _{2}$ क्रमश:

1. प्रत्येक बिट को गुणा (तार्किक संयोजन) करें $w_{1}$, के प्रत्येक बिट द्वारा $w_{2}$, उपज $\ell _{1}\cdot \ell _{2}$ परिणाम, स्तंभों में वजन के आधार पर समूहीकृत
2. योजक (इलेक्ट्रॉनिक्स) के चरणों द्वारा आंशिक उत्पादों की संख्या कम करें जब तक कि हमारे पास प्रत्येक भार के अधिकतम दो बिट न रह जाएं।
3. अंतिम परिणाम को पारंपरिक योजक के साथ जोड़ें।

वालेस गुणक की तरह, पहले चरण के गुणन उत्पाद अलग-अलग भार रखते हैं जो गुणन में मूल बिट मानों के परिमाण को दर्शाते हैं। उदाहरण के लिए, बिट्स का उत्पाद $a_{n}b_{m}$ वजन है $n+m$.

वालेस मल्टीप्लायरों के विपरीत, जो प्रत्येक परत पर जितना संभव हो उतना कम करते हैं, दद्दा मल्टीप्लायर उपयोग किए गए गेटों की संख्या, साथ ही इनपुट/आउटपुट विलंब को कम करने का प्रयास करते हैं। इस वजह से, दद्दा मल्टीप्लायरों में कम खर्चीला कटौती चरण होता है, लेकिन अंतिम संख्या कुछ बिट लंबी हो सकती है, इस प्रकार थोड़े बड़े योजक की आवश्यकता होती है।

विवरण

पूर्ण-योजक सर्किट का एक उदाहरण.

अधिक इष्टतम अंतिम उत्पाद प्राप्त करने के लिए, कटौती प्रक्रिया की संरचना वालेस मल्टीप्लायरों की तुलना में थोड़े अधिक जटिल नियमों द्वारा नियंत्रित होती है।

कमी की प्रगति को अधिकतम-ऊंचाई अनुक्रम द्वारा नियंत्रित किया जाता है $d_{j}$, द्वारा परिभाषित:

$d_{1}=2{\text{ and }}d_{j+1}=\operatorname {floor} (1.5d_{j}).$

इससे इस प्रकार एक अनुक्रम प्राप्त होता है:

$d_{1}=2,d_{2}=3,d_{3}=4,d_{4}=6,d_{5}=9,d_{6}=13,\ldots$

का प्रारंभिक मूल्य $j$ को सबसे बड़े मान के रूप में चुना जाता है $d_{j}<\min {(n_{1},n_{2})}$, कहाँ $n_{1}$ और $n_{2}$ इनपुट गुणक और गुणक में बिट्स की संख्या है। गुणन के पहले चरण के बाद दो बिट लंबाई में से जो कम होगी वह वजन के प्रत्येक कॉलम की अधिकतम ऊंचाई होगी। प्रत्येक चरण के लिए $j$ कटौती के लिए, एल्गोरिथ्म का लक्ष्य प्रत्येक कॉलम की ऊंचाई को कम करना है ताकि यह के मूल्य से कम या उसके बराबर हो $d_{j}$.

से प्रत्येक चरण के लिए $,\ldots ,1$, सबसे कम वजन वाले कॉलम से शुरू करके प्रत्येक कॉलम को छोटा करें, $c_{0}$ इन नियमों के अनुसार:

1. अगर $\operatorname {height} (c_{i})\leqslant d_{j}$ कॉलम में कमी की आवश्यकता नहीं है, कॉलम पर जाएँ $c_{i+1}$
2. अगर $\operatorname {height} (c_{i})=d_{j}+1$ शीर्ष दो तत्वों को अर्ध-योजक में जोड़ें, परिणाम को कॉलम के नीचे रखें और कैरी को कॉलम के नीचे रखें $c_{i+1}$, फिर कॉलम पर जाएँ $c_{i+1}$
3. अन्यथा, शीर्ष तीन तत्वों को पूर्ण-योजक में जोड़ें, परिणाम को कॉलम के नीचे रखें और कैरी को कॉलम के नीचे रखें $c_{i+1}$, पुनः आरंभ करें $c_{i}$चरण 1 पर

एल्गोरिथम उदाहरण

7 अर्ध योजक (दो बिंदु) और 35 पूर्ण योजक (तीन बिंदु) का उपयोग करके, 8x8 आंशिक उत्पाद मैट्रिक्स की 4 परत दद्दा कटौती। प्रत्येक कॉलम में बिंदु समान वजन के बिट हैं। कम वजन वाले बिट्स सबसे दाहिने होते हैं।

निकटवर्ती छवि में उदाहरण 8×8 गुणक की कमी को दर्शाता है, जिसे यहां समझाया गया है।

प्रारंभिक अवस्था $j=4$ के रूप में चुना गया है $d_{4}=6$, सबसे बड़ा मान 8 से कम।

अवस्था $j=4$, $d_{4}=6$* $\operatorname {height} (c_{0}\cdots c_{5})$ सभी की ऊंचाई छह बिट से कम या उसके बराबर है, इसलिए कोई बदलाव नहीं किया गया है

• $\operatorname {height} (c_{6})=d_{4}+1=7$, इसलिए एक आधा-योजक लागू किया जाता है, इसे छह बिट तक कम किया जाता है और इसके कैरी बिट को जोड़ा जाता है $c_{7}$
• $\operatorname {height} (c_{7})=9$ से कैरी बिट सहित $c_{6}$, इसलिए हम इसे छह बिट तक कम करने के लिए एक पूर्ण-योजक और एक आधा-योजक लागू करते हैं
• $\operatorname {height} (c_{8})=9$ जिसमें से दो कैरी बिट्स शामिल हैं $c_{7}$, इसलिए हम इसे छह बिट तक कम करने के लिए फिर से एक पूर्ण-योजक और एक आधा-योजक लागू करते हैं
• $\operatorname {height} (c_{9})=8$ जिसमें से दो कैरी बिट्स शामिल हैं $c_{8}$, इसलिए हम एक पूर्ण-योजक लागू करते हैं और इसे छह बिट्स तक कम करते हैं
• $\operatorname {height} (c_{10}\cdots c_{14})$ कैरी बिट्स सहित ऊंचाई में सभी छह बिट्स से कम या उसके बराबर हैं, इसलिए कोई बदलाव नहीं किया गया है

अवस्था $j=3$, $d_{3}=4$* $\operatorname {height} (c_{0}\cdots c_{3})$ सभी की ऊंचाई चार बिट से कम या उसके बराबर है, इसलिए कोई बदलाव नहीं किया गया है

• $\operatorname {height} (c_{4})=d_{3}+1=5$, इसलिए एक आधा-योजक लागू किया जाता है, इसे चार बिट तक कम कर दिया जाता है और इसके कैरी बिट को जोड़ दिया जाता है $c_{5}$
• $\operatorname {height} (c_{5})=7$ से कैरी बिट सहित $c_{4}$, इसलिए हम इसे चार बिट तक कम करने के लिए एक पूर्ण-योजक और एक आधा-योजक लागू करते हैं
• $\operatorname {height} (c_{6}\cdots c_{10})=8$ पिछले कैरी बिट्स सहित, इसलिए हम उन्हें चार बिट्स तक कम करने के लिए दो पूर्ण-योजक लागू करते हैं
• $\operatorname {height} (c_{11})=6$ पिछले कैरी बिट्स सहित, इसलिए हम इसे चार बिट्स तक कम करने के लिए एक पूर्ण-योजक लागू करते हैं
• $\operatorname {height} (c_{12}\cdots c_{14})$ कैरी बिट्स सहित ऊंचाई में सभी चार बिट्स से कम या उसके बराबर हैं, इसलिए कोई बदलाव नहीं किया गया है

अवस्था $j=2$, $d_{2}=3$* $\operatorname {height} (c_{0}\cdots c_{2})$ सभी की ऊंचाई तीन बिट से कम या उसके बराबर है, इसलिए कोई बदलाव नहीं किया गया है

• $\operatorname {height} (c_{3})=d_{2}+1=4$, इसलिए एक आधा-योजक लागू किया जाता है, इसे तीन बिट तक कम किया जाता है और इसके कैरी बिट को जोड़ा जाता है $c_{4}$
• $\operatorname {height} (c_{4}\cdots c_{12})=5$ पिछले कैरी बिट्स सहित, इसलिए हम उन्हें तीन बिट्स तक कम करने के लिए एक पूर्ण-योजक लागू करते हैं
• $\operatorname {height} (c_{13}\cdots c_{14})$ कैरी बिट्स सहित ऊंचाई में सभी तीन बिट्स से कम या उसके बराबर हैं, इसलिए कोई बदलाव नहीं किया गया है

अवस्था $j=1$, $d_{1}=2$* $\operatorname {height} (c_{0}\cdots c_{1})$ सभी की ऊंचाई दो बिट से कम या उसके बराबर है, इसलिए कोई बदलाव नहीं किया गया है

• $\operatorname {height} (c_{2})=d_{1}+1=3$, इसलिए एक आधा-योजक लागू किया जाता है, इसे दो बिट तक कम किया जाता है और इसके कैरी बिट को जोड़ा जाता है $c_{3}$
• $\operatorname {height} (c_{3}\cdots c_{13})=4$ पिछले कैरी बिट्स सहित, इसलिए हम उन्हें दो बिट्स तक कम करने के लिए एक पूर्ण-योजक लागू करते हैं
• $\operatorname {height} (c_{14})=2$ से कैरी बिट सहित $c_{13}$, इसलिए कोई परिवर्तन नहीं किया गया है

जोड़ना

अंतिम चरण का आउटपुट दो या उससे कम ऊंचाई के 15 कॉलम छोड़ता है जिन्हें एक मानक योजक में पारित किया जा सकता है।

यह भी देखें

• बूथ का गुणन एल्गोरिथ्म
• फ़्यूज्ड गुणा-जोड़ें
• वालेस का पेड़
• जटिल लघुगणक और घातांक के लिए एल्गोरिथम कितना है?
• मॉड्यूलर अंकगणितीय गुणन के लिए कोचानस्की गुणन

अग्रिम पठन

• Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.