कैरी-सेव योजक

एक कैरी-सेव योजक ^[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 से अधिक नहीं हो सकता है। उदाहरण के लिए, दशमलव में, $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 लंबी बाइनरी संख्याओं के बाइनरी योग का एक उदाहरण दिया गया है:

  1011 1010 1010 1101 1111 0000 0000 1101 (ए)
+ 1101 1110 1010 1101 1011 1110 1110 1111 (बी)
+ 0001 0010 1011 0111 0101 0011 0101 0010 (सी)

ऐसा करने का सीधा तरीका यह होगा कि पहले (ए+बी) की गणना करें, और फिर ((ए+बी)+सी) की गणना करें। किसी भी प्रकार के कैरी प्रसार को त्यागकर कैरी-सेव अंकगणितीय कार्य करें। यह अंक दर अंक योग की गणना इस प्रकार करता है:

  1011 1010 1010 1101 1111 0000 0000 1101 (ए)
+ 1101 1110 1010 1101 1011 1110 1110 1111 (बी)
+ 0001 0010 1011 0111 0101 0011 0101 0010 (सी)
= 2113 2130 3031 2313 2223 1121 1211 2222

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

   0111 0110 1011 0111 0001 1101 1011 0000 और
 1 0011 0101 0101 1011 1110 0100 1001 1110

अब इन 2 नंबरों को कैरी-प्रोपेगेट योजक पर भेजा जा सकता है जो परिणाम आउटपुट करेगा।

विलंब (गणना-समय) के नजरिए से यह बहुत फायदेमंद था। यदि आप पारंपरिक तरीकों का उपयोग करके इन 3 नंबरों को जोड़ते हैं, तो उत्तर तक पहुंचने में आपको 2 कैरी-प्रोपेगेट योजक विलंब लगेगा। यदि आप कैरी-सेव तकनीक का उपयोग करते हैं, तो आपको केवल 1 कैरी-प्रोपेगेट योजक विलंब और 1 पूर्ण-योजक विलंब की आवश्यकता होती है (जो कैरी-प्रोपेगेट विलंब से बहुत कम है)। इस प्रकार, सीएसए आमतौर पर बहुत तेज़ होते हैं।

संचायक ले जाएं-बचाएं

मान लीजिए कि हमारे पास प्रति अंक दो बिट स्टोरेज हैं, तो हम प्रत्येक अंक की स्थिति में 0, 1, 2, या 3 मान संग्रहीत करते हुए एक अनावश्यक बाइनरी प्रतिनिधित्व का उपयोग कर सकते हैं। इसलिए यह स्पष्ट है कि हमारी भंडारण क्षमता को बढ़ाए बिना हमारे कैरी-सेव परिणाम में एक और बाइनरी नंबर जोड़ा जा सकता है: लेकिन फिर क्या?

सफलता की कुंजी यह है कि प्रत्येक आंशिक जोड़ के समय हम तीन बिट जोड़ते हैं:

0 या 1, हम जो संख्या जोड़ रहे हैं उसमें से।
यदि हमारे स्टोर में अंक 0 या 2 है तो 0, या 1 या 3 है तो 1।
यदि दाहिनी ओर का अंक 0 या 1 है तो 0, या यदि 2 या 3 है तो 1।

इसे दूसरे तरीके से कहें तो, हम अपने दाहिनी ओर की स्थिति से एक कैरी डिजिट ले रहे हैं, और पारंपरिक जोड़ की तरह, एक कैरी डिजिट को बाईं ओर पास कर रहे हैं; लेकिन बाईं ओर हम जो कैरी डिजिट पास करते हैं वह पिछली गणना का परिणाम है, वर्तमान का नहीं। प्रत्येक घड़ी चक्र में, कैरीज़ को केवल एक कदम आगे बढ़ना होता है, पारंपरिक जोड़ की तरह n कदम नहीं।

क्योंकि सिग्नलों को उतनी दूर नहीं जाना पड़ता, घड़ी बहुत तेजी से टिक सकती है। ..

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

कमियां

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

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

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

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

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

तकनीकी विवरण

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

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}).

फिर संपूर्ण राशि की गणना इस प्रकार की जा सकती है:

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

यह भी देखें

वालेस का पेड़

संदर्भ

↑ 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). "अवशेष संख्या प्रणाली में काटी गई बहु-संचित इकाइयों पर उच्च-प्रदर्शन डिजिटल फ़िल्टरिंग". 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.

[NB_CSA-3] Carry-save adder is often abbreviated as CSA, however, this can be confused with the carry-skip adder.

[Earle_1965_1-1] Earle, John G. (1965-07-12), Latched Carry Save Adder Circuit for Multipliers, U.S. Patent 3,340,388

[Earle_1965_2-2] Earle, John G. (March 1965), "Latched Carry-Save Adder", IBM Technical Disclosure Bulletin, 7 (10): 909–910

[Neumann-4] von Neumann, John. Collected Works.

[5] Parhami, Behrooz (2010). Computer arithmetic: algorithms and hardware designs (2nd ed.). New York: Oxford University Press. ISBN 978-0-19-532848-6. OCLC 428033168.

[6] Lyakhov, P.; Valueva, M.; Valuev, G.; Nagornov, N. (2020). "अवशेष संख्या प्रणाली में काटी गई बहु-संचित इकाइयों पर उच्च-प्रदर्शन डिजिटल फ़िल्टरिंग". IEEE Access. 8: 209181–209190. doi:10.1109/ACCESS.2020.3038496. ISSN 2169-3536.

[encrypt-7] 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.

[1]

[2]

[nb 1]

[3]

[4]

[5]

[6]

कैरी-सेव योजक

Contents