कैरी-स्किप योजक

एक कैरी-स्किप योजक^{[nb 1]}(कैरी-बायपास योजक के रूप में भी जाना जाता है) एक योजक (इलेक्ट्रॉनिक्स) कार्यान्वयन है जो अन्य योजकों की तुलना में रिपल कैरी योजक#रिपल-कैरी योजक|रिपल-कैरी योजक की देरी में सुधार करता है। ब्लॉक-कैरी-स्किप योजक बनाने के लिए कई कैरी-स्किप योजक का उपयोग करके सबसे खराब स्थिति में सुधार प्राप्त किया जाता है।

अन्य तेज़ योजकों के विपरीत, कैरी-स्किप योजक प्रदर्शन केवल इनपुट बिट्स के कुछ संयोजनों के साथ बढ़ा है। इसका मतलब है, गति में सुधार केवल संभावना है।

सिंगल कैरी-स्किप योजक

एक साधारण एक स्तर के रिपल-कैरी योजक के लिए सबसे खराब स्थिति तब होती है, जब प्रचार-स्थिति होती है^[1]प्रत्येक अंक युग्म के लिए सत्य है $(a_{i},b_{i})$ . फिर कैरी-इन तरंग के माध्यम से $n$ -बिट योजक और बाद में कैरी-आउट के रूप में दिखाई देता है $\tau _{CRA}(n)\approx n\cdot \tau _{VA}$ .

अतिरिक्त जेनरेट और प्रचार संकेतों के साथ पूर्ण योजक।

प्रत्येक ऑपरेंड इनपुट बिट जोड़ी के लिए $(a_{i},b_{i})$ प्रसार की स्थिति $p_{i}=a_{i}\oplus b_{i}$ XOR-गेट का उपयोग करके निर्धारित किया जाता है। जब सभी प्रचार-शर्तें सही हों, तो कैरी-इन बिट $c_{0}$ कैरी-आउट बिट निर्धारित करता है।

एन-बिट-कैरी-स्किप योजक में एक एन-बिट-कैरी-रिपल-चेन, एक एन-इनपुट एंड-गेट और एक मल्टीप्लेक्सर होता है। प्रत्येक प्रचार बिट $p_{i}$ , जो कैरी-रिपल-चेन द्वारा प्रदान किया जाता है, एन-इनपुट AND-गेट से जुड़ा है। परिणामी बिट का उपयोग मल्टीप्लेक्सर के चुनिंदा बिट के रूप में किया जाता है जो या तो अंतिम कैरी-बिट को स्विच करता है $c_{n}$ या कैरी-इन $c_{0}$ कैरी-आउट सिग्नल के लिए $c_{out}$ .

$s=p_{n-1}\wedge p_{n-2}\wedge \dots \wedge p_{1}\wedge p_{0}=p_{[0:n-1]}$

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

4 बिट कैरी-स्किप योजक।

प्रदर्शन

कैरी-स्किप-एडर का महत्वपूर्ण पथ पहले पूर्ण-योजक से शुरू होता है, सभी योजकों से होकर गुजरता है और सम-बिट पर समाप्त होता है $s_{n-1}$ . समग्र महत्वपूर्ण पथ को कम करने के लिए कैरी-स्किप-एडर्स जंजीर (ब्लॉक-कैरी-स्किप-एडर्स देखें) हैं, क्योंकि एक $n$ -बिट कैरी-स्किप-एडर की तुलना में कोई वास्तविक गति लाभ नहीं है $n$ -बिट रिपल-कैरी योजक।

\tau _{CSA}(n)=\tau _{CRA}(n)

स्किप-लॉजिक में एक शामिल होता है $m$ -इनपुट एंड-गेट और एक मल्टीप्लेक्सर।

T_{SK}=T_{AND}(m)+T_{MUX}

जैसा कि प्रचार संकेतों की गणना समानांतर में की जाती है और जल्दी उपलब्ध होती है, कैरी-स्किप योजक में स्किप लॉजिक के लिए महत्वपूर्ण पथ में केवल मल्टीप्लेक्सर (सशर्त स्किप) द्वारा लगाया गया विलंब होता है।

T_{CSK}=T_{MUX}=2D

.

ब्लॉक-कैरी-स्किप एडर्स

