Skip to content
Tutorials Center
My learning

Topics

Lesson 55 of 57 ยท Practice and Review

Practice: Sequential Logic

Solve exercises on flip-flop inputs, counters, shift registers, a 101 sequence detector and clock-period timing, with every answer checked by runnable Python.

Sequential circuits have memory, so the questions change from "what is the output?" to "what is the output after the next clock edge?" This lesson gives you six exercises on the second half of the course: flip-flop inputs, counters and dividers, shift registers, finite-state-machine design and timing. As in the combinational practice, each exercise has a worked solution and a program that checks it.

Try each exercise on paper first. For sequential problems, writing the table of present state, input, next state and output is not optional; it is the method.

Four habits for sequential problems

Make a table Present state, input, next state, output.
Think per clock edge Nothing changes between edges.
Use the equations Characteristic and excitation tables.
Simulate to check Compare with a plain-Python reference.
1 / 2

Useful background: JK and T flip-flops, counters, shift registers, state machines and timing.

Part 1: flip-flops, counters and shift registers

Exercise 1. A JK flip-flop has the characteristic equation Q+ = JยทQ' + K'ยทQ. Which values of J and K make Q go from 0 to 1? From 1 to 0? Hold at 0? Hold at 1? List all choices.

Exercise 2. You have a D flip-flop but need a T (toggle) flip-flop. What logic goes in front of D?

Exercise 3. (a) How many flip-flops does a mod-6, mod-10, mod-12 and mod-100 counter need at least? (b) A 100 MHz clock drives a chain of toggle flip-flops. What are the frequencies after 1, 4 and 10 stages?

Exercise 4. (a) A 4-bit serial-in shift register starts at 0000. Bits 1, 0, 1, 1 are shifted in, the first bit entering at the left end, and the register shifts right. What does it hold after each clock edge? (b) List the states of a 4-bit Johnson counter starting at 0000. (c) List the states of a 4-bit ring counter starting at 1000.

Python Check the answers to exercises 1 to 4

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions

Exercise 1. To set the flip-flop from 0 to 1 you need J = 1 and do not care about K: both (1, 0) and (1, 1) work, since with Q = 0 the K term multiplies Q and vanishes. To reset from 1 to 0 you need K = 1, with J free. To hold at 0, J must be 0 and K is free. To hold at 1, K must be 0 and J is free. These don't-cares are the excitation table of the JK flip-flop and they are what makes JK-based designs often cheaper than D-based ones.

Exercise 2. Toggle means the next state is the opposite of the present state when T = 1 and the same when T = 0. That is Q+ = T โŠ• Q, so D = T โŠ• Q: one XOR gate between T, the flip-flop's own output and its input. With T tied to 1, you get a flip-flop that toggles on every edge, a divide-by-two stage.

Exercise 3. (a) A counter with N states needs โŒˆlog2 NโŒ‰ flip-flops: 3 for mod-6, 4 for mod-10 and mod-12 and 7 for mod-100. Counting to 10 uses only 10 of the 16 states a 4-bit register can hold, which is why a decade counter needs extra logic to reset. (b) Each toggle stage halves the frequency: 50 MHz, 6.25 MHz and about 97.7 kHz (0.0977 MHz).

Exercise 4. (a) After the four edges the register reads 1000, 0100, 1010 and 1101. The oldest bit sits at the right and is pushed out next. (b) A Johnson counter feeds the inverted last output back to the first input. Its sequence 0000, 0001, 0011, 0111, 1111, 1110, 1100, 1000 has 8 states, twice the number of flip-flops, and only one bit changes at each step. (c) A ring counter feeds the last output back unchanged. Starting with a single 1, that 1 circulates: 1000, 0100, 0010, 0001, only 4 states for 4 flip-flops.

Part 2: state machines and timing

Exercise 5. Design a Mealy machine with one input X that outputs 1 when the last three input bits were 1, 0, 1. Overlap is allowed: 10101 contains two detections. Give the state table, an encoding with two flip-flops and the equations for the D inputs and the output.

