"Sequential Circuits" — Practice

Question 1

A JK flip-flop has J = K = 1 and is clocked at 200 MHz. What is the output frequency?

Accepted Answer

B

Question 2

How many flip-flops are required to build a modulo-60 counter?

Accepted Answer

B

Question 3

In which machine does the output depend on both the present state and the present input?

Accepted Answer

A

Question 4

A synchronous design uses flip-flops with clock-to-Q delay 1.5 ns, setup time 0.8 ns and hold time 0.6 ns. The combinational logic between stages has a maximum delay of 4.2 ns and a minimum delay of 0.3 ns. Find the maximum clock frequency and check the hold constraint.

Accepted Answer

Apply the setup inequality, which uses the maximum combinational delay because slow data must still arrive before the next edge.

T_clk must be at least 1.5 + 4.2 + 0.8 = 6.5 ns.

The maximum frequency is 1 divided by 6.5 ns, which is approximately 153.8 MHz.

Now check hold, which uses the minimum combinational delay because the danger is data arriving too early and corrupting the value being captured.

T_cq plus minimum combinational delay is 1.5 + 0.3 = 1.8 ns, which must be at least the hold time of 0.6 ns.

Since 1.8 exceeds 0.6, the hold constraint is satisfied with margin.

Two points are worth extracting. The two constraints deliberately use opposite extremes of the combinational delay. And had the hold check failed, reducing the clock frequency would not have helped, because the clock period appears nowhere in the hold inequality; the only fix would be to add delay to the fast path.

Question 5

Convert a JK flip-flop into a D flip-flop, deriving the required input logic.

Accepted Answer

The target behaviour is Q-next equals D. The available device obeys Q-next equals J times not-Q plus not-K times Q.

Use the excitation table to find what J and K must be for each required transition.

When Q = 0 and D = 1, the transition is 0 to 1, which JK achieves with J = 1 and K = don't care.
When Q = 0 and D = 0, the transition is 0 to 0, which needs J = 0 and K = don't care.
When Q = 1 and D = 1, the transition is 1 to 1, which needs J = don't care and K = 0.
When Q = 1 and D = 0, the transition is 1 to 0, which needs J = don't care and K = 1.

Read J across the four rows: 1, 0, don't care, don't care. Using the don't cares to simplify gives J = D.

Read K across the four rows: don't care, don't care, 0, 1. Using the don't cares gives K = not-D.

So the conversion is J = D and K = not-D, requiring a single inverter.

Verify: with D = 1 the inputs are J = 1, K = 0, which sets. With D = 0 they are J = 0, K = 1, which resets. In both cases Q-next equals D, as required.

Question 6

A 4-bit ripple counter uses flip-flops with a propagation delay of 8 ns each. What is the maximum frequency at which it can be clocked without transient errors reaching the output?

Accepted Answer

In a ripple counter each stage is clocked by the previous stage's output, so the delays accumulate rather than overlapping.

The worst case is a transition where every stage changes, such as 0111 to 1000. The first flip-flop toggles after 8 ns, which then clocks the second, which toggles 8 ns later, and so on.

With 4 stages the last one settles after 4 times 8 = 32 ns.

For the counter to present a stable value before the next clock edge, the clock period must be at least 32 ns.

The maximum frequency is 1 divided by 32 ns, which is 31.25 MHz.

Compare this with a synchronous counter built from the same flip-flops. There every stage is clocked simultaneously, so the settling time is one flip-flop delay of 8 ns plus the delay of the combinational logic feeding the inputs, giving a far higher frequency independent of the counter width.

This accumulation is also why a ripple counter shows transient wrong values during the 32 ns, and therefore why it cannot drive a decoder without producing spurious output pulses.

Question 7

A machine has states S0 to S4 with outputs 0, 0, 1, 0, 1 respectively. On input 0 the next states are S1, S3, S0, S1, S0; on input 1 they are S2, S4, S2, S4, S2. Reduce the machine.

