Digital Logic synthesis और cumulative review
Teaching sequence के बाद यह पाठ लें
यह छह मौलिक diagnostic MCQs वाला सीमित synthesis पाठ है,full GATE mock,score predictor या पिछले पाठों का विकल्प नहीं। इसमें representation,minimization,circuit realization,state behavior और timing जुड़ते हैं। गलत representation या sampling assumption में मिला सही numerical calculation भी गलत समाधान है।
पूर्वज्ञान पूरी Digital Logic teaching sequence है:integer/fixed/floating representation तथा arithmetic;Boolean/K-map/tabular methods;combinational components और timing;flip-flops,registers,counters,FSM design/reduction। Carry lookahead,Booth,decimal codes और alternate counters इन्हीं broad क्षेत्रों के चुने implementations हैं,अलग named official clauses नहीं। नीचे की विधि अपरिचित हो तो answer key याद करने के बजाय संबंधित prerequisite दोहराएँ।
पाँच चरणों की reasoning routine
- Contract लिखें। Bit width,signedness,scale,code,bit order,valid inputs,clock edge और rounding rule पहचानें। केवल “चार bits” पूरा number representation नहीं;केवल “counter” से sequence तय नहीं।
- Exact reference बनाएँ। Operands को mathematical values में decode करें,छोटी truth/state table बनाएँ या required transfer equation लिखें। Reference को truncated/rounded storage से अलग रखें।
- Mechanism चुनें। ऐसा arithmetic algorithm,cover,MUX/decoder realization या flip-flop excitation method चुनें जो reference लागू करे।
- Boundaries जाँचें। Zero,most-negative values,invalid codes,unused states,tie rounding और transitions लें। Don't-care की अनुमति specification देता है,सुविधा नहीं।
- Implementation constraints अलग जाँचें। Resources,widths,old-state updates,propagation deadlines और earliest-change/hold conditions देखें। Functional equivalence जरूरी है,लेकिन उससे समान timing/hazard behavior सिद्ध नहीं होता।
गलत उत्तर पर गणना दोहराने से पहले failure की श्रेणी पहचानें:representation,arithmetic width,Boolean specification,state/update order या timing assumption। इससे पता चलता है कि कौन-सा पिछला पाठ दोहराना है।
हल synthesis1:fixed-point addition और widening
Signed six-bit two's-complement storage में दो fractional bits लें। Stored signed integer I हो तो value=I/4;resolution1/4 और range−8…7.75 है। Scale स्पष्ट है,इसलिए ambiguous Q-format naming की जरूरत नहीं।
x=5.5,y=3 लें। Stored integers22=010110 और12=001100 हैं। Exact sum8.5 है। Patterns जोड़ने से100010 मिलता है,जिसका six-bit signed integer34−64=−30 और retained numerical value−7.5 है। Exact result7.75 से बड़ा है:यह signed overflow है,rounding समस्या नहीं। दोनों inputs और exact sum scale step के multiples हैं।
दोनों operands को सात signed bits में widen करें और दो fractional bits ही रखें। Stored integers22,12 वही हैं;नई range−16…15.75। Sum34 का seven-bit0100010 अब8.5 exact decode होता है। Original operands को widen करने से range समस्या रुकती है। पहले से overflow हुए100010 को sign-extend करने से−7.5 ही बचेगा,खोया sum वापस नहीं आएगा। Information छोड़ने से पहले prevention और बाद की repair अलग हैं।
हल synthesis2:floating midpoint
पूरा specified seven-bit toy format लें:sign1,exponent3,fraction3,bias3। Exponent field e=1…6 पर value=(−1)^s(1+f/8)2^(e−3)। e=0 पर value=(−1)^s(f/8)2^(1−3),जिसमें f=0 पर signed zero शामिल है। e=7,f=0 पर infinity तथा f≠0 पर NaN के लिए reserved है। Finite results को nearest,ties-to-even round करें। यह teaching format है,IEEE binary32 नहीं।
1.75+1/16 लें। पहला operand normal1.110₂×2^0,fields0|011|110 है। दूसरा subnormal f=2 है क्योंकि2/32=1/16,fields0|000|010। Exact sum29/16=1.8125 है। पास के representable values1.75 तथा1.875 हैं,दोनों1/16 दूर। Retained fraction integers6 तथा7 होने से ties-to-even,6 चुनता है:stored result फिर1.75।
Addition “असफल” नहीं हुआ:exact sum बदला,लेकिन rounding ने वही stored value चुनी। इसे integer overflow न कहें और arithmetic identity से rounding बाद exact stored equality न मानें। Exact rational result,पास के grid points और tie decision अलग दिखाएँ।
हल synthesis3:एक function,कई realizations
F(A,B,C)=Σm(0,2,5,7),index4A+2B+C और कोई don't-care नहीं लें। Pairs(0,2),(5,7) केवल B में अलग हैं। Implicants A′C′ तथा AC से F=A′C′+AC। यही maximal valid cubes हैं और दोनों essential हैं। कोई four-cell cube off-set को छोड़े बिना नहीं बनता,इसलिए पहले terms फिर literals घटाने की lexicographic cost में two terms,four literals minimum हैं।
Result,A XNOR C है;settled function में B irrelevant है। A को2:1 MUX select बनाकर I0=C′,I1=C रखें। A=0 पर restriction C′ तथा A=1 पर C है। यह cofactor check है,ones के pattern से अनुमान नहीं।
हर adjacent on-set pair एक implicant से covered है,इसलिए two-level SOP,single-input static-1 bridging criterion पूरा करता है। इससे A,C साथ बदलने पर glitch-free behavior की guarantee नहीं। उदाहरण endpoints A,C=00 और11 में output1,लेकिन intermediate01 या10 में0 है। Boolean minimization,implementation selection और transition assumptions अलग सवाल हल करते हैं।
हल synthesis4:saturating state machine
दो rising-edge D flip-flops Q_1Q_0 को unsigned count0…3 मानें। Synchronous reset r=1 सबसे अधिक priority से00 load करता है। अन्यथा enable e=1 increment करे,पर3 पर hold; e=0 पर hold। Moore output full=Q_1Q_0 current saturated state बताता है। चारों patterns legal हैं;unused-state don't-cares नहीं।
r=0 में आठ(Q,e) rows से:
D_1=Q_1 OR(e AND Q_0); D_0=(Q_0 XOR e) OR(Q_1 AND Q_0)।
Q=11 पर e=1 में भी11 रहता है;ordinary modulo-four increment00 पर wrap करके specification तोड़ता। r=1 पर इन D inputs की जगह00 चुनकर reset लागू करें।00 से reset inactive रखते हुए e sequence1,1,0,1,1 पर successive post-edge states01,10,10,11,11 हैं। दोनों equations में पुराना Q लें;एक bit update करके उसी edge पर उसका नया मान दूसरे में न दें।
अब zero skew,maximum clock-to-Q0.5ns,maximum next-state logic4ns और setup0.7ns लें। Setup के लिए period कम-से-कम5.2ns। Minimum clock-to-Q0.2ns,minimum logic0.3ns और hold0.6ns हों तो0.2+0.3=0.5ns,hold को0.1ns से चूकता है। केवल clock धीमा करने से same-edge condition ठीक नहीं। पर्याप्त minimum data-path delay जोड़ना एक उपाय है,लेकिन उसका maximum delay भी setup दोबारा जाँचते समय शामिल करें। State equations सही हो सकती हैं,जबकि physical timing budget गलत हो।
Consolidation checklist
- Number questions में decode,exact गणित,range check,फिर बताए rule से rounding/bit retention करें। Carry और signed overflow अलग checks हैं।
- Minimization में on-set,off-set,allowed don't-cares लिखें;coverage,cost और hazard requirement अलग जाँचें। Prime का अर्थ essential नहीं।
- Components में select/enable polarity तथा invalid-input behavior बताएँ। Priority,parity,Gray और BCD codes के अर्थ अलग हैं।
- State machines में हर allowed state/input pair,reset priority,source snapshots और output observation time देखें। केवल current outputs समान होने से states equivalent नहीं।
- Timing में maximum-path setup तथा minimum-path hold अलग जाँचें। Ripple transients और single-input hazard guarantees अपने models पर निर्भर हैं।
नीचे practice इन connections के कुछ नमूने लेती है। छह सही choices से हर Digital Logic skill mastered होना सिद्ध नहीं। हर explanation दोबारा derive करें और फिर पास का एक boundary case स्वयं जाँचें।
मौलिक अभ्यास
ये छह single-correct MCQ सीखने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. Signed six-bit fixed-point में value I/4 है।010010 तथा001110 जोड़कर छह bits रखें। कौन-सा result सही है?
A. Exact8;retained100000 का मान−8;signed overflow है। B. Exact8;retained100000 का मान+8;overflow नहीं। C. Exact4;retained010000;overflow नहीं। D. Exact8;retained100000 का मान−8 केवल rounding से है।
उत्तर: A
A सही है:stored integers18+14=32 से4.5+3.5=8;छह-bit32 का signed मान−32,scale बाद−8 है;exact result सीमा से बाहर है।
B गलत है:top-bit-one100000 scale से पहले signed−32 है,+32 नहीं।
C गलत है:scale तय है;exact योग8 है,4 नहीं।
D गलत है:सभी values1/4 grid पर हैं;समस्या range overflow है,quantization नहीं।
C02. बताए s1/e3/f3,bias3 toy float में1.75+1/16 को nearest,ties-to-even round करें। कौन-सा value store होगा?
A. 1.875 B. 1.75 C. 1.8125 exact D. 2.0
उत्तर: B
A गलत है:दोनों neighbors tie हैं,पर इसका retained fraction7 odd है।
B सही है:exact midpoint1.8125,even retained fraction6 वाले neighbor पर round है।
C गलत है:इस exponent पर format से अधिक fraction precision चाहिए।
D गलत है:2.0 दोनों पास के grid points से अधिक दूर है।
C03. F(A,B,C)=Σm(1,3,4,6),index4A+2B+C,बिना don't-cares के,A-selected2:1 MUX में(I0,I1) क्या हैं?
A. (C′,C) B. (B,B′) C. (C,C′) D. (0,1)
उत्तर: C
A गलत है:वह complement XNOR है,जिसका on-set0,2,5,7 है।
B गलत है:required function,B से स्वतंत्र है।
C सही है:A=0 पर C,A=1 पर C′ चाहिए;F=A′C+AC′।
D गलत है:वे constants केवल A देते हैं,A XOR C नहीं।
C04. बताया two-bit saturating counter00 से reset inactive में शुरू है। Successive edges पर e=1,0,1,1,1 हो तो post-edge sequence क्या है?
A. 01,10,11,00,01 B. 01,01,10,11,00 C. 00,00,01,10,11 D. 01,01,10,11,11
उत्तर: D
A गलत है:e=0 पर hold तथा saturation पर wrap रोकना चाहिए।
B गलत है:last step saturated11 से गलत00 wrap करता है।
C गलत है:first enabled edge पर00 से01 increment होना चाहिए।
D सही है:increment,hold,increment,increment,फिर maximum पर hold।
C05. Zero-skew timing में t_cq,max=0.5ns,t_pd=4ns,setup=0.7ns,t_cq,min=0.2ns,t_cd=0.3ns,hold=0.6ns हैं। सही assessment क्या है?
A. Period≥5.2ns से setup पूरा,लेकिन hold0.1ns से fail है। B. Period≥5.2ns हर hold violation अपने आप ठीक करता है। C. Period≥4ns पर्याप्त और hold pass है। D. Period≤0.5ns दोनों constraints ठीक करता है।
उत्तर: A
A सही है:maximum path0.5+4+0.7=5.2;minimum0.2+0.3=0.5<0.6।
B गलत है:hold same-edge earliest-arrival condition है;लंबा period उसे नहीं सुधारता।
C गलत है:register/setup delays छोड़े और minimum path गलत जाँचा।
D गलत है:छोटा period setup और खराब करता है,hold inequality नहीं बदलता।
C06. Signed चार-bit−8 को+3 से exact आठ bits में multiply करें,फिर केवल चार bits रखें। सही निष्कर्ष क्या है?
A. Full00011000;low1000 exact+8 है। B. Full11101000;low1000 का मान−8,इसलिए signed narrowing में exact−24 खोता है। C. Full11101000;low1000 अब भी−24 है। D. Full11111000;width बढ़ाने की जरूरत नहीं।
उत्तर: B
A गलत है:product negative है और चार-bit1000,−8 है।
B सही है:256−24=232=11101000;−24,−8…7 में नहीं समाता,इसलिए retained signed value बदलता है।
C गलत है:चार-bit two's complement में−24 नहीं समाता।
D गलत है:11111000,−8 अर्थात original multiplicand है,product नहीं।
सीमा और स्रोत
यह Digital Logic के एक सीमित हिस्से का पाठ है, पूरे GATE CS की तैयारी नहीं। आधिकारिक पाठ्यक्रम केवल विषय की प्रासंगिकता की पुष्टि करता है; व्युत्पत्तियाँ, उदाहरण और अभ्यास मौलिक हैं। तकनीकी संदर्भों से representation और circuit की conventions जाँची गई हैं; उनके अभ्यास प्रश्न नहीं दोहराए गए।
- Official GATE 2027 CS syllabus Section 2
- MIT combinational synthesis conventions
- MIT sequential timing and old-state conventions
- Oracle floating-point format and rounding conventions
स्रोत 14 अक्टूबर 2026 को जाँचे गए।
प्रगति सहेजने के लिए साइन इन करें। साइन इन