कैरी-सेव एडर

एक कैरी-सेव योजकएक प्रकार का योजक (इलेक्ट्रॉनिक्स) है, जिसका उपयोग तीन या अधिक बाइनरी अंक प्रणाली संख्याओं के योग की कुशलता से गणना करने के लिए किया जाता है। यह अन्य डिजिटल योजकों से भिन्न है जिसमें यह दो (या अधिक) संख्याओं को आउटपुट करता है, और इन आउटपुट को एक साथ जोड़कर मूल योग का उत्तर प्राप्त किया जा सकता है। एक कैरी सेव ऐडर का उपयोग आमतौर पर बाइनरी गुणक में किया जाता है, क्योंकि बाइनरी गुणक में गुणन के बाद दो से अधिक बाइनरी नंबर शामिल होते हैं। इस तकनीक का उपयोग करके लागू किया गया एक बड़ा योजक आमतौर पर उन संख्याओं के पारंपरिक जोड़ से बहुत तेज होगा।

प्रेरणा

योग पर विचार करें:

   12345678
+ 87654322
= 100000000

बुनियादी अंकगणित का उपयोग करते हुए, हम दाएं से बाएं, 8 + 2 = 0 की गणना करते हैं, 1, 7 + 2 + 1 = 0 ले जाते हैं, 1, 6 + 3 + 1 = 0 ले जाते हैं, 1 ले जाते हैं, और इसी तरह योग के अंत तक . हालाँकि हम परिणाम के अंतिम अंक को एक ही बार में जान लेते हैं, हम पहले अंक को तब तक नहीं जान सकते जब तक कि हम गणना में प्रत्येक अंक से गुजरे नहीं हैं, प्रत्येक अंक से उसके बाईं ओर के अंक को पास करते हैं। इस प्रकार दो n-अंकीय संख्याओं को जोड़ने में n के समानुपाती समय लगता है, भले ही हम जिस मशीनरी का उपयोग कर रहे हैं वह एक साथ कई गणना करने में सक्षम हो।

इलेक्ट्रॉनिक शब्दों में, बिट्स (द्विआधारी अंक) का उपयोग करते हुए, इसका मतलब यह है कि भले ही हमारे निपटान में n एक-बिट योजक हों, फिर भी हमें संख्या के एक छोर से प्रचार करने के लिए संभावित कैरी की अनुमति देने के लिए n के आनुपातिक समय की अनुमति देनी होगी। अन्य के लिए। जब तक हमने ऐसा नहीं किया है,

1. हम योग का परिणाम नहीं जानते हैं।
2. हम नहीं जानते कि जोड़ का परिणाम दी गई संख्या से बड़ा है या छोटा (उदाहरण के लिए, हम नहीं जानते कि यह धनात्मक है या ऋणात्मक)।

कैरी लुक-फॉरवर्ड ऐडर विलंब को कम कर सकता है। सिद्धांत रूप में देरी को कम किया जा सकता है ताकि यह लॉग के समानुपाती हो, लेकिन बड़ी संख्या के लिए यह अब मामला नहीं है, क्योंकि जब कैरी लुक-फॉरवर्ड लागू किया जाता है, तो चिप पर संकेतों को यात्रा करने वाली दूरी अनुपात में बढ़ जाती है से n तक, और प्रचार-प्रसार में देरी उसी दर से बढ़ती है। एक बार जब हम 512-बिट से 2048-बिट संख्या आकार प्राप्त कर लेते हैं, जो सार्वजनिक कुंजी क्रिप्टोग्राफी में आवश्यक होते हैं, तो लुक-फॉरवर्ड ले जाने से ज्यादा मदद नहीं मिलती है।

मूल अवधारणा

जॉन वॉन न्यूमैन के कारण अंत तक कैरी रिज़ॉल्यूशन में देरी करने या कैरी को बचाने का विचार है।

दो अंकों का योग कभी भी 1 से अधिक नहीं हो सकता है, और दो अंकों का जोड़ 1 भी कभी भी 1 से अधिक नहीं हो सकता है। उदाहरण के लिए, दशमलव में, $9+9=18$, जिसमें 1 है; $9+9+1=19$, जिसमें एक 1 भी है। तीन अंक जोड़ते समय, हम पहले दो को जोड़ सकते हैं और एक योग और कैरी अंक दे सकते हैं; फिर योग और कैरी अंकों को तीसरे आंकड़े में जोड़ें और एक योग और कैरी अंक का उत्पादन करें। बाइनरी में, केवल अंक शून्य और एक होते हैं, और इसलिए $0+0=0$, $0+1=1$, और $1+1=0$ कैरी बिट के साथ 1. कैरी बिट को जोड़ने से अधिक से अधिक, $1+1+1=1$ कैरी 1 के साथ, इसलिए तीन तरह से जोड़ संभव है। इस वजह से, पहले तीन अंकों को जोड़ना और योग और कैरी करना भी संभव है; बाद के आंकड़ों के लिए, योग और कैरी दो पद हैं, और अगला एकल अंक इनमें जोड़ा जाता है।