Exercise 6. (a) A path between two flip-flops has clock-to-Q delay 0.5 ns, logic delay 3.2 ns, setup time 0.3 ns and clock skew 0.2 ns (counted against you in both checks). What is the minimum clock period and the maximum frequency? (b) For the shortest path, clock-to-Q is 0.3 ns, logic is 0.2 ns, hold time is 0.1 ns and skew is still 0.2 ns. Is the hold requirement met? (c) A 4-bit ripple counter has 0.4 ns delay per flip-flop. How long can the output take to settle?

Python Check the answers to exercises 5 and 6

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions

Exercise 5. Three states are enough. S0: nothing useful seen yet (or the last bits were 00). S1: the last bit was 1. S2: the last two bits were 10.

State X = 0 X = 1
S0 S0 / 0 S1 / 0
S1 S2 / 0 S1 / 0
S2 S0 / 0 S1 / 1

Entries are next state / output. From S2 (we have 10), input 1 completes the pattern, so the output is 1 and we go to S1, because that final 1 could start another pattern. That return to S1 is what allows overlap. With the encoding S0 = 00, S1 = 01, S2 = 10 (bits Q1 Q0) the table gives D1 = X'ยทQ0, D0 = X and Y = XยทQ1. The state 11 never occurs; the design treats it as a don't-care. Look at the program output: for the input 1 0 1 0 1 1 0 1 the machine raises the output at positions 3, 5 and 8, including the overlapping detection. It also matches a brute-force reference on all 4096 twelve-bit inputs. The full method is in Designing a Sequential Circuit.

Exercise 6. (a) The data launched by one edge must arrive before the next edge, minus setup. With skew eating into the budget: T >= tcq + tlogic + tsu + skew = 0.5 + 3.2 + 0.3 + 0.2 = 4.2 ns, so fmax is about 238 MHz. (b) For hold, the new data must not arrive too soon after the clock edge: tcq,min + tlogic,min >= thold + skew. Here 0.3 + 0.2 = 0.5 ns against 0.1 + 0.2 = 0.3 ns, so the slack is +0.2 ns and hold is met. Note that hold does not depend on the clock period, so you cannot fix a hold violation by slowing the clock. (c) In the worst case, such as 0111 going to 1000, the change ripples through all four stages in turn, so the output may take up to 1.6 ns to settle, and glitchy intermediate values appear on the way. That is the reason synchronous counters exist.

Do not mix up the two checks. A setup failure is cured by a slower clock or shorter logic. A hold failure is independent of the clock period and is cured by adding delay to the short path.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A JK flip-flop holds its state at 1 when...

    With Q = 1 the next state is K'ยทQ (plus JยทQ' which vanishes), so it holds when K = 0, whatever J is.
  2. 2. How many flip-flops does a mod-12 counter need at minimum?

    Twelve states need ceil(log2 12) = 4 bits, so four flip-flops, with extra logic to skip the unused states.
  3. 3. Why does the 101 detector return to S1, not S0, after detecting a match?

    The last 1 of one detection can be the first 1 of the next, as in 10101. Going back to S1 remembers it.
  4. 4. A setup violation can be fixed by...

    Setup compares the longest path with the clock period. Slowing the clock or shortening the path gives data more time to arrive. Hold fixes are different: they add delay.

Summary

  • Excitation tables show which flip-flop inputs produce a wanted transition; JK has many don't-cares, D has none, and T needs D = T โŠ• Q.
  • An N-state counter needs โŒˆlog2 NโŒ‰ flip-flops; each toggle stage halves the frequency.
  • A Johnson counter has 2n states, a ring counter n states, from n flip-flops.
  • To design an FSM, write the state table, assign codes, derive the next-state and output equations, then simulate against a reference.
  • Tmin = tcq + tlogic + tsu + skew; hold slack is independent of the clock period.

Next: Digital Logic Interview Questions.