4 बिट के ब्लॉक आकार के साथ 16-बिट फिक्स्ड-ब्लॉक-कैरी-स्किप योजक।

ब्लॉक-कैरी-स्किप एडर्स कई कैरी-स्किप एडर्स से बने होते हैं। ब्लॉक-कैरी-स्किप योजक दो प्रकार के होते हैं

दो ऑपरेंड $A=(a_{n-1},a_{n-2},\dots ,a_{1},a_{0})$ तथा $B=(b_{n-1},b_{n-2},\dots ,b_{1},b_{0})$ में विभाजित हैं $k$ के ब्लॉक $(m_{k},m_{k-1},\dots ,m_{2},m_{1})$ बिट्स।

ब्लॉक-कैरी-स्किप-एडर्स का उपयोग क्यों किया जाता है?
क्या ब्लॉक का आकार स्थिर या परिवर्तनशील होना चाहिए?
फिक्स्ड ब्लॉक चौड़ाई बनाम वेरिएबल ब्लॉक चौड़ाई

निश्चित आकार ब्लॉक-कैरी-स्किप एडर्स

फिक्स्ड साइज ब्लॉक-कैरी-स्किप एडर्स स्प्लिट करते हैं $n$ इनपुट बिट्स के ब्लॉक में बिट्स $m$ बिट्स प्रत्येक, जिसके परिणामस्वरूप $k={\frac {n}{m}}$ ब्लॉक। क्रिटिकल पाथ में रिपल पाथ और पहले ब्लॉक के स्किप एलिमेंट होते हैं, स्किप पाथ जो पहले और आखिरी ब्लॉक के बीच में होते हैं, और अंत में आखिरी ब्लॉक के रिपल-पाथ होते हैं।

T_{FCSA}(n)=T_{CRA_{[0:c_{out}]}}(m)+T_{CSK}+(k-2)\cdot T_{CSK}+T_{CRA}(m)=3D+m\cdot 2D+(k-1)\cdot 2D+(m+2)2D=(2m+k)\cdot 2D+5D

किसी दिए गए योजक चौड़ाई n के लिए इष्टतम ब्लॉक आकार 0 के बराबर करके प्राप्त किया जाता है

{\frac {dT_{FCSA}(n)}{dm}}=0

2D\cdot \left(2-n\cdot {\frac {1}{m^{2}}}\right)=0

\Rightarrow m_{1,2}=\pm {\sqrt {\frac {n}{2}}}

केवल सकारात्मक ब्लॉक आकार ही वसूली योग्य हैं

\Rightarrow m={\sqrt {\frac {n}{2}}}

चर आकार ब्लॉक-कैरी-स्किप एडर्स

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

मल्टीलेवल कैरी-स्किप ऐडर्स

एक अतिरिक्त परत में अतिरिक्त स्किप-ब्लॉक का उपयोग करके, ब्लॉक-प्रोपेगेट सिग्नल $p_{[i:i+3]}$ आगे संक्षेप में हैं और बड़े स्किप करने के लिए उपयोग किए जाते हैं:

p_{[i:i+15]}=p_{[i:i+3]}\wedge p_{[i+4:i+7]}\wedge p_{[i+8:i+11]}\wedge p_{[i+12:i+15]}

इस प्रकार योजक को और भी तेज़ बना देता है।

कैरी-स्किप ऑप्टिमाइज़ेशन

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

थॉमस डब्ल्यू. लिंच द्वारा एक मनमाना डिवाइस प्रक्रिया नोड के लिए चर ब्लॉक आकार और कई स्तरों के लिए कैरी-स्किप ऑप्टिमाइज़ेशन समस्या हल की गई थी।^[2]यह संदर्भ यह भी दर्शाता है कि कैरी-स्किप जोड़ समानांतर उपसर्ग जोड़ के समान है और इस प्रकार से संबंधित है, और हान-कार्लसन योजक के समान कुछ विन्यासों के लिए। हान-कार्लसन,^[3]^[4]ब्रेंट-कुंग योजक|ब्रेंट-कुंग,^[5]कोगगे-स्टोन योजक^[6]और कई अन्य योजक प्रकार।

कार्यान्वयन सिंहावलोकन

