कैरी-सेव एडर: Difference between revisions

From Vigyanwiki
(Created page with "{{Sidebar arithmetic logic circuits|expand=Components|expand-components=Adder}} एक कैरी-सेव योजक<ref name="Earle_1965_1"/><ref name="Earle_1965_2"/><...")
 
m (6 revisions imported from alpha:कैरी-सेव_एडर)
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Sidebar arithmetic logic circuits|expand=Components|expand-components=Adder}}
'''कैरी-सेव योजक'''<ref name="Earle_1965_1"/><ref name="Earle_1965_2"/><ref group="nb" name="NB_CSA"/>एक प्रकार का [[योजक (इलेक्ट्रॉनिक्स)]] है, जिसका उपयोग तीन या अधिक युग्मक अंक प्रणाली संख्याओं के योग की कुशलता से गणना करने के लिए किया जाता है। यह अन्य अंकीय योजकों से भिन्न है जिसमें यह दो (या अधिक) संख्याओं का प्रक्षेपण करता है, और इन प्रक्षेपण को एक साथ जोड़कर मूल योग का उत्तर प्राप्त किया जा सकता है। कैरी सेव योजक का उपयोग सामान्यतः युग्मक गुणक में किया जाता है, क्योंकि युग्मक गुणक में गुणन के बाद दो से अधिक युग्मक अंक सम्मिलित होते हैं। इस तकनीक का उपयोग करके लागू किया गया एक बड़ा योजक सामान्यतः उन संख्याओं के पारंपरिक जोड़ से बहुत तीव्रगामी होगा।
एक कैरी-सेव योजक<ref name="Earle_1965_1"/><ref name="Earle_1965_2"/><ref group="nb" name="NB_CSA"/>एक प्रकार का [[योजक (इलेक्ट्रॉनिक्स)]] है, जिसका उपयोग तीन या अधिक बाइनरी अंक प्रणाली संख्याओं के योग की कुशलता से गणना करने के लिए किया जाता है। यह अन्य डिजिटल योजकों से भिन्न है जिसमें यह दो (या अधिक) संख्याओं को आउटपुट करता है, और इन आउटपुट को एक साथ जोड़कर मूल योग का उत्तर प्राप्त किया जा सकता है। एक कैरी सेव ऐडर का उपयोग आमतौर पर बाइनरी गुणक में किया जाता है, क्योंकि बाइनरी गुणक में गुणन के बाद दो से अधिक बाइनरी नंबर शामिल होते हैं। इस तकनीक का उपयोग करके लागू किया गया एक बड़ा योजक आमतौर पर उन संख्याओं के पारंपरिक जोड़ से बहुत तेज होगा।


== प्रेरणा ==
== प्रेरणा ==


योग पर विचार करें:
निम्न योग पर विचार करें:
     12345678
     12345678
  + 87654322
  + 87654322
  = 100000000
  = 100000000


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


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


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


== मूल अवधारणा ==
== मूल अवधारणा ==
[[जॉन वॉन न्यूमैन]] के कारण अंत तक कैरी रिज़ॉल्यूशन में देरी करने या कैरी को बचाने का विचार है।<ref name="Neumann"/>
[[जॉन वॉन न्यूमैन]] के कारण अंत तक कैरी विश्लेषण में देरी करने या कैरी को बचाने का विचार है।<ref name="Neumann"/>


दो अंकों का योग कभी भी 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 के साथ, इसलिए तीन तरह से जोड़ संभव है। इस वजह से, पहले तीन अंकों को जोड़ना और योग और कैरी करना भी संभव है; बाद के आंकड़ों के लिए, योग और कैरी दो पद हैं, और अगला एकल अंक इनमें जोड़ा जाता है।
दो अंकों का योग कभी भी 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 लंबी युग्मक संख्याओं के युग्मक योग का एक उदाहरण दिया गया है:
   10111010101011011111000000001101 ()
   10111010101011011111000000001101 (a)
  + 11011110101011011011111011101111 (बी)
  + 11011110101011011011111011101111 (b)
  + 00010010101101110101001101010010 (सी)
  + 00010010101101110101001101010010 (c)


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


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


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


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


== कैर्री-सेव एक्युमुलेटर्स ==
== कैर्री-सेव संचायक ==


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


सफलता की कुंजी यह है कि प्रत्येक आंशिक जोड़ के क्षण में हम तीन बिट जोड़ते हैं:
सफलता की कुंजी यह है कि प्रत्येक आंशिक जोड़ के क्षण में हम तीन बिट जोड़ते हैं:
Line 49: 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 कदम।
इसे दूसरे तरीके से रखने के लिए, हम अपने दाहिनी ओर की स्थिति से एक कैरी अंक ले रहे हैं, और एक कैरी अंक को बाईं ओर पारंपरिक जोड़ के रूप में हस्तांतरित कर रहे हैं; परन्तु कैरी अंक जिसे हम बाईं ओर पारित करते हैं, पिछली गणना का परिणाम है न कि वर्तमान की गणना का परिणाम। प्रत्येक घड़ी चक्र में, कैर्री को केवल एक कदम आगे बढ़ना होता है, न कि पारंपरिक जोड़ के रूप में n कदम।


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


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


