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

www.amazon.co.jp

最近この本をやり始めたのでメモ

1章概要

ブール理論を理解し、本書から提供されているハードウェアシミュレーターを用いて数種類の論理ゲートを実装する。

論理ゲート

ブール関数を実装した物理デバイスのことらしい。が、実際に物理デバイスを作る必要はなく、ハードウェアシミュレーター上で論理ゲートを実装すればOK。

ブール関数とは And とか Or とか Not のように、 n個の入力値を元に新しいブール値を出力するような関数のこと

And だったら2つの入力値が共に True であれば True を出力し、それ以外であれば False を出力するし、 Not であれば1つの入力値を反転させた出力をする。
出力値は1つとは限らず、例えば Demultiplexor と呼ばれるブール関数は複数の出力を持つ

論理ゲートの実装

Nand (=not and) という論理ゲートだけが予め用意されているので、 Nand を使って他の論理ゲートを実装していく。実行効率についてはあまり考えずに、最初に浮かんだロジックをとりあえず実装して進める方針でやっていく。

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

Not

与えられた入力値を反転して出力すればいい。

Nandしか使えないので以下のような実装になった。

Nand(a=in, b=true, out=out);

PHPだとこんな感じになる

<?php
function not(bool $in): bool
{
    return nand($in, true);
}

And

入力値が2つとも True だったら True を出力し、それ以外であれば False を出力すればいい。

そもそも Nand が !And なので、さらに否定すれば !!And となって And になるじゃんと思ったので以下のような実装になった。

Nand(a=a, b=b, out=nand);
Not(in=nand, out=out);

PHPだとこう

<?php
function and(bool $a, bool $b): bool
{
    return not(nand($a, $b));
}

Or

2つの入力値がどちらも False である場合に False を出力し、それ以外の場合は True を出力する。

Nand は 2つの入力値が True である場合のみ True を出力し、それ以外の場合は False を出力するという Or の動作と似てる感じだったので、入力値をそれぞれ否定すればいいんじゃねということで以下のような実装になった

Not(in=a, out=notA);
Not(in=b, out=notB);
Nand(a=notA, b=notB, out=out);

Xor

2つの入力値がそれぞれ異なる値の場合に True を出力し、そうでない場合に False を出力する。

Or と Nand がそれぞれ True を出力すれば2つの入力値が異なる状態であると言えると思うので、以下のような実装になった

Nand(a=a, b=b, out=nand);
Or(a=a, b=b, out=or);
And(a=nand, b=or, out=out);

Multiplexor

a,b,selという3つの入力値を受け取り、selが False であれば a を selが True であれば b を出力すればOK。

こういった分岐はif文を使うことが前提な思考になっていたので、少し戸惑ってしまった。
あと変数名をどうすればいいかわからなさすぎる

b の値を出力する場合は sel と b を And 関数に通せばいいが a を出力する場合はそうもいかない。
が、sel を反転すれば a も b と同じ扱いが出来るのではという感じで以下の実装になった。

Not(in=sel, out=notSel);
And(a=a, b=notSel, out=a1);
And(a=b, b=sel, out=b1);
Or(a=a1, b=b1, out=out);

Demultiplexor

in,sel という2つの入力値をとり、a, b という2つの出力をする。 sel が False であれば a=in, b=0 を sel が True であれば a=0, b=in を出力すればOK。

先ほどの Multiplexor を使えば簡単そうだったのでそうした

Mux(a=in, b=false, sel=sel, out=a);
Mux(a=false, b=in, sel=sel, out=b);

多ビットAnd, Not, Or, Multiplexor / 複数入力 Or, Multiplexor, Demultiplexor

他にも課題のゲートはいくつかあったが、新しい考え方は特になかったのでスキップ

感想

ブール関数だけで Multiplexor みたいなゲートを実装するのはすごく新鮮で面白かったなー

がんばるぞ

がんばります