Sequential logic

Introduction

Combinational chips cannot maintain state because their operation is instantaneous. We cannot use loops which feed a chip's output to its input because this creates instantaneous and uncontrolled dependency between input and output, which is called data race.

In order to build chips that remember information, we must first develop means for representing the progression of time. The passage of time in computers is regulated by a master clock which is an oscillating device. It broadcasts its current phase to all of the sequential chips throughout the computer platform.

Memory chips

Memory elements that can preserve data over time are built from sequential chips. The most primitive sequential gates are called flip-flops. We build data flip flops (DFF) by feeding flip-flop gates with inputs of data and clock signals together to implement time-based behavior \(out(t) = in(t-1)\), where \(in\) and \(out\) are the gate's input and output values respectively, and \(t\) is the current clock cycle. In other words, DFF simply outputs the input value from the previous time unit. The operation of sequential chips is clock-regulated. Combinational chips never change their state just because of the progression of time.

Note that nothing in the HDL code for a given chip suggests that it may be clocked because the chip may or may not use a sequential chip down below the level of abstraction.

A register is a memory device that implements storage behavior \(out(t) = out(t-1)\). We can build registers from DFF by using a multiplexor for its load control bit.

Stacking together many multi-bit registers form a Random Access Memory (RAM) unit. Any word in the RAM can accessed directly in equal speed. RAM device accepts three inputs: a data input, an address input, and a load bit. The design of a RAM unit is based on the data width parameter (width of one of its words) and the number of words (RAM size) in the RAM.

Counters

A counter is a sequential chip whose state is an integer number that increments every time unit, performing the function \(out(t) = out(t-1) + c\), where \(c\) is typically 1. A program counter is a chip in the CPU which is used to point to the instruction address that should be executed next in the current program.

Time

DFF gates can either maintain state (memory) or operate on state (counters). This is done by forming feedback loops. There is no difficulty in feeding the output of a sequential chip back into itself because of the time delay: the output at time \(t\) depends on the output at previous the time \(t-1\). This inherent property of time delays guards against data races.

DFFs in sequential chips change their output only at the point of transition from one clock cycle to the next, and not within itself. We allow sequential chips to have unstable states during clock cycles. At these times DFFs are latched, meaning that changes in their inputs have no immediate effect on their outputs. However, we require that at the beginning of the next cycle the chips output correct values.

When we build the computer's clock, we have to be sure that the length of the clock cycle is slightly longer than the time it takes for a bit to travel the longest distance from one chip in the architecture to another.

1-bit register

/**
 * 1-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 *                 else out does not change (out[t+1] = out[t])
 */

CHIP Bit {
    IN in, load;
    OUT out;

    PARTS:
    Mux(a=d, b=in, sel=load, out=m);
    DFF(in=m, out=d, out=out);
}

16-bit register

/**
 * 16-bit register:
 * If load[t] == 1 then out[t+1] = in[t]
 * else out does not change
 */

CHIP Register {
    IN in[16], load;
    OUT out[16];

    PARTS:
    Bit(in=in[0], load=load, out=out[0]);
    Bit(in=in[1], load=load, out=out[1]);
    Bit(in=in[2], load=load, out=out[2]);
    Bit(in=in[3], load=load, out=out[3]);
    Bit(in=in[4], load=load, out=out[4]);
    Bit(in=in[5], load=load, out=out[5]);
    Bit(in=in[6], load=load, out=out[6]);
    Bit(in=in[7], load=load, out=out[7]);
    Bit(in=in[8], load=load, out=out[8]);
    Bit(in=in[9], load=load, out=out[9]);
    Bit(in=in[10], load=load, out=out[10]);
    Bit(in=in[11], load=load, out=out[11]);
    Bit(in=in[12], load=load, out=out[12]);
    Bit(in=in[13], load=load, out=out[13]);
    Bit(in=in[14], load=load, out=out[14]);
    Bit(in=in[15], load=load, out=out[15]);
}

16-bit RAM8

/**
 * Memory of 8 registers, each 16 bit-wide. Out holds the value
 * stored at the memory location specified by address. If load==1, then 
 * the in value is loaded into the memory location specified by address 
 * (the loaded value will be emitted to out from the next time step onward).
 */

CHIP RAM8 {
    IN in[16], load, address[3];
    OUT out[16];

    PARTS:
    DMux8Way(in=load, sel=address, a=la, b=lb, c=lc, d=ld, e=le, f=lf, g=lg, h=lh);
    Register(in=in, load=la, out=a);
    Register(in=in, load=lb, out=b);
    Register(in=in, load=lc, out=c);
    Register(in=in, load=ld, out=d);
    Register(in=in, load=le, out=e);
    Register(in=in, load=lf, out=f);
    Register(in=in, load=lg, out=g);
    Register(in=in, load=lh, out=h);
    Mux8Way16(a=a, b=b, c=c, d=d, e=e, f=f, g=g, h=h, sel=address, out=out);
}

16-bit RAM16

/**
 * Memory of 64 registers, each 16 bit-wide. Out holds the value
 * stored at the memory location specified by address. If load==1, then 
 * the in value is loaded into the memory location specified by address 
 * (the loaded value will be emitted to out from the next time step onward).
 */

