कैरी-लुकहेड योजक

From alpha
Jump to navigation Jump to search
कैरी लुकहेड के साथ 4-बिट योजक

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

पहले से ही 1800 के दशक के मध्य में, चार्ल्स बैबेज ने अपने अंतर इंजन में उपयोग किए जाने वाले रिपल-कैरी द्वारा लगाए गए प्रदर्शन दंड को मान्यता दी, और बाद में अपने (कभी निर्मित) विश्लेषणात्मक इंजन के लिए 'प्रत्याशित गाड़ी' के लिए तंत्र तैयार किया।[1][2]माना जाता है कि कोनराड ज़्यूस ने अपने 1930 के बाइनरी मैकेनिकल कंप्यूटर, Z1 (कंप्यूटर) में पहला कैरी-लुकहेड योजक लागू किया था।[3] आईबीएम के जेराल्ड बी. रोसेनबर्गर ने 1957 में एक आधुनिक बाइनरी कैरी-लुकहेड एडर पर पेटेंट के लिए आवेदन किया।[4]

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

ऑपरेशन का सिद्धांत

तरंग जोड़

एक बाइनरी रिपल-कैरी योजक उसी तरह काम करता है जैसे जोड़ के अधिकांश पेंसिल-एंड-पेपर तरीके। सबसे दाहिने (सबसे कम महत्वपूर्ण अंक) अंक की स्थिति से शुरू करते हुए, दो संबंधित अंक जोड़े जाते हैं और एक परिणाम प्राप्त होता है। यदि परिणाम के लिए उच्च अंक की आवश्यकता होती है तो 'कैरी आउट' हो सकता है; उदाहरण के लिए, 9 + 5 = 4, 1 रखें। बाइनरी अंकगणित उसी तरह से काम करता है, जिसमें कम अंक होते हैं। इस मामले में, केवल चार संभावित ऑपरेशन हैं, 0+0, 0+1, 1+0 और 1+1; 1+1 मामला एक कैरी उत्पन्न करता है। तदनुसार, सबसे दायीं ओर के अंकों के अलावा सभी अंकों की स्थिति को अंकों के एक स्थान से दाईं ओर एक कैरी से अतिरिक्त 1 जोड़ने की संभावना पर प्रतीक्षा करने की आवश्यकता है।

इसका मतलब यह है कि किसी भी अंक की स्थिति का पूर्ण रूप से अंतिम मूल्य नहीं हो सकता है जब तक कि यह स्थापित नहीं हो जाता है कि कोई कैरी दाईं ओर से आ रहा है या नहीं। इसके अलावा, यदि कैरी के बिना योग आधार में उच्चतम मान है (बेस -10 पेंसिल-एंड-पेपर विधियों में 9 या बाइनरी अंकगणित में 1), तो यह बताना संभव नहीं है कि दी गई अंकों की स्थिति जा रही है या नहीं एक कैरी को उसके बाईं ओर की स्थिति में पास करें। सबसे खराब स्थिति में, जब योगों का एक पूरा क्रम …99999999… (दशमलव में) या …11111111… (बाइनरी में) आता है, तब तक कुछ भी नहीं घटाया जा सकता जब तक कि दाईं ओर से आने वाले कैरी का मूल्य ज्ञात न हो; उस कैरी को बाईं ओर प्रचारित किया जाना चाहिए, एक समय में एक कदम, क्योंकि प्रत्येक अंक की स्थिति 9 + 1 = 0 का मूल्यांकन करती है, 1 या 1 + 1 = 0 ले जाती है, 1 ले जाती है। यह कैरी की दाएं से बाईं ओर की तरंग है जो रिपल-कैरी योजक को उसका नाम और धीमापन देती है। उदाहरण के लिए, 32-बिट पूर्णांक जोड़ते समय, इस संभावना के लिए भत्ता दिया जाना चाहिए कि 32 एक-बिट योजकों में से हर एक के माध्यम से एक कैरी को रिपल करना पड़ सकता है।

लुकहेड

कैरी-लुकहेड दो बातों पर निर्भर करता है:

  1. प्रत्येक अंक की स्थिति के लिए गणना करना कि क्या वह स्थिति एक कैरी को प्रचारित करने वाली है यदि कोई दाईं ओर से आता है।
  2. इन परिकलित मानों को जोड़कर शीघ्रता से निष्कर्ष निकालने में सक्षम होने के लिए, अंकों के प्रत्येक समूह के लिए, वह समूह एक कैरी का प्रचार करने जा रहा है जो दाईं ओर से आता है।

