Logic gates, half adders और full adders
उद्देश्य और मॉडल
Boolean expressions को gates से जोड़ें, half adder और full adder का अंतर समझें, truth tables से sum तथा carry निकालें और छोटा unsigned ripple-carry addition चरणों में करें। पूर्वज्ञान: Boolean AND, OR, NOT, XOR, binary स्थानों के भार और निश्चित width की unsigned सीमा। Inputs और outputs आदर्श bits 0 या 1 हैं; signals स्थिर होने के बाद मान पढ़ते हैं। इस मॉडल में combinational circuit का स्थिर output केवल वर्तमान inputs पर निर्भर है; उसमें stored state नहीं। Sequential circuits, clocking, flip-flops, signed overflow और वास्तविक gate delays आगे के विषय हैं।
Gate किसी Boolean function को लागू करने वाला मूल भाग है। Wire एक bit ले जाती है; उसकी शाखाएँ वही मान कई inputs तक पहुँचाती हैं, नया स्वतंत्र variable नहीं बनातीं। Circuit को inputs से intermediate signals होते हुए outputs तक पढ़ें। बीच के signals को नाम देने से हर चरण जाँचना आसान होता है।
1. Gates और उनके functions
NOT से A′, दो-input AND से AB, OR से A+B और XOR से A⊕B मिलता है। NAND यानी NOT-AND: (AB)′। NOR यानी NOT-OR: (A+B)′। XNOR यानी NOT-XOR: (A⊕B)′। इन सूत्रों में + Boolean OR है, integer addition नहीं।
| A | B | AND | OR | XOR | NAND | NOR | XNOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
NAND और NOR दोनों अलग-अलग universal हैं। केवल एक प्रकार के gates से NOT, AND और OR बना सकते हैं, और उनसे sum-of-products में लिखे जाने वाला कोई भी सीमित Boolean function। NAND के लिए NOT A=NAND(A,A)। t=NAND(A,B) लें; तब AND(A,B)=NAND(t,t)। u=NAND(A,A), v=NAND(B,B) लें; De Morgan से NAND(u,v)=A+B। इससे functions बन सकना सिद्ध होता है, हर circuit में सबसे कम gates होना नहीं।
इसी तरह NOR(A,A)=A′। NOR(A,B) का output दोनों inputs से जुड़े दूसरे NOR में देकर OR मिलता है। Complemented A और B को NOR में देने पर AB मिलता है। दोनों inputs को एक signal से जोड़ना जानबूझकर बनाया connection है; वे दो स्वतंत्र inputs नहीं हैं।
2. एक-bit जोड़ के दो outputs
इस भाग में a+b bits के मानों का सामान्य integer addition है, जबकि a⊕b और ab Boolean XOR तथा AND हैं। दो bits जोड़ने पर 0,1 या 2 मिलता है। एक bit तीनों मान नहीं रख सकती, इसलिए भार 1 वाला sum bit s और भार 2 वाला carry bit c रखते हैं। परिभाषित करने वाली integer identity है a+b=2c+s।
| a | b | Integer a+b | Carry c | Sum s |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 2 | 1 | 0 |
यह half adder है: s=a⊕b और c=ab। 1+1 पर (c,s)=(1,0), यानी binary 10 और integer 2 है। s के लिए OR लगाने से गलत output (1,1), यानी 3 मिलेगा। जोड़ी का क्रम अवश्य लिखें; (sum,carry) और (carry,sum) अलग reporting conventions हैं।
Half adder में incoming carry input नहीं होता। शुरुआती carry 0 हो तो सबसे निचले column के लिए यह पर्याप्त है। ऊपर के columns में सामान्यतः नीचे से आया carry भी जोड़ना पड़ता है, इसलिए वहाँ full adder चाहिए।
3. Full adder का निर्माण
Full adder के inputs a,b,c_in और outputs s,c_out हैं। Integer arithmetic में a+b+c_in=2c_out+s होना चाहिए। कुल मान 0 से 3 तक है। Sum bit उसकी parity है: s=a⊕b⊕c_in। Carry-out तभी 1 है जब कम-से-कम दो inputs 1 हों। Boolean notation में c_out=ab+ac_in+bc_in, जहाँ इस expression का + OR है।
| a | b | c_in | Integer total | c_out | s |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 2 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 2 | 1 | 0 |
| 1 | 1 | 0 | 2 | 1 | 0 |
| 1 | 1 | 1 | 3 | 1 | 1 |
Carry का नियम “ठीक दो inputs 1 हों” नहीं है: 111 पर भी carry 1 है। “कोई भी input 1 हो” भी गलत है: केवल एक 1 वाली rows में carry नहीं है। पहली गलती majority को ठीक दो की शर्त समझती है और दूसरी उसे OR समझती है।
4. दो half adders से full adder
पहला half adder: p=a⊕b और g=ab। दूसरा half adder: s=p⊕c_in और h=pc_in। दोनों carries का OR लें: c_out=g+h। XOR वाली इस convention में p को propagate और g को generate कहते हैं। कुछ किताबें propagate की अलग परिभाषा लेती हैं; केवल शब्द के बजाय दिए equations पर भरोसा करें।
यह क्यों सही है? a=b=1 पर g=1 और p=0, इसलिए incoming carry कुछ भी हो, नया carry बनता है। a,b में ठीक एक 1 हो तो g=0,p=1 और c_out=c_in; incoming carry आगे जाता है। a=b=0 पर p और g दोनों शून्य, इसलिए carry भी शून्य। ये सभी input pairs हैं। g और h एक साथ 1 नहीं हो सकते, हालांकि उन्हें जोड़ने वाला बताए अनुसार OR ही है।
हल किया input a=1,b=0,c_in=1: p=1,g=0,s=1⊕1=0,h=1,c_out=1। जाँच 2×1+0=2, जो 1+0+1 से मिलता है। 111 पर p=0,g=1,s=1,h=0,c_out=1 और पूरा मान 3 है।
5. Unsigned ripple-carry जोड़
n-bit ripple adder में full adders की श्रृंखला होती है। सबसे कम महत्वपूर्ण bit का index i=0 है। Column i में a_i,b_i,c_i आते हैं और s_i,c_(i+1) निकलते हैं। उसकी identity a_i+b_i+c_i=s_i+2c_(i+1) है। Carry अधिक महत्वपूर्ण columns की ओर बढ़ता है, जबकि संख्या लिखते समय अधिक महत्वपूर्ण bit पहले आती है।
A=1011 और B=0110 को c_0=0 के साथ जोड़ें। नीचे table सबसे निचले column से ऊपर की ओर है:
| Column i | a_i | b_i | c_i | s_i | c_(i+1) |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 1 | 0 | 1 |
| 3 | 1 | 0 | 1 | 0 | 1 |
Stored bits उलटी दिशा में पढ़ें: s_3s_2s_1s_0=0001। अंतिम carry c_4=1। पूरा पाँच-bit परिणाम 10001 है, जिसका मान 17=11+6 है। चार-bit unsigned storage में low=1 और carry-out=1 हैं; carry हटाने से गणितीय योग 1 नहीं बन जाता।
सामान्य unsigned inputs के लिए columns की भार वाली identities जोड़ने पर A+B+c_0=S+2^n c_n मिलता है, जहाँ 0≤S<2^n। बीच के carry terms कट जाते हैं। इसलिए S पूरे योग का modulo 2^n है और अंतिम carry unsigned addition overflow बताता है। केवल अंतिम carry से signed overflow न तय करें; वह अलग व्याख्या है और इस पाठ के बाहर है।
Circuit की जाँच और सीमाएँ
एक full adder की सभी आठ rows और integer identity जाँचें। पूरी श्रृंखला में zero, maximum values, निचले column में बनता carry, लंबी carry chain और c_0 के दोनों मान जाँचें। Ripple connection से function सही होने का तर्क मिलता है; delay model के बिना ठीक latency नहीं बता सकते। Carry आगे जाते समय वास्तविक outputs क्षणिक रूप से बदल सकते हैं। यह पाठ केवल अंतिम स्थिर मान जाँचता है, clock frequency का दावा नहीं करता।
मौलिक अभ्यास: छह single-correct MCQ
ये बुनियाद मजबूत करने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. NAND(A,A) क्या लागू करता है?
A. A B. 0 C. A′ D. 1
उत्तर: C
A गलत है: NAND(A,A), A को copy नहीं बल्कि complement करता है।
B गलत है: A=0 पर output 1 है, इसलिए constant 0 नहीं।
C सही है: idempotence से NAND(A,A)=(AA)′=A′।
D गलत है: A=1 पर output 0 है, इसलिए constant 1 नहीं।
C02. a=b=1 वाले half adder के लिए क्रमित जोड़ी (sum, carry) क्या है?
A. (0,1) B. (1,0) C. (1,1) D. (0,0)
उत्तर: A
A सही है: sum=1⊕1=0 और carry=1×1=1, इसलिए 2×carry+sum=2।
B गलत है: माँगा क्रम उलट दिया है; यह integer 1 दर्शाएगा।
C गलत है: sum में OR लगाने से यह गलत जोड़ी मिलती है, जो 3 दर्शाएगी।
D गलत है: carry 1 है; यह जोड़ी 0 दर्शाएगी।
C03. Full adder में a=1,b=1,c_in=1 हैं। (Sum, carry-out) क्या होंगे?
A. (0,1) B. (1,0) C. (0,0) D. (1,1)
उत्तर: D
A गलत है: तीन 1 का योग विषम है, इसलिए sum bit 1 है।
B गलत है: कुल 3 के लिए carry 1 चाहिए, 0 नहीं।
C गलत है: कुल 3 का binary 11 है, इसलिए कोई output 0 नहीं।
D सही है: integer total 3=2×1+1, इसलिए sum 1 और carry-out 1।
C04. p=a⊕b और g=ab लेने पर full-adder carry-out का Boolean expression कौन-सा है?
A. p+c_in B. g+pc_in C. gc_in D. p⊕c_in
उत्तर: B
A गलत है: a=1,b=0,c_in=0 पर यह 1 देता है, जबकि कुल 1 में carry नहीं।
B सही है: g से carry generate होता है या p और c_in दोनों 1 होने पर propagate होता है।
C गलत है: a=b=1,c_in=0 पर g=1 carry बनाता है, लेकिन gc_in का मान 0 है।
D गलत है: यह sum bit का expression है, carry-out का नहीं।
C05. चार-bit unsigned ripple adder में A=1001, B=0111 और c_0=1 हैं। (निचले चार bits, अंतिम carry) क्या हैं?
A. 0001, 1 B. 0000, 1 C. 10001, 0 D. 1111, 0
उत्तर: A
A सही है: 9+7+1=17=1×16+1, इसलिए low bits 0001 और अंतिम carry 1।
B गलत है: incoming carry 1 छूट गया; केवल 9+7 जोड़ा है।
C गलत है: 10001 पूरा पाँच-bit परिणाम है, चार retained bits नहीं।
D गलत है: 1111 का मान 15 है, आवश्यक exact total 17 नहीं।
C06. Half adder और full adder के बारे में सही कथन कौन-सा है?
A. Half adder incoming carry लेता है लेकिन full adder नहीं। B. दोनों का एक output है क्योंकि हर input एक bit है। C. Half adder दो bits जोड़ता है; full adder incoming carry bit भी लेता है। D. Full adder का carry-out हमेशा 1 है।
उत्तर: C
A गलत है: inputs की क्षमताएँ उलट दी हैं।
B गलत है: कुल मान दर्शाने के लिए दोनों में अलग sum और carry outputs हैं।
C सही है: full adder a,b,c_in जोड़ता है, जबकि half adder केवल a,b।
D गलत है: 000 या ठीक एक 1 वाली row में carry-out 0 है।
पाठ्यक्रम से संबंध और सीमा
यह Digital Logic का शुरुआती पाठ है; इससे GATE CS का पूरा Digital Logic पूरा नहीं होता। आधिकारिक GATE 2027 CS पाठ्यक्रम में Boolean algebra और minimization, combinational तथा sequential design, और number representation तथा arithmetic शामिल हैं। Karnaugh map, tabular minimization, sequential design, signed-number arithmetic और floating-point arithmetic के लिए आगे अलग पाठ चाहिए। पाठ्यक्रम से विषय की प्रासंगिकता जाँची गई है; यहाँ के उदाहरण और प्रश्न मौलिक हैं।
Official GATE 2027 CS syllabus, Section 2 (checked 2026-10-14).
तकनीकी convention का संदर्भ; हल किए उदाहरण और अभ्यास मौलिक हैं: MIT Computation Structures combinational logic.
प्रगति सहेजने के लिए साइन इन करें। साइन इन