Accepted Answer

Begin with a partition by output.

Group P1 = {S0, S1, S3} with output 0, and group P2 = {S2, S4} with output 1.

First refinement pass. Examine P1 under input 0: S0 goes to S1 which is in P1, S1 goes to S3 which is in P1, S3 goes to S1 which is in P1. All agree.

Examine P1 under input 1: S0 goes to S2 in P2, S1 goes to S4 in P2, S3 goes to S4 in P2. All agree.

So P1 does not split.

Examine P2 under input 0: S2 goes to S0 in P1, S4 goes to S0 in P1. Agree.

Examine P2 under input 1: S2 goes to S2 in P2, S4 goes to S2 in P2. Agree.

So P2 does not split either.

A complete pass has produced no split, which is the termination condition, so the partition is final.

S0, S1 and S3 are equivalent and merge into one state; S2 and S4 are equivalent and merge into another. The machine reduces from 5 states to 2.

That reduction saves genuine hardware: 5 states needed 3 flip-flops while 2 states need only 1. Note that had the pass been stopped after examining input 0 alone, the same partition would have resulted here, but only by coincidence; the rule is to complete a full pass over every input before concluding.

Question 8

Design a sequence detector for 1101 with overlap allowed. How many states does the Mealy version need, and how many does the Moore version need? Explain the difference.

Accepted Answer

For the Mealy version, states track how much of the pattern has been matched so far.

S0: nothing matched. S1: 1 matched. S2: 11 matched. S3: 110 matched.

From S3, an input of 1 completes the pattern 1101, so the output is asserted on that transition. Because overlap is allowed, the trailing 1 can begin a new match, so the machine moves to S1 rather than S0.

Four states suffice for the Mealy version, because the output is attached to the transition out of S3 rather than to any state.

For the Moore version, the output depends only on the state, so there must be a distinct state meaning 'pattern just completed' that carries output 1.

Add S4 with output 1. The transition from S3 on input 1 now goes to S4 instead of directly to S1, and S4 behaves like S1 on all subsequent inputs, since the trailing 1 is also the start of a possible new match.

Five states are needed for the Moore version.

The difference is structural rather than incidental. A Mealy output can be produced during the same cycle as the completing input, while a Moore output must wait until the machine has entered a state, so it appears one clock cycle later. The trade is latency against a registered, glitch-free output.

Question 9

Two flip-flops are connected directly with no combinational logic between them. The second flip-flop's clock arrives 0.4 ns later than the first's. Flip-flop parameters are clock-to-Q 1.0 ns and hold time 1.6 ns. Does the path meet its hold constraint, and what would happen without the skew?

Accepted Answer

With no combinational logic, data launched by the first flip-flop arrives at the second after only the clock-to-Q delay of 1.0 ns.

Without skew, the hold requirement is that data must remain stable for 1.6 ns after the clock edge, but new data arrives after just 1.0 ns. Since 1.0 is less than 1.6, the constraint is violated by 0.6 ns and the second flip-flop may capture the new value instead of the old one.

Now include the skew. The second flip-flop's clock edge arrives 0.4 ns later than the first's, so its hold window also shifts 0.4 ns later relative to the launching edge.

Effectively the available time becomes 1.0 ns of data delay against a hold requirement measured from an edge that is 0.4 ns later, so the requirement becomes 1.6 minus 0.4 = 1.2 ns against 1.0 ns of delay.

The path still fails, now by 0.2 ns.

Two conclusions follow. Positive skew in this direction makes hold worse rather than better, because it delays the capturing edge into the window where new data is already arriving. And the failure cannot be repaired by slowing the clock, since neither side of the inequality contains the clock period. The fix is to insert buffer delay on the data path or to reduce the skew, which is why clock distribution is designed to minimise skew between adjacent stages.

Practice — "Sequential Circuits"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities