Combinational timing और static hazards
Truth table settled values का contract है
Boolean equivalence बताता है कि inputs तथा internal nodes settle होने के बाद outputs क्या हैं। इससे दो implementations के transient waveforms समान होना नहीं निकलता। Delayed physical circuit का output थोड़े समय बदल सकता है, भले प्रारंभिक और अंतिम Boolean values समान हों। हम timing bounds, specific delay simulation और structural hazard prevention को अलग रखेंगे।
पूर्वज्ञान: gates, Boolean algebra, Karnaugh maps और full adders। Sequential setup/hold का उपयोग केवल output delay को sampling deadline से जोड़ने के लिए है। सभी numerical delays उदाहरण के हैं, device specifications नहीं। जब तक अलग न कहा जाए wires का delay zero है; register उदाहरण में clock skew नहीं है।
Gate का propagation delay t_pd, relevant inputs valid और stable होने के बाद output के valid तथा settled होने के समय की upper bound है। Contamination delay t_cd, input change के बाद पुराने valid output में बदलाव शुरू होने की earliest-time lower bound है। इनके बीच का interval किसी pulse की निश्चित duration नहीं। Valid specification में 0≤t_cd≤t_pd है।
Acyclic logic में conservative total propagation bound, input-to-output paths पर gate propagation delays के योग का maximum है। Conservative contamination bound, contamination path sums का minimum है। ये bounds हैं, हर transition पर हर path सक्रिय होने का दावा नहीं। Side-input values कोई path रोक सकती हैं; Boolean constraints कुछ structural paths को unsensitizable बना सकती हैं। संबंधित restrictions सिद्ध करने के बाद ही tighter bound लें।
Gate count नहीं, arrival times आगे बढ़ाएँ
हल किया उदाहरण 1: u=a AND b,v=c XOR d,F=u OR v। AND के (t_cd,t_pd)=(1,3) ns, XOR के (2,5) ns और OR के (1,2) ns हैं। सभी primary inputs time zero पर valid हों तो AND branch bound 3+2=5 ns और XOR branch 5+2=7 ns है। इसलिए network t_pd की bound 7 ns है। Minimum contamination path sum min(1+1,2+1)=2 ns है।
हर gate का latest output arrival=max(latest input arrivals)+t_pd है। c time 2 ns पर आए और a,b,d time zero पर, तो v अधिकतम max(2,0)+5=7 ns पर valid है, और F अधिकतम max(3,7)+2=9 ns पर। केवल दो logic levels गिनकर एक “gate delay” से गुणा करना अंतर चूक जाएगा। इन guarantees के लिए चारों inputs पर्याप्त देर स्थिर भी रहने चाहिए।
Zero-skew edge-triggered registers के बीच setup bound है T_clock≥t_cq,max+t_pd,logic+t_setup। Clock-to-Q 0.8 ns, logic 7 ns और setup 0.7 ns से T_clock≥8.5 ns। संबंधित ideal upper frequency 1/(8.5 ns)≈117.65 MHz है। Hold अलग है: t_cq,min+t_cd,logic≥t_hold। ये 0.4,2,0.6 ns हों तो 2.4≥0.6 पूरा होता है। लंबा clock period same-edge hold violation ठीक नहीं करता।
Carry timing में starting condition बताएँ
Ripple adder में p_i=a_i XOR b_i,g_i=a_i b_i,c_(i+1)=g_i OR (p_i AND c_i),s_i=p_i XOR c_i लें। यह एक स्पष्ट implementation है; दूसरे full-adder gate arrangements के delays अलग हो सकते हैं।
हल किया उदाहरण 2: p_i XOR delay 2 ns,g_i AND delay 1 ns, हर carry-path AND 2 ns, हर carry OR 1 ns और हर sum XOR 2 ns है। Operands और c_0 time zero पर valid हों, तो सभी p_i अधिकतम 2 ns और g_i,1 ns पर valid हैं। इसलिए c_1 अधिकतम max(1,max(2,0)+2)+1=5 ns पर valid है। आगे c_2 की bound 8 ns,c_3 की 11 ns,c_4 की 14 ns है। Most-significant sum s_3 अधिकतम max(2,11)+2=13 ns पर valid है। चार-bit adder के सभी outputs बड़ी bound,14 ns तक valid हैं।
इसके बजाय c_0 बदलने से पहले p_i,g_i settled हों, तो propagated carry केवल carry AND और OR से गुजरता है, अर्थात हर stage में 3 ns। तब c_0 के बाद c_4 अधिकतम 12 ns और s_3,11 ns में बदलता है। अलग उत्तर अलग starting conditions के हैं, विरोधाभासी गणित के नहीं। हर ripple stage पर p-generation delay फिर जोड़ना parallel में हो चुका काम दो बार गिनना होगा।
Concrete waveform वाला static-1 hazard
Two-level AND-OR implementation F=xy+x′z में y=z=1 स्थिर रखें। x के दोनों values पर settled output 1 है। शुरू में x=1 और circuit settled है; t=0 पर अकेला change x:1→0 हो। केवल इस उदाहरण में exact transport delays लें: inverter 3 ns, हर product AND 2 ns और final OR 1 ns; rising/falling delays समान हैं। Transport का अर्थ pulse को delay करना है, छोटा होने पर filter करना नहीं।
xy term,2 ns पर गिरता है। Inverted x,3 ns पर उठता है, इसलिए x′z,5 ns पर उठता है। 2 से 5 ns के बीच दोनों OR inputs zero हैं। इसलिए output,3 ns पर गिरकर 6 ns पर उठता है: तीन-nanosecond zero pulse, जबकि दोनों endpoint values one हैं। यह static-1 hazard है। Hazard का अर्थ कुछ allowed delays में glitch संभव है; दूसरे delays या inertial filtering से pulse बदल या दब सकता है। केवल upper/lower delay bounds से यह exact waveform न निकालें।
Consensus term yz जोड़ें: F_safe=xy+x′z+yz। Truth table नहीं बदलती। यदि yz=1,तो y=z=1 और x=1 होने पर xy true, x=0 होने पर x′z true है; इसलिए अतिरिक्त term केवल पहले से मौजूद ones ढकता है। बताए transition में yz one रहता है, इसलिए stable input final OR को high रखता है। सामान्य Boolean minimization इस redundancy को हटाता, लेकिन यहाँ उसका timing उद्देश्य है।
K-map अर्थ और static-0 dual
Single-input-change assumption में two-level SOP implementation के static-1 hazards हटाने के लिए हर adjacent on-set cell pair को कम-से-कम एक common implicant से cover करें। ऊपर F में xyz=011 और 111, x के पार adjacent हैं, पर शुरू में अलग terms से covered थे। Shared group yz उन्हें जोड़ता है। Physical implementation को उस cover के अनुरूप रखें; बाद की arbitrary factoring hazard behavior बदल सकती है।
Dual उदाहरण G=(x+y)(x′+z) है। y=z=0 हों तो x बदलने पर settled output zero रहना चाहिए। यदि थोड़ी देर दोनों sum terms one हों तो static-0 hazard हो सकता है। Redundant sum factor (y+z) से गुणा करने पर G_safe=(x+y)(x′+z)(y+z) मिलता है; truth table वही है और बताए case में stable zero factor उपलब्ध है। POS/K-map में common zero groups adjacent zero cells जोड़ते हैं।
ये परिणाम मानते हैं कि एक समय पर केवल एक external input बदले और बाकी inputs fixed रहें। कई inputs साथ बदलना, unequal arrivals, multilevel dynamic hazards तथा asynchronous clock/control safety की अलग analysis चाहिए। Dynamic hazard में एक अपेक्षित अंतिम change की जगह output बार-बार switch करता है। “Minimum literals” या केवल एक consensus term से पूरा physical system glitch-free सिद्ध नहीं होता।
मुख्य बातें और सामान्य गलतियाँ
Settled-output deadlines के लिए maximum path delay और earliest-change guarantees के लिए minimum path delay लें। Nonzero input arrival times शामिल करें। Operand-generation delay को पहले से settled carry propagation से अलग रखें। Hazard analysis, implementation और transitions का विषय है, केवल truth-table equality का नहीं। Static-1 glitch, अपेक्षित one से थोड़े समय गिरता है; static-0 glitch, अपेक्षित zero से थोड़े समय उठता है। Pulse width या hazard-free दावा करने से पहले delay और input-change models लिखें।
मौलिक अभ्यास
ये छह single-correct MCQ सीखने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. Worked AND/XOR branches के OR पर मिलने वाले network में सभी inputs time zero पर valid हों तो conservative (t_cd,t_pd) bounds क्या हैं?
A. (3,5) ns B. (2,7) ns C. (7,2) ns D. (1,5) ns
उत्तर: B
A गलत है: minimum contamination और maximum propagation paths नहीं चुने।
B सही है: min(1+1,2+1)=2 और max(3+2,5+2)=7।
C गलत है: min/max भूमिकाएँ उलटी हैं; यहाँ t_cd,t_pd से बड़ा नहीं।
D गलत है: final OR delay छोड़ दिया।
C02. उसी network में केवल c,2 ns पर valid होता है; a,b,d zero पर valid हैं। F अधिकतम किस समय तक valid होने की guarantee है?
A. 5 ns B. 7 ns C. 9 ns D. 11 ns
उत्तर: C
A गलत है: केवल छोटा AND-to-OR branch गिना।
B गलत है: यह v का arrival है, final output का नहीं।
C सही है: v,2+5=7 पर और OR के 2 जोड़कर F,9 ns पर।
D गलत है: input lateness के 2 ns दो बार गिने।
C03. बताए चार-bit ripple model में c_0 बदलने से पहले p_i,g_i settled हों, तो c_0 से c_4 की propagation bound क्या है?
A. 12 ns B. 14 ns C. 8 ns D. 11 ns
उत्तर: A
A सही है: चार carry stages में हर बार 2+1=3 ns।
B गलत है: 14 ns तब था जब p_i भी time zero से generate होना था।
C गलत है: हर carry OR का 1 ns छोड़ दिया।
D गलत है: 11 ns संबंधित c_0-to-s_3 bound है, c_4 का नहीं।
C04. F=xy+x′z,y=z=1,x:1→0 में exact transport delays NOT=3,AND=2,OR=1 ns हों, तो output glitch क्या है?
A. 2 से 5 ns तक high B. 2 से 5 ns तक low C. Glitch नहीं क्योंकि endpoint outputs समान हैं D. 3 से 6 ns तक low
उत्तर: D
A गलत है: expected output high है; hazard low pulse है।
B गलत है: ये OR-input gap times हैं, final OR delay से पहले।
C गलत है: समान truth-table endpoints से transients नहीं हटते।
D सही है: product terms 2…5 में zero; OR का 1 ns delay pulse को 3…6 करता है।
C05. xy+x′z के बताए single-input static-1 hazard को function बदले बिना कौन-सा redundant term जोड़ता है?
A. xz B. yz C. y+z D. x+x′
उत्तर: B
A गलत है: xz सामान्यतः redundant नहीं; x=1,y=0,z=1 पर output बदलता है।
B सही है: yz consensus term है और बताए transition में one रहता है।
C गलत है: y+z को OR करने से कई rows पर function बदलता है।
D गलत है: x+x′ one है; जोड़ने से function हमेशा one हो जाएगा।
C06. Two-level SOP में हर adjacent on-set pair को common implicant से जोड़ने पर कौन-सा निष्कर्ष उचित है?
A. हर asynchronous system safe है। B. सभी multiple-input-change glitches असंभव हैं। C. बताए single-input-change model और सुरक्षित two-level implementation में static-1 hazards हटते हैं। D. Circuit का area अनिवार्यतः minimum है।
उत्तर: C
A गलत है: system-level asynchronous safety के लिए अतिरिक्त assumptions और analysis चाहिए।
B गलत है: multiple-input transitions इस guarantee के बाहर हैं।
C सही है: common product term हर covered single-input transition में asserted रहता है।
D गलत है: hazard हटाने वाले redundant terms area बढ़ा सकते हैं।
सीमा और स्रोत
यह Digital Logic के एक सीमित हिस्से का पाठ है, पूरे GATE CS की तैयारी नहीं। आधिकारिक पाठ्यक्रम केवल विषय की प्रासंगिकता की पुष्टि करता है; व्युत्पत्तियाँ, उदाहरण और अभ्यास मौलिक हैं। तकनीकी संदर्भों से representation और circuit की conventions जाँची गई हैं; उनके अभ्यास प्रश्न नहीं दोहराए गए।
- Official GATE 2027 CS syllabus Section 2
- MIT delay-bound definitions and path composition
- IISc NPTEL Digital Systems: hazard conventions
स्रोत 14 अक्टूबर 2026 को जाँचे गए।
प्रगति सहेजने के लिए साइन इन करें। साइन इन