Memory and sequential logic: latch, flip-flop, register, FSM

Last week’s circuits remembered nothing: when you changed the input, the output changed immediately. A computer, on the other hand, needs to store numbers, the program and the information “where am I right now”. This page describes the storage elements: latch, register, memory. Then it moves on to the idea of the finite state machine that uses them. The LC-3’s control unit is also really a large FSM.

The question types from this topic on the midterm: latch tracing (a sequence of S, R is given, Q is asked), memory calculation (how many address bits, how many bytes in total), the number of flip-flops, FSM tracing.

What is a sequential circuit?

The output of a combinational circuit depends only on the current input. The output of a sequential circuit depends both on the input and on the information the circuit has stored up to that moment, that is, its state.

Example: a combination lock. If the correct code is 4-1-8, the “8” key alone does not open the lock. Whether it opens depends on which keys were pressed before. The lock stores a state.

The R-S latch

The simplest storage element is two cross-coupled NAND gates: the output of each NAND goes to the input of the other. The external inputs are S (set) and R (reset), the outputs are Q and Q’.

If one input of a NAND is 0, its output is definitely 1. That is why in this latch the inputs are active-low: to do something you make the input 0.

Why does it hold? With S = R = 1 both NANDs see only the other one’s output. If Q = 1, the lower NAND sees (1, 1) and gives Q’ = 0; the upper one sees (1, 0) and gives Q = 1. The system feeds itself, and the same holds for Q = 0. There are two stable states, and the latch stays in whichever one it is in.

Worked trace: initial Q = 1, inputs 10 → 11 → 10 → 01 → 11.

step  S R   what happens?  Q
 1    1 0   reset          0
 2    1 1   hold           0
 3    1 0   reset          0   (already 0)
 4    0 1   set            1
 5    1 1   hold           1

PITFALL · the active-low rule. In a latch built with NOR, S = 1 sets; in a NAND latch, S = 0 sets. This course (Patt & Patel) uses the NAND latch: 11 holds, the letter that is 0 does its job.

The gated D latch

The R-S latch has two problems: the forbidden input state and not being able to control “when to write”. The gated D latch solves both. The inputs: data D and WE (write enable).

Two NANDs are added in front of the R-S latch: $S = (D \cdot WE)'$, $R = (D' \cdot WE)'$.

• WE = 0 → S = R = 1 → the latch holds.
• WE = 1, D = 1 → S = 0 → set → Q = 1.
• WE = 1, D = 0 → R = 0 → reset → Q = 0.

S and R can never be 0 at the same time, because one uses D and the other uses D’.

In short: when WE = 1, Q = D; when WE = 0, Q is frozen.

Register

A register is $n$ D latches (or flip-flops) sharing the same WE line. All of them are written at the same time. A 16-bit register = 16 storage elements.

Bit range notation: for a 16-bit A, A[15:12] is the leftmost 4 bits, A[3:0] is the rightmost 4 bits. Bits are numbered from the right, starting at 0.

A = x3A7C = 0011 1010 0111 1100
A[15:12] = 0011   A[11:8] = 1010   A[3:0] = 1100   A[6:4] = 111

You will use this notation constantly when decoding LC-3 instructions: opcode = IR[15:12], destination register = IR[11:9].

Memory

Memory is an orderly array of a large number of storage locations. It is described by two numbers:

• Address space: how many separate locations there are. $k$ address bits → $2^k$ locations.
• Addressability: how many bits each location has.

$\text{total size} = 2^k \times m \text{ bits}$

In byte-addressable memory each location is 1 byte (most modern computers). The LC-3 is word-addressable: there is a 16-bit word at each address.

How is a read done?

1. A $k$-bit address enters a $k$-to-$2^k$ decoder.
2. The decoder sets exactly one word line to 1: the location in that row is selected.
3. The $m$ bits of the selected row pass to the output.

For a write, WE = 1 is added, and only the WE of the latches in the selected row is enabled.

TIP · Quick power table. $2^{10}$ = 1K, $2^{16}$ = 64K, $2^{20}$ = 1M, $2^{30}$ = 1G, $2^{32}$ = 4G. “How many address bits does 64 KB byte-addressable memory need?” → 64K = $2^{16}$ → 16 bits.

The clock and the flip-flop

In a computer, thousands of storage elements must be updated at the same time. The clock provides this: a signal that goes back and forth regularly between 0 and 1. One clock cycle is one full period. In a 3 GHz processor, one cycle is 1/3 of a nanosecond.

The problem with the gated D latch: it is transparent as long as WE = 1. The output changes, the changed output is fed back, and in the same cycle the latch can change again. To prevent this, the master-slave flip-flop is used: two gated D latches back to back. The master takes the new value while the clock is 1, and the slave passes it to the output while the clock is 0. The result: the output changes once per cycle, at the clock edge. Everything that stores state (registers, the FSM state) is built with flip-flops.

Finite state machine (FSM)

An FSM is defined by five things:

1. A finite number of states,
2. A finite number of external inputs,
3. A finite number of external outputs,
4. An explicit definition of the next state for each state and input (transitions),
5. An explicit definition of what each output depends on.

Its drawing is the state diagram: circles are states, arrows are transitions, and the input value is written on the arrow.

States are stored in flip-flops. To distinguish $s$ states you need $\lceil \log_2 s \rceil$ flip-flops: 4 states → 2, 5 states → 3, 9 states → 4.

Worked FSM trace

A machine that gives Z = 1 when it sees two 1s in a row. States: A (the last input was not 1), B (one 1 has been seen), C (at least two 1s in a row). Z = 1 only in C.

Start at A, inputs 0, 1, 1, 1, 0, 1:

input:      0   1   1   1   0   1
new state:  A   B   C   C   A   B
Z:          0   0   1   1   0   0

At each step, look at a single row: current state + input → new state. Since there are 3 states, 2 flip-flops are enough.

A machine like this, whose output depends only on the state, is called a Moore machine. The LC-3’s control unit is also an FSM: each state is one step of the instruction cycle (week 5).

Common mistakes