State equivalence minimization और encoding
Behavior बदले बिना redundant history हटाएँ
अलग नाम वाली दो states भविष्य के हर output के लिए समान जरूरी जानकारी रख सकती हैं। State minimization ऐसी states मिलाकर specified observable behavior बचाता है। यह states को छोटे binary नाम देना या Boolean equation simplify करना नहीं है।
पूर्वज्ञान: Moore/Mealy machines, next-state tables, D flip-flops और combinational minimization। यहाँ deterministic, पूरी तरह specified machines, एक binary input x और current state में, reset सहित, पढ़े Moore outputs हैं। Transitions valid rising edges पर हैं। Incompletely specified machines और asynchronous state assignment के लिए अलग तरीके चाहिए।
दो Moore states equivalent हैं यदि current output समान हो और हर possible future input sequence पर outputs समान हों। केवल एक trace मिलना पर्याप्त नहीं। Recursive शर्त: current outputs समान हों और हर input पर successor states भी equivalent हों। समान output आवश्यक है, लेकिन अकेले पर्याप्त नहीं।
Reachability, allowed starts पर निर्भर है
कोई state reachable है यदि permitted input sequence उसे allowed initial state से पहुँचाती है। Reset से शुरू करके पहले मिली states के successors जोड़ें; नया state न मिले तो रुकें। इस set के बाहर की state, बताई input assumptions में उस reset से normal traces नहीं बदल सकती।
Unreachable state हटाना केवल उसी behavior contract में सुरक्षित है। Fault recovery, दूसरी reset, test mode या allowed initial state वहाँ पहुँचा सकती हो तो behavior जरूरी रह सकता है। Unreachable का अर्थ hardware startup/recovery को सामान्यतः अनदेखा करने की अनुमति नहीं।
उदाहरण machine
नीचे Moore machine A पर reset होती है। y वर्तमान state का output है, transition का नहीं।
| State | y | x=0 पर अगली | x=1 पर अगली |
|---|---|---|---|
| A | 0 | C | D |
| B | 0 | C | E |
| C | 0 | C | C |
| D | 1 | B | D |
| E | 1 | A | E |
| F | 1 | F | F |
A से input 0, C और input 1, D पहुँचाते हैं। D से 0, B और B से 1, E। इसलिए A,B,C,D,E reachable हैं। उनसे F तक रास्ता नहीं और F allowed start नहीं, इसलिए normal-operation minimization में हटाएँ। C reachable है; sink होने भर से उसे नहीं हटा सकते।
Partition refinement
पहले समान current output वाली states के groups बनाएँ: यहाँ {A,B,C} और {D,E}। हर state के 0 तथा 1 successors किन blocks में हैं, उनकी सूची बनाएँ। एक block के सदस्यों की successor-block lists अलग हों तो block split करें। जब तक split हो, दोहराएँ।
पहली partition में A,B का signature (zero-output block,one-output block) है। C का (zero-output block,zero-output block), इसलिए C अलग होगा। D,E का signature भी (zero-output block,one-output block) है, लेकिन current output 1 होने से वे A,B से अलग ही रहेंगे। समान successor signature, पहले से मौजूद output अंतर नहीं हटाता।
अब blocks U={A,B},V={C},W={D,E} हैं:
| Block | y | 0 पर अगली | 1 पर अगली |
|---|---|---|---|
| U | 0 | V | W |
| V | 0 | V | V |
| W | 1 | U | W |
Stability जाँचें: A,B दोनों 0 पर V और 1 पर W; D,E दोनों 0 पर U और 1 पर W। अब split नहीं चाहिए। Fully specified Moore machine में यह fixed-point partition equivalent-state classes देती है।
तीन states आवश्यक क्यों हैं
U,W के current outputs 0,1 अलग हैं; V,W भी तुरंत अलग हैं। U,V अभी दोनों 0 देते हैं, लेकिन input 1 से U, W में जाकर 1 देगा और V,0 पर रहेगा। इसलिए एक-symbol sequence 1 उन्हें distinguish करती है। तीनों blocks की हर जोड़ी distinguishable है; और merge करने से behavior बदलेगा।
हल किया trace: inputs 1,0,1,0 पर मूल A→D→B→E→A और reduced U→W→U→W→U। Initial output सहित दोनों में 0,1,0,1,0 है। यह trace mapping समझाता है; सामान्य proof stable partition से है, केवल इस trace से नहीं।
Reduced machine encode करें और unused patterns तय करें
तीन reduced states के लिए कम-से-कम दो binary storage bits चाहिए। Q_1Q_0 में U=00,V=01,W=10 चुनें। यह encoding है, नया minimization नहीं। Unused pattern 11 के लिए next V=01 और output 0 तय करें। Reset U=00 है। इस recovery rule से unused patterns का behavior मनमाना मानने की छिपी धारणा नहीं रहती।
D flip-flops में next-state functions:
D_1=Q_0′x; D_0=Q_0+Q_1′x′; y=Q_1Q_0′.
चार binary states और दो inputs की आठ-row table से निकालें। U=00 में input 0 पर 01 और 1 पर 10। V=01 में दोनों पर 01। W=10 में 0 पर 00 और 1 पर 10। 11 में दोनों पर 01 और y=0। इससे valid states के साथ आवश्यक recovery भी जाँची जाती है।
One-hot encoding में तीन flip-flops में से एक हर state को दे सकते हैं। Storage bits अधिक हैं, लेकिन कुछ next-state logic सरल हो सकती है। कम abstract states, कम stored bits, कम literals और छोटा physical delay अलग objectives हैं। Binary-minimal bit count से fastest circuit सिद्ध नहीं होता।
Mealy में output vectors चाहिए
Mealy machine का output input और state दोनों पर है। पहले उन states को अलग करें जिनके output vectors किसी input पर अलग हों। फिर हर input के successor classes से refinement करें। Input बताए बिना केवल एक output symbol तुलना करना पर्याप्त नहीं। Equivalence में output observation convention समान रहे; pre-edge output को registered post-edge output में बदलने से interface contract बदलता है।
जाँच और सामान्य गलतियाँ
Reachability से पहले allowed starts लिखें; जरूरी recovery बचाएँ। पहले outputs से partition, फिर successor classes से बार-बार split करके stable partition पाएँ। कोई merge गलत हो तो distinguishing sequence दें। Quotient transition table बनाएँ, encoding चुनें, सभी unused patterns तय करें और equations जाँचें। केवल current outputs समान होने पर states न मिलाएँ; raw successor नाम अलग होने से उन्हें अनिवार्यतः अलग भी न मानें, क्योंकि अलग नाम equivalent classes में हो सकते हैं।
मौलिक अभ्यास
ये छह single-correct MCQ सीखने के लिए बनाए गए मौलिक प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। हर प्रश्न में ठीक एक विकल्प चुनें।
C01. दो Moore states के current outputs समान हैं। क्या केवल इतना equivalence के लिए पर्याप्त है?
A. हाँ, हमेशा B. नहीं; हर future input sequence पर भी outputs समान चाहिए। C. हाँ, यदि नामों की लंबाई समान हो D. अलग नाम की states कभी equivalent नहीं
उत्तर: B
A गलत है: भविष्य के successors अलग outputs दे सकते हैं।
B सही है: current समानता आवश्यक है, future behavior भी मिलना चाहिए।
C गलत है: नाम labels हैं, behavior नहीं।
D गलत है: अलग नाम की equivalent states के कारण ही minimization उपयोगी है।
C02. A-reset वाली उदाहरण machine में F खुद पर loop करता है और कोई reachable state F पर नहीं जाती। Normal-operation contract में क्या कर सकते हैं?
A. F को unreachable मानकर हटाएँ। B. C को sink होने से हटाएँ। C. Output कुछ भी हो, F किसी state से मिला दें। D. मान लें सभी hardware faults असंभव हैं।
उत्तर: A
A सही है: बताए reset से F का allowed path नहीं।
B गलत है: A पर input 0 से C reachable है।
C गलत है: merging में behavior बचाना है, outputs अनदेखे नहीं।
D गलत है: model की reachability physical fault guarantee नहीं।
C03. Reduced U,V दोनों output 0 देते हैं; input 1 पर U, output 1 वाले W जाता है और V वहीं रहता है। कौन-सी sequence उन्हें अलग दिखाती है?
A. Empty sequence B. कोई sequence अलग नहीं कर सकती। C. केवल input 1 D. हर sequence में कम-से-कम तीन inputs चाहिए।
उत्तर: C
A गलत है: current outputs समान हैं।
B गलत है: दिए successors ही counterexample हैं।
C सही है: input 1 के बाद outputs 1 और 0 हैं।
D गलत है: एक input पर्याप्त है।
C04. उदाहरण table की reachable A,B,C,D,E के लिए कौन-सी stable partition मिलती है?
A. {A,B,C},{D,E} B. {A,D},{B,E},{C} C. पाँचों अलग singleton blocks D. {A,B},{C},{D,E}
उत्तर: D
A गलत है: C का successor-block signature A,B से अलग है।
B गलत है: अलग current outputs वाली states मिलाई हैं।
C गलत है: A/B और D/E के outputs तथा successor-class behavior समान हैं।
D सही है: तीन blocks outputs और same successor-class choices रखते हैं।
C05. D_1=Q_0′x,D_0=Q_0+Q_1′x′,y=Q_1Q_0′ में unused state 11 पर किसी भी input में क्या होता है?
A. अगली 11,y=1 B. अगली 01,y=0 C. अगली 00,y=0 D. अगली state unspecified
उत्तर: B
A गलत है: Q_0′=0 से D_1=0,y=0।
B सही है: x से स्वतंत्र D_1=0,D_0=1,y=0।
C गलत है: Q_0=1 से D_0=1।
D गलत है: equations दोनों input cases स्पष्ट करती हैं।
C06. State minimization और encoding का सही संबंध क्या है?
A. Encoding हमेशा abstract states घटाती है। B. One-hot हमेशा सबसे कम bits लेती है। C. Minimization equivalent states मिलाता है; encoding बची states को bit patterns देती है। D. सबसे कम bits वाली encoding का physical delay सबसे छोटा ही होगा।
उत्तर: C
A गलत है: states को bit names देने से behavior merge नहीं होता।
B गलत है: binary encoding one-hot से कम bits ले सकती है।
C सही है: दोनों अलग उद्देश्य वाले design decisions हैं।
D गलत है: bit count और timing अलग circuit costs पर निर्भर हैं।
सीमा और स्रोत
यह Digital Logic के एक सीमित हिस्से का पाठ है, पूरे GATE CS की तैयारी नहीं। आधिकारिक पाठ्यक्रम केवल विषय की प्रासंगिकता की पुष्टि करता है; व्युत्पत्तियाँ, उदाहरण और अभ्यास मौलिक हैं। तकनीकी संदर्भों से representation और circuit की conventions जाँची गई हैं; उनके अभ्यास प्रश्न नहीं दोहराए गए।
स्रोत 14 अक्टूबर 2026 को जाँचे गए।
प्रगति सहेजने के लिए साइन इन करें। साइन इन