コンピュータシステムの理論と実装 Chap2

www.amazon.co.jp

前回に引き続きこれです

２章概要

2進数、符号付き2進数、2の補数、ブール算術など理解し、加算器・算術論理演算機を実装する

2進数

0と1のみを使って数を表現するやつ

符号付き2進数

正の数と負の数を表現できる2進数

2の補数

符号付き2進数を実現するために使われているやつ。
最上位bitの状態で正か負かを判断できる。
補数を求めるための数式は 2**n - x ※ n= bit数

たとえば 8bitで -5 を表す場合は 2**8 - 5 = 256 -5 = 251 となり、2進数に直すと 11111011 となる
これに8bitの5である 00000101 を加算してみると 00000000 となり (繰り上がった9bit目はオーバーフローで無視) 答えが0になっているので補数であることが確認できる。

符号付き2進数において2の補数での表現を採用するメリットは、減算を加算と同じ手順で計算できるためシンプルな実装になることらしい。
たとえば4bitの 3-2 であれば 0011 + 1110 となり、計算結果は 0001 (繰り上がった5bit目は無視) なので、正しく計算できていることがわかる。

加算器とALUの実装

1章で実装した論理ゲートを用いて、いくつかの加算器と算術論理演算機(ALU=Arithmetic Logical Unit)を実装する。

以降は僕が実装したコードが出てくるので、ネタバレされたくない人は読まない方がよいです

半加算器

2つの入力の和を出力すればOK。
出力パターンは 00, 01, 10 の3つ

最下位ビットは2つの入力がそれぞれ 0 と 1 だった場合にのみ 1 を出力し、それ以外は 0 を返せばよく、これは Xor の挙動と同じなので Xor を使い、
最上位ビット(=繰り上がり) は2つの入力が両方とも 1 だった場合にのみ 1 を出力すればいいので And を使った。

Xor(a=a, b=b, out=sum);
And(a=a, b=b, out=carry);

全加算器

3つの入力の和を出力すればOK。
出力パターンは 00, 01, 10, 11 の4つ

半加算器を2つ使用して最下位bitの和を求めて、どちらかで繰り上がりが発生していた場合に最上位bitに1を出力すれば良さそうと思ったのでそうした

HalfAdder(a=a, b=b, sum=tmp, carry=carry1);
HalfAdder(a=c, b=tmp, sum=sum, carry=carry2);
Or(a=carry1, b=carry2, out=carry);

16bit加算器

2つの16bitの入力の和を出力すればOK。
オーバーフローは検出しない

半加算器と全加算器を並べるだけで良さそうだったのでそうした

HalfAdder(a=a[0], b=b[0], sum=out[0], carry=carry1);
FullAdder(a=a[1], b=b[1], c=carry1, sum=out[1], carry=carry2);
...
FullAdder(a=a[14], b=b[14], c=carry14, sum=out[14], carry=carry15);
FullAdder(a=a[15], b=b[15], c=carry15, sum=out[15]);

インクリメンタ

与えられた16bitの入力に1を加算すればOK

先ほどの16bit加算器を使うと楽そうだったのでそうした

Add16(a=in, b[0]=true, b[1..15]=false, out=out);

ALU

2つの16bitの入力といくつかの制御ビットをもとに計算する。
出力は計算結果の out , out が 0 であるかどうかを表す zr , outが負の数であるかどうかを表す ng の3つ。

制御ビット	説明
zx	入力 x をゼロにする
nx	入力 x を反転する
zy	入力 y をゼロにする
ny	入力 y を反転する
f	True であれば加算、 False であれば And演算する
no	出力を反転する

If文使いてえ〜と思いながら Multiplexor を使ってそれぞれの制御ビットを適用した計算結果を選択していく感じで実装した。

out は制御ビットを適用したあとの数値をそのまま出力し、
zr は out の全てのbit が 0 だった場合に 1 を出力すればよいため Or8Way (8bitの中に1つでも 1 があれば 1 を出力する論理ゲート) を2つ使い
ng は最上位ビットが 1 であれば 1 を出力し、そうでなければ 0 を出力すればいいため、 out の15bit目をそのまま出力した

変数名が無になって辛い...。

// zx, nx
Mux16(a=x, b[0..15]=false, sel=zx, out=x1);
Not16(in=x1, out=x2);
Mux16(a=x1, b=x2, sel=nx, out=x3);

// zy, ny
Mux16(a=y, b[0..15]=false, sel=zy, out=y1);
Not16(in=y1, out=y2);
Mux16(a=y1, b=y2, sel=ny, out=y3);

// f
Add16(a=x3, b=y3, out=xAddY);
And16(a=x3, b=y3, out=xAndY);
Mux16(a=xAndY, b=xAddY, sel=f, out=f1);

// no
Not16(in=f1, out=notF1);
Mux16(a=f1, b=notF1, sel=no, out=out, out[0..7]=out0to7, out[8..15]=out8to15, out[15]=ng);

Or8Way(in=out0to7, out=zr1);
Or8Way(in=out8to15, out=zr2);
Or(a=zr1, b=zr2, out=zr3);
Not(in=zr3, out=zr);

感想

ALUはもうちょっと良い実装があるんだろうなーと思ったけど特に浮かばなかったのが残念。
模範解答的なやつがあれば見てみたいなー

がんばるぞ

がんばります