D-type flip-flops and clocks

Clock signals, edge triggering, the D-type flip-flop as one bit of memory, registers and a divide-by-two counter.

A8.8Boolean algebra and logic circuitsA level20 min

Every circuit so far has been combinational: its output depends only on its inputs right now. Change an input and the output follows. That cannot remember anything, yet a processor is full of memory: the program counter, the accumulator, every register you met in lesson F9.4. This lesson builds memory out of logic, and introduces the clock that keeps it all in step.

Memory needs feedback

A circuit whose output depends on what happened before, as well as its current inputs, is sequential. The trick that makes it possible is feedback: a gate's output is wired back round to an input, so the circuit can hold itself in a state.

The simplest example is two NOR gates, each with its output wired to one input of the other. This is an SR latch, with inputs S (set) and R (reset). Setting S to 1 makes the output Q 1; setting R to 1 makes Q 0; with both at 0 the loop holds whichever value Q had. It stores one bit, but it changes the moment S or R changes, which makes it hard to keep many of them in step. The latch is background here: the D-type flip-flop below is what the specifications name.

The clock

A clock is a signal that switches between 0 and 1 at a fixed rate. Its frequency is the number of complete cycles per second: BugBot's processor clock runs at hundreds of millions of hertz (you met clock speed in lesson F9.5). The clock keeps every part of the processor in step, so that each stage of the fetch-decode-execute cycle happens at a known moment.

Each cycle has two edges:

• the rising edge, where the clock goes from 0 to 1;
• the falling edge, where it goes from 1 to 0.

Memory that only changes on an edge changes at one instant per cycle, and the rest of the time holds steady while the combinational logic around it settles.

The D-type flip-flop

A D-type flip-flop stores one bit and changes only on a clock edge.

• D is the data input: the bit to be stored.
• Clock is the clock input. The small triangle on it means edge-triggered.
• Q is the stored bit, and Q̅ is its inverse.

The rule for a positive edge-triggered D-type flip-flop is:

At the rising edge, Q takes the value D has at that moment. At every other time, D can change as much as it likes and Q holds its value. That is exactly what a memory cell should do: it takes a copy when told to, then keeps it.

Reading a timing diagram

Exam questions show flip-flops with timing diagrams: each signal drawn against time, with the edges lined up.

Follow Q along the rising edges (the dashed lines):

• Before step 1 nothing has been stored, and Q is 0.
• At step 1 the clock rises while D is 1, so Q becomes 1.
• At steps 2 and 3, D goes to 0 and back to 1. There is no rising edge, so Q stays 1.
• At step 5 the clock rises while D is 0, so Q becomes 0, and holds through the change in D at step 6.
• At step 9 the clock rises while D is 1: Q becomes 1.
• At step 12 the clock rises while D is 0: Q becomes 0.

The diagram only changes D between edges. In a real circuit, D must be steady for a short time before and after the edge for the flip-flop to store it reliably.

class DFlipFlop:
    def __init__(self):
        self.q = 0
        self.last_clock = 0

    def tick(self, clock, d):
        if self.last_clock == 0 and clock == 1:    # rising edge: store D
            self.q = d
        self.last_clock = clock
        return self.q

clock = [0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0]
data  = [1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1]
ff = DFlipFlop()
print("step clock D  Q")
for step in range(len(clock)):
    q = ff.tick(clock[step], data[step])
    print(f"{step:4}   {clock[step]}   {data[step]}  {q}")

Run this in the simulator

What flip-flops build

• Registers. Put 8 flip-flops side by side, one per bit, with a shared clock, and you have an 8-bit register. On each rising edge it stores a whole byte at once. The program counter and accumulator are registers like this.
• Shift registers. Wire each flip-flop's Q to the next one's D, and on every edge each bit moves along one place. This is how a serial link turns a byte into a stream of bits.
• Counters and frequency dividers. Wire a flip-flop's own Q̅ back to its D. On every rising edge it stores the opposite of what it held, so Q toggles: 1, 0, 1, 0. Q changes once per clock cycle, so it completes one cycle every two clock cycles: its frequency is half the clock's. Chain several and each halves the frequency again, which is how a binary counter works.

The robot can show a divider working. Each pass round the loop is one clock cycle, and the LED shows Q:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

q = 0
for edge in range(8):
    d = 1 - q            # Q-bar wired back to D
    q = d                # the rising edge stores D
    led("green" if q == 1 else "off")
    print("edge", edge + 1, "Q =", q)
    wait(0.25)

Run this in the simulator

Task: a D-type flip-flop

Write rising_edge(previous, now), which takes two clock values (each 0 or 1) and returns True if the clock has just gone from 0 to 1, otherwise False.

Part 1. Simulate a D-type flip-flop over the 14 steps in the lists CLOCK and D. Q starts at 0 and the clock value before step 0 counts as 0. At each step, if rising_edge is true for the previous and current clock values, Q becomes D at that step; otherwise Q keeps its value. Record Q after every step, and print all 14 values on one line, separated by spaces, in the form Q: 0 0 0 ....

Part 2. Build a divide-by-two counter: a flip-flop whose D is always NOT Q. Q starts at 0. Simulate 8 rising edges. After each edge, show Q on the LED (led(0, 255, 0) when Q is 1, led(0, 0, 0) when it is 0) and wait(0.25). Then print the 8 values of Q on one line, in the form divider: 1 0 ....

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

CLOCK = [0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1]
D = [0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1]

def rising_edge(previous, now):
    return False

Challenges

1. Change Part 1 so the flip-flop triggers on the falling edge instead. Which values of Q change?
2. Chain two dividers: the second flip-flop changes whenever the first one's Q falls from 1 to 0. Print both Qs for 8 edges and read them as a 2-bit binary number.
3. Build a 4-bit register from four DFlipFlop objects sharing one clock, and store 1011 on one rising edge.