GATE EC · EE · IN

Sequential circuits

Flip-flops, counters, shift registers, state machines and timing

Sequential circuits have memory: their outputs depend on stored state as well as on the present inputs, and in a synchronous circuit flip-flops update that state at clock edges. The standard problems are tracing a counter or shift register clock by clock, analysing or converting flip-flops with their characteristic and excitation tables, drawing the state diagram of a sequence detector, finding the maximum clock frequency or checking hold time from delay data, and finding the timing of a 555 timer. Each is mechanical once the tables, formulas and timing inequalities below are learned.

30 previous-year questions · 30 solved · 5 practice questions

Latches, flip-flops and the conventions used here

Conventions in these notes. A complement is written with an overline, so $\overline{Q}$ means NOT $Q$ . $Q_{n}$ is the present state (just before the active clock edge) and $Q_{n + 1}$ is the next state (just after it). Positive logic is used (1 = HIGH). Flip-flops are positive-edge-triggered unless stated otherwise. A multi-bit state such as $Q_{2} Q_{1} Q_{0}$ is written MSB first. X in a table means don't care. The propagation delay of a flip-flop, $t_{p d}$ , is its clock-to-Q delay $t_{cq}$ . Setup time $t_{s u}$ and hold time $t_{h}$ are defined in the timing section.

A combinational circuit's output depends only on its present inputs. A sequential circuit's output also depends on stored state. The basic storage element is the SR latch. It is built either from two cross-coupled NOR gates with active-HIGH inputs $S$ and $R$ , or from two cross-coupled NAND gates with active-LOW inputs $\overline{S}$ and $\overline{R}$ .

NOR latch: S R	NOR latch: $Q_{n + 1}$	NAND latch: $\overline{S} \overline{R}$	NAND latch: $Q_{n + 1}$
0 0	$Q_{n}$ (hold)	1 1	$Q_{n}$ (hold)
0 1	0 (reset)	1 0	0 (reset)
1 0	1 (set)	0 1	1 (set)
1 1	Forbidden: $Q = \overline{Q} = 0$	0 0	Forbidden: $Q = \overline{Q} = 1$

Why S = R = 1 is forbidden in the NOR latch. Both outputs are forced to 0, so $Q$ and $\overline{Q}$ are no longer complements of each other. It gets worse if $S$ and $R$ then return to 0 together: the two gates race, and the final state cannot be predicted. The NAND latch has the same fault when both of its active-LOW inputs are 0, which forces both outputs to 1.

Gated latches. A gated (clocked) SR latch adds an enable input EN. With EN = 0 it holds its state whatever $S$ and $R$ do. With EN = 1 it behaves as an SR latch, so $S = R = 1$ with EN = 1 is still forbidden. The gated D latch connects $S = D$ and $R = \overline{D}$ , which removes the forbidden input. While EN = 1 the output follows $D$ (the latch is transparent), and when EN goes to 0 the latch holds the last value of $D$ .

Property	Gated latch	Edge-triggered flip-flop
Responds to	The level of the enable (clock)	Only the active clock edge
Output while the clock is active	Follows the input (transparent)	Held; changes once, just after the edge

Edge-triggered and master-slave flip-flops. An edge-triggered flip-flop samples its inputs only at the active clock edge, so its state changes at most once per clock period. A master-slave flip-flop is two latches in series, enabled on opposite clock phases. In the usual arrangement the master is transparent while CLK = 1 and the slave while CLK = 0. The output therefore changes only when the clock falls. Apart from a brief overlap caused by the delay of the clock inverter, the two latches are never transparent at the same time.

Race-around condition. Consider a level-triggered JK flip-flop with $J = K = 1$ . The output toggles, the new output feeds back to the input gates, and the output toggles again. This repeats for as long as the clock stays HIGH, so the state left after the pulse cannot be predicted. It happens when the clock pulse width $t_{p}$ is longer than the flip-flop's propagation delay $t_{p d}$ . Master-slave and edge-triggered designs remove it. A level-triggered JK can avoid it only by keeping the clock pulse narrower than the propagation delay.

CONDITION TO AVOID RACE-AROUND

t_{p} < t_{p d} < T

$t_{p}$ = width of the HIGH clock pulse, $t_{p d}$ = flip-flop propagation delay, $T$ = clock period. Applies to a level-triggered JK flip-flop in toggle mode ( $J = K = 1$ ).

EXAM TIP

In a waveform question, first check whether the element is a latch or an edge-triggered flip-flop. A D latch's output copies $D$ for as long as the enable is active. A D flip-flop copies $D$ only at the edge and ignores any change in between. The same $D$ and clock waveforms therefore give different outputs.

EXAM TIP

A master-slave JK cures race-around, but its master is open for the whole HIGH phase. A brief 1 on $J$ (when $Q = 0$ ) or on $K$ (when $Q = 1$ ) during that phase is therefore caught by the master and passed to the output at the falling edge, even if the input went back to 0 before the edge. This fault is called 1s catching. Edge-triggered flip-flops do not have it.

Characteristic tables, excitation tables and flip-flop conversion

The characteristic table (or characteristic equation) gives the next state $Q_{n + 1}$ from the inputs and the present state $Q_{n}$ . Use it to analyse a circuit. The excitation table answers the reverse question: which inputs produce a required transition $Q_{n} \to Q_{n + 1}$ ? Use it to design counters and state machines.

SR FLIP-FLOP

Q_{n + 1} = S + \overline{R} Q_{n}, S R = 0

The constraint $S R = 0$ is part of the equation, because $S = R = 1$ is not allowed. $S R = 00$ holds, $10$ sets, $01$ resets.

JK FLIP-FLOP

Q_{n + 1} = J \overline{Q_{n}} + \overline{K} Q_{n}

$J K = 00$ holds, $01$ resets, $10$ sets, $11$ toggles. No input combination is forbidden.

D FLIP-FLOP

Q_{n + 1} = D

The next state is the value of $D$ at the active edge, so a D flip-flop delays its input by one clock period.

T FLIP-FLOP

Q_{n + 1} = T \oplus Q_{n} = T \overline{Q_{n}} + \overline{T} Q_{n}

$T = 1$ toggles, $T = 0$ holds. In toggle mode the output frequency is half the clock frequency, and n toggling stages in cascade divide the clock by $2^{n}$ .

$J$	$K$	$Q_{n + 1}$	Action
0	0	$Q_{n}$	Hold
0	1	0	Reset
1	0	1	Set
1	1	$\overline{Q_{n}}$	Toggle

Transition	S R	J K	D	T
$0 \to 0$	0 X	0 X	0	0
$0 \to 1$	1 0	1 X	1	1
$1 \to 0$	0 1	X 1	0	1
$1 \to 1$	X 0	X 0	1	0

Write the characteristic table of the flip-flop you need (the target): its inputs and $Q_{n}$ as columns, and $Q_{n + 1}$ as the result.
For every row, look up in the available flip-flop's excitation table the inputs it needs to make that $Q_{n} \to Q_{n + 1}$ transition.
Plot each input of the available flip-flop on a K-map whose variables are the target's inputs and $Q_{n}$ . Use the X entries as don't cares.
Minimise. The resulting expressions are the gates placed in front of the available flip-flop.

