बाइनरी गुणक
| Part of a series on | |||||||
| Arithmetic logic circuits | |||||||
|---|---|---|---|---|---|---|---|
| Quick navigation | |||||||
|
Components
|
|||||||
|
See also |
|||||||
एक बाइनरी गुणक एक विद्युत सर्किट है जिसका उपयोग डिजिटल इलेक्ट्रॉनिक्स में किया जाता है, जैसे कि कंप्यूटर, दो बाइनरी संख्याों को गुणा करने के लिए।
विभिन्न प्रकार की : श्रेणी: कंप्यूटर अंकगणितीय तकनीकों का उपयोग डिजिटल गुणक को लागू करने के लिए किया जा सकता है। अधिकांश तकनीकों में आंशिक उत्पादों के सेट की गणना करना शामिल है, जिन्हें बाद में बाइनरी योजक्स का उपयोग करके एक साथ जोड़ दिया जाता है। यह प्रक्रिया दीर्घ गुणन के समान है, सिवाय इसके कि यह आधार-2 (द्विआधारी अंक प्रणाली) अंक प्रणाली का उपयोग करता है।
इतिहास
1947 और 1949 के बीच आर्थर एलेक रॉबिन्सन ने एक छात्र प्रशिक्षु के रूप में और फिर एक विकास इंजीनियर के रूप में इंग्लिश इलेक्ट्रिक लिमिटेड के लिए काम किया। महत्वपूर्ण रूप से इस अवधि के दौरान उन्होंने मैनचेस्टर विश्वविद्यालय में पीएचडी की डिग्री के लिए अध्ययन किया, जहां उन्होंने शुरुआती मैनचेस्टर मार्क 1 के लिए हार्डवेयर गुणक के डिजाइन पर काम किया। हालाँकि, 1970 के दशक के अंत तक, अधिकांश मिनी कंप्यूटर में मल्टीप्ल इंस्ट्रक्शन नहीं था, और इसलिए प्रोग्रामर मल्टीप्ल रूटीन का उपयोग करते थे।[1][2][3] जो बार-बार गुणन एल्गोरिथम#Shift और आंशिक परिणाम जोड़ते हैं, अक्सर लूप खोलना का उपयोग करके लिखा जाता है। मेनफ़्रेम कंप्यूटर में मल्टीपल निर्देश होते थे, लेकिन वे एक ही तरह के बदलाव करते थे और एक मल्टीप्ल रूटीन के रूप में जोड़ते थे।
शुरुआती माइक्रोप्रोसेसरों के पास भी कोई गुणा निर्देश नहीं था। हालाँकि 16-बिट पीढ़ी के साथ गुणा निर्देश आम हो गया था,[4] कम से कम दो 8-बिट प्रोसेसर के लिए एक गुणा निर्देश है: मोटोरोला 6809, जिसे 1978 में पेश किया गया था,[5] और Intel MCS-51 परिवार, 1980 में विकसित हुआ, और बाद में ATMega, ATTiny और ATXMega माइक्रोकंट्रोलर्स में मौजूद आधुनिक Atmel AVR 8-बिट माइक्रोप्रोसेसर।
जैसे-जैसे बड़े पैमाने पर एकीकरण के कारण अधिक ट्रांजिस्टर की गिनती उपलब्ध होती गई, एक बार में प्रत्येक आंशिक उत्पाद को संभालने के लिए एकल योजक का पुन: उपयोग करने के बजाय, सभी आंशिक उत्पादों को एक साथ जोड़ने के लिए एक ही चिप पर पर्याप्त योजक लगाना संभव हो गया।
क्योंकि कुछ सामान्य अंकीय संकेत प्रक्रिया एल्गोरिदम अपना अधिकांश समय गुणा करने में व्यतीत करते हैं, डिजिटल सिग्नल प्रोसेसर डिजाइनर जितना संभव हो उतना तेजी से गुणा करने के लिए काफी चिप क्षेत्र का त्याग करते हैं; एक एकल-चक्र गुणा-संचय इकाई अक्सर शुरुआती डीएसपी के अधिकांश चिप क्षेत्र का उपयोग करती थी।
बाइनरी लंबी गुणा
स्कूल में दशमलव संख्याओं को गुणा करने की विधि आंशिक गुणनफल की गणना करने, उन्हें बाईं ओर स्थानांतरित करने और फिर उन्हें एक साथ जोड़ने पर आधारित है। सबसे कठिन हिस्सा आंशिक उत्पाद प्राप्त करना है, क्योंकि इसमें एक लंबी संख्या को एक अंक (0 से 9 तक) से गुणा करना शामिल है:
123
एक्स 456
=====
738 (यह 123 x 6 है)
615 (यह 123 x 5 है, एक स्थिति को बाईं ओर स्थानांतरित कर दिया गया है)
+ 492 (यह 123 x 4 है, बाईं ओर दो स्थिति बदली गई है)
=====
56088
एक बाइनरी कंप्यूटर ठीक वैसा ही गुणा करता है जैसा कि दशमलव संख्याएँ करती हैं, लेकिन बाइनरी संख्याओं के साथ। बाइनरी एन्कोडिंग में प्रत्येक लंबी संख्या को एक अंक (या तो 0 या 1) से गुणा किया जाता है, और यह दशमलव की तुलना में बहुत आसान है, क्योंकि 0 या 1 का गुणनफल केवल 0 या समान संख्या है। इसलिए, दो बाइनरी नंबरों का गुणन आंशिक उत्पादों (जो 0 या पहली संख्या है) की गणना करने के लिए नीचे आता है, तार्किक रूप से उन्हें छोड़ दिया जाता है, और फिर उन्हें एक साथ जोड़ दिया जाता है (निश्चित रूप से एक बाइनरी जोड़):
1011 (यह दशमलव 11 के लिए बाइनरी है)
x 1110 (यह दशमलव 14 के लिए बाइनरी है)
== अ[[हस्ताक्षर]]ित पूर्णांक ==
उदाहरण के लिए, मान लीजिए कि हम दो सिग्नेनेस आठ बिट पूर्णांकों को एक साथ गुणा करना चाहते हैं: a[7:0] और b[7:0]। हम आठ एक-बिट गुणन करके आठ आंशिक उत्पाद बना सकते हैं, प्रत्येक बिट के लिए एक गुणक a में:
<nowiki>p0[7:0] = a[0] × b[7:0] = {8{a[0]}} & b[7:0]
p1[7:0] = a[1] × b[7:0] = {8{a[1]}} और b[7:0]
p2[7:0] = a[2] × b[7:0] = {8{a[2]}} और b[7:0]
p3[7:0] = a[3] × b[7:0] = {8{a[3]}} और b[7:0]
p4[7:0] = a[4] × b[7:0] = {8{a[4]}} और b[7:0]
p5[7:0] = a[5] × b[7:0] = {8{a[5]}} और b[7:0]
p6[7:0] = a[6] × b[7:0] = {8{a[6]}} और b[7:0]
p7[7:0] = a[7] × b[7:0] = {8{a[7]}} और b[7:0]
जहाँ {8{a[0]}} का अर्थ है a[0] (a का 0वां बिट) को 8 बार दोहराना (Verilog नोटेशन)।
अपना उत्पाद प्राप्त करने के लिए, हमें अपने सभी आठ आंशिक उत्पादों को जोड़ने की आवश्यकता है, जैसा कि यहां दिखाया गया है:
पी0[7] पी0[6] पी0[5] पी0[4] पी0[3] पी0[2] पी0[1] पी0[0]
+ p1[7] p1[6] p1[5] p1[4] p1[3] p1[2] p1[1] p1[0] 0
+ पी2[7] पी2[6] पी2[5] पी2[4] पी2[3] पी2[2] पी2[1] पी2[0] 0 0
+ p3[7] p3[6] p3[5] p3[4] p3[3] p3[2] p3[1] p3[0] 0 0 0
+ p4[7] p4[6] p4[5] p4[4] p4[3] p4[2] p4[1] p4[0] 0 0 0 0
+ p5[7] p5[6] p5[5] p5[4] p5[3] p5[2] p5[1] p5[0] 0 0 0 0 0
+ p6[7] p6[6] p6[5] p6[4] p6[3] p6[2] p6[1] p6[0] 0 0 0 0 0 0
+ p7[7] p7[6] p7[5] p7[4] p7[3] p7[2] p7[1] p7[0] 0 0 0 0 0 0 0
--------------------------------------------------- ----------------------------------------------------------------------
पी[15] पी[14] पी[13] पी[12] पी[11] पी[10] पी[9] पी[8] पी[7] पी[6] पी[5] पी[4] पी[ 3] पी[2] पी[1] पी[0]
दूसरे शब्दों में, P[15:0] हमारे अंतिम अहस्ताक्षरित 16-बिट उत्पाद का उत्पादन करने के लिए, p0, p1 << 1, p2 << 2, और इसी तरह के योग द्वारा निर्मित होता है।
हस्ताक्षरित पूर्णांक
यदि b एक हस्ताक्षरित पूर्णांक के बजाय एक हस्ताक्षरित पूर्णांक होता, तो आंशिक उत्पादों को योग से पहले उत्पाद की चौड़ाई तक साइन-विस्तारित करने की आवश्यकता होती। यदि a एक हस्ताक्षरित पूर्णांक होता, तो आंशिक उत्पाद p7 को इसमें जोड़े जाने के बजाय अंतिम योग से घटाया जाना चाहिए।
उपरोक्त सरणी गुणक को कई उत्पाद शर्तों को उलट कर और पहले आंशिक उत्पाद शब्द के बाईं ओर एक सम्मिलित करके दो के पूरक संकेतन हस्ताक्षरित संख्याओं का समर्थन करने के लिए संशोधित किया जा सकता है:
1 ~p0[7] p0[6] p0[5] p0[4] p0[3] p0[2] p0[1] p0[0]
~p1[7] +p1[6] +p1[5] +p1[4] +p1[3] +p1[2] +p1[1] +p1[0] 0
~p2[7] +p2[6] +p2[5] +p2[4] +p2[3] +p2[2] +p2[1] +p2[0] 0 0
~p3[7] +p3[6] +p3[5] +p3[4] +p3[3] +p3[2] +p3[1] +p3[0] 0 0 0
~p4[7] +p4[6] +p4[5] +p4[4] +p4[3] +p4[2] +p4[1] +p4[0] 0 0 0 0
~p5[7] +p5[6] +p5[5] +p5[4] +p5[3] +p5[2] +p5[1] +p5[0] 0 0 0 0 0
~p6[7] +p6[6] +p6[5] +p6[4] +p6[3] +p6[2] +p6[1] +p6[0] 0 0 0 0 0 0
1 +p7[7] ~p7[6] ~p7[5] ~p7[4] ~p7[3] ~p7[2] ~p7[1] ~p7[0] 0 0 0 0 0 0 0
--------------------------------------------------- --------------------------------------------------- --------
पी[15] पी[14] पी[13] पी[12] पी[11] पी[10] पी[9] पी[8] पी[7] पी[6] पी[5] पी[4] पी[ 3] पी[2] पी[1] पी[0]
जहाँ ~p, p के पूरक (विपरीत मान) को दर्शाता है।
उपरोक्त बिट सरणी में कई सरलीकरण हैं जो दिखाए नहीं गए हैं और स्पष्ट नहीं हैं। एक पूरक बिट के अनुक्रम के बाद गैर-पूरक बिट्स साइन एक्सटेंशन से बचने के लिए दो पूरक चाल को लागू कर रहे हैं। p7 का अनुक्रम (सभी पूरक बिट्स के बाद गैर-पूरक बिट) इसलिए है क्योंकि हम इस शब्द को घटा रहे हैं, इसलिए वे सभी को शुरू करने के लिए नकार दिया गया था (और 1 को कम से कम महत्वपूर्ण स्थिति में जोड़ा गया था)। दोनों प्रकार के अनुक्रमों के लिए, अंतिम बिट को फ़्लिप किया जाता है और एक अंतर्निहित -1 सीधे MSB के नीचे जोड़ा जाना चाहिए। जब बिट स्थिति 0 (LSB) में p7 के लिए दो के पूरक निषेध से +1 और बिट कॉलम 7 से 14 (जहां प्रत्येक MSB स्थित हैं) में सभी -1 को एक साथ जोड़ा जाता है, तो उन्हें एकल 1 में सरल बनाया जा सकता है वह जादुई रूप से बाईं ओर तैर रहा है। MSB को फ़्लिप करने से हमें साइन एक्सटेंशन की बचत क्यों होती है, इसकी व्याख्या और प्रमाण के लिए, एक कंप्यूटर अंकगणितीय पुस्तक देखें।[6]
फ़्लोटिंग पॉइंट नंबर
एक बाइनरी फ़्लोटिंग नंबर में एक साइन बिट, महत्वपूर्ण बिट्स (महत्व के रूप में जाना जाता है) और एक्सपोनेंट बिट्स (सरलता के लिए, हम आधार और संयोजन फ़ील्ड पर विचार नहीं करते हैं) शामिल हैं। उत्तर का चिह्न प्राप्त करने के लिए प्रत्येक संकार्य के चिह्न बिट XOR'd होते हैं। फिर, परिणाम का घातांक प्राप्त करने के लिए दो घातांकों को जोड़ा जाता है। अंत में, प्रत्येक ऑपरेंड के महत्व का गुणन परिणाम के महत्व को वापस कर देगा। हालाँकि, यदि बाइनरी गुणन का परिणाम एक विशिष्ट परिशुद्धता (जैसे 32, 64, 128) के लिए बिट्स की कुल संख्या से अधिक है, तो राउंडिंग की आवश्यकता होती है और एक्सपोनेंट को उचित रूप से बदल दिया जाता है।
हार्डवेयर कार्यान्वयन
गुणन की प्रक्रिया को 3 चरणों में विभाजित किया जा सकता है:[7][8]
- आंशिक उत्पाद बनाना
- आंशिक उत्पाद को कम करना
- कंप्यूटिंग अंतिम उत्पाद
पुराने मल्टीप्लायर आर्किटेक्चर ने प्रत्येक आंशिक उत्पाद को योग करने के लिए एक शिफ्टर और संचायक को नियोजित किया, अक्सर प्रति चक्र एक आंशिक उत्पाद, मरने वाले क्षेत्र के लिए गति से व्यापार करना। आधुनिक गुणक आर्किटेक्चर (संशोधित) बॉघ-वूली एल्गोरिथम का उपयोग करते हैं,[9][10][11][12]वालेस का पेड़, या दद्दा मल्टीप्लायर आंशिक उत्पादों को एक ही चक्र में एक साथ जोड़ने के लिए। वालेस ट्री कार्यान्वयन के प्रदर्शन को कभी-कभी संशोधित बूथ एन्कोडिंग द्वारा दो गुणकों में से एक में सुधार किया जाता है, जो आंशिक उत्पादों की संख्या को कम करता है जिन्हें योग किया जाना चाहिए।
गति के लिए, शिफ्ट-एंड-ऐड मल्टीप्लायरों को एक तेज़ योजक (रिपल-कैरी से कुछ तेज़) की आवश्यकता होती है।[13]
एक एकल चक्र गुणक (या तेज गुणक ) शुद्ध संयोजी तर्क है।
तेज गुणक में, आंशिक-उत्पाद कमी प्रक्रिया आमतौर पर गुणक के विलंब, शक्ति और क्षेत्र में सबसे अधिक योगदान देती है।[7]गति के लिए, कम आंशिक उत्पाद चरणों को आमतौर पर कंप्रेशर्स से बने कैरी-सेव योजक के रूप में लागू किया जाता है और गणना अंतिम उत्पाद चरण को एक तेज़ योजक (रिपल-कैरी की तुलना में कुछ तेज़) के रूप में लागू किया जाता है।
कई तेज मल्टीप्लायर स्थिर सीएमओएस में कार्यान्वित कंप्रेसर (3:2 कंप्रेसर) के रूप में पूर्ण योजक का उपयोग करते हैं। एक ही क्षेत्र में बेहतर प्रदर्शन या एक छोटे क्षेत्र में समान प्रदर्शन प्राप्त करने के लिए गुणक डिजाइन उच्च क्रम के कंप्रेसर जैसे 7:3 कंप्रेसर का उपयोग कर सकते हैं;[8][7]कंप्रेशर्स को तेज लॉजिक में लागू करें (जैसे ट्रांसमिशन गेट लॉजिक, पास ट्रांजिस्टर लॉजिक, डोमिनोज़ लॉजिक);[13] कंप्रेशर्स को एक अलग पैटर्न में कनेक्ट करें; या कुछ संयोजन।
उदाहरण सर्किट
यह भी देखें
- बूथ गुणन एल्गोरिथ्म
- जुड़े हुए गुणा-जोड़ें
- वालेस ट्री
- जटिल लघुगणक और घातांक के लिए एल्गोरिदम कितना है?
- मॉड्यूलर अंकगणितीय गुणन के लिए कोचनस्की गुणन
- तार्किक बदलाव बाकी
संदर्भ
- ↑ Rather, Elizabeth D.; Colburn, Donald R.; Moore, Charles H. (1996) [1993]. "The Evolution of Forth". In Bergin, Thomas J.; Gibson, Richard G. (eds.). History of Programming Languages—II. Association for Computing Machinery. pp. 625–670. doi:10.1145/234286.1057832. ISBN 0201895021.
- ↑ Davies, A.C.; Fung, Y.T. (1977). "Interfacing a hardware multiplier to a general-purpose microprocessor". Microprocessors. 1 (7): 425–432. doi:10.1016/0308-5953(77)90004-6.
- ↑ Rafiquzzaman, M. (2005). "§2.5.1 Binary Arithmetic: Multiplication of Unsigned Binary Numbers". Fundamentals of Digital Logic and Microcomputer Design. Wiley. p. 46. ISBN 978-0-47173349-2.
- ↑ Rafiquzzaman 2005, §7.3.3 Addition, Subtraction, Multiplication and Division of Signed and Unsigned Numbers p. 251
- ↑ Kant, Krishna (2007). "§2.11.2 16-Bit Microprocessors". Microprocessors and Microcontrollers: Architecture, Programming and System Design 8085, 8086, 8051, 8096. PHI Learning. p. 57. ISBN 9788120331914.
- ↑ Parhami, Behrooz (2000). Computer Arithmetic: Algorithms and Hardware Designs. Oxford University Press. ISBN 0-19-512583-5.
- ↑ 7.0 7.1 7.2 Rouholamini, Mahnoush; Kavehie, Omid; Mirbaha, Amir-Pasha; Jasbi, Somaye Jafarali; Navi, Keivan. "A New Design for 7:2 Compressors" (PDF).
- ↑ 8.0 8.1 Leong, Yuhao; Lo, HaiHiung; Drieberg, Michael; Sayuti, Abu Bakar; Sebastian, Patrick. "Performance Comparison Review of 8-3 compressor on FPGA".
- ↑ Baugh, Charles Richmond; Wooley, Bruce A. (December 1973). "A Two's Complement Parallel Array Multiplication Algorithm". IEEE Transactions on Computers. C-22 (12): 1045–1047. doi:10.1109/T-C.1973.223648. S2CID 7473784.
- ↑ Hatamian, Mehdi; Cash, Glenn (1986). "A 70-MHz 8-bit×8-bit parallel pipelined multiplier in 2.5-μm CMOS". IEEE Journal of Solid-State Circuits. 21 (4): 505–513. Bibcode:1986IJSSC..21..505H. doi:10.1109/jssc.1986.1052564.
- ↑ Gebali, Fayez (2003). "Baugh–Wooley Multiplier" (PDF). University of Victoria, CENG 465 Lab 2. Archived (PDF) from the original on 2018-04-14. Retrieved 2018-04-14.
- ↑ Reynders, Nele; Dehaene, Wim (2015). Ultra-Low-Voltage Design of Energy-Efficient Digital Circuits. doi:10.1007/978-3-319-16136-5. ISBN 978-3-319-16135-8. ISSN 1872-082X. LCCN 2015935431.
{{cite book}}:|journal=ignored (help) - ↑ 13.0 13.1 Peng Chang. "A Reconfigurable Digital Multiplier and 4:2 Compressor Cells Design". 2008.
- Hennessy, John L.; Patterson, David A. (1990). "Section A.2, section A.9". Computer Architecture: A quantitative Approach. Morgan Kaufmann. pp. A–3..A–6, A–39..A–49. ISBN 978-0-12383872-8.
