More than 3 years have passed since last update.

2章ブール算術 (コンピュータシステムの理論と実装)

Last updated at 2021-08-12Posted at 2021-08-12

はじめに

これは、「コンピュータシステムの理論と実装」(以下「Nand2Tetris」という)の第2章ブール算術のプロジェクトに対するレポートである。

Qiitaでは、画像の利用に制約があるため、論理ゲート図など掲載することは省いている。

プロジェクトに対するレポート

目標

1章で作成した論理ゲートを使い、算術用の論理回路を作成する。

材料

Nand2Tetrisで定義しているHDL言語
ハードウェアエミュレータ

実装

半加算器

半加算器の真理値表は、以下の通りである。

a	b	carry	sum
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

半加算器は、AndゲートとXorゲートにより構成できることが真理値表からわかる。

HalfAdder.hdl

    // Put your code here:
    Xor(a=a, b=b, out=sum);
    And(a=a, b=b, out=carry);

ハードウェアエミュレータを使い、HalfAdder.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

全加算器

全加算器の真理値表は、以下の通りである。

a	b	c	carry	sum
0	0	0	0	0
0	0	1	0	1
0	1	0	0	1
0	1	1	1	0
1	0	0	0	1
1	0	1	1	0
1	1	0	1	0
1	1	1	1	1

まず、aとbを半加算器で計算し、その出力とcを半加算器で計算した結果を出力する。

FullAdder.hdl

    // Put your code here:
    HalfAdder(a=a, b=b, sum=w1, carry=w2);
    HalfAdder(a=w1, b=c, sum=sum, carry=w3);
    Or(a=w2, b=w3, out=carry);

ハードウェアエミュレータを使い、FullAdder.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

加算器

全加算器を16個並列に並べ、0桁目から順に計算していく。
最初の桁にはcは定数0とし、最後のcarryも特に利用しない(オーバフローのチェックに利用できる)。

Add16.hdl

    // Put your code here:
   FullAdder(a=a[0], b=b[0], c=false, sum=out[0], carry=w1);
   FullAdder(a=a[1], b=b[1], c=w1, sum=out[1], carry=w2);
   FullAdder(a=a[2], b=b[2], c=w2, sum=out[2], carry=w3);
   FullAdder(a=a[3], b=b[3], c=w3, sum=out[3], carry=w4);
   FullAdder(a=a[4], b=b[4], c=w4, sum=out[4], carry=w5);
   FullAdder(a=a[5], b=b[5], c=w5, sum=out[5], carry=w6);
   FullAdder(a=a[6], b=b[6], c=w6, sum=out[6], carry=w7);
   FullAdder(a=a[7], b=b[7], c=w7, sum=out[7], carry=w8);
   FullAdder(a=a[8], b=b[8], c=w8, sum=out[8], carry=w9);
   FullAdder(a=a[9], b=b[9], c=w9, sum=out[9], carry=w10);
   FullAdder(a=a[10], b=b[10], c=w10, sum=out[10], carry=w11);
   FullAdder(a=a[11], b=b[11], c=w11, sum=out[11], carry=w12);
   FullAdder(a=a[12], b=b[12], c=w12, sum=out[12], carry=w13);
   FullAdder(a=a[13], b=b[13], c=w13, sum=out[13], carry=w14);
   FullAdder(a=a[14], b=b[14], c=w14, sum=out[14], carry=w15);
   FullAdder(a=a[15], b=b[15], c=w15, sum=out[15], carry=w16);

ハードウェアエミュレータを使い、Add16.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

インクリメンタ

加算器を使い、bに定数1を入力する。

Inc16.hdl

    // Put your code here:
   Add16(a=in, b[0]=true, b[1..15]=false, out=out);

ハードウェアエミュレータを使い、Inc16.Tstスクリプトを動作させると、Comparison ended successfullyと表示され。真理値表の通りである。

ALU

ALUを手順に従い作成する。

ALU.hdl

    // Put your code here:
   // zero the x input
   Mux16(a=x, b[0..15]=false, sel=zx, out=w1);
   // negate the x input
   Not16(in=w1, out=w2);
   Mux16(a=w1, b=w2, sel=nx, out=w3);
   // zero the y input
   Mux16(a=y, b[0..15]=false, sel=zy, out=w4);
   // negate the y input
   Not16(in=w4, out=w5);
   Mux16(a=w4, b=w5, sel=ny, out=w6);
   // compute out=x + y (if f=1) or out=x&y (if f=0)
   And16(a=w3, b=w6, out=w7);
   Add16(a=w3, b=w6, out=w8);
   Mux16(a=w7, b=w8, sel=f, out=w9);
   // negate the out output
   Not16(in=w9, out=w10);
   Mux16(a=w9, b=w10, sel=no, out=out);

ハードウェアエミュレータを使い、ALU-nostat.Tstスクリプトを動作させると、Comparison ended successfullyと表示される。

ngとzrについて検討する。ngは最上位ビットが0か1かで正負が決まるため、out[15]を使う。zrは、全ビットがゼロであることをチェックする。