Available flip-flop	Required behaviour	Input logic (Q = present output)
JK	T	$J = K = T$
JK	D	$J = D$ , $K = \overline{D}$
JK	SR	$J = S$ , $K = R$ (with $S R = 0$ )
D	T	$D = T \oplus Q$
D	JK	$D = J \overline{Q} + \overline{K} Q$
T	D	$T = D \oplus Q$
T	JK	$T = J \overline{Q} + K Q$
SR	D	$S = D$ , $R = \overline{D}$
SR	JK	$S = J \overline{Q}$ , $R = K Q$
SR	T	$S = T \overline{Q}$ , $R = T Q$

EXAM TIP

Two one-line shortcuts cover most conversions. To build any flip-flop from a D flip-flop, set $D$ equal to the target's characteristic equation (for JK, $D = J \overline{Q} + \overline{K} Q$ ). To build any flip-flop from a T flip-flop, set $T = Q_{n} \oplus Q_{n + 1}$ , so that T is 1 exactly when the output must change (for JK, $T = J \overline{Q} + K Q$ ).

EXAM TIP

Asynchronous preset and clear inputs act immediately, without waiting for the clock, and override the synchronous inputs. They are often active-LOW (drawn with a bubble), so check for the bubble before tracing a circuit. Preset and clear must not be asserted together: as with $S = R = 1$ in a latch, $Q$ and $\overline{Q}$ stop being complements and the state left afterwards is unpredictable.

Counters and timers: ripple, synchronous, mod-N, up/down and the 555

A counter steps through a fixed cycle of states, one step per clock pulse. A mod-N counter has N states in its cycle, so its state repeats every N clock pulses and it divides the clock frequency by N. With n flip-flops at most $2^{n}$ states exist, and any state outside the cycle is an unused state. A counter also works as a timer: counting pulses from a clock of known frequency $f$ measures time, since $N$ pulses take $N / f$ .

MINIMUM FLIP-FLOPS FOR N STATES

n = ⌈ lo g_{2} N ⌉

Applies to a mod-N counter and to an N-state machine with binary state encoding. The $2^{n} - N$ unused states must be checked for lock-out.

OUTPUT FREQUENCY OF A MOD-N COUNTER

f_{out} = \frac{f _{c l k}}{N}

$f_{out}$ is the rate at which the whole state repeats. In a binary mod-N counter it is also the frequency of the most significant output. Lower bits can repeat faster: in a mod-6 binary counter (0 to 5), $Q_{0}$ still alternates 0, 1 on every clock, so its frequency is $f_{c l k} /2$ . The output need not have a 50% duty cycle; in a mod-5 binary counter the MSB is HIGH for 1 clock period in 5. A mod-M counter cascaded into a mod-N counter gives a mod- $M N$ counter with $f_{out} = f_{c l k} / (M N)$ . In a full n-bit binary (mod- $2^{n}$ ) counter, bit $Q_{k}$ ( $k = 0$ for the LSB) has frequency $f_{c l k} / 2^{k + 1}$ and a 50% duty cycle.

Asynchronous (ripple) counter. Only the first flip-flop receives the external clock. Each later flip-flop is clocked by the output of the one before it, and every stage is in toggle mode ( $T = 1$ , or $J = K = 1$ ). A change must pass down the chain one flip-flop at a time, so the delays add. Whether the circuit counts up or down depends on the triggering edge and on which output clocks the next stage:

Flip-flops trigger on	Next stage clocked from $Q$	Next stage clocked from $\overline{Q}$
Negative (falling) edge	Up counter	Down counter
Positive (rising) edge	Down counter	Up counter

MAXIMUM CLOCK FREQUENCY OF AN N-BIT RIPPLE COUNTER

f_{max} = \frac{1}{n t _{p d}}

The worst case is a transition in which all n stages change (for example 0111 to 1000 in a 4-bit up counter), which takes $n t_{p d}$ . The clock period must be at least this long for the count to settle, and be readable, before the next edge. If a decoder must also read the count, add its delay or strobe time $t_{s}$ : $f_{max} = 1/ (n t_{p d} + t_{s})$ .

Mod-N ripple counter by reset. Connect every output that is 1 in the binary code of N to a NAND gate, and use it to drive the active-LOW asynchronous CLEAR of every flip-flop. Any number with all of these bits HIGH is at least N, so N is the first count that fires the gate. The count N lasts only a few nanoseconds before it is cleared (a transient state), so the stable sequence is 0 to $N - 1$ . For a decade (mod-10) counter, $N = 10 = 1010$ , so the gate is a NAND of $Q_{3}$ and $Q_{1}$ . No count from 0 to 9 has both of these bits HIGH.

EXAM TIP

With an asynchronous CLEAR, decode the state N, because the clear acts immediately. With a synchronous CLEAR, which acts only at the next clock edge, decode $N - 1$ instead. Decoding N there would give a mod- $(N + 1)$ counter.

EXAM TIP

Decoding a ripple counter's outputs can produce false pulses. Going from 0111 to 1000, an up ripple counter passes briefly through 0110, 0100 and 0000 as each stage flips in turn. A synchronous counter avoids this sequence of false states, because all its stages switch on the same edge. Small differences between its flip-flops' delays can still produce much shorter spikes.

Synchronous counter. All flip-flops share the clock, so every stage that changes does so one clock-to-Q delay after the same edge. Combinational logic decides which stages change. In a binary up counter a bit toggles exactly when every lower bit is 1. In a down counter it toggles when every lower bit is 0.

SYNCHRONOUS BINARY COUNTER WITH T FLIP-FLOPS

T_{0} = 1, T_{k} = Q_{0} Q_{1} \dots Q_{k - 1} (k \geq 1)

This is the up counter. Down counter: $T_{k} = \overline{Q_{0}} \overline{Q_{1}} \dots \overline{Q_{k - 1}}$ . Up/down with mode input $M$ (1 = up, 0 = down): $T_{k} = M Q_{0} \dots Q_{k - 1} + \overline{M} \overline{Q_{0}} \dots \overline{Q_{k - 1}}$ . With JK flip-flops, use $J_{k} = K_{k} = T_{k}$ .

Fix the count sequence and use $n = ⌈ lo g_{2} N ⌉$ flip-flops.
Write the state table: each present state with its next state. Unused states get don't-care next states.
From the chosen flip-flop's excitation table, write the input each flip-flop needs in every row. For D flip-flops, D is simply the next-state bit.
Minimise each input on a K-map of the present-state bits, using the unused states as don't cares.
Check for lock-out: work out where each unused state goes with the logic you chose. The counter is self-starting only if every unused state eventually enters the main cycle. If one does not, redesign with those next states fixed.

WORKED EXAMPLE

Design a synchronous counter with D flip-flops that counts $000 \to 001 \to 010 \to 011 \to 100 \to 101 \to 000$ (state $Q_{2} Q_{1} Q_{0}$ , MSB first). Find minimal sum-of-products expressions for $D_{2}$ , $D_{1}$ and $D_{0}$ , using the unused states 110 and 111 as don't cares, and check whether the counter is self-starting.

Solution

