Carry lookahead और width-safe Booth multiplication
Arithmetic को दो तरह से व्यवस्थित करना
Carry lookahead, addition की Boolean dependencies बदलता है। Booth recoding, signed multiplier के bit contributions बदलता है। Exact गणितीय उत्तर दोनों में वही रहता है। Speed का दावा करने से पहले representation,width और hardware assumptions स्पष्ट चाहिए।
पूर्वज्ञान: full adders,two's complement,integer multiplication और combinational timing। ये official syllabus के broad circuit/arithmetic क्षेत्रों के चुने implementations हैं; syllabus इन्हें अलग नाम से सूचीबद्ध नहीं करता। यहाँ four-bit carry expansion और radix-two Booth algorithm हैं, optimized commercial multiplier या पूरा controller नहीं।
Carry lookahead याद करने के बजाय निकालें
Least significant bit को 0 कहें। p_i=a_i XOR b_i और g_i=a_i AND b_i रखें। तब s_i=p_i XOR c_i तथा c_(i+1)=g_i OR (p_i AND c_i)। Boolean equations में “+” OR और साथ लिखना AND है।
Substitution से serial carry variables हटते हैं:
c_1=g_0+p_0c_0; c_2=g_1+p_1g_0+p_1p_0c_0; c_3=g_2+p_2g_1+p_2p_1g_0+p_2p_1p_0c_0; c_4=g_3+p_3g_2+p_3p_2g_1+p_3p_2p_1g_0+p_3p_2p_1p_0c_0.
हर term कहता है कि किसी lower bit ने carry generate किया और बीच के positions ने propagate किया, या external carry पूरे prefix से गुजरा। Group P=p_3p_2p_1p_0 तथा G=g_3+p_3g_2+p_3p_2g_1+p_3p_2p_1g_0 रखें। तब c_4=G+Pc_0। Groups को भी इसी generate/propagate reasoning से जोड़ सकते हैं।
हल किया उदाहरण 1: a=1011,b=0110,c_0=0। High bit पहले लिखने पर p=1101,g=0010। Bit 1 carry generate करता है और bits 2,3 उसे propagate करते हैं, इसलिए G=1,P=0,c_4=1। Carries c_1,c_2,c_3,c_4 क्रमशः 0,1,1,1 हैं। Sum bits 0001, इसलिए full unsigned result 10001=17 है। Group P=0 का अर्थ carry-out zero नहीं; G one generate कर सकता है।
कुछ designs carry-propagate को a_i OR b_i लेते हैं; carry recurrence में वह भी काम करता है। लेकिन उस OR-defined p को s_i=p_i XOR c_i में न डालें: sum को अब भी a_i XOR b_i चाहिए। इस पाठ में दोनों formulas के लिए लगातार XOR-defined p है।
Logic depth gate model पर निर्भर है
p/g पहले settled हों और arbitrary fan-in AND/OR का delay एक time unit हो, तो expanded c_4 की two-level AND-OR bound है। इसके विपरीत चार ripple carry stages में हर stage का एक AND और एक OR मिलकर आठ-unit bound देते हैं। तुलना में p/g generation और final sum XOR शामिल नहीं। यह जानबूझकर idealized model है।
Five-input AND जरूरी नहीं कि two-input AND के समान delay में उपलब्ध हो। Bounded fan-in में decomposition या hierarchical lookahead चाहिए; loading,wiring और implementation भी delay बदलते हैं। Equations serial dependency हटाती हैं, लेकिन width-independent physical delay या universal fixed speedup सिद्ध नहीं करतीं।
Adjacent multiplier bits से Booth recoding
Signed n-bit multiplier के bits q_(n−1)…q_0 हों और q_−1=0 रखें। उसका signed मान Σ(q_(i−1)−q_i)2^i, i=0…n−1 है। Sum खोलने पर bits 0…n−2 के positive weights और sign bit का −2^(n−1) weight बचता है; यही identity का प्रमाण है।
इसलिए pair (q_i,q_(i−1)) में 00/11 का contribution zero,01 पर M·2^i जोड़ना और 10 पर M·2^i घटाना है। उदाहरण signed 0011=3 में low-to-high pairs 10,11,01,00 हैं, इसलिए 3=−1+4। M=−5 हो तो product=−(−5)+4(−5)=−15। Ones की runs से nonzero partial terms घट सकते हैं, पर alternating bits में जरूरी नहीं; हर multiplier के लिए speed लाभ की guarantee नहीं।
Width-safe register version
Inputs M और Q,n-bit two's complement हैं,n≥2। M को n+1 bits में sign-extend करके स्थिर रखें। Accumulator A,n+1 bits का और शुरू में zero है; Q का original n-bit register तथा one-bit q_prev शुरू में zero रखें। ठीक n iterations में:
- पुराना (Q_0,q_prev) देखें। 01 पर A←A+M;10 पर A←A−M;00/11 पर A hold। Arithmetic n+1-bit accumulator में है।
- फिर पूरे concatenated (A,Q,q_prev) register को एक arithmetic-right-shift करें। कुल width 2n+2 bits है। A का sign नए top पर copy हो; पुराना A_0,Q के top में और पुराना Q_0,q_prev में जाए।
- तीनों registers को अलग-अलग shift न करें। Sign और दोनों boundary transfers एक combined shift का हिस्सा हैं।
n iterations बाद q_prev हटाएँ। बचा A,Q exact 2n-bit product का 2n+1-bit sign extension है; 2n-bit answer चाहिए तो redundant top sign bit हटाएँ। अतिरिक्त A/M bit से most-negative n-bit multiplicand को negate करने पर +2^(n−1) समाता है। साधारण n-bit accumulator version इस सीमा पर असफल हो सकता है।
हल किया उदाहरण 2: n=4,M=−5, इसलिए पाँच-bit M=11011 और शुरू में Q=0011। Table हर combined shift के बाद का state दिखाती है।
| Iteration | पुराना pair | Shift से पहले operation | Shift के बाद A | Shift के बाद Q | q_prev |
|---|---|---|---|---|---|
| 1 | 10 | A−M | 00010 | 1001 | 1 |
| 2 | 11 | hold | 00001 | 0100 | 1 |
| 3 | 01 | A+M | 11110 | 0010 | 0 |
| 4 | 00 | hold | 11111 | 0001 | 0 |
A,Q=111110001 है; redundant top sign bit हटाकर आठ-bit 11110001=−15 मिलता है। स्वतंत्र जाँच −5×3=−15। यही width-safe algorithm चार-bit M=−8,Q=−1 के लिए आठ-bit 00001000=+8 भी देता है।
मुख्य बातें और सामान्य गलतियाँ
हर carry term सही bit order से निकालें। Generated carry और group propagation अलग हैं। Sum में OR-defined तथा XOR-defined propagate न मिलाएँ। Levels गिनने से पहले fan-in assumptions लिखें। Booth में 10 subtract और 01 add है; shift से पहले pair देखें, sign तथा cross-register transfers बचाएँ। Most-negative multiplicand को tests से हटाने के बजाय जाँचें। सही recoding identity अपने आप cycle-count या physical-speed का दावा नहीं है।
मौलिक अभ्यास
ये छह single-correct MCQ सीखने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. XOR-defined p तथा AND-defined g में c_2 क्या है?
A. g_1+p_1g_0+p_1p_0c_0 B. g_1+p_0g_0+p_1c_0 C. p_1+p_0+c_0 D. g_0+p_0c_0
उत्तर: A
A सही है: c_2=g_1+p_1c_1 में c_1=g_0+p_0c_0 रखें।
B गलत है: बीच के bit-1 propagation factors छूटे या गलत स्थान पर हैं।
C गलत है: केवल propagation carry generate नहीं करता।
D गलत है: यह c_1 है,c_2 नहीं।
C02. चार-bit a=1011,b=0110,c_0=0 में group (G,P,c_4) क्या हैं?
A. (0,1,0) B. (0,0,0) C. (1,0,1) D. (1,1,1)
उत्तर: C
A गलत है: bit 1 carry generate करता है,सभी bits propagate नहीं।
B गलत है: generated carry,bits 2,3 से output तक जाता है।
C सही है: g_1=1,p_2=p_3=1 से G=1 तथा p_1=0 से P=0।
D गलत है: group P को हर p_i=1 चाहिए,पर p_1=0।
C03. Radix-two Booth में पुराना pair (Q_0,q_prev)=10,shift से पहले क्या माँगता है?
A. A←A+M B. A←A−M C. A hold D. केवल M का logical-right-shift
उत्तर: B
A गलत है: addition pair 01 के लिए है।
B सही है: q_prev−Q_0=0−1=−1,इसलिए M घटता है।
C गलत है: hold,00 या 11 में है।
D गलत है: M स्थिर है;operation के बाद combined state shift होता है।
C04. बताए Booth algorithm में A को n+1 bits क्यों करते हैं?
A. Signed product को unsigned sum बनाने को B. हर addition हटाने को C. क्योंकि Q को 2n bits चाहिए D. Most-negative n-bit multiplicand का negation same-width overflow के बिना रखने को
उत्तर: D
A गलत है: algorithm अब भी signed product निकालता है।
B गलत है: कुछ pairs में addition/subtraction जरूरी है।
C गलत है: इस version में Q,n bits रहता है।
D सही है: +2^(n−1),n+1 signed bits में समाता है,n में नहीं।
C05. n=4,M=−5,Q शुरू में 0011 हो,तो final आठ-bit product क्या है?
A. 00001111 B. 11110001 C. 11111011 D. 00010001
उत्तर: B
A गलत है: यह +15 है,−15 नहीं।
B सही है: −5×3=−15 और 256−15=241=11110001।
C गलत है: यह केवल multiplicand −5 है।
D गलत है: यह +17 है,signed product नहीं।
C06. बताई two-level c_4 तथा eight-level ripple तुलना कब valid है?
A. Fan-in कुछ भी हो,हर physical library में B. केवल carry न होने पर C. बताए settled-p/g और unit-delay arbitrary-fan-in AND/OR model में D. इससे हर n-bit adder का constant physical delay सिद्ध है
उत्तर: C
A गलत है: fan-in और implementation actual delay बदलते हैं।
B गलत है: तुलना model में carry computation की है।
C सही है: इन assumptions में p/g और sum generation छोड़कर level count उचित है।
D गलत है: simplified level model universal physical scaling law नहीं।
सीमा और स्रोत
यह Digital Logic के एक सीमित हिस्से का पाठ है, पूरे GATE CS की तैयारी नहीं। आधिकारिक पाठ्यक्रम केवल विषय की प्रासंगिकता की पुष्टि करता है; व्युत्पत्तियाँ, उदाहरण और अभ्यास मौलिक हैं। तकनीकी संदर्भों से representation और circuit की conventions जाँची गई हैं; उनके अभ्यास प्रश्न नहीं दोहराए गए।
- Official GATE 2027 CS syllabus Section 2
- University of Wisconsin carry-lookahead supplement
- MIT signed Booth multiplier and width caveat
स्रोत 14 अक्टूबर 2026 को जाँचे गए।
प्रगति सहेजने के लिए साइन इन करें। साइन इन