इसे और अधिक विशिष्ट शब्दों में तोड़कर, 4-बिट कैरी-बाईपास योजक बनाने के लिए, 6 पूर्ण योजक # पूर्ण योजक की आवश्यकता होगी। इनपुट बसें कैरी-इन (CIN) सिग्नल के साथ 4-बिट A और 4-बिट B होंगी। आउटपुट 4-बिट बस X और कैरी-आउट सिग्नल (COUT) होगा।

पहले दो पूर्ण योजक पहले दो बिट्स को एक साथ जोड़ देंगे। दूसरे पूर्ण योजक से कैरी-आउट संकेत ( $C_{1}$ ) तीन 2 से 1 मल्टीप्लेक्सर्स के लिए सेलेक्ट सिग्नल चलाएगा। 2 पूर्ण योजकों का दूसरा सेट मानकर अंतिम दो बिट्स जोड़ देगा $C_{1}$ एक तार्किक 0 है। और पूर्ण योजकों का अंतिम सेट यह मान लेगा $C_{1}$ तार्किक 1 है।

मल्टीप्लेक्सर्स तब नियंत्रित करते हैं कि COUT के लिए किस आउटपुट सिग्नल का उपयोग किया जाता है, $X_{2}$ तथा $X_{3}$ .

संदर्भ

↑ Parhami, Behrooz (2000). Computer arithmetic: Algorithms and Hardware Designs. Oxford University Press. p. 108. ISBN 0-19-512583-5.
↑ Lynch, Thomas Walker (May 1996). "Binary Adders" (Thesis). University of Texas. Archived (PDF) from the original on 2018-04-14. Retrieved 2018-04-14.
↑ Han, Tackdon; Carlson, David A.; Levitan, Steven P. (October 1982). "VLSI design of high-speed, low-area addition circuitry". Proceedings 1981 IEEE International Conference on Computer Design: VLSI in Computers & Processors. IEEE: 418–422. ISBN 0-81860802-1.
↑ Han, Tackdon; Carlson, David A. (October 1987). "Fast area-efficient VLSI adders". Proceedings 8th Symposium on Computer Arithmetic. IEEE: 49–56.
↑ Brent, Richard Peirce; Kung, Hsiang Te (March 1982). "A regular layout for parallel adders" (PDF). IEEE Transactions on Computers. C-31 (3): 260–264. doi:10.1109/TC.1982.1675982. Archived from the original on September 24, 2017.
↑ Kogge, Peter Michael; Stone, Harold S. (August 1973). "A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations". IEEE Transactions on Computers. C-22 (8): 786–793. doi:10.1109/TC.1973.5009159.

इस पेज में लापता आंतरिक लिंक की सूची

बाहरी संबंध

Explanation for critical path of the variable-skip adder

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

[Parhami_2000-2] Parhami, Behrooz (2000). Computer arithmetic: Algorithms and Hardware Designs. Oxford University Press. p. 108. ISBN 0-19-512583-5.

[Lynch_1996-3] Lynch, Thomas Walker (May 1996). "Binary Adders" (Thesis). University of Texas. Archived (PDF) from the original on 2018-04-14. Retrieved 2018-04-14.

[Han-Carlson_Levitan_1981-4] Han, Tackdon; Carlson, David A.; Levitan, Steven P. (October 1982). "VLSI design of high-speed, low-area addition circuitry". Proceedings 1981 IEEE International Conference on Computer Design: VLSI in Computers & Processors. IEEE: 418–422. ISBN 0-81860802-1.

[Han-Carlson_1987-5] Han, Tackdon; Carlson, David A. (October 1987). "Fast area-efficient VLSI adders". Proceedings 8th Symposium on Computer Arithmetic. IEEE: 49–56.

[Brent-Kung_1982-6] Brent, Richard Peirce; Kung, Hsiang Te (March 1982). "A regular layout for parallel adders" (PDF). IEEE Transactions on Computers. C-31 (3): 260–264. doi:10.1109/TC.1982.1675982. Archived from the original on September 24, 2017.

[Kogge-Stone_1973-7] Kogge, Peter Michael; Stone, Harold S. (August 1973). "A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations". IEEE Transactions on Computers. C-22 (8): 786–793. doi:10.1109/TC.1973.5009159.

[nb 1]

[1]

[2]

[3]

[4]

[5]

[6]