मान लीजिए कि चार अंकों के समूह चुने गए हैं। घटनाओं का क्रम इस प्रकार होगा:

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

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

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

लुकहेड कैरी लॉजिक द्वारा नियंत्रित किए जाने वाले समूह के आकार का निर्णय लेने के लिए उपयोग की जा रही विशेष तकनीक के लिए गेट और प्रसार विलंब के विस्तृत विश्लेषण की आवश्यकता होती है।

लुकहेड-कैरी लॉजिक के एक से अधिक स्तर होना संभव है, और यह वास्तव में आमतौर पर किया जाता है। प्रत्येक आगे की ओर ले जाने वाली इकाई पहले से ही एक संकेत उत्पन्न करती है जो कहती है कि यदि कोई वाहक दाईं ओर से आता है, तो मैं इसे बाईं ओर प्रचारित कर दूंगा, और उन संकेतों को जोड़ा जा सकता है ताकि प्रत्येक समूह, कहें, चार आगे की ओर ले जाने वाली इकाइयां एक का हिस्सा बन जाएं जोड़े जा रहे कुल 16 बिट्स को नियंत्रित करने वाला सुपरग्रुप। सुपरग्रुप लुकहेड-कैरी लॉजिक यह कहने में सक्षम होगा कि क्या सुपरग्रुप में प्रवेश करने वाले कैरी को इसके माध्यम से सभी तरह से प्रचारित किया जाएगा, और इस जानकारी का उपयोग करके, यह भोले-भाले रिपल कैरी के रूप में 16 गुना तेजी से दाईं से बाईं ओर प्रचार करने में सक्षम है। . इस तरह के दो-स्तरीय कार्यान्वयन के साथ, एक कैरी पहले अलग-अलग योजकों की धीमी सड़क के माध्यम से प्रचार कर सकता है, फिर, अपने समूह के बाएं हाथ के अंत तक पहुंचने पर, 4-बिट लुकहेड-कैरी लॉजिक की तेज़ सड़क के माध्यम से प्रचार कर सकता है, फिर , अपने सुपरग्रुप के बायीं ओर पहुंचने पर, 16-बिट लुकहेड-कैरी लॉजिक के सुपरफास्ट रोड के माध्यम से प्रचारित करें।

फिर से, चुने जाने वाले समूह आकार सटीक विवरण पर निर्भर करते हैं कि लॉजिक गेट्स के भीतर और एक लॉजिक गेट से दूसरे तक कितनी तेजी से सिग्नल प्रसारित होते हैं।

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

कैरी लुकहेड विधि

कैरी लुकहेड के साथ 4-बिट योजक का कार्यान्वयन

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

दो 1-अंकीय इनपुट A और B के जोड़ को उत्पन्न करने के लिए कहा जाता है यदि जोड़ हमेशा ले जाएगा, भले ही कोई इनपुट-कैरी हो (समतुल्य, चाहे कोई भी हो) क्या योग में कोई कम महत्वपूर्ण अंक हैं)। उदाहरण के लिए, दशमलव योग 52 + 67 में, दहाई अंक 5 और 6 का जोड़ उत्पन्न होता है क्योंकि परिणाम सैकड़ों अंक तक होता है, भले ही इकाई अंक वहन करता हो; उदाहरण में, इकाई का अंक (2 + 7 = 9) नहीं है। यहां तक ​​​​कि अगर संख्याएं, 54 और 69 थीं, तो दहाई अंक 5 और 6 का योग अभी भी उत्पन्न होगा क्योंकि परिणाम एक बार फिर से 4 और 9 के बावजूद एक सौ अंक तक ले जाता है।

बाइनरी जोड़ के मामले में, उत्पन्न करता है अगर और केवल अगर A और B दोनों 1 हैं। यदि हम लिखते हैं द्विआधारी विधेय का प्रतिनिधित्व करने के लिए जो सत्य है और केवल यदि उत्पन्न करता है, हमारे पास है

कहाँ पे एक तार्किक संयोजन है (यानी, एक और)।

दो 1-अंकीय इनपुट A और B को प्रोपेगेट करने के लिए कहा जाता है यदि जोड़ जब भी कोई इनपुट कैरी करता है (समतुल्य रूप से, जब अगला कम महत्वपूर्ण अंक होता है) राशि वहन करती है)। उदाहरण के लिए, दशमलव जोड़ 37 + 62 में, दहाई अंक 3 और 6 का जोड़ प्रचार करता है क्योंकि परिणाम सैकड़ों अंकों तक ले जाएगा यदि वे ले जाने वाले थे (जो इस उदाहरण में नहीं है)। ध्यान दें कि प्रचार और उत्पन्न को जोड़ के एक अंक के संबंध में परिभाषित किया गया है और योग में किसी अन्य अंक पर निर्भर नहीं है।