Six states need $⌈ lo g_{2} 6 ⌉ = 3$ flip-flops. For a D flip-flop, the required input is just the next value of that bit.
State table: $000 \to 001$ , $001 \to 010$ , $010 \to 011$ , $011 \to 100$ , $100 \to 101$ , $101 \to 000$ ; 110 and 111 are don't cares.
$D_{0}$ : the next $Q_{0}$ is 1, 0, 1, 0, 1, 0 for present states 0 to 5, so $D_{0} = \overline{Q_{0}}$ .
$D_{1}$ : the next $Q_{1}$ is 1 only for present states 001 and 010 (minterms 1 and 2); 6 and 7 are don't cares. Grouping 010 with 110 gives $Q_{1} \overline{Q_{0}}$ . State 001 has no adjacent 1 or X, so it stays as $\overline{Q_{2}} \overline{Q_{1}} Q_{0}$ . Hence $D_{1} = Q_{1} \overline{Q_{0}} + \overline{Q_{2}} \overline{Q_{1}} Q_{0}$ .
$D_{2}$ : the next $Q_{2}$ is 1 for present states 011 and 100 (minterms 3 and 4); 6 and 7 are don't cares. Grouping 011 with 111 gives $Q_{1} Q_{0}$ , and 100 with 110 gives $Q_{2} \overline{Q_{0}}$ . Hence $D_{2} = Q_{1} Q_{0} + Q_{2} \overline{Q_{0}}$ .
Lock-out check. From 110: $D_{2} = 0 + 1 = 1$ , $D_{1} = 1 + 0 = 1$ , $D_{0} = 1$ , so the next state is 111. From 111: $D_{2} = 1$ , $D_{1} = 0$ , $D_{0} = 0$ , so the next state is 100, which is in the cycle.

Answer: $D_{0} = \overline{Q_{0}}$ , $D_{1} = Q_{1} \overline{Q_{0}} + \overline{Q_{2}} \overline{Q_{1}} Q_{0}$ , $D_{2} = Q_{1} Q_{0} + Q_{2} \overline{Q_{0}}$ . The counter is self-starting: $110 \to 111 \to 100$ .

The 555 timer. A timer can also be built around an RC circuit. The 555 timer IC contains two comparators, an SR flip-flop and a discharge transistor. With its control pin unused, the comparator thresholds are $V_{C C} /3$ and $2 V_{C C} /3$ . In astable mode (a free-running rectangular-wave oscillator) the timing capacitor $C$ charges through $R_{A} + R_{B}$ from $V_{C C} /3$ to $2 V_{C C} /3$ while the output is HIGH. It then discharges through $R_{B}$ alone, back to $V_{C C} /3$ , while the output is LOW. In monostable mode (a one-shot) a trigger pulse, which takes the trigger pin below $V_{C C} /3$ , sets the output HIGH. The output stays HIGH while $C$ charges through $R$ from 0 to $2 V_{C C} /3$ , and then returns LOW.

555 ASTABLE MULTIVIBRATOR

t_{H} = 0.693 (R_{A} + R_{B}) C, t_{L} = 0.693 R_{B} C, f = \frac{1}{t _{H} + t _{L}} \approx \frac{1.44}{( R _{A} + 2 R _{B} ) C}

$0.693 \approx ln 2$ : an RC charge toward $V_{C C}$ from $V_{C C} /3$ to $2 V_{C C} /3$ , or a discharge toward 0 from $2 V_{C C} /3$ to $V_{C C} /3$ , takes $R C ln 2$ . Duty cycle $= t_{H} / (t_{H} + t_{L}) = (R_{A} + R_{B}) / (R_{A} + 2 R_{B})$ , which is always above 50% in this basic circuit. Applies to the standard astable connection with the control pin unused.

555 MONOSTABLE PULSE WIDTH

t_{w} = R C ln 3 \approx 1.1 R C

$C$ charges from 0 toward $V_{C C}$ , and the output falls when $C$ reaches $2 V_{C C} /3$ . So $t_{w} = R C ln (V_{C C} / (V_{C C} - 2 V_{C C} /3)) = R C ln 3$ . Applies with the control pin unused.

Shift registers, ring counters and Johnson counters

A shift register is a chain of D flip-flops on a common clock, with each D input fed from the previous Q. The stored word moves one position per clock pulse, so an n-stage shift register also delays a serial bit stream by n clock periods, that is $n / f_{c l k}$ . Shift registers are classified by how data enter and leave:

Type	Data in	Data out	Clock pulses for an n-bit word
SISO	Serial	Serial	n to load; the first bit fed in reaches the output after n clocks, the last after $2 n - 1$
SIPO	Serial	Parallel	n, then all bits are read at once
PISO	Parallel	Serial	1 to load; the first bit is then at the output, and $n - 1$ more shifts bring out the rest
PIPO	Parallel	Parallel	1

Shifting an unsigned binary number one place toward the MSB, with a 0 entering at the LSB, multiplies it by 2, provided no 1 is shifted out. Shifting it one place toward the LSB, with a 0 entering at the MSB, divides it by 2 and discards the remainder. For a signed number in 2's complement, a shift toward the LSB must copy the sign bit into the MSB (an arithmetic shift). It then divides by 2 and rounds toward $- \infty$ : for example $1101 = - 3$ becomes $1110 = - 2$ . A universal (bidirectional) shift register has mode inputs that select hold, shift toward the MSB, shift toward the LSB, or parallel load.

Ring counter. The last flip-flop's Q feeds back to the first flip-flop's D, and the register is preset to a single 1 (for example 1000). The 1 circulates, giving n states with n flip-flops. No decoding is needed, because exactly one flip-flop is HIGH in each state.

Johnson counter (also called twisted-ring or switch-tail). The last flip-flop's $\overline{Q}$ feeds back to the first flip-flop's D. Starting from all zeros, the register fills with 1s from one end and then empties, giving 2n states with n flip-flops. Consecutive states differ in one bit, and each state can be decoded with a single 2-input gate. The 4-bit sequence, shifting from $Q_{A}$ toward $Q_{D}$ with $D_{A} = \overline{Q_{D}}$ , is:

Clock pulse	$Q_{A} Q_{B} Q_{C} Q_{D}$
0	0000
1	1000
2	1100
3	1110
4	1111
5	0111
6	0011
7	0001
8	0000 (the cycle repeats)

RING COUNTER WITH N FLIP-FLOPS (ONE CIRCULATING 1)

states = n, unused = 2^{n} - n, f_{Q} = \frac{f _{c l k}}{n}

Each output is HIGH for one clock period in every n (duty cycle $1/ n$ ). It is not self-starting without extra logic: from 0000, or from a state with two 1s, it never reaches the intended cycle.

JOHNSON COUNTER WITH N FLIP-FLOPS

states = 2 n, unused = 2^{n} - 2 n, f_{Q} = \frac{f _{c l k}}{2 n}

Each output is a square wave with a 50% duty cycle. It is not self-starting without extra logic. In a 3-bit Johnson counter, for example, the unused states 010 and 101 switch back and forth between each other forever.

Linear feedback shift register (LFSR). If the first stage's D input is the XOR of selected flip-flop outputs, the all-zeros state maps to itself, because an XOR of 0s is 0. The longest cycle possible with n flip-flops is therefore $2^{n} - 1$ states. Whether that maximum is reached depends on which outputs are fed back.

EXAM TIP

For N states, a binary counter needs $⌈ lo g_{2} N ⌉$ flip-flops, a Johnson counter needs $N /2$ (N even) and a ring counter needs N. Ring and Johnson counters use more flip-flops in exchange for simple decoding.

EXAM TIP

