NAND2Tetris Note 04 - Sequential Logic and Memory

All of the chips described in the previous course notes used what is called “combinational logic”, where the output is available instantenously and there is no time-component to their operation. Combinational chips compute functions that depend solely on combinations of their input values.

Sequential logic incorporates the concept of time, or more specifically, discretized time in the form of a clock signal into determining their output. This is the core concept behind digital circuits with memory. Just like how NAND formed the basic building blocks of combinational logic, the “D-Flip-Flip” is the fundamental building block used to build sequential logic. A D-Flip-Flop can be built out of nand-gates using a loop-based design but that is beyond the scope of the course.

Clocked Data Flip Flop (D Flip-Flop or DFF)

The D Flip-Flop has one input “in” and one output “out”. There’s also an implicit “clock” signal that cycles from high to low and back to high to make a single “clock cycle”. The output of the D flip-flip is simply the input of the last time step (with the output of the initial timestep being indeterminate).

D-Flip-Flops are combined in various ways with combinational logic circuits to build up basic memory units like a 1-bit register, larger addressed registers (RAM) and counters that form the basis of computer memory.

One-Bit Register

A bit regsiter has two inputs “in” and “load” and a single output “out”. The output is the same as the last output if “load” is zero. It is equal to “in” if “load” is set to one. The HDL imlementation uses a Mux to select between the lastOutput and the current input. This is then passed into a DFF and the output of the DFF is the output of the register.

Mux(a=lastOutput, b=in, sel=load, out=dffIn);
DFF(in=dffIn, out=out, out=lastOutput);

The output of the DFF is fanned out to the input of the Mux as well. This is possible because HDL is not a programming language. It can be thought of as a description of electrical wiring. So the output line of the DFF is looped back to the input of the Mux here.

16-bit register

A 16-bit register chip has a 16-bit input in, a single bit load input and a 16-bit output, out. This can be implemented by stacking 8 one-bit register and fanning out the load input to all of them. The inputs and outputs of each “bit” chip is wired to the individual bits of in and out respectively.

RAM8 chip

This is a chip that can store 8 “words” (in this case 16-bit words). The chip has a 16-bit in input, 3-bit address input and a 16-bit output, out. It uses a Demuxer to split out the address into 8 different load bits which are then fed into Register chips. in is fanned out to all the underlying Register chips. The outputs of the registers are then connected to the out pin through a Multiplexer with the address as its selector.

RAM64, RAM512, RAM4K and RAM16K

These are built in the same manner as RAM8 but by composing RAMx chips using a Demuxer and Muxer. RAM64 has a 6-bit address input, where the 3 most-significant bits select the underlying RAM8 chip and the 3 LSBs signify the address in the underlying RAM8. Therefore the load bit is wired to the RAM8 chips through a Demuxer with address[3..5] as the sel input and address[0..2] is passed through directly to the underlying chips. The output is similarly muxed using address[3..5] as the selector. The higher capacity chips are built in the same way by stacking 4 or 8 lower capacity chips and an appropriately sized Demuxer and Muxer.