यहाँ 3 लंबी बाइनरी संख्याओं के बाइनरी योग का एक उदाहरण दिया गया है:

  10111010101011011111000000001101 (ए)
+ 11011110101011011011111011101111 (बी)
+ 00010010101101110101001101010010 (सी)

इसे करने का पारंपरिक तरीका पहले (a+b) की गणना करना और फिर ((a+b)+c) की गणना करना होगा। किसी भी प्रकार के कैरी प्रोपेगेशन को त्याग कर कैरी-सेव अंकगणितीय कार्य। यह अंकों के आधार पर योग की गणना करता है, जैसे:

  10111010101011011111000000001101
+ 11011110101011011011111011101111
+ 00010010101101110101001101010010
= 21132130303123132223112112112222

संकेतन अपरंपरागत है, लेकिन परिणाम अभी भी स्पष्ट नहीं है। यदि हम तीन संख्याओं को a, b और c मान लें। फिर यहाँ, परिणाम को 2 बाइनरी नंबरों के योग के रूप में वर्णित किया जाएगा, जहाँ पहली संख्या, S, केवल अंकों को जोड़कर प्राप्त योग है (बिना किसी प्रचार प्रसार के), अर्थात S_i = ए_i ⊕ ख_i ⊕ सी_i और दूसरी संख्या, सी, पिछले अलग-अलग योगों से बनी है, यानी सी_i+1 = (अ_ib_i) + (बी_ic_i) + (सी_ia_i) :

  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 वहन करता है।

कमियां

कैरी-सेव जोड़ के प्रत्येक चरण में,

1. हम एक ही बार में जोड़ का परिणाम जानते हैं।
2. हम अभी भी नहीं जानते हैं कि जोड़ का परिणाम दी गई संख्या से बड़ा है या छोटा है (उदाहरण के लिए, हम नहीं जानते कि यह सकारात्मक है या नकारात्मक)।

मॉड्यूलर गुणन को लागू करने के लिए कैरी-सेव एडर्स का उपयोग करते समय यह बाद वाला बिंदु एक दोष है (भाग के बाद गुणा, शेष को केवल रखते हुए)। यदि हम यह नहीं जान सकते हैं कि मध्यवर्ती परिणाम मापांक से अधिक है या कम है, तो हम कैसे जान सकते हैं कि मापांक घटाना है या नहीं?

मोंटगोमरी गुणन, जो परिणाम के सबसे दाहिने अंक पर निर्भर करता है, एक समाधान है; हालांकि कैरी-सेव ऐडिशन की तरह ही, यह एक निश्चित ओवरहेड वहन करता है, ताकि मोंटगोमरी गुणन का एक क्रम समय बचाता है लेकिन एक अकेला नहीं। सौभाग्य से घातांक, जो प्रभावी रूप से गुणन का एक क्रम है, सार्वजनिक-कुंजी क्रिप्टोग्राफी में सबसे आम ऑपरेशन है।

सावधानीपूर्वक त्रुटि विश्लेषणमापांक को घटाने के बारे में चुनाव करने की अनुमति देता है, भले ही हम निश्चित रूप से यह नहीं जानते हैं कि जोड़ का परिणाम घटाव के लिए पर्याप्त बड़ा है या नहीं। इसके लिए काम करने के लिए, सर्किट डिजाइन के लिए आवश्यक है कि वह -2, -1, 0, +1 या +2 मापांक को जोड़ सके। मॉन्टगोमरी गुणन पर लाभ यह है कि गुणन के प्रत्येक क्रम से जुड़ा कोई निश्चित ओवरहेड नहीं है।

तकनीकी विवरण

कैरी-सेव यूनिट में n योजक (इलेक्ट्रॉनिक्स) # पूर्ण योजक होते हैं, जिनमें से प्रत्येक एक एकल योग की गणना करता है और तीन इनपुट संख्याओं के संबंधित बिट्स पर आधारित होता है। तीन एन-बिट संख्या 'ए', 'बी' और 'सी' को देखते हुए, यह आंशिक योग 'पीएस' और एक शिफ्ट-कैरी 'एससी' उत्पन्न करता है:

$ps_{i}=a_{i}\oplus b_{i}\oplus c_{i},$

$sc_{i}=(a_{i}\wedge b_{i})\vee (a_{i}\wedge c_{i})\vee (b_{i}\wedge c_{i}).$

इसके बाद पूरी राशि की गणना की जा सकती है:

1. तार्किक पारी कैरी सीक्वेंस sc को एक स्थान से छोड़ दिया।
2. आंशिक योग अनुक्रम ps के सामने (सबसे महत्वपूर्ण बिट) में 0 को जोड़ना।
3. एक योजक (इलेक्ट्रॉनिक्स) का उपयोग करना # रिपल-कैरी योजक इन दोनों को एक साथ जोड़ने और परिणामी (n + 1) - बिट मान का उत्पादन करने के लिए।

यह भी देखें

• वालेस का पेड़

अग्रिम पठन

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