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

Noam Nisan、Shimon Schocken(2015)『コンピューターシステムの理論と実装』O'REILLYの第1章について。

書かれていること：論理的に抽象化されたアプリケーションのプログラムが、物理的な電気信号に変換されるまでの間に何が起きているのか。

本書第1章について。

コンピューターアーキテクチャーを構築する第一歩は、ブール関数を定式化して分析することにある。

ブール関数は出力としてブール値(バイナリ値や2値とも)を返す関数。True/Falseを格納するboolean型に関連。

ここで、3つのブール値を格納できる変数x,y,zを用意する。x,y,zのそれぞれに適当なブール値を設定し、それらをあるブール関数に入力として与えて出力を得る。

変数x,y,zに対して設定可能なブール値のパターンを全て洗い出し、それらを入力としたときに対応するブール関数の出力値を表にしたものを「真理値表」と呼ぶ。

ブール関数自体は例えば(x or y) and zのようなブール式として表すことができる。

この場合、(x or y)はxとyの最低どちらか一つの変数のブール値が1の場合に1を返します。a and zはaとz共にブール値が1の場合に1を返す。

x,y,zの全ての組み合わせをブール関数を通した時、ある組み合わせについては出力が1となり、ある組み合わせについては出力が0となる。

例えば、以下3つの組み合わせがブール関数を通すと1を出力したとする。

(0,1,0)

(0,1,1)

(1,0,1)

上の3つの組み合わせの "いずれか(or)" であれば必ず1を返す。これは以下のように表現できる。

(0,1,0) or (0,1,1) or (1,0,1)

ブール式を正準表現で表すと、f(x,y,z)= $\bar{x}y\bar{z}$ or $\bar{x}yz$ or $x\bar{y}z$

この表現を正準表現と呼ぶ。

n個のブール値の変数によって定義されるブール関数は $2^2$ のn乗(数式表現できず。。)となる。以下で検証。

n=2とし、ブール値を格納する変数x,yを定義。

もし上の説が正しいのであれば、2^2^2=16通りのブール関数が存在。

2つの変数xとyについてのそれぞれboolean型の組み合わせは $2^2$ の4通り。xとyに代入される4通りの0と1の組み合わせについて、あるブール関数f(x,y)の入力とした時、出力が0または1となる。

ブール関数f(x,y)は、x,yの組み合わせが(0,0)であろうが(0,1)であろうが(1,0)でも(1,1)でも必ず0を返す関数が考えられる。(関数1つ目)

(x,y)が(1,1)の時のみ1を返すブール関数。(関数2つ目)

(x,y)が(0,0)の時のみ1を返すブーr(略)

ブール関数の数はx,yの全ての組み合わせ(0,0)、(0,1)、(1,0)、(1,1)についての0と1のパターンの数。

2^4=16 通り

この式は

(ブール関数の出力としての0と1)^(変数のパターンの数。上の場合変数xとyに0と1が入る組み合わせ。->2^変数の数)

なのでつまり、ブール関数のパターン数=2^2^変数の数

ある入力のブール関数の完備性(completeness)について考える。

完備性とはある少数の論理関数の集まりについて、全ての論理関数を表現することができる性質。全ての論理関数を表現することができる少数の論理関数の集まりのことを完備集合と呼ぶ。

例えば、{AND, OR, NOT}や{AND,NOT}、{OR,NOT}、{NOR}、{NAND}が完備集合。

このブール関数を実装する物理デバイスがゲート(gate)。

ゲート(とブール関数)の入力と出力が必ずしも1:1ではない。ゲートで実装するブール関数は、n個の変数を入力として受け取りm個のバイナリを返す。(これまでの関数はm=1)

なのでブール関数fを実装するゲートには入力ピン(v1...vn)が存在するのでブール関数自体はf(v1...vn)と表現できる。

NANDやNORが最小構成の完備集合であるので、NANDないしNORゲートで他の全てのゲートを構成可能。物理的な実装はダイオードとトランジスタで体験できる。(商用コンピュータは基本的にシリコンからつくられたトランジスタで、ゲートは「回路」ないし「チップ」として抽象化される)

2値データの表現と伝達(gate to gateの伝達)は電気が用いられているが、電気以外に水圧、磁石でも実装可能。

情報科学(コンピュータ・サイエンス)の分野においては物理的な電気・回路について考える必要はない。(物理レイヤーは電気エンジニアの専門でありコンピュータ・サイエンスはその上のレイヤーに集中する。)

なので、And、Or、Notについて実装を気にする必要はなく、それらをどう利用するかを考える。

(ただしこの後ハードウェアシミュレーターでNANDによるゲート実装は体験する)