== कमियां ==
== कमियाँ ==


कैरी-सेव जोड़ के प्रत्येक चरण में,
कैरी-सेव जोड़ के प्रत्येक चरण में,
Line 61: 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> यदि हम यह नहीं जान सकते हैं कि मध्यवर्ती परिणाम मापांक से अधिक है या कम है, तो हम कैसे जान सकते हैं कि मापांक घटाना है या नहीं?
प्रमापीय गुणन को लागू करने के लिए कैरी-सेव योजक का उपयोग करते समय यह बाद वाला बिंदु एक दोष है (भाग के बाद गुणा, शेष को केवल रखते हुए)।<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> यदि हम यह नहीं जान सकते हैं कि मध्यवर्ती परिणाम मापांक से अधिक है या कम है, तो हम किस प्रकार जान सकते हैं कि मापांक को घटाना है या नहीं?


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


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


== तकनीकी विवरण ==
== तकनीकी विवरण ==


कैरी-सेव यूनिट में 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>
:<math>sc_i = (a_i \wedge b_i) \vee (a_i \wedge c_i) \vee (b_i \wedge c_i).</math>
:<math>sc_i = (a_i \wedge b_i) \vee (a_i \wedge c_i) \vee (b_i \wedge c_i).</math>
इसके बाद पूरी राशि की गणना की जा सकती है:
इसके बाद पूरे योग की गणना की जा सकती है:
# [[तार्किक पारी]] कैरी सीक्वेंस sc को एक स्थान से छोड़ दिया।
# कैरी सीक्वेंस sc को एक स्थान से स्थानांतरित करना।।
# आंशिक योग अनुक्रम ps के सामने ([[सबसे महत्वपूर्ण बिट]]) में 0 को जोड़ना।
# आंशिक योग अनुक्रम ps के सामने ([[सबसे महत्वपूर्ण बिट]]) में 0 को जोड़ना।  
# एक योजक (इलेक्ट्रॉनिक्स) का उपयोग करना # रिपल-कैरी योजक इन दोनों को एक साथ जोड़ने और परिणामी (''n'' + 1) - बिट मान का उत्पादन करने के लिए।
# इन दोनों को एक साथ जोड़ने और परिणामी (''n'' + 1) -बिट मान उत्पन्न करने के लिए एक ऊर्मिका कैरी योजक का उपयोग करना।


== यह भी देखें ==
== यह भी देखें ==
* [[वालेस का पेड़]]
* [[वालेस का पेड़|वालेस प्रवर्धक]]


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 108: Line 107:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 13/02/2023]]
[[Category:Created On 13/02/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 09:23, 7 November 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 के आनुपातिक समय की अनुमति देनी होगी। जब तक हमने निम्न नहीं किया है,

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

कैरी अग्रावलोकन योजक विलंब को कम कर सकता है। सिद्धांत रूप में देरी को कम किया जा सकता है ताकि यह अभिलेख के समानुपाती हो, परन्तु बड़ी संख्या के लिए यह अब स्तिथि नहीं है, क्योंकि जब कैरी अग्रावलोकन लागू किया जाता है, तो चिप पर संकेतों को यात्रा करने वाली दूरी अनुपात से 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 वहन करता है।

कमियाँ

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

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

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

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

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

तकनीकी विवरण

कैरी-सेव ईकाई में n योजक पूर्ण योजक होते हैं, जिनमें से प्रत्येक एक एकल योग की गणना करता है और तीन निविष्ट संख्याओं के संबंधित बिट्स पर आधारित होता है। तीन n-बिट संख्या 'a', 'b' और 'c' को देखते हुए, यह आंशिक योग 'ps' और एक शिफ्ट-कैरी 'sc' उत्पन्न करता है:

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

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

यह भी देखें

टिप्पणियाँ

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


संदर्भ

  1. Earle, John G. (1965-07-12), Latched Carry Save Adder Circuit for Multipliers, U.S. Patent 3,340,388
  2. Earle, John G. (March 1965), "Latched Carry-Save Adder", IBM Technical Disclosure Bulletin, 7 (10): 909–910
  3. von Neumann, John. Collected Works.
  4. Parhami, Behrooz (2010). Computer arithmetic: algorithms and hardware designs (2nd ed.). New York: Oxford University Press. ISBN 978-0-19-532848-6. OCLC 428033168.
  5. 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.
  6. 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.


अग्रिम पठन