順序回路

ALUなどの算術演算・論理演算の回路はずべて、組み合わせ回路と呼ばれる。単純な入力によって値が決定されるから。

一方、これらの回路は状態を持つことができない。そのため、時間経過後に値を取り出すことができる記憶素子が必要になる。このような記憶素子は順序回路から構築できる。

フリップフロップという複雑な順序回路を最低構成要素として扱う。

記録を扱うということは、時間という概念を導入しないといけない。コンピュータ内での時間はクロックと呼ばれる

クロック

継続的に発せられる0/1（tick / tock or low/hight）の信号変化。tickのスタートから、次のtockの終わりまでを1周期(cycle)と呼ぶ。

フリップフロップ

フリップフロップにはいくつか種類があるが、今回使うのはD型フリフロップ (data filp-flop. DFF)。インターフェースは1bit入力と1bit出力。さらにクロック入力があることで、データ入力とクロック入力をあわせて時間に基づく振る舞いが可能になる。
${out({t})} = {in}({t} - 1)$ と表現される。DFFは単にひとつ前のタイムユニットの入力を出力するのみ。

レジスタ

データを格納したり呼び出したりできる記憶装置。${out({t})} = {out}({t} - 1)$を実現する。
1bitレジスタ（binary cell）は以下のようにHDLで表現される。

CHIP Bit {
    IN in, load;
    OUT out;

    PARTS:

    Mux(a=dffOut, b=in, sel=load, out=muxOut);
    DFF(in=muxOut, out=dffOut, out=out);
}

これはDFFとMuxの組み合わせで実現される。新しい値を保持したいなら、選択bit(load)を立てればいい。一つ前のクロックの出力値を読み込みたいのなら選択bitを下ろす。

上記のbinary cellを連結し、多bitレジスタを構成する。

/**
 * 16-bit register:
 * If load is asserted, the register's value is set to in;
 * Otherwise, the register maintains its current value:
 * if (load(t)) out(t+1) = int(t), else out(t+1) = out(t)
 */
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]);
}

これで16bitのデータについて状態を持つことが可能となる。多bitレジスタが持つデータのことを一般的にワードと呼ぶ。

メモリ

では、任意のワードを記憶するにはどうしたらいいだろう。
レジスタをたくさん積み重ねることでRAM（Randam Access Memory）を作ることができる。メモリ中のすべてのワードはその物理的に保存されている場所に関係なく、同じ時間で常に直接アクセスできなければならない。場所によらないアクセスを許可するので Random Access Memoryとよばれる。
このために、RAMの各ワードに対してユニークなアドレスが割当られる。
次に、n個のレジスタに対して、j番目のレジスタを選択できる論理ゲートを構築する。このアドレスは物理的な位置ではない。direct access logic によって論理的な意味でのアドレスが実現される

入力は、データ入力・アドレス入力・ロードビット。
RAMはwidth (ワードの長さ。32bitとか64bitとか)とsize(何万個のレジスタが連結されてるか)で大きさが表現される。

カウンタ

タイムユニットが進むたびに加算されていく値。CPUには、プログラムカウンタというカウンタが含まれ次に実行されるプログラムのアドレスとして解釈される。これによりプログラムの順次実行が可能になる。HDLで書くと以下のようになる

/**
 * A 16-bit counter.
 * if      reset(t): out(t+1) = 0
 * else if load(t):  out(t+1) = in(t)
 * else if inc(t):   out(t+1) = out(t) + 1
 * else              out(t+1) = out(t)
 */
CHIP PC {
    IN in[16], inc, load, reset;
    OUT out[16];

    PARTS:

    Inc16(in=outT, out=incOut);
    Mux16(a=outT, b=incOut, sel=inc, out=afterInc);
    Mux16(a=afterInc, b=in, sel=load, out=afterLoad);
    Mux16(a=afterLoad, b[0..15]=false, sel=reset, out=afterReset);
    Register(in=afterReset, load=true, out=outT, out=out);
}

回路を考えるときのコツは、Registerに出力を記憶させること。Registerのloadを常にtrueにして前回の出力結果を記憶させる

RAM8

レジスタが8つ組み合わさったもの。どのレジスタに書き込み要求があるかはaddressで制御する。
HDLで記述すると以下のようになる。

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

    PARTS:
    DMux8Way(in=load, sel=address, a=outa, b=outb, c=outc, d=outd, e=oute, f=outf, g=outg, h=outh);

    Register(in=in, load=outa, out=out1);
    Register(in=in, load=outb, out=out2);
    Register(in=in, load=outc, out=out3);
    Register(in=in, load=outd, out=out4);
    Register(in=in, load=oute, out=out5);
    Register(in=in, load=outf, out=out6);
    Register(in=in, load=outg, out=out7);
    Register(in=in, load=outh, out=out8);

    Mux8Way16(a=out1, b=out2, c=out3, d=out4, e=out5, f=out6, g=out7, h=out8, sel=address, out=out);
}

DMux8Wayで、どのレジスタの値をロードしてくるかを決定する。このaddressをload bitに適用して 所望のレジスタに値を書き込む。他のレジスタは以前の内容が入力され値を保持する。Mux8Way16でaddressを元に採用する値を決定する。

出力も同様のaddressを使って行われる。前の値を取り出したいだけのときはload bitを0にすれば所望のレジスタから値を取り出せる。

RAMn

nは2の累乗。例えばRAM64を構築する場合、RAM8を8つつなげる。address[6]の先頭3bitをどのRAMを使用するかにつかう。address[6]の後方3bitは選択されたRAMのレジスタを参照するのに使う。

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

    PARTS:

    DMux8Way(in=load, sel=address[0..2], a=load1, b=load2, c=load3, d=load4, e=load5, f=load6, g=load7, h=load8);

    RAM8(in=in, load=load1, address=address[3..5], out=out1);
    RAM8(in=in, load=load2, address=address[3..5], out=out2);
    RAM8(in=in, load=load3, address=address[3..5], out=out3);
    RAM8(in=in, load=load4, address=address[3..5], out=out4);
    RAM8(in=in, load=load5, address=address[3..5], out=out5);
    RAM8(in=in, load=load6, address=address[3..5], out=out6);
    RAM8(in=in, load=load7, address=address[3..5], out=out7);
    RAM8(in=in, load=load8, address=address[3..5], out=out8);

    Mux8Way16(a=out1, b=out2, c=out3, d=out4, e=out5, f=out6, g=out7, h=out8, sel=address[0..2], out=out);
}

フリフロップというクロックに合わせて動作する素子のおかげで、情報を記憶するということが可能になった。また、それを任意のタイミングで読み出すことも可能になった。