बाइनरी जोड़ के मामले में, प्रोपेगेट करता है यदि और केवल यदि A या B में से कम से कम एक 1 है। यदि द्विआधारी विधेय का प्रतिनिधित्व करने के लिए लिखा गया है जो सत्य है और केवल यदि प्रचार करता है, एक ने किया है

कहाँ पे समीकरण के दाईं ओर एक तार्किक संयोजन है (यानी, एक या)।

कभी-कभी प्रचार की थोड़ी भिन्न परिभाषा का उपयोग किया जाता है। इस परिभाषा के अनुसार A + B को प्रोपेगेट कहा जाता है यदि जब भी इनपुट कैरी होता है तो जोड़ ले जाएगा, लेकिन इनपुट कैरी नहीं होने पर कैरी नहीं करेगा। जिस तरह से जनरेट और प्रोपेगेट बिट्स का उपयोग कैरी-लुकहेड लॉजिक द्वारा किया जाता है, इससे कोई फर्क नहीं पड़ता कि किस परिभाषा का उपयोग किया जाता है। बाइनरी जोड़ के मामले में, यह परिभाषा व्यक्त की जाती है

कहाँ पे एक अनन्य या (यानी, एक xor) है।

Type of Carry
0 0 0 0 None
0 0 1 0 None
0 1 0 0 None
0 1 1 1 Propagate
1 0 0 0 None
1 0 1 1 Propagate
1 1 0 1 Generate
1 1 1 1 Generate/Propagate

कब वहन दिखाने वाली तालिका प्रचारित या उत्पन्न होती है।

बाइनरी अंकगणित के लिए, या xor से तेज है और इसे लागू करने के लिए कम ट्रांजिस्टर लेता है। हालाँकि, बहु-स्तरीय कैरी-लुकहेड योजक के लिए, इसका उपयोग करना सरल है .

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


कार्यान्वयन विवरण

जोड़े जाने वाले बाइनरी अनुक्रम में प्रत्येक बिट के लिए, कैरी-लुकहेड लॉजिक यह निर्धारित करेगा कि क्या बिट जोड़ी एक कैरी उत्पन्न करेगी या एक कैरी का प्रचार करेगी। यह सर्किट को समय से पहले कैरी निर्धारित करने के लिए जोड़े जा रहे दो नंबरों को पूर्व-संसाधित करने की अनुमति देता है। फिर, जब वास्तविक जोड़ किया जाता है, तो रिपल-कैरी प्रभाव (या पहले पूर्ण योजक से अंतिम पूर्ण योजक तक नीचे जाने के लिए ले जाने में लगने वाले समय) की प्रतीक्षा करने में कोई देरी नहीं होती है। नीचे एक साधारण 4-बिट सामान्यीकृत कैरी-लुकहेड सर्किट है जो 4-बिट रिपल-कैरी योजक के साथ जोड़ती है जिसे हमने ऊपर कुछ मामूली समायोजन के साथ उपयोग किया था:

प्रदान किए गए उदाहरण के लिए, उत्पन्न करने के लिए तर्क () और प्रचार () मान नीचे दिए गए हैं। संख्यात्मक मान ऊपर के सर्किट से सिग्नल को निर्धारित करता है, 0 से शुरू होकर सबसे दाईं ओर 3 से सबसे बाईं ओर:

स्थानापन्न में , फिर में , फिर में निम्नलिखित विस्तारित समीकरण देता है:

यह निर्धारित करने के लिए कि क्या बिट जोड़ी एक कैरी उत्पन्न करेगी, निम्न तर्क कार्य करता है:

यह निर्धारित करने के लिए कि क्या बिट जोड़ी कैरी का प्रचार करेगी, निम्न तर्क कथनों में से कोई भी कार्य करता है:

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

कैरी-लुकहेड 4-बिट योजक का उपयोग उच्च-स्तरीय सर्किट में भी किया जा सकता है, जिसमें प्रत्येक सीएलए लॉजिक सर्किट एक उच्च-स्तरीय सीएलए लॉजिक सर्किट के लिए प्रचार और सिग्नल उत्पन्न करता है। समूह प्रचार करता है () और समूह उत्पन्न () 4-बिट CLA के लिए हैं:

