कैरी-सेव एडर

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

प्रेरणा

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

   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 अंक जोड़ कर भी कभी भी 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 (a)
+ 11011110101011011011111011101111 (b)
+ 00010010101101110101001101010010 (c)

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

  10111010101011011111000000001101
+ 11011110101011011011111011101111
+ 00010010101101110101001101010010
= 21132130303123132223112112112222

संकेतन अपरंपरागत है, लेकिन परिणाम अभी भी स्पष्ट नहीं है। यदि हम तीन संख्याओं को a, b और c मान लें। फिर यहाँ, परिणाम को 2 युग्मक अंकों के योग के रूप में वर्णित किया जाएगा, जहाँ पहली संख्या, S, केवल अंकों को जोड़कर प्राप्त योग है (बिना किसी प्रचार प्रसार के), अर्थात S_i = a_i ⊕ b_i ⊕ c_i और दूसरी संख्या, C, पिछले अलग-अलग योगों से बनी है, यानी C_i+1 = (a_ib_i) + (b_ic_i) + (c_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 योजक पूर्ण योजक होते हैं, जिनमें से प्रत्येक एक एकल योग की गणना करता है और तीन इनपुट संख्याओं के संबंधित बिट्स पर आधारित होता है। तीन n-बिट संख्या 'a', 'b' और 'c' को देखते हुए, यह आंशिक योग 'ps' और एक शिफ्ट-कैरी 'sc' उत्पन्न करता है:

$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.