Count clock pulses carefully in SISO questions. In an n-bit register, the first bit fed in appears at the serial output after n clocks, and the last bit of an n-bit word after $2 n - 1$ clocks.

Finite state machines: Mealy, Moore and sequence detectors

A finite state machine (FSM) is a synchronous sequential circuit with a finite set of states. Flip-flops hold the present state. Combinational next-state logic works out, from the present state and the inputs, the state to be loaded at the next clock edge. Combinational output logic produces the outputs. An FSM is specified by a state diagram or an equivalent state table.

	Moore machine	Mealy machine
Output depends on	Present state only	Present state and present input
In the state diagram	Output written inside each state	Output written on each transition, as input/output
Output changes	Only after a clock edge	Also whenever the input changes (can glitch mid-period)
Timing of a detection	One clock later: after the edge that enters the detecting state	In the same clock period as the last input bit
States for the same task	Equal or more	Equal or fewer

MINIMUM STATES TO DETECT ONE BIT PATTERN OF LENGTH L

S_{Mealy} = L, S_{Moore} = L + 1

Valid for both overlapping and non-overlapping detection. The states record how many pattern bits have been matched (0 to $L - 1$ ), and a Moore machine needs one extra state whose output is 1. Minimum flip-flops = $⌈ lo g_{2} S ⌉$ .

Overlapping and non-overlapping detection. With overlapping detection, the end of one occurrence can also be the start of the next: in 1011011 the pattern 1011 is found twice, sharing the middle 1. With non-overlapping detection the machine starts again from scratch after each detection, so 1011 is found only once in that string. The two state diagrams differ only in where the detecting transition goes. For overlapping detection it goes to the state for the longest proper suffix of the pattern (shorter than the whole pattern) that is also a prefix of it. For non-overlapping detection it goes to the reset state.

Create one state for each number of pattern bits matched so far: $S_{0}$ (none), $S_{1}$ (first bit), and so on. A Mealy machine stops at $S_{L - 1}$ ; a Moore machine adds $S_{L}$ with output 1.
From each state, draw the transition for the correct next bit to the next state.
For the wrong bit, append it to the bits matched so far. Go to the state for the longest suffix of that string that is also a prefix of the pattern. This is not always $S_{0}$ .
For the detecting transition, go to the state for the longest proper suffix of the full pattern that is also a prefix of it (overlapping), or return to $S_{0}$ (non-overlapping). In a Moore machine the detecting transition enters $S_{L}$ , and the transitions out of $S_{L}$ are those of the state this rule names.
Check the diagram with a test string that contains overlaps.

Present state (bits matched)	$w = 0$ : next state / $Z$	$w = 1$ : next state / $Z$
$S_{0}$ (none)	$S_{0}$ / 0	$S_{1}$ / 0
$S_{1}$ (1)	$S_{2}$ / 0	$S_{1}$ / 0
$S_{2}$ (10)	$S_{0}$ / 0	$S_{3}$ / 0
$S_{3}$ (101)	$S_{2}$ / 0	$S_{1}$ / 1

The table is a Mealy detector for 1011 with overlapping, with input $w$ and output $Z$ . From $S_{3}$ with $w = 0$ , the bits received end in 1010. The longest suffix of 1010 that is also a prefix of 1011 is 10, so the machine goes to $S_{2}$ , not $S_{0}$ . On detection ( $w = 1$ in $S_{3}$ ), the longest proper suffix of 1011 that is also a prefix is 1, so the machine goes to $S_{1}$ ; a non-overlapping detector would go to $S_{0}$ instead. Trace for 1011011: $S_{0} \to S_{1} \to S_{2} \to S_{3} \to S_{1}$ ( $Z = 1$ ) $\to S_{2} \to S_{3} \to S_{1}$ ( $Z = 1$ ), which is two detections. The Moore version needs a fifth state $S_{4}$ with output 1, and therefore 3 flip-flops instead of 2.

State minimisation. Two states are equivalent if every input sequence produces the same output sequence from both. Put another way: for each input they give the same output and move to equivalent next states. Equivalent states can be merged into one, which may reduce the number of flip-flops. Quick test: two rows of a state table with identical outputs and identical next-state entries are equivalent. Delete one row, rename its state to the other everywhere, and look again, because the renaming can make more rows identical. Complete method (partitioning): group the states by their output rows. Split any group whose members go to states in different groups for some input. Repeat until no group splits. Each final group is one state of the minimal machine.

EXAM TIP

A wrong bit does not always send a detector back to $S_{0}$ . Always ask which tail of the bits received so far could still be the start of the pattern.

EXAM TIP

A Mealy output can rise or glitch in the middle of a clock period when the input changes. If the output must stay clean for a whole period, pass it through a flip-flop. It then behaves like a Moore output, one clock later.

EXAM TIP

'Minimum number of flip-flops' for a state machine means binary encoding of the minimised machine, $⌈ lo g_{2} S ⌉$ . One-hot encoding uses S flip-flops, with exactly one of them HIGH in each state.

Timing: setup, hold, clock-to-Q, maximum frequency and skew

Setup time $t_{s u}$ : the data input must be stable for at least $t_{s u}$ before the active clock edge.
Hold time $t_{h}$ : the data input must stay stable for at least $t_{h}$ after the active clock edge.
Clock-to-Q delay $t_{cq}$ (the flip-flop propagation delay $t_{p d}$ ): the time from the active edge until Q shows its new value. The maximum $t_{cq}$ is used in the setup check, and the minimum $t_{cq,min}$ (contamination delay) in the hold check.
Combinational delays: $t_{comb,max}$ is the delay of the longest path through the logic between two flip-flops, and $t_{comb,min}$ is the delay of the shortest path.
Violating setup or hold can make the flip-flop metastable: its output may sit between logic levels for an unpredictable time before settling.

Consider a launching flip-flop FF1 whose Q passes through combinational logic to the D input of a capturing flip-flop FF2. The setup check: data launched at one clock edge must reach FF2 at least $t_{s u}$ before the next edge. The hold check: data launched at an edge must not reach FF2 until at least $t_{h}$ after that same edge has arrived at FF2, or it would overwrite the value FF2 is capturing. The critical path is the register-to-register path with the largest $t_{cq} + t_{comb,max} + t_{s u}$ . With zero clock skew, that sum is the minimum clock period.

MAXIMUM CLOCK FREQUENCY (ZERO SKEW)

f_{max} = \frac{1}{t _{cq} + t _{comb,max} + t _{s u}}

Follows from the setup constraint $T \geq t_{cq} + t_{comb,max} + t_{s u}$ . Use the maximum clock-to-Q delay and the longest (critical) combinational path between any two flip-flops. Applies to synchronous counters, registers and FSMs.

HOLD CONSTRAINT (ZERO SKEW)

t_{cq,min} + t_{comb,min} \geq t_{h}

Uses the minimum (contamination) delays. The clock period does not appear, so slowing the clock cannot fix a hold violation. It is fixed by adding delay to the short path, or by using flip-flops with a shorter hold time or a longer minimum clock-to-Q delay.

Clock skew is the difference between the times at which the same clock edge arrives at different flip-flops. Sign convention used here: $t_{skew} = t_{capture} - t_{launch}$ , the arrival time of the clock at FF2 minus its arrival time at FF1. Skew is positive when the capturing flip-flop receives the edge later.

SETUP CONSTRAINT WITH CLOCK SKEW

