कैरी-सेव एडर: Difference between revisions
No edit summary |
(text) |
||
Line 1: | Line 1: | ||
'''कैरी-सेव | '''कैरी-सेव योजक'''<ref name="Earle_1965_1"/><ref name="Earle_1965_2"/><ref group="nb" name="NB_CSA"/>एक प्रकार का [[योजक (इलेक्ट्रॉनिक्स)]] है, जिसका उपयोग तीन या अधिक युग्मक अंक प्रणाली संख्याओं के योग की कुशलता से गणना करने के लिए किया जाता है। यह अन्य अंकीय योजकों से भिन्न है जिसमें यह दो (या अधिक) संख्याओं का प्रक्षेपण करता है, और इन प्रक्षेपण को एक साथ जोड़कर मूल योग का उत्तर प्राप्त किया जा सकता है। कैरी सेव योजक का उपयोग सामान्यतः युग्मक गुणक में किया जाता है, क्योंकि युग्मक गुणक में गुणन के बाद दो से अधिक युग्मक अंक सम्मिलित होते हैं। इस तकनीक का उपयोग करके लागू किया गया एक बड़ा योजक सामान्यतः उन संख्याओं के पारंपरिक जोड़ से बहुत तीव्रगामी होगा। | ||
== प्रेरणा == | == प्रेरणा == | ||
Line 8: | Line 8: | ||
= 100000000 | = 100000000 | ||
बुनियादी अंकगणित का उपयोग करते हुए, हम दाएं से बाएं , "8 + 2 = 0, कैरी 1", "7 + 2 + 1 = 0, कैरी 1", "6 + 3 + 1 = 0, कैरी 1", और इसी तरह राशि के अंत तक गणना करते हैं। | बुनियादी अंकगणित का उपयोग करते हुए, हम दाएं से बाएं , "8 + 2 = 0, कैरी 1", "7 + 2 + 1 = 0, कैरी 1", "6 + 3 + 1 = 0, कैरी 1", और इसी तरह राशि के अंत तक गणना करते हैं। सामान्यतः हम परिणाम के अंतिम अंक को एक ही बार में जान लेते हैं, हम पहले अंक को तब तक नहीं जान सकते जब तक कि हम गणना में प्रत्येक अंक से पारित नहीं होते हैं, प्रत्येक अंक से उसके बाईं ओर के अंक को पारित करते हैं। इस प्रकार दो n-अंकीय संख्याओं को जोड़ने में n के समानुपाती समय लगता है, भले ही हम जिस यंत्रगति का उपयोग कर रहे हैं वह एक साथ कई गणना करने में सक्षम हो। | ||
इलेक्ट्रॉनिक शब्दों में, बिट्स (द्विआधारी अंक) का उपयोग करते हुए, इसका अर्थ यह है कि भले ही हमारे निष्कासन में n एक-बिट | इलेक्ट्रॉनिक शब्दों में, बिट्स (द्विआधारी अंक) का उपयोग करते हुए, इसका अर्थ यह है कि भले ही हमारे निष्कासन में n एक-बिट योजक हों, फिर भी हमें संख्या के एक छोर से अन्य के लिए संभावित कैरी की अनुमति देने के लिए n के आनुपातिक समय की अनुमति देनी होगी। जब तक हमने निम्न नहीं किया है, | ||
# हम योग का परिणाम नहीं जानते हैं। | # हम योग का परिणाम नहीं जानते हैं। | ||
# हम नहीं जानते कि योग का परिणाम दी गई संख्या से बड़ा या छोटा | # हम नहीं जानते कि योग का परिणाम दी गई संख्या से बड़ा या छोटा है (उदाहरण के लिए, हम नहीं जानते कि यह धनात्मक है या ऋणात्मक)। | ||
कैरी अग्रावलोकन | कैरी अग्रावलोकन योजक विलंब को कम कर सकता है। सिद्धांत रूप में देरी को कम किया जा सकता है ताकि यह अभिलेख के समानुपाती हो, लेकिन बड़ी संख्या के लिए यह अब स्तिथि नहीं है, क्योंकि जब कैरी अग्रावलोकन लागू किया जाता है, तो चिप पर संकेतों को यात्रा करने वाली दूरी अनुपात से n तक बढ़ जाती है, और प्रगमन में देरी उसी दर से बढ़ती है। एक बार जब हम 512-बिट से 2048-बिट संख्या आकार प्राप्त कर लेते हैं, जो [[सार्वजनिक कुंजी क्रिप्टोग्राफी|सार्वजनिक कुंजी कूटलेखन]] में आवश्यक होते हैं, तो अग्रावलोकन से अधिक मदद नहीं मिलती है। | ||
== मूल अवधारणा == | == मूल अवधारणा == | ||
[[जॉन वॉन न्यूमैन]] के कारण अंत तक कैरी विश्लेषण में देरी करने या कैरी को बचाने का विचार है।<ref name="Neumann"/> | [[जॉन वॉन न्यूमैन]] के कारण अंत तक कैरी विश्लेषण में देरी करने या कैरी को बचाने का विचार है।<ref name="Neumann"/> | ||
दो अंकों का योग कभी भी 1 से अधिक नहीं हो सकता है, और दो अंकों का जोड़ 1 और उसमें 1 अंक जोड़ कर भी कभी भी 1 से अधिक नहीं हो सकता है। उदाहरण के लिए, दशमलव में, <math>9+9=18</math>, जिसमें 1 है; <math>9+9+1=19</math>, जिसमें एक 1 भी है। तीन अंक जोड़ते समय, हम पहले दो को जोड़ सकते हैं और एक योग और कैरी अंक दे सकते हैं; फिर योग और कैरी अंकों को तीसरे आंकड़े में | दो अंकों का योग कभी भी 1 से अधिक नहीं हो सकता है, और दो अंकों का जोड़ 1 और उसमें 1 अंक जोड़ कर भी कभी भी 1 से अधिक नहीं हो सकता है। उदाहरण के लिए, दशमलव में, <math>9+9=18</math>, जिसमें 1 है; <math>9+9+1=19</math>, जिसमें एक 1 भी है। तीन अंक जोड़ते समय, हम पहले दो को जोड़ सकते हैं और एक योग और कैरी अंक दे सकते हैं; फिर योग और कैरी अंकों को तीसरे आंकड़े में जोड़ते हैं और एक योग और कैरी अंक का उत्पादन करते हैं। युग्मक में, केवल अंक शून्य और एक होते हैं, और इसलिए <math>0+0=0</math>, <math>0+1=1</math>, और <math>1+1=0</math> 1 कैरी बिट के साथ है। कैरी बिट को जोड़ने से अधिक से अधिक, <math>1+1+1=1</math> कैरी 1 के साथ, इसलिए तीन तरह से जोड़ संभव है। इस वजह से, पहले तीन अंकों को जोड़ना और योग और कैरी करना भी संभव है; बाद के आंकड़ों के लिए, योग और कैरी दो पद हैं, और अगला एकल अंक इनमें जोड़ा जाता है। | ||
यहाँ 3 लंबी युग्मक संख्याओं के युग्मक योग का एक उदाहरण दिया गया है: | यहाँ 3 लंबी युग्मक संख्याओं के युग्मक योग का एक उदाहरण दिया गया है: | ||
Line 36: | Line 36: | ||
100110101010110111110010010011110 | 100110101010110111110010010011110 | ||
अब इन 2 अंकों को एक कैरी-प्रचार | अब इन 2 अंकों को एक कैरी-प्रचार योजक को भेजा जा सकता है जो परिणाम को प्रक्षेपण करेगा। | ||
यह देरी (गणना-समय) के नजरिए से बहुत लाभकारी था। यदि आप पारंपरिक तरीकों का उपयोग करके इन 3 अंकों को जोड़ते हैं, तो उत्तर प्राप्त करने के लिए आपको 2 कैरी-प्रचार | यह देरी (गणना-समय) के नजरिए से बहुत लाभकारी था। यदि आप पारंपरिक तरीकों का उपयोग करके इन 3 अंकों को जोड़ते हैं, तो उत्तर प्राप्त करने के लिए आपको 2 कैरी-प्रचार योजक विलंब होंगे। यदि आप कैरी-सेव तकनीक का उपयोग करते हैं, तो आपको केवल 1 कैरी-प्रचार योजक विलंब और 1 पूर्ण-योजक विलंब (जो कैरी-प्रचार विलंब से बहुत कम है) की आवश्यकता होती है। इस प्रकार, CSA योजक सामान्यतः बहुत तेज़ होते हैं। | ||
== कैर्री-सेव संचायक == | == कैर्री-सेव संचायक == | ||
यह मानते हुए कि हमारे पास प्रति अंक दो बिट संचयन है, हम प्रत्येक अंक की स्थिति में 0, 1, 2, या 3 मानों को संग्रहीत करते हुए एक [[निरर्थक बाइनरी प्रतिनिधित्व|निरर्थक युग्मक प्रतिनिधित्व]] का उपयोग कर सकते हैं। इसलिए यह स्पष्ट है कि हमारी संचयन क्षमता को अधिप्रवाह किए बिना हमारे कैरी-सेव रिजल्ट में एक और युग्मक | यह मानते हुए कि हमारे पास प्रति अंक दो बिट संचयन है, हम प्रत्येक अंक की स्थिति में 0, 1, 2, या 3 मानों को संग्रहीत करते हुए एक [[निरर्थक बाइनरी प्रतिनिधित्व|निरर्थक युग्मक प्रतिनिधित्व]] का उपयोग कर सकते हैं। इसलिए यह स्पष्ट है कि हमारी संचयन क्षमता को अधिप्रवाह किए बिना हमारे कैरी-सेव रिजल्ट में एक और युग्मक अंक जोड़ा जा सकता है: लेकिन फिर क्या? | ||
सफलता की कुंजी यह है कि प्रत्येक आंशिक जोड़ के क्षण में हम तीन बिट जोड़ते हैं: | सफलता की कुंजी यह है कि प्रत्येक आंशिक जोड़ के क्षण में हम तीन बिट जोड़ते हैं: | ||
Line 48: | Line 48: | ||
* 0 यदि हमारे स्टोर में अंक 0 या 2 है, या 1 यदि यह 1 या 3 है। | * 0 यदि हमारे स्टोर में अंक 0 या 2 है, या 1 यदि यह 1 या 3 है। | ||
* 0 यदि इसके दाईं ओर का अंक 0 या 1 है, या 1 यदि यह 2 या 3 है। | * 0 यदि इसके दाईं ओर का अंक 0 या 1 है, या 1 यदि यह 2 या 3 है। | ||
इसे दूसरे तरीके से रखने के लिए, हम अपने दाहिनी ओर की स्थिति से एक कैरी अंक ले रहे हैं, और एक कैरी अंक को बाईं ओर पारंपरिक जोड़ के रूप में हस्तांतरित कर रहे हैं | इसे दूसरे तरीके से रखने के लिए, हम अपने दाहिनी ओर की स्थिति से एक कैरी अंक ले रहे हैं, और एक कैरी अंक को बाईं ओर पारंपरिक जोड़ के रूप में हस्तांतरित कर रहे हैं; लेकिन कैरी अंक जिसे हम बाईं ओर पारित करते हैं, पिछली गणना का परिणाम है न कि वर्तमान की गणना का परिणाम। प्रत्येक घड़ी चक्र में, कैर्री को केवल एक कदम आगे बढ़ना होता है, न कि पारंपरिक जोड़ के रूप में n कदम। | ||
क्योंकि संकेतों को | क्योंकि संकेतों को अधिक दूर जाने की जरूरत नहीं है, घड़ी बहुत तेजी से टिक सकती है। .. | ||
गणना के अंत में परिणाम को युग्मक में बदलने की अभी भी आवश्यकता है, जिसका प्रभावी रूप से अर्थ है कि कैरी को एक पारंपरिक | गणना के अंत में परिणाम को युग्मक में बदलने की अभी भी आवश्यकता है, जिसका प्रभावी रूप से अर्थ है कि कैरी को एक पारंपरिक योजक की तरह संख्या के माध्यम से सभी तरह से यात्रा करने देना है। लेकिन अगर हमने 512-बिट गुणन करने की प्रक्रिया में 512 जोड़ दिए हैं, तो उस अंतिम रूपांतरण की लागत प्रभावी रूप से उन 512 योगों में विभाजित हो जाती है, इसलिए प्रत्येक जोड़ उस अंतिम पारंपरिक जोड़ की लागत का 1/512 वहन करता है। | ||
== | == कमियाँ == | ||
कैरी-सेव जोड़ के प्रत्येक चरण में, | कैरी-सेव जोड़ के प्रत्येक चरण में, | ||
Line 60: | Line 60: | ||
# हम अभी भी नहीं जानते हैं कि जोड़ का परिणाम दी गई संख्या से बड़ा है या छोटा है (उदाहरण के लिए, हम नहीं जानते कि यह सकारात्मक है या नकारात्मक)। | # हम अभी भी नहीं जानते हैं कि जोड़ का परिणाम दी गई संख्या से बड़ा है या छोटा है (उदाहरण के लिए, हम नहीं जानते कि यह सकारात्मक है या नकारात्मक)। | ||
प्रमापीय गुणन को लागू करने के लिए कैरी-सेव | प्रमापीय गुणन को लागू करने के लिए कैरी-सेव योजक्स का उपयोग करते समय यह बाद वाला बिंदु एक दोष है (भाग के बाद गुणा, शेष को केवल रखते हुए)।<ref>{{Cite book|last=Parhami|first=Behrooz |title=Computer arithmetic: algorithms and hardware designs |date=2010 |publisher=Oxford University Press |isbn=978-0-19-532848-6 |edition=2nd |location=New York |oclc=428033168}}</ref><ref>{{Cite journal|last=Lyakhov|first=P.|last2=Valueva|first2=M.|last3=Valuev|first3=G.|last4=Nagornov|first4=N.|date=2020|title=High-Performance Digital Filtering on Truncated Multiply-Accumulate Units in the Residue Number System |journal=IEEE Access|volume=8|pages=209181–209190|doi=10.1109/ACCESS.2020.3038496 |doi-access=free |issn=2169-3536}}</ref> यदि हम यह नहीं जान सकते हैं कि मध्यवर्ती परिणाम मापांक से अधिक है या कम है, तो हम कैसे जान सकते हैं कि मापांक घटाना है या नहीं? | ||
[[मोंटगोमरी गुणन|प्रतिपाल्य गुणन]], एक समाधान है जो परिणाम के सबसे दाहिने अंक पर निर्भर करता है; हालांकि कैरी-सेव योग की तरह ही, यह एक निश्चित शिरोपरि वहन करता है, ताकि प्रतिपाल्य गुणन का एक क्रम समय बचाता है लेकिन एक अकेला नहीं। सौभाग्य से घातांक, जो प्रभावी रूप से गुणन का एक क्रम है, सार्वजनिक-कुंजी कूटलेखन में सबसे सामान्य संचालन है। | [[मोंटगोमरी गुणन|प्रतिपाल्य गुणन]], एक समाधान है जो परिणाम के सबसे दाहिने अंक पर निर्भर करता है; हालांकि कैरी-सेव योग की तरह ही, यह एक निश्चित शिरोपरि वहन करता है, ताकि प्रतिपाल्य गुणन का एक क्रम समय बचाता है लेकिन एक अकेला नहीं। सौभाग्य से घातांक, जो प्रभावी रूप से गुणन का एक क्रम है, सार्वजनिक-कुंजी कूटलेखन में सबसे सामान्य संचालन है। | ||
Line 68: | Line 68: | ||
== तकनीकी विवरण == | == तकनीकी विवरण == | ||
कैरी-सेव ईकाई में n | कैरी-सेव ईकाई में n योजक पूर्ण योजक होते हैं, जिनमें से प्रत्येक एक एकल योग की गणना करता है और तीन इनपुट संख्याओं के संबंधित बिट्स पर आधारित होता है। तीन n-बिट संख्या 'a', 'b' और 'c' को देखते हुए, यह आंशिक योग 'ps' और एक शिफ्ट-कैरी 'sc' उत्पन्न करता है: | ||
:<math>ps_i = a_i \oplus b_i \oplus c_i,</math> | :<math>ps_i = a_i \oplus b_i \oplus c_i,</math> | ||
Line 75: | Line 75: | ||
# [[तार्किक पारी]] कैरी सीक्वेंस sc को एक स्थान से छोड़ दिया। | # [[तार्किक पारी]] कैरी सीक्वेंस sc को एक स्थान से छोड़ दिया। | ||
# आंशिक योग अनुक्रम ps के सामने ([[सबसे महत्वपूर्ण बिट]]) में 0 को जोड़ना। | # आंशिक योग अनुक्रम ps के सामने ([[सबसे महत्वपूर्ण बिट]]) में 0 को जोड़ना। | ||
# इन दोनों को एक साथ जोड़ने और परिणामी (''n'' + 1) -बिट मान उत्पन्न करने के लिए एक रिपल कैरी | # इन दोनों को एक साथ जोड़ने और परिणामी (''n'' + 1) -बिट मान उत्पन्न करने के लिए एक रिपल कैरी योजक का उपयोग करना। | ||
== यह भी देखें == | == यह भी देखें == |
Revision as of 12:46, 16 February 2023
कैरी-सेव योजक[1][2][nb 1]एक प्रकार का योजक (इलेक्ट्रॉनिक्स) है, जिसका उपयोग तीन या अधिक युग्मक अंक प्रणाली संख्याओं के योग की कुशलता से गणना करने के लिए किया जाता है। यह अन्य अंकीय योजकों से भिन्न है जिसमें यह दो (या अधिक) संख्याओं का प्रक्षेपण करता है, और इन प्रक्षेपण को एक साथ जोड़कर मूल योग का उत्तर प्राप्त किया जा सकता है। कैरी सेव योजक का उपयोग सामान्यतः युग्मक गुणक में किया जाता है, क्योंकि युग्मक गुणक में गुणन के बाद दो से अधिक युग्मक अंक सम्मिलित होते हैं। इस तकनीक का उपयोग करके लागू किया गया एक बड़ा योजक सामान्यतः उन संख्याओं के पारंपरिक जोड़ से बहुत तीव्रगामी होगा।
प्रेरणा
निम्न योग पर विचार करें:
12345678 + 87654322 = 100000000
बुनियादी अंकगणित का उपयोग करते हुए, हम दाएं से बाएं , "8 + 2 = 0, कैरी 1", "7 + 2 + 1 = 0, कैरी 1", "6 + 3 + 1 = 0, कैरी 1", और इसी तरह राशि के अंत तक गणना करते हैं। सामान्यतः हम परिणाम के अंतिम अंक को एक ही बार में जान लेते हैं, हम पहले अंक को तब तक नहीं जान सकते जब तक कि हम गणना में प्रत्येक अंक से पारित नहीं होते हैं, प्रत्येक अंक से उसके बाईं ओर के अंक को पारित करते हैं। इस प्रकार दो n-अंकीय संख्याओं को जोड़ने में n के समानुपाती समय लगता है, भले ही हम जिस यंत्रगति का उपयोग कर रहे हैं वह एक साथ कई गणना करने में सक्षम हो।
इलेक्ट्रॉनिक शब्दों में, बिट्स (द्विआधारी अंक) का उपयोग करते हुए, इसका अर्थ यह है कि भले ही हमारे निष्कासन में n एक-बिट योजक हों, फिर भी हमें संख्या के एक छोर से अन्य के लिए संभावित कैरी की अनुमति देने के लिए n के आनुपातिक समय की अनुमति देनी होगी। जब तक हमने निम्न नहीं किया है,
- हम योग का परिणाम नहीं जानते हैं।
- हम नहीं जानते कि योग का परिणाम दी गई संख्या से बड़ा या छोटा है (उदाहरण के लिए, हम नहीं जानते कि यह धनात्मक है या ऋणात्मक)।
कैरी अग्रावलोकन योजक विलंब को कम कर सकता है। सिद्धांत रूप में देरी को कम किया जा सकता है ताकि यह अभिलेख के समानुपाती हो, लेकिन बड़ी संख्या के लिए यह अब स्तिथि नहीं है, क्योंकि जब कैरी अग्रावलोकन लागू किया जाता है, तो चिप पर संकेतों को यात्रा करने वाली दूरी अनुपात से n तक बढ़ जाती है, और प्रगमन में देरी उसी दर से बढ़ती है। एक बार जब हम 512-बिट से 2048-बिट संख्या आकार प्राप्त कर लेते हैं, जो सार्वजनिक कुंजी कूटलेखन में आवश्यक होते हैं, तो अग्रावलोकन से अधिक मदद नहीं मिलती है।
मूल अवधारणा
जॉन वॉन न्यूमैन के कारण अंत तक कैरी विश्लेषण में देरी करने या कैरी को बचाने का विचार है।[3]
दो अंकों का योग कभी भी 1 से अधिक नहीं हो सकता है, और दो अंकों का जोड़ 1 और उसमें 1 अंक जोड़ कर भी कभी भी 1 से अधिक नहीं हो सकता है। उदाहरण के लिए, दशमलव में, , जिसमें 1 है; , जिसमें एक 1 भी है। तीन अंक जोड़ते समय, हम पहले दो को जोड़ सकते हैं और एक योग और कैरी अंक दे सकते हैं; फिर योग और कैरी अंकों को तीसरे आंकड़े में जोड़ते हैं और एक योग और कैरी अंक का उत्पादन करते हैं। युग्मक में, केवल अंक शून्य और एक होते हैं, और इसलिए , , और 1 कैरी बिट के साथ है। कैरी बिट को जोड़ने से अधिक से अधिक, कैरी 1 के साथ, इसलिए तीन तरह से जोड़ संभव है। इस वजह से, पहले तीन अंकों को जोड़ना और योग और कैरी करना भी संभव है; बाद के आंकड़ों के लिए, योग और कैरी दो पद हैं, और अगला एकल अंक इनमें जोड़ा जाता है।
यहाँ 3 लंबी युग्मक संख्याओं के युग्मक योग का एक उदाहरण दिया गया है:
10111010101011011111000000001101 (a) + 11011110101011011011111011101111 (b) + 00010010101101110101001101010010 (c)
इसे करने का पारंपरिक तरीका पहले (a+b) की गणना करना और फिर ((a+b)+c) की गणना करना होगा। किसी भी प्रकार के कैरी प्रवर्धन को त्याग कर कैरी-सेव अंकगणितीय कार्य करता है। यह अंकों के आधार पर योग की गणना करता है, जैसे:
10111010101011011111000000001101 + 11011110101011011011111011101111 + 00010010101101110101001101010010 = 21132130303123132223112112112222
संकेतन अपरंपरागत है, लेकिन परिणाम अभी भी स्पष्ट नहीं है। यदि हम तीन संख्याओं को a, b और c मान लें। फिर यहाँ, परिणाम को 2 युग्मक अंकों के योग के रूप में वर्णित किया जाएगा, जहाँ पहली संख्या, S, केवल अंकों को जोड़कर प्राप्त योग है (बिना किसी प्रचार प्रसार के), अर्थात Si = ai ⊕ bi ⊕ ci और दूसरी संख्या, C, पिछले अलग-अलग योगों से बनी है, यानी Ci+1 = (aibi) + (bici) + (ciai) :
01110110101101110001110110110000 और 100110101010110111110010010011110
अब इन 2 अंकों को एक कैरी-प्रचार योजक को भेजा जा सकता है जो परिणाम को प्रक्षेपण करेगा।
यह देरी (गणना-समय) के नजरिए से बहुत लाभकारी था। यदि आप पारंपरिक तरीकों का उपयोग करके इन 3 अंकों को जोड़ते हैं, तो उत्तर प्राप्त करने के लिए आपको 2 कैरी-प्रचार योजक विलंब होंगे। यदि आप कैरी-सेव तकनीक का उपयोग करते हैं, तो आपको केवल 1 कैरी-प्रचार योजक विलंब और 1 पूर्ण-योजक विलंब (जो कैरी-प्रचार विलंब से बहुत कम है) की आवश्यकता होती है। इस प्रकार, CSA योजक सामान्यतः बहुत तेज़ होते हैं।
कैर्री-सेव संचायक
यह मानते हुए कि हमारे पास प्रति अंक दो बिट संचयन है, हम प्रत्येक अंक की स्थिति में 0, 1, 2, या 3 मानों को संग्रहीत करते हुए एक निरर्थक युग्मक प्रतिनिधित्व का उपयोग कर सकते हैं। इसलिए यह स्पष्ट है कि हमारी संचयन क्षमता को अधिप्रवाह किए बिना हमारे कैरी-सेव रिजल्ट में एक और युग्मक अंक जोड़ा जा सकता है: लेकिन फिर क्या?
सफलता की कुंजी यह है कि प्रत्येक आंशिक जोड़ के क्षण में हम तीन बिट जोड़ते हैं:
- 0 या 1, हम जो संख्या जोड़ रहे हैं उससे।
- 0 यदि हमारे स्टोर में अंक 0 या 2 है, या 1 यदि यह 1 या 3 है।
- 0 यदि इसके दाईं ओर का अंक 0 या 1 है, या 1 यदि यह 2 या 3 है।
इसे दूसरे तरीके से रखने के लिए, हम अपने दाहिनी ओर की स्थिति से एक कैरी अंक ले रहे हैं, और एक कैरी अंक को बाईं ओर पारंपरिक जोड़ के रूप में हस्तांतरित कर रहे हैं; लेकिन कैरी अंक जिसे हम बाईं ओर पारित करते हैं, पिछली गणना का परिणाम है न कि वर्तमान की गणना का परिणाम। प्रत्येक घड़ी चक्र में, कैर्री को केवल एक कदम आगे बढ़ना होता है, न कि पारंपरिक जोड़ के रूप में n कदम।
क्योंकि संकेतों को अधिक दूर जाने की जरूरत नहीं है, घड़ी बहुत तेजी से टिक सकती है। ..
गणना के अंत में परिणाम को युग्मक में बदलने की अभी भी आवश्यकता है, जिसका प्रभावी रूप से अर्थ है कि कैरी को एक पारंपरिक योजक की तरह संख्या के माध्यम से सभी तरह से यात्रा करने देना है। लेकिन अगर हमने 512-बिट गुणन करने की प्रक्रिया में 512 जोड़ दिए हैं, तो उस अंतिम रूपांतरण की लागत प्रभावी रूप से उन 512 योगों में विभाजित हो जाती है, इसलिए प्रत्येक जोड़ उस अंतिम पारंपरिक जोड़ की लागत का 1/512 वहन करता है।
कमियाँ
कैरी-सेव जोड़ के प्रत्येक चरण में,
- हम एक ही बार में जोड़ का परिणाम जानते हैं।
- हम अभी भी नहीं जानते हैं कि जोड़ का परिणाम दी गई संख्या से बड़ा है या छोटा है (उदाहरण के लिए, हम नहीं जानते कि यह सकारात्मक है या नकारात्मक)।
प्रमापीय गुणन को लागू करने के लिए कैरी-सेव योजक्स का उपयोग करते समय यह बाद वाला बिंदु एक दोष है (भाग के बाद गुणा, शेष को केवल रखते हुए)।[4][5] यदि हम यह नहीं जान सकते हैं कि मध्यवर्ती परिणाम मापांक से अधिक है या कम है, तो हम कैसे जान सकते हैं कि मापांक घटाना है या नहीं?
प्रतिपाल्य गुणन, एक समाधान है जो परिणाम के सबसे दाहिने अंक पर निर्भर करता है; हालांकि कैरी-सेव योग की तरह ही, यह एक निश्चित शिरोपरि वहन करता है, ताकि प्रतिपाल्य गुणन का एक क्रम समय बचाता है लेकिन एक अकेला नहीं। सौभाग्य से घातांक, जो प्रभावी रूप से गुणन का एक क्रम है, सार्वजनिक-कुंजी कूटलेखन में सबसे सामान्य संचालन है।
सावधानीपूर्वक त्रुटि विश्लेषण[6]मापांक को घटाने के बारे में चुनाव करने की अनुमति देता है, भले ही हम निश्चित रूप से यह नहीं जानते हैं कि जोड़ का परिणाम घटाव के लिए पर्याप्त बड़ा है या नहीं। इसके काम करने के लिए, विद्युत परिपथ अभिकल्पना के लिए आवश्यक है कि वह -2, -1, 0, +1 या +2 मापांक को जोड़ सके। मॉन्टगोमरी गुणन पर लाभ यह है कि गुणन के प्रत्येक क्रम से जुड़ा कोई निश्चित शिरोपरी नहीं है।
तकनीकी विवरण
कैरी-सेव ईकाई में n योजक पूर्ण योजक होते हैं, जिनमें से प्रत्येक एक एकल योग की गणना करता है और तीन इनपुट संख्याओं के संबंधित बिट्स पर आधारित होता है। तीन n-बिट संख्या 'a', 'b' और 'c' को देखते हुए, यह आंशिक योग 'ps' और एक शिफ्ट-कैरी 'sc' उत्पन्न करता है:
इसके बाद पूरे योग की गणना की जा सकती है:
- तार्किक पारी कैरी सीक्वेंस sc को एक स्थान से छोड़ दिया।
- आंशिक योग अनुक्रम ps के सामने (सबसे महत्वपूर्ण बिट) में 0 को जोड़ना।
- इन दोनों को एक साथ जोड़ने और परिणामी (n + 1) -बिट मान उत्पन्न करने के लिए एक रिपल कैरी योजक का उपयोग करना।
यह भी देखें
टिप्पणियाँ
- ↑ Carry-save adder is often abbreviated as CSA, however, this can be confused with the carry-skip adder.
संदर्भ
- ↑ Earle, John G. (1965-07-12), Latched Carry Save Adder Circuit for Multipliers, U.S. Patent 3,340,388
- ↑ Earle, John G. (March 1965), "Latched Carry-Save Adder", IBM Technical Disclosure Bulletin, 7 (10): 909–910
- ↑ von Neumann, John. Collected Works.
- ↑ Parhami, Behrooz (2010). Computer arithmetic: algorithms and hardware designs (2nd ed.). New York: Oxford University Press. ISBN 978-0-19-532848-6. OCLC 428033168.
- ↑ Lyakhov, P.; Valueva, M.; Valuev, G.; Nagornov, N. (2020). "High-Performance Digital Filtering on Truncated Multiply-Accumulate Units in the Residue Number System". IEEE Access. 8: 209181–209190. doi:10.1109/ACCESS.2020.3038496. ISSN 2169-3536.
- ↑ Kochanski, Martin (2003-08-19). "A New Method of Serial Modular Multiplication" (PDF). Archived from the original (PDF) on 2018-07-16. Retrieved 2018-07-16.
अग्रिम पठन
- Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.