उसके बाद उस विशेष 4-बिट समूह के लिए कैरी-आउट बनाने के लिए उनका उपयोग किया जा सकता है:

यह देखा जा सकता है कि यह के बराबर है पिछले समीकरणों में

चार 4-बिट सीएलए को एक साथ रखने से चार समूह प्रचार करते हैं और चार समूह उत्पन्न होते हैं। एक पूर्वदर्शी-कैरी यूनिट (LCU) इन 8 मानों को लेती है और गणना करने के लिए समान तर्क का उपयोग करती है कक्षा में। LCU तब 4 क्लासेस में से प्रत्येक के लिए कैरी इनपुट और पाँचवें के बराबर उत्पन्न करता है .

16-बिट योजक (4 सीएलए और 1 एलसीयू का उपयोग करके) के गेट विलंब की गणना रिपल कैरी योजक के रूप में सीधे आगे नहीं है।

शून्य के समय से प्रारंभ:

  • की गणना तथा समय 1 पर किया जाता है,
  • की गणना समय 3 पर किया जाता है,
  • की गणना समय 2 पर किया जाता है,
  • की गणना समय 3 पर किया जाता है,
  • एलसीयू से सीएलए के लिए इनपुट की गणना यहां की जाती है:
    • पहले सीएलए के लिए समय 0,
    • दूसरे, तीसरे और चौथे सीएलए के लिए समय 5,
  • की गणना पर किया जाता है:
    • पहले सीएलए के लिए समय 4,
    • दूसरे, तीसरे और चौथे सीएलए के लिए समय 8,
  • अंतिम कैरी बिट की गणना () समय 5 पर किया जाता है।

अधिकतम समय 8 गेट विलंब (के लिए ).

एक मानक 16-बिट रिपल-कैरी योजक 16 × 3 − 1 = 47 गेट विलंब लेगा।

मैनचेस्टर कैरी चेन

मैनचेस्टर कैरी चेन कैरी-लुकहेड योजक का एक रूपांतर है[5]जो ट्रांजिस्टर संख्या को कम करने के लिए साझा तर्क का उपयोग करता है। जैसा कि कार्यान्वयन अनुभाग में ऊपर देखा जा सकता है, प्रत्येक कैरी को उत्पन्न करने के तर्क में पिछले कैर्री उत्पन्न करने के लिए उपयोग किए जाने वाले सभी तर्क शामिल हैं। एक मैनचेस्टर कैरी चेन गेट में नोड्स को टैप करके इंटरमीडिएट कैर्री उत्पन्न करता है जो सबसे महत्वपूर्ण कैरी वैल्यू की गणना करता है। हालांकि, सभी लॉजिक परिवारों के पास ये आंतरिक नोड नहीं होते हैं, CMOS एक प्रमुख उदाहरण है। डायनेमिक लॉजिक (डिजिटल लॉजिक) साझा लॉजिक का समर्थन कर सकता है, जैसा कि ट्रांसमिशन गेट लॉजिक कर सकता है। मैनचेस्टर कैरी चेन के प्रमुख डाउनसाइड्स में से एक यह है कि ट्रांजिस्टर के प्रतिरोध के साथ-साथ इन सभी आउटपुट का कैपेसिटिव लोड एक नियमित कैरी लुकहेड की तुलना में प्रचार विलंब को और अधिक तेज़ी से बढ़ाता है। मैनचेस्टर-कैरी-चेन अनुभाग आम तौर पर 4 बिट्स से अधिक नहीं होता है।

यह भी देखें

  • कैरी-स्किप योजक
  • कैरी ऑपरेटर
  • सट्टा निष्पादन

संदर्भ

  1. "विश्लेषणात्मक इंजन - चार्ल्स बैबेज विश्लेषणात्मक इंजन का इतिहास". history-computer.com. 4 January 2021. Retrieved 2021-06-19.
  2. Babbage, Charles (1864). Passages from the Life of a Philosopher. London: Longman, Green, Longmand Roberts & Green. pp. 59–63, 114–116.
  3. Rojas, Raul (2014-06-07). "Z1: कोनराड ज़्यूस के पहले कंप्यूटर की वास्तुकला और एल्गोरिदम". arXiv:1406.1886 [cs.AR].
  4. Rosenberger, Gerald B. (1960-12-27). "Simultaneous Carry Adder". U.S. Patent 2,966,305.
  5. "Manchester carry-chain adder - WikiChip". en.wikichip.org. Retrieved 2017-04-24.


अग्रिम पठन


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

बाहरी संबंध