T \geq t_{cq} + t_{comb,max} + t_{s u} - t_{skew}

Positive skew gives the data extra time and relaxes setup; negative skew tightens it.

HOLD CONSTRAINT WITH CLOCK SKEW

t_{cq,min} + t_{comb,min} \geq t_{h} + t_{skew}

Positive skew makes hold harder to meet; negative skew makes it easier. Skew therefore trades setup margin against hold margin.

WORKED EXAMPLE

Positive-edge-triggered flip-flop FF1 drives FF2 through combinational logic, and this is the only register-to-register path. For both flip-flops, $t_{cq}$ is 1.0 ns (minimum) to 2.0 ns (maximum), $t_{s u} = 1.5$ ns and $t_{h} = 1.0$ ns. The logic has $t_{comb,max} = 6.5$ ns and $t_{comb,min} = 0.5$ ns. (a) Find $f_{max}$ with zero skew, and check hold. (b) Repeat if the clock reaches FF2 1.0 ns later than FF1.

Solution

(a) Setup: $T_{m i n} = 2.0 + 6.5 + 1.5 = 10.0$ ns, so $f_{max} = 1/ (10 ns) = 100$ MHz.
(a) Hold: $t_{cq,min} + t_{comb,min} = 1.0 + 0.5 = 1.5$ ns $\geq t_{h} = 1.0$ ns, so hold is met with a 0.5 ns margin.
(b) $t_{skew} = + 1.0$ ns. Setup: $T_{m i n} = 10.0 - 1.0 = 9.0$ ns, so setup alone would allow $f = 111.1$ MHz.
(b) Hold: we need $1.5 \geq t_{h} + t_{skew} = 1.0 + 1.0 = 2.0$ ns. This fails by 0.5 ns, and no clock frequency fixes it. The shortest path must be lengthened by at least 0.5 ns (or the skew reduced by at least 0.5 ns), and the longest path must still meet setup afterwards.

Answer: (a) $f_{max} = 100$ MHz, and hold is met with a 0.5 ns margin. (b) Setup allows 111.1 MHz, but hold is violated by 0.5 ns, so the circuit as drawn fails at every clock frequency.

EXAM TIP

An n-bit ripple counter needs $T \geq n t_{p d}$ , because the delays add along the chain. A synchronous counter needs only $T \geq t_{cq} + t_{comb,max} + t_{s u}$ : one flip-flop delay however many bits it has, although the gate path may grow with n.

EXAM TIP

When Q is wired straight to D with no logic between stages, as in a shift register, $t_{comb} = 0$ . Setup then needs $T \geq t_{cq} + t_{s u} - t_{skew}$ , and hold needs $t_{cq,min} \geq t_{h} + t_{skew}$ . Set $t_{skew} = 0$ when there is no skew.

EXAM TIP

In a counter or FSM, a flip-flop whose output returns through logic to its own input is also a register-to-register path, with zero skew. Include such paths when searching for the critical path.

EXAM TIP

If a question gives only one propagation delay for a flip-flop, use it as both the maximum and the minimum clock-to-Q delay.

PREVIOUS-YEAR QUESTIONS

30 questions from the EC, EE and IN papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE ECE 2026 · GATE ECE 2025 · GATE ECE 2024 · GATE ECE 2023 · GATE ECE 2022 · GATE ECE 2020 · GATE ECE 2018 · GATE EE 2024 · GATE EE 2023 · GATE EE 2022 · GATE EE 2020 · GATE EE 2018 · GATE IN 2026 · GATE IN 2025 · GATE IN 2024 · GATE IN 2023 · GATE IN 2022 · GATE IN 2020 · GATE IN 2018

GATE 2026 EC Q.27

GATE 2026 · ECQ.27 · 1 mark · MSQ

A binary ripple counter is designed to count $(0)_{10}$ to $(64)_{10}$ .

Which of the following is/are the number of flip-flops required to design the counter?

(A)
6
(B)
7
(C)
4
(D)
5

Answer and solution

GATE 2026 EC Q.27: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 EC Q.27: answer and solution

GATE 2026 EC Q.35

GATE 2026 · ECQ.35 · 1 mark · NAT

The negative edge triggered JK flip-flop in the Figure has J and K inputs tied to Logic High and a square wave of 10 cycles/second is applied to its clock (C) input.

The frequency of the output Q (in cycles/second) is ____. (rounded off to two decimal places)

GATE 2026 EC question 35: A single JK flip-flop drawn as a rectangle. — Figure from the GATE 2026 EC paper. It is part of the question.

Answer and solution

GATE 2026 EC Q.35: answer and solution

GATE 2026 EC Q.49

GATE 2026 · ECQ.49 · 2 marks · MCQ

A shift-left Shift Register (SR) and a D flip-flop are connected to a synchronized clock as shown in the Figure. Assume that the SR and D flip-flops are initially cleared and the XOR gate has no propagation delay.

Which of the following options gives the correct binary representation $(b_{7} b_{6} b_{5} b_{4} b_{3} b_{2} b_{1} b_{0})$ of the content of the shift register immediately after the $5^{th}$ clock transition (positive edge)?

GATE 2026 EC question 49: An 8-bit shift register labelled 'SR (Shift Left)' with cells b7 b6 b5 b4 b3 b2 b1 b0 from left to right. — Figure from the GATE 2026 EC paper. It is part of the question.

(A)
$(00011111)_{2}$
(B)
$(10111111)_{2}$
(C)
$(00111111)_{2}$
(D)
$(11000011)_{2}$

Answer and solution

GATE 2026 EC Q.49: answer and solution

GATE 2026 IN Q.47

GATE 2026 · INQ.47 · 2 marks · MCQ

The initial state of $Q_{3} Q_{2} Q_{1} Q_{0}$ in the digital circuit shown below is 1011.

The new value of $Q_{3} Q_{2} Q_{1} Q_{0}$ after two rising edges of the clock (CLK) will be ______.

