執筆: H.T
はじめに
こんにちは。低レイヤー好きのH.Tです。
突然ですが、皆様は「コンピュータとは何か」と考えたことがありますか？我々のようなコンピュータ好きにとって「コンピュータとは何か」という疑問は、人類が「宇宙とは何か」と考えることと等しく根源的なものだと思います。そして、素晴らしいことに宇宙と異なり、コンピュータは仕組みが解明されています！（当たり前ですね…）
コンピュータとは何か。電気を使ってどうやって計算をしているのか。そもそも計算とは何なのか…。コンピュータには様々な秘密が隠されているのです！
今回は、そんなコンピュータの機能の中でも基礎となる、演算について紐解いていこうと思います。大きなテーマを扱うにあたり、本稿ではいくつかの概念について断片的に紹介し、徐々に一つの装置を組み上げていく方式を取ります。是非最後までお付き合いいただけますと幸いです。
デジタルとアナログ
1つ目のキーワードはアナログとデジタルです。
誰しも一度は聞いたことのある言葉ですが、実はコンピュータと密接な関係があります。
アナログとは数を連続的に表現すること。
デジタルとは数を離散的に表現することです。
例えば、体温計にはアナログ式とデジタル式が存在します。アナログ式の体温計は、中に赤く着色されたアルコール等の液体が封入されており、熱膨張による連続的な値を目で読み取ります。対してデジタル式では、センサーで読み取られた温度を、0.1度刻みなど離散的な値でディスプレイに表示します。
アナログとデジタルの数値の推移
デジタル表現は電気で動くものに限った話ではありません。
例えば古来から使われている原始的な計算機、「算盤」も離散的な数を扱っていますので「デジタル計算機」の一種と言えます。
また、昔は紐の長さや、水の量などを利用した、アナログな計算機も多く存在していたそうです。簡単な計算結果をアバウトに出すのであれば、アナログ計算機は便利でしたが、これでは複雑で精密な計算を行うことはできません。機構が複雑になればなるほど、アナログ世界特有のノイズ（誤差）による影響が大きくなります。
現代のデジタルコンピュータは、電圧の高・低を1・0に見立てて計算を行うのですが、このようなデジタル化は、アナログ世界の「ノイズ」を省き、ブレのない正確な計算を行うという利点をもたらします。
電圧が0から1に変わるとき、現実世界では多少ゆらぎながら連続的に変化していきます。
アナログ世界における実際の電圧の推移
デジタルの場合、例えば0.4未満を0とし、0.6以上を1と見立ててしまうことで、計算に必要のないノイズを無視できるのです。結果として、大量の回路をつなぎ合わせて大規模な計算を正確に行うことができます。
数理論理学
論理学というものがあります。
紀元前から存在し、非常に古い歴史を持つ学問です。
よく、「論理的に考えましょう」などと言われることがありますが、物事を順序立てて考え、正しい答えを導く思考法について考えるのが論理学だそうです。
例えば
- ORENDAは3DCGの製作会社である
- 3DCGの製作にはコンピュータが必須である
という2つの命題が与えられた場合、これらが真である（正しい）限り、「ORENDAの業務にはコンピュータが必須である」という推論が成り立ちます。ちなみに、命題が正しくないことを偽といいます。
一方
- ORENDAは3DCGの製作会社である
- ORENDAの業務にはコンピュータが必須である
という命題が与えられても、ここから導かれる推論として「3DCGの製作にはコンピュータが必須である」は正しいとは言えません。
このような思考法について考えるのが、論理学です。
数理論理学は論理学の発展型として、数学を取り入れた学問です。19世紀頃発明されたこの新しい学問では、命題を変数として記号化し、数式の代わりに論理式を使うことで、代数学のように式を変形したり、計算を行うことができるようになりました。数学で+/-/×/÷を使って計算を行うように、数理論理学ではAND/OR/NOTという論理演算子を使って演算を行います。
A and B : AかつB(AND)
A or B : AまたはB(OR)
￢A : Aでない(NOT)
※ 実際に式を組み立てる際は専用の記号を演算子として使用するのですが、本稿ではわかりやすさを重視して and や or と表記します。
論理演算
上でご紹介したとおり、現代コンピュータはデジタル計算機です。デジタルでは離散的な値を扱いますが、具体的には0と1の2進法を使っています。2進法には様々なメリットが有るのですが、主要なものとして「0と1の2種類だけを扱えば良いので回路が単純になること」、「命題の真と偽をそのまま1と0に対応させられること」が上げられると思います。
2進法は、その名の通り0と1の2種類だけを使った数の表現方法です。我々が普段利用している0～9の10種類の記号を使った表記は10進法と呼ばれます。
2進法では、0→1の次は繰り上がって10となります。
| 10進数 | 2進数 |
| 0 | 0 |
| 1 | 1 |
| 2 | 10 |
| 3 | 11 |
| 4 | 100 |
2進法も10進法も四則演算（+ – × ÷）の方法は変わりません。繰り上がりのタイミングが異なるだけです。例として、2進数 1010 と 1100 の足し算をやってみましょう。
こうやって見てみると、2進法の計算は10進法よりも単純なルールで動いているように見えます。何しろ、1桁だけを抽出するとパターンは2^2=4通りしか存在しません。
実は、論理演算子AND/OR/NOTをつかって、+ – × ÷ と同じ機能を再現することができます。（「だから何？」とか言わずにもう少しだけ付き合ってください…。）
試しに足し算の機能を作ってみましょう。
単純化のため、まずは1桁同士かつ繰り上がりの無い足し算を考えます。1桁同士なので、式と答えのパターンは4通りあります。（④の式の答えは通常10ですが、今は繰り上がりを無視しているので0となります）
- 0 + 0 = 0
- 0 + 1 = 1
- 1 + 0 = 1
- 1 + 1 = 0
これらの4パターンのうち、答えが真となるのは②または③であることがわかります。言い換えると、② or ③です。
ここで、それぞれの被演算子にA・Bという名前をつけます。0は偽、1は真とすると、
2. ￢A and B
3. A and ￢B
と表されます。
よって、
② or ③ は
(￢A and B) or (A and ￢B)
と表されます。Aが偽かつBが真のときまたは、Aが真かつBが偽のとき、答えが真となるということです。
トランジスタ
論理演算を物理的に実装するには、AND/OR/NOT を電気的に行うための回路を設計する必要があります。これに欠かせないのが、トランジスタという部品です。
トランジスタには様々な種類がありますが、ここではFETを扱います。FETは、ゲート、ソース、ドレインという3つのピンを持つ電子部品です。ゲートに電圧をかけることで、ドレン – ソース間に流れる電流を制御することができます。（原理について触れると長くなってしまうので、ここでは「これが宇宙の摂理」という説明に留めさせていただこうと思います。）
コンピュータはトランジスタを、電気のスイッチとして利用します。つまり、ゲートにかかる電圧を上げたり下げたりして、ソース – ドレイン間に電流を流したり、止めたりすることができるのです。詳しくは触れませんが、このトランジスタを複数組み合わせることで、AND/OR/NOTを実現できます。（トランジスタを直列につなげればAND回路が、並列につなげればOR回路が作れます。）
論理回路
論理演算を行う論理回路を設計するには、トランジスタを組み合わせて作ったAND/OR/NOTを、下図のように抽象化された記号として表した、論理回路図が利用されます。
論理回路の説明にあたって、CircuitVerseという素晴らしいWebサービスを紹介します。IIIT-Bangaloreの学生が製作した学習用の論理回路シミュレータで、Webブラウザ上で論理回路を作って動作を確認することができます。
CircuitVerseを使って、上で作った1桁の足し算回路(￢A and B) or (A and ￢B)を作成してみましょう。(￢A and B)と(A and ￢B)をorで繋げば完成です。
ここに繰り上がりの出力をするにはどうすれば良いでしょうか。1桁の計算において、繰り上がりが起きるのはAとBがともに1になった時、つまり(A and B)です。
AとBをクリックし、共に1を立ててみると、繰り上がり（carry）がうまく動作していることが確認できます！
この状態の回路を半加算器（half adder）と呼びます。半加算器は繰り上がり桁の出力ができます。
では、複数桁の計算を行うにはどうすればよいでしょう。まず、繰り上がりの出力については考えず、3つの入力と答えの組み合わせを書き出してみましょう。
| A | B | C | Output |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
この内答えが1となるのは、以下4通りの組み合わせの場合です。
- A and B and ￢C
- A and ￢B and C
- ￢A and B and C
- ￢A and ￢B and ￢C
ということで、1桁 + 繰り上がり桁 の足し算回路は
(A and B and ￢C)or (A and ￢B and C)or (￢A and B and C)or (￢A and ￢B and ￢C)
となります。これでも良いのですが、回路が複雑になりすぎるのでもう少し考えてみます。最初の回路、(￢A and B) or (A and ￢B)=Dとしてみましょう。すると、答えが1となる組み合わせは
- D and ￢C
- ￢D and C
の2通りとなり、回路１を応用して以下の回路図で表すことができます。
少し複雑になってきたので、新しい回路記号を紹介します。回路1の動作は良く登場するので、XORという1つの回路記号で表すことができます。
回路3をXORを用いて表すと、以下のようになります。
かなりスッキリしました！それでは最後に、繰り上がり出力を追加します。繰り上がりが発生するのは、A、B、Cのうち2つ以上のインプットが1となる、以下の場合です。
- A and B and ￢C
- A and ￢B and C
- ￢A and B and C
- A and B and C
この内、1と4をまとめると、A and Bとなります。（Cがどのような値でも、AとBが真であれば出力が1になるため）
さらに、(￢A and B) or (A and ￢B)=Dとすると、2と3はD and Cとなります。
よって、(A and B) or (D and C)という以下のような回路を作成すれば良いはずです。
このように、繰り上がり入力と繰り上がり出力に対応した加算回路を、全加算器（Full Adder）と呼びます。半加算器および全加算器をいくつも組み合わせることで、複数の桁に対応した加算器を作成することができます。
複数ビット加算器の構造
これで、足し算を行う回路が完成しました。足し算は演算回路の最も基礎となる部分で、これを応用することでその他の四則演算回路を作ることができます。
例えば、4 – 3 という引き算は 4 + ( -3 ) と、4 × 3という掛け算は 4 + 4 + 4 と言い換えることができます。8 ÷ 2といった割り算も、8 – 2 – 2 … と、8から2を何回引けるかを数えることで実現できます。
ただし、これはあくまで基礎的な回路ですので、実際のコンピュータには高速な計算を行うための様々なハードウェアアルゴリズムが実装されています。
まとめ
今回は、コンピュータの5大機能の1つである、演算について紹介しました。
AND/OR/NOTを使った論理回路によって様々な種類の計算を、（電気のオン・オフを使って表される）2進数で実行できるということをわかっていただけたかと思います。
お気付きの方もいるかも知れませんが、演算回路単体では、ある入力に対する答えを出すだけの電卓のようなマシンしか作れません。
コンピュータのように複雑な動作を行うためには、演算装置とは別に、それを制御する「制御装置」や、プログラム及びデータを保存する「記憶装置」等が必要となります。これらの機能が一つになったとき、あらゆる複雑な計算を行う万能チューリングマシンが誕生します。
機会があれば、またここで語らせていただければと思います。
参考書籍
- David A. Patterson & John L. Hennessy,『コンピュータの構成と設計』.第5版.日経BP.2014
- Sarah L. Harris & David Money Harris,『ディジタル回路設計とコンピュータアーキテクチャ』.第2版.翔泳社.2017