O'REILLY コンピューターシステムの理論と実装【第2章②】

第2章の課題。
HDLによる加算器の実装。
利用可能な構成要素は、1章の課題で構築した基本的な回路。(なので以降はNANDをプリミティブな要素としてAndやOrを定義しなくて良い)

課題1. 半加算器の実装。
2つのbitの和を求める。以下のように2桁で出力する。

0+0=00
1+0=01
0+1=01
1+1=10

このとき、出力の最上位ビットと最下位ビットをそれぞれ"carry"、"sum"として定義する。

CHIP halfadder {
    IN  a, b;
    OUT carry, sum;
    PARTS:
    Xor(a=a,b=b,out=sum);
    And(a=a,b=b,out=carry);
}

以下の通り、1+1の場合carryが1、sumが0となる。(他のパターンの紹介は割愛。)

半加算器の1+1の出力

課題2. 全加算器の実装。
3つのbitの和を求める。

CHIP fullAdder {
    IN a,b,c;
    OUT sum,carry;
    PARTS:
    Xor(a=a,b=b,out=sum1);
    And(a=a,b=b,out=carry1);

    Xor(a=sum1,b=c,out=sum);
    And(a=sum1,b=c,out=carry2);

    Or(a=carry1,b=carry2,out=carry);
}

以下の通り、1+1+1の場合carryが1、sumが1となる。(こちらも他のパターンの紹介は割愛。全パターン確認済。)

全加算器の1+1+1の出力

課題3. 加算器の実装。
2つのn bitの和を求める(多ビット加算器)。今回は16bit想定。
最下位ビットのみ半加算器を実装して以降最上位ビットの手前まで各桁について全ビット(3ビット)加算器を実装。最上位ビットは全ビット加算器実装のうち桁上げに関連する実装を省略。

CHIP adder {

    IN a[16],b[16];
    OUT sum[16];

    PARTS:
/*for the first 1 least significat bit*/
    Xor(a=a[0],b=b[0],out=sum[0]);
    And(a=a[0],b=b[0],out=carry0);

/*for the 2nd least significant bit*/
    Xor(a=a[1],b=b[1],out=sum1);
    And(a=a[1],b=b[1],out=carry1a);

    Xor(a=sum1,b=carry0,out=sum[1]);
    And(a=sum1,b=carry0,out=carry1b);

    Or(a=carry1a,b=carry1b,out=carry1);

/*for the 3nd least significant bit*/
    Xor(a=a[2],b=b[2],out=sum2);
    And(a=a[2],b=b[2],out=carry2a);

    Xor(a=sum2,b=carry1,out=sum[2]);
    And(a=sum2,b=carry1,out=carry2b);

    Or(a=carry2a,b=carry2b,out=carry2);

/*for the 4th least significant bit*/
    Xor(a=a[3],b=b[3],out=sum3);
    And(a=a[3],b=b[3],out=carry3a);

    Xor(a=sum3,b=carry2,out=sum[3]);
    And(a=sum3,b=carry2,out=carry3b);

    Or(a=carry3a,b=carry3b,out=carry3);

/*for the 5th least significant bit*/
    Xor(a=a[4],b=b[4],out=sum4);
    And(a=a[4],b=b[4],out=carry4a);

    Xor(a=sum4,b=carry3,out=sum[4]);
    And(a=sum4,b=carry3,out=carry4b);

    Or(a=carry4a,b=carry4b,out=carry4);


/*for the 6th least significant bit*/
    Xor(a=a[5],b=b[5],out=sum5);
    And(a=a[5],b=b[5],out=carry5a);

    Xor(a=sum5,b=carry4,out=sum[5]);
    And(a=sum5,b=carry4,out=carry5b);

    Or(a=carry5a,b=carry5b,out=carry5);


/*for the 7th least significant bit*/
    Xor(a=a[6],b=b[6],out=sum6);
    And(a=a[6],b=b[6],out=carry6a);

    Xor(a=sum6,b=carry5,out=sum[6]);
    And(a=sum6,b=carry5,out=carry6b);

    Or(a=carry6a,b=carry6b,out=carry6);

/*for the 8th least significant bit*/
    Xor(a=a[7],b=b[7],out=sum7);
    And(a=a[7],b=b[7],out=carry7a);

    Xor(a=sum7,b=carry6,out=sum[7]);
    And(a=sum7,b=carry6,out=carry7b);

    Or(a=carry7a,b=carry7b,out=carry7);

/*for the 9th least significant bit*/
    Xor(a=a[8],b=b[8],out=sum8);
    And(a=a[8],b=b[8],out=carry8a);

    Xor(a=sum8,b=carry7,out=sum[8]);
    And(a=sum8,b=carry7,out=carry8b);

    Or(a=carry8a,b=carry8b,out=carry8);


/*for the 10th least significant bit*/
    Xor(a=a[9],b=b[9],out=sum9);
    And(a=a[9],b=b[9],out=carry9a);

    Xor(a=sum9,b=carry8,out=sum[9]);
    And(a=sum9,b=carry8,out=carry9b);

    Or(a=carry9a,b=carry9b,out=carry9);


/*for the 11th least significant bit*/
    Xor(a=a[10],b=b[10],out=sum10);
    And(a=a[10],b=b[10],out=carry10a);

    Xor(a=sum10,b=carry9,out=sum[10]);
    And(a=sum10,b=carry9,out=carry10b);

    Or(a=carry10a,b=carry10b,out=carry10);


/*for the 12th least significant bit*/
    Xor(a=a[11],b=b[11],out=sum11);
    And(a=a[11],b=b[11],out=carry11a);

    Xor(a=sum11,b=carry10,out=sum[11]);
    And(a=sum11,b=carry10,out=carry11b);

    Or(a=carry11a,b=carry11b,out=carry11);

/*for the 13th least significant bit*/
    Xor(a=a[12],b=b[12],out=sum12);
    And(a=a[12],b=b[12],out=carry12a);

    Xor(a=sum12,b=carry11,out=sum[12]);
    And(a=sum12,b=carry11,out=carry12b);

    Or(a=carry12a,b=carry12b,out=carry12);


/*for the 14th least significant bit*/
    Xor(a=a[13],b=b[13],out=sum13);
    And(a=a[13],b=b[13],out=carry13a);

    Xor(a=sum13,b=carry12,out=sum[13]);
    And(a=sum13,b=carry12,out=carry13b);

    Or(a=carry13a,b=carry13b,out=carry13);


/*for the 15th least significant bit*/
    Xor(a=a[14],b=b[14],out=sum14);
    And(a=a[14],b=b[14],out=carry14a);

    Xor(a=sum14,b=carry13,out=sum[14]);
    And(a=sum14,b=carry13,out=carry14b);

    Or(a=carry14a,b=carry14b,out=carry14);

/*for the most significant bit*/
    Xor(a=a[15],b=b[15],out=sum15);
/*    And(a=a[15],b=b[15],out=carry15a);*/

    Xor(a=sum15,b=carry14,out=sum[15]);
/*   And(a=sum15,b=carry14,out=carry15b);

    Or(a=carry15a,b=carry15b,out=carry15);*/
}

12+13の実行結果。

16bit加算器での12+13の実行

課題4. インクリメンタの実装。
与えられた数字に1を加算する。

(後日更新。)

課題5. ALU(算術論理演算器)の実装。

(後日更新。)