CHIP RAM64 {
    IN in[16], load, address[6];
    OUT out[16];

    PARTS:
    DMux8Way(in=load, sel=address[3..5], a=la, b=lb, c=lc, d=ld, e=le, f=lf, g=lg, h=lh);
    RAM8(in=in, load=la, address=address[0..2], out=a);
    RAM8(in=in, load=lb, address=address[0..2], out=b);
    RAM8(in=in, load=lc, address=address[0..2], out=c);
    RAM8(in=in, load=ld, address=address[0..2], out=d);
    RAM8(in=in, load=le, address=address[0..2], out=e);
    RAM8(in=in, load=lf, address=address[0..2], out=f);
    RAM8(in=in, load=lg, address=address[0..2], out=g);
    RAM8(in=in, load=lh, address=address[0..2], out=h);
    Mux8Way16(a=a, b=b, c=c, d=d, e=e, f=f, g=g, h=h, sel=address[3..5], out=out);
}

16-bit RAM512

/**
 * Memory of 512 registers, each 16 bit-wide. Out holds the value
 * stored at the memory location specified by address. If load==1, then 
 * the in value is loaded into the memory location specified by address 
 * (the loaded value will be emitted to out from the next time step onward).
 */

CHIP RAM512 {
    IN in[16], load, address[9];
    OUT out[16];

    PARTS:
    DMux8Way(in=load, sel=address[6..8], a=la, b=lb, c=lc, d=ld, e=le, f=lf, g=lg, h=lh);
    RAM64(in=in, load=la, address=address[0..5], out=a);
    RAM64(in=in, load=lb, address=address[0..5], out=b);
    RAM64(in=in, load=lc, address=address[0..5], out=c);
    RAM64(in=in, load=ld, address=address[0..5], out=d);
    RAM64(in=in, load=le, address=address[0..5], out=e);
    RAM64(in=in, load=lf, address=address[0..5], out=f);
    RAM64(in=in, load=lg, address=address[0..5], out=g);
    RAM64(in=in, load=lh, address=address[0..5], out=h);
    Mux8Way16(a=a, b=b, c=c, d=d, e=e, f=f, g=g, h=h, sel=address[6..8], out=out);
}

16-bit RAM4K

/**
 * Memory of 4K registers, each 16 bit-wide. Out holds the value
 * stored at the memory location specified by address. If load==1, then 
 * the in value is loaded into the memory location specified by address 
 * (the loaded value will be emitted to out from the next time step onward).
 */

CHIP RAM4K {
    IN in[16], load, address[12];
    OUT out[16];

    PARTS:
    DMux8Way(in=load, sel=address[9..11], a=la, b=lb, c=lc, d=ld, e=le, f=lf, g=lg, h=lh);
    RAM512(in=in, load=la, address=address[0..8], out=a);
    RAM512(in=in, load=lb, address=address[0..8], out=b);
    RAM512(in=in, load=lc, address=address[0..8], out=c);
    RAM512(in=in, load=ld, address=address[0..8], out=d);
    RAM512(in=in, load=le, address=address[0..8], out=e);
    RAM512(in=in, load=lf, address=address[0..8], out=f);
    RAM512(in=in, load=lg, address=address[0..8], out=g);
    RAM512(in=in, load=lh, address=address[0..8], out=h);
    Mux8Way16(a=a, b=b, c=c, d=d, e=e, f=f, g=g, h=h, sel=address[9..11], out=out);
}

16-bit RAM16K

/**
 * Memory of 16K registers, each 16 bit-wide. Out holds the value
 * stored at the memory location specified by address. If load==1, then 
 * the in value is loaded into the memory location specified by address 
 * (the loaded value will be emitted to out from the next time step onward).
 */

CHIP RAM16K {
    IN in[16], load, address[14];
    OUT out[16];

    PARTS:
    DMux4Way(in=load, sel=address[12..13], a=la, b=lb, c=lc, d=ld);
    RAM4K(in=in, load=la, address=address[0..11], out=a);
    RAM4K(in=in, load=lb, address=address[0..11], out=b);
    RAM4K(in=in, load=lc, address=address[0..11], out=c);
    RAM4K(in=in, load=ld, address=address[0..11], out=d);
    Mux4Way16(a=a, b=b, c=c, d=d, sel=address[12..13], out=out);
}

Program counter

/**
 * A 16-bit counter with load and reset control bits.
 * if      (reset[t] == 1) out[t+1] = 0
 * else if (load[t] == 1)  out[t+1] = in[t]
 * else if (inc[t] == 1)   out[t+1] = out[t] + 1  (integer addition)
 * else                    out[t+1] = out[t]
 */

CHIP PC {
    IN in[16],load,inc,reset;
    OUT out[16];

    PARTS:
    // obtain a 16-bit zero for the reset procedure
    Not16(in=in, out=notin);
    And16(a=in, b=notin, out=zero16);

    // get the current register value and increment it
    Inc16(in=curReg, out=curRegInc);

    // if the control bit (inc == 1) then pass the incremented value,
    // otherwise pass the current register value
    Mux16(a=curReg, b=curRegInc, sel=inc, out=ifInc);

    // if the control bit (load == 1) then pass the input value,
    // otherwise pass the previously calculated value
    Mux16(a=ifInc, b=in, sel=load, out=ifLoad);

    // if the control bit (reset == 1) then pass the 16-bit zero
    // otherwise pass the previously calculated value
    Mux16(a=ifLoad, b=zero16, sel=reset, out=ifReset);

    // decide if either control bits are set (inc Or load Or reset == 1)
    // and use it later as the load control bit in the register
    Or(a=load, b=inc, out=incOrLoad);
    Or(a=incOrLoad, b=reset, out=incOrLoadOrReset);

    // if either control bits are set then load to the register
    // the previously calculated value and output it
    // otherwise output the current value in the register
    // note that we also use the output from the register
    // for the incrementing procedure earlier in the code
    Register(in=ifReset, load=incOrLoadOrReset, out=curReg, out=out);
}