GATE 2026 IN question 47: Four positive-edge-triggered D flip-flops drawn left to right: FF3 (D_3, Q_3), FF2 (D_2, Q_2), FF1 (D_1, Q_1), FF0 (D_0… — Figure from the GATE 2026 IN paper. It is part of the question.

(A)
1101
(B)
0101
(C)
1010
(D)
1011

Answer and solution

GATE 2026 IN Q.47: answer and solution

GATE 2025 EC Q.45

GATE 2025 · ECQ.45 · 2 marks · MCQ

A positive-edge-triggered sequential circuit is shown below. There are no timing violations in the circuit. Input $P 0$ is set to logic '0' and $P 1$ is set to logic '1' at all times. The timing diagram of the inputs $S E L$ and $S$ are also shown below.

The sequence of output $Y$ from time $T_{0}$ to $T_{3}$ is ________.

GATE 2025 EC question 45: Circuit: a 2:1 MUX (MUX1) has input 1 = S, input 0 = P0 and select line SEL. — Figure from the GATE 2025 EC paper. It is part of the question.

(A)
1011
(B)
0100
(C)
0010
(D)
1101

Answer and solution

GATE 2025 EC Q.45: answer and solution

GATE 2025 EC Q.62

GATE 2025 · ECQ.62 · 2 marks · NAT

In the circuit shown below, the AND gate has a propagation delay of 1 ns. The edge-triggered flip-flops have a set-up time of 2 ns, a hold-time of 0 ns, and a clock-to-Q delay of 2 ns.

The maximum clock frequency (in MHz, rounded off to the nearest integer) such that there are no setup violations is ________.

GATE 2025 EC question 62: Two edge-triggered D flip-flops, FF1 (left) and FF2 (right), each drawn with outputs Q and Q and a clock input marked with… — Figure from the GATE 2025 EC paper. It is part of the question.

Answer and solution

GATE 2025 EC Q.62: answer and solution

GATE 2025 IN Q.40

GATE 2025 · INQ.40 · 2 marks · MCQ

The clock frequency of the digital circuit shown in the figure is 12 MHz. The frequencies of the output (F) corresponding to Control = 0 and Control = 1, respectively, are

GATE 2025 IN question 40: Two positive-edge-triggered D flip-flops, FF1 (left) and FF2 (right), share one clock line labelled 'clock'… — Figure from the GATE 2025 IN paper. It is part of the question.

(A)
4 MHz and 6 MHz
(B)
6 MHz and 4 MHz
(C)
3 MHz and 4 MHz
(D)
3 MHz and 6 MHz

Answer and solution

GATE 2025 IN Q.40: answer and solution

GATE 2024 EC Q.42

GATE 2024 · ECQ.42 · 2 marks · MCQ

The sequence of states $(Q_{1} Q_{0})$ of the given synchronous sequential circuit is ________.

GATE 2024 EC question 42: Two positive-edge-triggered T flip-flops share a common clock line CLK (the clock inputs are drawn with a triangle and no… — Figure from the GATE 2024 EC paper. It is part of the question.

(A)
00 → 10 → 11 → 00
(B)
11 → 00 → 10 → 01 → 00
(C)
01 → 10 → 11 → 00 → 01
(D)
00 → 01 → 10 → 00

Answer and solution

GATE 2024 EC Q.42: answer and solution

GATE 2024 EE Q.25

GATE 2024 · EEQ.25 · 1 mark · MCQ

In the circuit, the present value of $Z$ is 1. Neglecting the delay in the combinatorial circuit, the values of $S$ and $Z$ , respectively, after the application of the clock will be

GATE 2024 EE question 25: A combinatorial circuit block labelled S = X Y Z has three inputs: Z (top, fed back), X = 1 (middle) and Y = 0 (bottom). — Figure from the GATE 2024 EE paper. It is part of the question.

(A)
$S = 0, Z = 0$
(B)
$S = 0, Z = 1$
(C)
$S = 1, Z = 0$
(D)
$S = 1, Z = 1$

Answer and solution

GATE 2024 EE Q.25: answer and solution

GATE 2024 IN Q.42

GATE 2024 · INQ.42 · 2 marks · MCQ

In the figure shown, the positive edge triggered D flip-flops are initially reset to Q = 0. The logic gates and the multiplexers have no propagation delay. After reset, a train of clock pulses (CLK) are applied. The logic-states of the inputs DIN, S and the clock pulses are also shown in the figure. Assuming no timing violations, the sequence of output Y from the 3rd clock to the 5th clock, $Y_{3} Y_{4} Y_{5}$ is

GATE 2024 IN question 42: Circuit: three identical stages, each a 2:1 MUX (inputs labelled 0 on top and 1 below, select line S common to all three)… — Figure from the GATE 2024 IN paper. It is part of the question.

(A)
001
(B)
010
(C)
000
(D)
011

Answer and solution

GATE 2024 IN Q.42: answer and solution

GATE 2023 EC Q.24

GATE 2023 · ECQ.24 · 1 mark · MCQ

The synchronous sequential circuit shown below works at a clock frequency of 1 GHz. The throughput, in Mbits/s, and the latency, in ns, respectively, are

GATE 2023 EC question 24: Three positive-edge-triggered D flip-flops connected in cascade (a 3-stage serial-in serial-out shift register). — Figure from the GATE 2023 EC paper. It is part of the question.

(A)
1000, 3
(B)
333.33, 1
(C)
2000, 3
(D)
333.33, 3

Answer and solution

GATE 2023 EC Q.24: answer and solution

GATE 2023 EC Q.34

GATE 2023 · ECQ.34 · 1 mark · NAT

For the circuit shown below, the propagation delay of each NAND gate is 1 ns. The critical path delay, in ns, is ________ (rounded off to the nearest integer).

GATE 2023 EC question 34: Two cross-coupled 2-input NAND gates (a NAND SR latch). — Figure from the GATE 2023 EC paper. It is part of the question.

Answer and solution

GATE 2023 EC Q.34: answer and solution

GATE 2023 EC Q.63

GATE 2023 · ECQ.63 · 2 marks · NAT

In a given sequential circuit, initial states are $Q_{1} = 1$ and $Q_{2} = 0$ . For a clock frequency of $1 MHz$ , the frequency of signal $Q_{2}$ in kHz, is ________ (rounded off to the nearest integer).

GATE 2023 EC question 63: Two positive-edge-triggered D flip-flops (clock input shown as a plain triangle with no bubble) share one clock, labelled… — Figure from the GATE 2023 EC paper. It is part of the question.

Answer and solution

GATE 2023 EC Q.63: answer and solution

GATE 2023 EE Q.56

GATE 2023 · EEQ.56 · 2 marks · NAT

Neglecting the delays due to the logic gates in the circuit shown in figure, the decimal equivalent of the binary sequence [ABCD] of initial logic states, which will not change with clock, is ________.

GATE 2023 EE question 56: Two D flip-flops, FF1 (left) and FF2 (right), both driven by a common CLK line. — Figure from the GATE 2023 EE paper. It is part of the question.

Answer and solution

GATE 2023 EE Q.56: answer and solution

GATE 2023 IN Q.16

GATE 2023 · INQ.16 · 1 mark · MCQ

The table shows the present state Q(t), next state Q(t+1), and the control input in a flip-flop. Identify the flip-flop.

| Q (t) | Q (t+1) | Input |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

GATE 2023 IN question 16: A table with three columns headed Q (t), Q (t+1) and Input, and four rows: (Q(t), Q(t+1), Input) = (0, 0, 0), (0, 1, 1)… — Figure from the GATE 2023 IN paper. It is part of the question.

(A)
T flip-flop
(B)
D flip-flop
(C)
SR flip-flop
(D)
JK flip-flop

Answer and solution

GATE 2023 IN Q.16: answer and solution

GATE 2023 IN Q.41

GATE 2023 · INQ.41 · 2 marks · MCQ

For the given digital circuit, A = B = 1. Assume that AND, OR, and NOT gates have propagation delays of 10 ns, 10 ns, and 5 ns respectively. All lines have zero propagation delay. Given that C = 1 when the circuit is turned on, the frequency of steady-state oscillation of the output Y is ______.

GATE 2023 IN question 41: Combinational loop. — Figure from the GATE 2023 IN paper. It is part of the question.

(A)
20 MHz
(B)
15 MHz
(C)
40 MHz
(D)
50 MHz

Answer and solution

GATE 2023 IN Q.41: answer and solution

GATE 2023 IN Q.42

GATE 2023 · INQ.42 · 2 marks · MCQ

In the circuit shown, the initial binary content of shift register A is 1101 and that of shift register B is 1010. The shift registers are positive-edge triggered, and the gates have no delay.

When the shift control is high, what will be the binary content of the shift registers A and B after four clock pulses?

GATE 2023 IN question 42: Two 4-bit shift registers in cascade, both shifting to the right. — Figure from the GATE 2023 IN paper. It is part of the question.

(A)
A = 1101, B = 1101
(B)
A = 1110, B = 1001
(C)
A = 0101, B = 1101
(D)
A = 1010, B = 1111

Answer and solution

GATE 2023 IN Q.42: answer and solution

GATE 2022 EC Q.43

GATE 2022 · ECQ.43 · 2 marks · MCQ

For the circuit shown, the clock frequency is $f_{0}$ and the duty cycle is 25%. For the signal at the Q output of the Flip-Flop, ________.

GATE 2022 EC question 43: A block labelled '2 Bit binary Counter' has two outputs on its right side: LSB (upper) and MSB (lower). — Figure from the GATE 2022 EC paper. It is part of the question.

(A)
frequency is $f_{0} /4$ and duty cycle is 50%
(B)
frequency is $f_{0} /4$ and duty cycle is 25%
(C)
frequency is $f_{0} /2$ and duty cycle is 50%
(D)
frequency is $f_{0}$ and duty cycle is 25%

Answer and solution

GATE 2022 EC Q.43: answer and solution

GATE 2022 EE Q.26

GATE 2022 · EEQ.26 · 1 mark · NAT

A MOD 2 and a MOD 5 up-counter when cascaded together results in a MOD ______ counter. (in integer)

Answer and solution

GATE 2022 EE Q.26: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 EE Q.26: answer and solution

GATE 2022 EE Q.29

GATE 2022 · EEQ.29 · 1 mark · NAT

The maximum clock frequency in MHz of a 4-stage ripple counter, utilizing flip-flops, with each flip-flop having a propagation delay of 20 ns, is ________. (round off to one decimal place)

Answer and solution

GATE 2022 EE Q.29: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 EE Q.29: answer and solution

GATE 2022 IN Q.46

GATE 2022 · INQ.46 · 2 marks · MCQ

The digital circuit shown ________

GATE 2022 IN question 46: Three positive-edge-triggered D flip-flops (clock inputs drawn with a triangle, no bubble) share one common clock line CLK. — Figure from the GATE 2022 IN paper. It is part of the question.

(A)
is a divide-by-5 counter
(B)
is a divide-by-7 counter
(C)
is a divide-by-8 counter
(D)
does not function as a counter due to disjoint cycles of states

Answer and solution

GATE 2022 IN Q.46: answer and solution

GATE 2020 EC Q.39

GATE 2020 · ECQ.39 · 2 marks · MCQ

The state diagram of a sequence detector is shown below. State $S_{0}$ is the initial state of the sequence detector. If the output is 1, then

GATE 2020 EC question 39: Mealy state diagram with five states S0, S1, S2, S3, S4. — Figure from the GATE 2020 EC paper. It is part of the question.

(A)
the sequence 01010 is detected.
(B)
the sequence 01011 is detected.
(C)
the sequence 01110 is detected.
(D)
the sequence 01001 is detected.

Answer and solution

GATE 2020 EC Q.39: answer and solution

GATE 2020 EC Q.50

GATE 2020 · ECQ.50 · 2 marks · NAT

For the components in the sequential circuit shown below, $t_{p d}$ is the propagation delay, $t_{se t u p}$ is the setup time, and $t_{h o l d}$ is the hold time. The maximum clock frequency (rounded off to the nearest integer), at which the given circuit can operate reliably, is ________ MHz.

GATE 2020 EC question 50: Two positive-edge-triggered flip-flops share one clock (Clk, drawn as a square wave on the left, wired to the clock input… — Figure from the GATE 2020 EC paper. It is part of the question.

Answer and solution

GATE 2020 EC Q.50: answer and solution

GATE 2020 EE Q.15

GATE 2020 · EEQ.15 · 1 mark · MCQ

A sequence detector is designed to detect precisely 3 digital inputs, with overlapping sequences detectable. For the sequence (1,0,1) and input data (1,1,0,1,0,0,1,1,0,1,0,1,1,0), what is the output of this detector?

(A)
1,1,0,0,0,0,1,1,0,1,0,0
(B)
0,1,0,0,0,0,0,1,0,1,0,0
(C)
0,1,0,0,0,0,0,1,0,1,1,0
(D)
0,1,0,0,0,0,0,0,1,0,0,0

Answer and solution

GATE 2020 EE Q.15: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 EE Q.15: answer and solution

GATE 2020 IN Q.40

GATE 2020 · INQ.40 · 2 marks · NAT

Two T-flip flops are interconnected as shown in the figure. The present state of the flip flops are: A = 1, B = 1. The input x is given as 1, 0, 1 in the next three clock cycles. The decimal equivalent of $(A B y)_{2}$ with A being the MSB and y being the LSB, after the 3rd clock cycle is ____

GATE 2020 IN question 40: Two T flip-flops, A (top) and B (bottom), share a common clock line labelled clk. — Figure from the GATE 2020 IN paper. It is part of the question.

Answer and solution

GATE 2020 IN Q.40: answer and solution

GATE 2018 EC Q.19

GATE 2018 · ECQ.19 · 1 mark · NAT

A traffic signal cycles from GREEN to YELLOW, YELLOW to RED and RED to GREEN. In each cycle, GREEN is turned on for 70 seconds, YELLOW is turned on for 5 seconds and the RED is turned on for 75 seconds. This traffic light has to be implemented using a finite state machine (FSM). The only input to this FSM is a clock of 5 second period. The minimum number of flip-flops required to implement this FSM is ________.

Answer and solution

GATE 2018 EC Q.19: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 EC Q.19: answer and solution

GATE 2018 EC Q.46

GATE 2018 · ECQ.46 · 2 marks · NAT

In the circuit shown below, a positive edge-triggered D Flip-Flop is used for sampling input data $D_{in}$ using clock $C K$ . The XOR gate outputs 3.3 volts for logic HIGH and 0 volts for logic LOW levels. The data bit and clock periods are equal and the value of $Δ T / T_{C K} = 0.15$ , where the parameters $Δ T$ and $T_{C K}$ are shown in the figure. Assume that the Flip-Flop and the XOR gate are ideal.

If the probability of input data bit ( $D_{in}$ ) transition in each clock period is 0.3, the average value (in volts, accurate to two decimal places) of the voltage at node $X$ , is ______.

GATE 2018 EC question 46: Circuit (left): input terminal D_in feeds the D input of a D Flip-Flop; — Figure from the GATE 2018 EC paper. It is part of the question.

Answer and solution

GATE 2018 EC Q.46: answer and solution

GATE 2018 EE Q.36

GATE 2018 · EEQ.36 · 2 marks · MCQ

Which one of the following statements is true about the digital circuit shown in the figure

GATE 2018 EE question 36: Three D flip-flops sit side by side. — Figure from the GATE 2018 EE paper. It is part of the question.

(A)
It can be used for dividing the input frequency by 3.
(B)
It can be used for dividing the input frequency by 5.
(C)
It can be used for dividing the input frequency by 7.
(D)
It cannot be reliably used as a frequency divider due to disjoint internal cycles.

Answer and solution

GATE 2018 EE Q.36: answer and solution

GATE 2018 IN Q.17

GATE 2018 · INQ.17 · 1 mark · NAT

For the 3-bit binary counter shown in the figure, the output increments at every positive transition in the clock (CLK). Assume ideal diodes and the starting state of the counter as 000. If output high is 1 V and output low is 0 V, the current $I$ (in mA) flowing through the 50 $Ω$ resistor during the 5 $^{th}$ clock cycle is (up to one decimal place) ______.

GATE 2018 IN question 17: A block labelled '3-bit binary counter' has a clock input CLK on its lower left, marked with the edge-trigger triangle. — Figure from the GATE 2018 IN paper. It is part of the question.

Answer and solution

GATE 2018 IN Q.17: answer and solution

GATE 2018 IN Q.44

GATE 2018 · INQ.44 · 2 marks · MCQ

A 2-bit synchronous counter using two $J$ - $K$ flip flops is shown. The expressions for the inputs to the $J$ - $K$ flip flops are also shown in the figure. The output sequence of the counter starting from $Q_{1} Q_{2} = 00$ is

GATE 2018 IN question 44: Two J-K flip-flops (each box labelled J, K, Q, Q-bar, SET, CLR) share one Clock line, so the counter is synchronous. — Figure from the GATE 2018 IN paper. It is part of the question.

(A)
$00 \to 11 \to 10 \to 01 \to 00 \dots$
(B)
$00 \to 01 \to 10 \to 11 \to 00 \dots$
(C)
$00 \to 01 \to 11 \to 10 \to 00 \dots$
(D)
$00 \to 10 \to 11 \to 01 \to 00 \dots$

Answer and solution

GATE 2018 IN Q.44: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · NAT

A 4-bit asynchronous (ripple) up counter is built from flip-flops whose clock-to-Q propagation delay is 12 ns each. Ignoring any decoding delay, the maximum clock frequency, in MHz, at which the counter always settles to the correct count before the next clock edge is ______ (round to two decimal places).

Answer and solution

Answer: $20.83$ (accepted range $\pm 0.05$ )

In a ripple counter each flip-flop is clocked by the one before it. In the worst case (for example $0111 \to 1000$ ) the change passes through all 4 stages.
Worst-case settling time $= 4 \times 12 = 48$ ns.
$f_{max} = 1/ (48 ns) = 20.83$ MHz.

PRACTICE 21 mark · MCQ

A positive-edge-triggered D flip-flop is to be made to behave exactly like a JK flip-flop by placing combinational logic in front of its D input. With $Q$ the present output and an overline denoting the complement, the required input is

(A)
$D = J \overline{Q} + \overline{K} Q$
(B)
$D = J Q + \overline{K} \overline{Q}$
(C)
$D = J \overline{Q} + K Q$
(D)
$D = J \oplus K$

Answer and solution

Answer: (A)

A D flip-flop's next state equals D, so D must equal the JK flip-flop's next state.
The JK characteristic equation is $Q_{n + 1} = J \overline{Q_{n}} + \overline{K} Q_{n}$ , hence $D = J \overline{Q} + \overline{K} Q$ .
Option C is the input that turns a T flip-flop, not a D flip-flop, into a JK. Option D gives $D = 0$ for $J = K = 1$ , which is wrong whenever $Q = 0$ .

PRACTICE 32 marks · MSQ

Which of the following statements are correct?

(A)
A 4-bit Johnson (twisted-ring) counter cycles through 8 distinct states.
(B)
A 4-bit ring counter preset to 1000 leaves 12 of the 16 possible states unused.
(C)
The minimum number of states in a Moore machine that detects the pattern 1101, with overlapping allowed, is 4.
(D)
In a Mealy machine, the output can change between two clock edges if the input changes.

Answer and solution

Answer: (A), (B), (D)

A: a Johnson counter with n flip-flops has 2n states, and $2 \times 4 = 8$ . True.
B: a ring counter with n flip-flops uses n states, so $2^{4} - 4 = 12$ states are unused. True.
C: a Moore detector for a pattern of length $L = 4$ needs $L + 1 = 5$ states: 0, 1, 2 or 3 bits matched, plus a detecting state whose output is 1. No two of these are equivalent, so the minimum is 5, not 4. False.
D: a Mealy output is a combinational function of the present input, so it changes as soon as the input changes, even between clock edges. True.

PRACTICE 42 marks · NAT

In a synchronous circuit, positive-edge-triggered flip-flop FF1 drives flip-flop FF2 through combinational logic. Both flip-flops have a clock-to-Q delay of 2 ns (minimum) to 3 ns (maximum), a setup time of 2 ns and a hold time of 1 ns. The logic has a longest-path delay of 9 ns and a shortest-path delay of 4 ns. The clock edge reaches FF2 1 ns earlier than it reaches FF1. Consider only the path from FF1 to FF2. The maximum clock frequency, in MHz, is ______ (round to two decimal places).

Answer and solution

Answer: $66.67$ (accepted range $\pm 0.1$ )

Skew: $t_{skew} = t_{capture} - t_{launch} = - 1$ ns, because the capturing flip-flop is clocked earlier.
Setup: $T \geq t_{cq} + t_{comb,max} + t_{s u} - t_{skew} = 3 + 9 + 2 - (- 1) = 15$ ns.
Hold: $t_{cq,min} + t_{comb,min} = 2 + 4 = 6$ ns $\geq t_{h} + t_{skew} = 1 + (- 1) = 0$ ns. Hold is met, so setup alone limits the frequency.
$f_{max} = 1/ (15 ns) = 66.67$ MHz.

PRACTICE 52 marks · MCQ

Three positive-edge-triggered D flip-flops form a synchronous circuit with state $Q_{2} Q_{1} Q_{0}$ (MSB first), where $D_{2} = Q_{1}$ , $D_{1} = Q_{0}$ and $D_{0} = \overline{Q_{2} + Q_{1}}$ . The circuit starts in 000. Which statement is correct?

(A)
It is a mod-6 counter and is not self-starting.
(B)
It is a mod-5 counter, and every unused state enters the counting cycle (self-starting).
(C)
It is a mod-5 counter, but the unused states 010 and 101 form a separate closed loop (lock-out).
(D)
It is a mod-8 counter.

Answer and solution

Answer: (B)

From 000: $D_{2} = 0$ , $D_{1} = 0$ , $D_{0} = \overline{0 + 0} = 1$ , so the next state is 001. From 001 the next state is 011. From 011: $D_{0} = \overline{0 + 1} = 0$ , giving 110. From 110 the next state is 100, and from 100 it is 000.
The cycle $000 \to 001 \to 011 \to 110 \to 100 \to 000$ has 5 states, so the circuit is a mod-5 counter.
Unused states: $010 \to 100$ ; $101 \to 010 \to 100$ ; $111 \to 110$ . All of them reach the cycle, so the counter is self-starting.
Answer B. For comparison, a 3-bit Johnson counter ( $D_{0} = \overline{Q_{2}}$ ) is mod-6 with the lock-out loop $010 \leftrightarrow 101$ . The NOR feedback here removes one state and also breaks that loop.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE EC

Sequential Circuits: Latches and flip-flops, counters, shift-registers, finite state machines, propagation delay, setup and hold time, critical path delay

GATE EE

sequential logic circuits

GATE IN

sequential circuits, finite state machines, flipflops, shift registers, timers and counters

Preparing in Kolkata? IAE Academy's course for GATE ECE, GATE EE or GATE IN.