Assyのリベラル文学研究所もご覧ください。

コンピュータの計算原理

参考文献

放送大学「情報学へのとびら」を参考に執筆しました。

回路記号

NOT

NOTは0と1を反転させたもの。
f:id:schwarz1009:20200710152210p:plain

AND

ANDは2つの値の積。
f:id:schwarz1009:20200710152247p:plain

OR

ORは2つの値の和。ただし1と1の論理和は1。
f:id:schwarz1009:20200710152539p:plain

スイッチング素子

このような論理回路は、スイッチング素子を用いて実現できる。スイッチング素子とは、オンとオフの2つを切り替えられる機能を持った素子。
ただし、いちいち人間が切り替えるのではなく、他の素子と関連して自動的に切り替わるようになっている。
コンピュータでよく使われるのは、MOS FETという半導体だが、歴史的にはバイポーラトランジスタ真空管、リレーなどが用いられた。
以下は原理の分かりやすいリレーによる論理回路

リレー

1つの接点に鉄片が蝶番で取り付けられており、その鉄片が電磁石の曲の先に配置されている。
鉄片は、ふだんはバネによって電磁石から遠い接点Out1に接しているため、Out1が導通状態(On)で、Out2は遮断状態(Off)であるが、InのスイッチをOnにすると、電磁石に電流が流れて鉄片を吸い寄せ、Out2をOnにし、Out1がOffになる。
f:id:schwarz1009:20200710152918p:plain

リレー

AND

ANDは、二つのInどちらもOnになった時に、OutがOnになる。
f:id:schwarz1009:20200710153004p:plain

OR

ORは、二つのInどちらかがOnになった時に、OutがOnになる。
f:id:schwarz1009:20200710153021p:plain

EXOR

EXORは、二つのInのどちらかがOnであればOutがOnになるが、二つのInどちらもOnであればOutがOffになる。
f:id:schwarz1009:20200710153052p:plain

スイッチングの簡単な図

上記のリレー図は難しく見えるが、単純化すると要はこういうことである。

f:id:schwarz1009:20200710153136p:plain

真理値表

二進数での1桁+1桁の加算は、0+0, 0+1, 1+0, 1+1の4通りしかない。
このうち最後の1+1は上の桁への繰り上がりが起きるので、繰り上がりの有無を示す出力を設ける必要がある。
Out1を繰り上がりの有無、Out2を加算結果の1桁目とすると、次のような真理値表が得られる。

In1 In2 Out1 Out2
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

これを見ると、Out1はIn1とIn2の論理積(AND)であり、Out2はIn1とIn2の排他的論理和(EXOR)であることが分かる。

半加算器

よって、AND回路とEXOR回路を組み合わせることで、以下のような加算器を構成できる。上半分がAND回路、下半分がEXOR回路で、入力In1とIn2を2つに分けて1つのスイッチで2つのリレーを作動させるようにしている。
f:id:schwarz1009:20200629182657p:plain
この加算器は1桁+1桁の時は問題ないが、多桁に拡張する際には、下の桁からの繰り上がりを考慮していない点で不完全である。そのため、半加算器と呼ばれる。

全加算器の真理値表

下からの繰り上がりを考慮に入れた全加算器の真理値表は以下のようになる。
Cが下の桁からの繰り上がりの有無を示す。

In1 In2 C Out1 Out2
0 0 0 0 0
0 1 0 0 1
1 0 0 0 1
1 1 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 1 0
1 1 1 1 1

全加算器

これは、このように実現出来る。
f:id:schwarz1009:20200629182825p:plain
この全加算器を用いることで多桁の加算器が構成できる。
多桁の加算器は、それぞれの桁に加算器を用意することで実現できる。
一番下の桁は半加算器で良い。
あとはその半加算器に結合する形でそれぞれの桁の全加算器を構築すれば良い。

減算

減算は、2の補数を加えることで実現できる。
2の補数とは、たとえば0001111であれば1110001であるかのように、全ての数を反転させて、その値に1を加えた数のこと。
この時、一番上のビットは必ずプラス値の場合0、マイナス値の場合1となる。
よって、00001111の補数は11110001となる。
-1は0001に対して1111、-2は0010に対して1110、-3は0011に対して1101、-4は0100に対して1100となる。
減算の例として、000111に111001を加える場合、全ての数を反転した数に1を加える前に、その反転させた数をまず足すことを考えてみる。
当然、必ず全ビットが1になる(111111)。
これに1を加えれば、桁あふれが起きると同時に必ず全ビットが0になる(000000)。
この桁あふれを無視すると、必ず結果は0となる。
-1よりも-2の方が符号なしの数値の上では1小さいため、差が存在する時は適切に差が残る。
-1よりも-2の方が小さいため、足した時に1小さな数値になる。

乗算と除算

乗算については、確かに3を3回繰り返して足しても実現できるのだが、人間が小学生で習う「筆算」を使って、それぞれの桁について、0をかけるときは何も加えず、1をかけるときは元の数をシフトした数を加えることで実現できる。よって、桁をシフトする機能と加算ができれば実現できる。
同様に除算についても、筆算を使って、減算と桁をシフトする機能があれば実現できる。割られる数から割る数を、右にシフトさせながら、引ける場合にだけ引く(実際は2の補数を加えて桁あふれが起きるかどうかで引けたかどうかを判断する)ことで実現できる。