Synchronous counters और finite state machine design
Gate equations से पहले state transitions
Sequential specification बताती है कि input sample होने पर stored state कैसे बदलती है। पहले transition rule लिखें, फिर encoding चुनें और flip-flop inputs निकालें। शुरुआत में gate equations का अंदाज़ा लगाने से missing states, output timing और reset की गलतियाँ छिप सकती हैं।
पूर्वज्ञान: D/T/JK characteristic equations, excitation tables, Boolean simplification और synchronous timing। सभी examples में साझा rising-edge clock, valid setup/hold और बताया reset state है। Traces में अलग बताए बिना reset inactive है। यह छोटे counters और FSM का design है, asynchronous control या पूरे state-minimization algorithm का पाठ नहीं।
Binary synchronous counter
तीन-bit modulo-8 counter की states Q_2Q_1Q_0 हैं और क्रम 000,001,010,011,100,101,110,111,000 दोहरता है। आठ states अलग करने के लिए तीन flip-flops चाहिए। Modulo का अर्थ तय अलग counts के बाद wrap है; अतिरिक्त नौवीं state जोड़ना नहीं।
T flip-flops में सबसे निचला bit हर count पर toggle होता है। Bit 1 तब toggle होता है जब पुराना Q_0=1 हो। Bit 2 तब जब दोनों पुराने lower bits 1 हों। इसलिए T_0=1,T_1=Q_0,T_2=Q_1Q_0। Q_i,next=Q_i⊕T_i में रखने पर वही sequence मिलता है।
Count-enable E के साथ T_0=E,T_1=EQ_0,T_2=EQ_1Q_0 लें। E=0 पर सभी T zero हैं और पूरी state hold होती है। पुरानी state 011 और E=1 पर तीनों T=1, इसलिए next state 100 है। T_1 निकालते समय नया Q_0 लेना गलत है; सभी controls पुरानी state से निकलते हैं।
Ripple counter में एक storage output दूसरे stage की clock बन सकता है; intermediate transitions एक common clock event पर नहीं होते। Settled count की दिशा actual edge polarities और connections पर निर्भर है। Synchronous counter ऐसा ripple-clock connection नहीं लेता, लेकिन उसके clock-to-Q और combinational delays फिर भी finite हैं। कोई design instantaneous नहीं है।
Unused state सहित modulo-3 counter
दो bits में चार states हैं, इसलिए तीन counts समा जाते हैं। क्रम 00→01→10→00 तय करें। Unused 11 की policy भी चाहिए: यहाँ अगले rising edge पर वह 00 जाएगा, यानी उस Boolean state से एक edge में recovery। Reset भी 00 स्थापित करता है। यह हर physical fault या metastability से सुरक्षा की गारंटी नहीं।
| वर्तमान Q_1Q_0 | अगला Q_1Q_0 | D_1 | D_0 |
|---|---|---|---|
| 00 | 01 | 0 | 1 |
| 01 | 10 | 1 | 0 |
| 10 | 00 | 0 | 0 |
| 11 | 00 | 0 | 0 |
D flip-flops में next-state bits ही data inputs हैं। Table से D_1=Q_1′Q_0 और D_0=Q_1′Q_0′ मिलता है। 11 सहित चारों rows जाँचें। Simplification में 11 को don't-care तभी मान सकते हैं जब specification सच में वहाँ मनमाना behavior दे; तब चुना recovery rule सिद्ध नहीं रहेगा।
हल किया उदाहरण 1: 00 से पाँच active edges के बाद 01,10,00,01,10 मिलते हैं। 11 से शुरू करें तो पहले 00 और फिर 01 होगा। तीन states के binary encoding में दो storage bits चाहिए; one-hot जैसी दूसरी encoding जानबूझकर अधिक bits ले सकती है।
Finite-state machine की शर्तें
FSM में सीमित states, input alphabet, next-state function और output rule होते हैं। Moore output केवल वर्तमान state पर निर्भर है: y=g(Q)। Mealy output state और वर्तमान input पर: y=g(Q,x)। दोनों में Q_next=f(Q,x) हो सकता है।
यह dependencies का अंतर है, physical glitches न होने का वादा नहीं। Mealy output edges के बीच input बदलने पर बदल सकता है। कई state bits से बना Moore output भी bits settle होते समय क्षणिक glitch दे सकता है। Specification को registered या glitch-free output चाहिए तो उसे अलग implement और check करें। Output trace edge से पहले है या बाद में, स्पष्ट लिखें।
Parity की Moore machine
अब तक आए input bits में ones की parity रखें। E state में ones की संख्या सम और O में विषम है। Inputs से पहले E reset करें, क्योंकि zero ones सम है। Input 0 पर state रखें; input 1 पर E↔O बदलें। E में y=0 और O में y=1।
एक D flip-flop में E=0,O=1 encode करें। D=Q⊕x और y=Q होगा। Sampled inputs 1,0,1,1 पर edges के बाद states O,O,E,O और outputs 1,1,0,1 हैं। पहले edge से पहले y=0 है। State आवश्यक history रखती है, पूरी input string नहीं।
पास-पास आए 01 की Mealy detector
Q=1 का अर्थ पिछला sampled bit 0 था; Q=0 का अर्थ previous zero उपलब्ध नहीं। Reset Q=0 करें, ताकि पहला input 1 गलत detection न दे। नया x sample करते समय y=1 ठीक तब है जब पुराना Q=1 और x=1। इसलिए y=Qx और D=x′; क्योंकि नए input के बाद याद रखना है कि नया bit zero था या नहीं।
| पुराना Q | Input x | इस sample का output y | अगला Q |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Inputs 0,1,0,1,1 के लिए पुराने state और current input से outputs 0,1,0,1,0 हैं। हर sample के बाद state 1,0,1,0,0 है। यदि updated Q और उसी x से y निकालें तो हमेशा x′x=0 मिलेगा; वह गलत observation convention है। Receiving register, timing शर्तों के साथ valid pre-edge Mealy output sample कर सकता है। इस model का अर्थ detection के बाद combinational y पूरे cycle high रहना नहीं है।
भरोसेमंद design और जाँच
- हर state का अर्थ, input sampling, output observation और reset तय करें।
- हर state/input transition लिखें। Contract अनुमति दे तभी states unspecified रखें।
- Encoding और storage चुनें। N अलग states के binary encoding में कम-से-कम ceil(log2 N) bits चाहिए; एक ही state हो तो pure combinational realization में state bits जरूरी नहीं।
- Next-state columns से D inputs या excitation rules से T/JK inputs निकालें।
- बताई recovery सुरक्षित रखते simplify करें; सभी rows और उपयोगी traces जाँचें।
- Setup/hold तथा physical output शर्तें state table से अलग जाँचें।
सामान्य गलतियाँ: states की जगह bits गिनना, wrap transition भूलना, synchronous model में bits को एक-एक करके update करना, हर unused state को don't-care मानना और pre-edge Mealy output के लिए after-edge state इस्तेमाल करना।
मौलिक अभ्यास
ये छह single-correct MCQ सीखने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. Binary encoding में पाँच FSM states अलग करनी हैं। न्यूनतम state bits कितने हैं?
A. 2 B. 5 C. 3 D. 4
उत्तर: C
A गलत है: दो bits में केवल चार states हैं।
B गलत है: one-hot में पाँच bits ले सकते हैं, लेकिन binary न्यूनतम नहीं।
C सही है: 2²<5≤2³, इसलिए तीन bits पर्याप्त और दो कम हैं।
D गलत है: चार पर्याप्त हैं लेकिन न्यूनतम नहीं।
C02. तीन-bit synchronous up-counter में T_0=1,T_1=Q_0,T_2=Q_1Q_0 हैं। पुरानी state 011 से अगली क्या है?
A. 100 B. 000 C. 111 D. 010
उत्तर: A
A सही है: पुराने 011 पर तीनों T एक हैं, इसलिए तीनों bits toggle।
B गलत है: high bit को 0 से 1 toggle होना है।
C गलत है: दोनों low bits भी 1 से 0 toggle होंगे।
D गलत है: केवल Q_0 बदला; T_1,T_2 के encoded carries छूटे।
C03. Modulo-3 counter में D_1=Q_1′Q_0,D_0=Q_1′Q_0′ हैं। Unused state 11 से अगले valid edge पर क्या होगा?
A. 11 पर रहता है। B. 01 पर जाता है। C. Equations इस state को तय नहीं करतीं। D. 00 पर जाता है।
उत्तर: D
A गलत है: Q_1′=0 से दोनों D zero हैं।
B गलत है: D_0 भी zero है, one नहीं।
C गलत है: equations चारों binary states पर defined हैं।
D सही है: दोनों next-state bits zero हैं, यानी बताई recovery।
C04. Moore output की परिभाषा कौन-सी है?
A. केवल current external input पर निर्भर। B. केवल current state पर निर्भर। C. हर implementation में state और input दोनों पर निर्भर। D. Physical glitches न होने की गारंटी है।
उत्तर: B
A गलत है: यह state-based Moore output की परिभाषा नहीं।
B सही है: y=g(Q) Moore dependency rule है।
C गलत है: सीधे input पर dependence सामान्यतः Mealy output बताती है।
D गलत है: Boolean dependency से glitch-free hardware timing सिद्ध नहीं।
C05. Parity Moore machine even से शुरू होकर 1,1,0,1 sample करती है। चार edges के बाद output bits क्या हैं?
A. 1,1,0,1 B. 0,1,1,0 C. 1,0,0,1 D. 0,0,0,1
उत्तर: C
A गलत है: दूसरा 1 state को even करता है, इसलिए दूसरा output 0।
B गलत है: पहला 1 odd parity देता है, इसलिए पहला output 1।
C सही है: cumulative parities odd, even, even, odd हैं।
D गलत है: पहले input के बाद odd state छूट गई।
C06. Mealy 01 detector में initial Q=0, पुराने Q से y=Qx और Q_next=x′ हैं। Inputs 1,0,1 के samples से कौन-से outputs जुड़े हैं?
A. 1,0,1 B. 0,0,1 C. 0,1,0 D. 0,0,0
उत्तर: B
A गलत है: reset Q=0 से पहले 1 पर false detection नहीं होता।
B सही है: पहले 1 पर 0; input 0 पर 0 और Q=1; अंतिम 1 पर 1।
C गलत है: detection में current input 1 चाहिए, बीच का 0 नहीं।
D गलत है: यह पुराने Q की जगह updated Q=x′ लगाने की गलती से मिल सकता है।
सीमा और स्रोत
यह Digital Logic के एक सीमित हिस्से का पाठ है, पूरे GATE CS की तैयारी नहीं। आधिकारिक पाठ्यक्रम केवल विषय की प्रासंगिकता की पुष्टि करता है; व्युत्पत्तियाँ, उदाहरण और अभ्यास मौलिक हैं। तकनीकी संदर्भों से representation और circuit की conventions जाँची गई हैं; उनके अभ्यास प्रश्न नहीं दोहराए गए।
स्रोत 14 अक्टूबर 2026 को जाँचे गए।
प्रगति सहेजने के लिए साइन इन करें। साइन इन