2.2 情報科学技術の基本原理:計算化、プログラム化

2.2.1 計算化への道(その1):論理演算によるデジタルデータ処理

すべてのデータを究極的には0と1の数字からなる2進列で表わすことができる。というデジタル化の原理は、実に様々な効用を我々にもたらしてくれる。その最も重要なものがデータ処理(計算)の単純化である。

すべてのデータを2進列で表わすことで、すべてのデータ処理を非常に単純な基本操作に分解できる。2進列の構成要素は0と1である。そこで処理の基本は、この0と1の計算規則(論理演算:解説1参照)に集約できるのである。

基本的な論理演算は、二つ(または一つ)の1ビットのデータから1ビットの答えを求める計算である。このような単純な計算であれば、電子素子で安定して実現することができる。これが今日の情報科学技術の第一歩となる発見である。1ビットのデータであれば、電気信号のオンオフで表わすことができる。そのような1ビットの信号を二つ入力し(各x1x2とする)、たとえば、論理積x1x2を1ビットの信号(これをyとする)として出力する素子が実現可能なのである。このような素子を(論理)演算ゲートあるいは(論理)演算素子などという。

こうしたゲートを図1のように表わすことにする。本来は、信号の入ってくるタイミングなどを調整する必要があるが、以下では話を簡単にするため、そのような点は無視し、データは瞬時に処理されるものとする。

1 論理積ゲート

解説1:論理演算

0と1の計算を論理演算という。「論理演算」とは、本来は真と偽の二値に対する計算であるが、1を「真」、0を「偽」と考えると、0と1の計算は論理値間の計算とみなせるからである。以下に示したのは、それぞれ論理積(∧)、論理和(∨)、否定(┐)の計算規則である。∧はAND演算とも呼ばれる。x yが1(真)となるのはxyの両方が共に真の場合のみだからである。同様な理由で∨はOR演算、┐は否定演算と呼ばれている。

0 ∧ 0  =  0 ∧ 1  =  1 ∧0  =  0、そして 1 ∧ 1  =  1

0 ∨ 1  =  1 ∨ 0  =  1 ∨1  =  1 、そして0 ∨ 0  =  0

┐0  =  1  そして  ┐1  =  0

この三つは論理演算の基本である。

図1は論理積を計算する素子であるが、その他に、論理和、否定を計算する論理演算ゲートさえあれば、すべての計算を実現することが可能である。

たとえば、次のように定義される演算(排他論理和)を考えてみよう。

00  =  11  =  0  そして 10  =  10  =  1

この論理演算も、xy  =  ( ¬x y) ∨(x∧¬y)という一般式が成り立つので、図2のような組み合わせで計算できる。

2 排他論理和の計算

さらに複雑な計算も、こうした演算ゲートを組み合わせれば実現できる。たとえば図3のように、基本演算ゲートをうまく配線すれば、より複雑な演算を行うことができる。

 

入力x, y ,zのうち、1が2個以上あるか否かを判定する計算を実現する方法。配線が交差しているときは太線が上で、その下を細線が通っているものとする。

3 より複雑な計算

さらに、この図3の回路全体を入力が3個の一つのゲートのように見ることもできる。(ここでは、≧2という名前のゲートとみなしている。)このような回路を部品として使って、さらに複雑な計算を行うこともできるのである。

こうして順次組み上げていけば、どのような複雑な計算も原理的には実現することができる。この種の回路を組合せ論理回路という。(例5に足し算を行なう回路例を示したので興味のある方は参照されたい。)

組み合わせ論理回路により、2進列の各ビットを入力とし、それらに対し何らかの処理をしたものを計算することができる。それらに対し何らかの処理をしたものを計算することができる。これは足し算や掛け算のような「計算」に限らない。画像や音声のデータ処理、あるいは、文字や言葉の変換も同様に可能なのである。

情報科学技術の大きな特徴は「計算」のこの汎用性にある。データは2進列という同じ顔を持ち、その処理は同一の論理演算の組み合わせで行なうことができる。そのため、同じ演算回路を様々な用途に用いることができ、共通の部品を利用することができ、それらを量産することができるのである。つまり、情報科学技術を支える部品は量産することができ、そのため焦点を絞った技術革新の競争が激しく行われてきたのである。その結果、記録や処理できるビット数がとてつもなく増えた。実際、回路は非常に小さくなり高速になった。半導体を使った電子回路技術の進展によって、量も速度も3年に2倍(おおよそ、10年で10倍)の勢いで増えてきたのである。

 

2.2.2 計算化への道(その2):「繰り返し」の導入

論理演算の組み合わせで、すべてのデジタルの処理が可能、というのは計算化への大きな一歩であるが、計算化にはまだ重要な要素が二つある。

演算ゲートの組み合わせである組み合わせ論理回路だけでは、決まった大きさのデータしか扱うことができない。たとえば、下の例に示した組み合わせ回路では4ビット同士の自然数の足し算しかすることができない。もちろん、同様の方法で、10ビット、50ビット、あるいは100ビットの自然数の足し算の回路を設計することはできるが、ビット数の増加とともに、毎回、新たな論理回路が必要になってしまう。こうした問題を解決する方法が「繰り返し」である。

計算では、似たようなことを繰り返し行うことが多い。足し算を計算する回路を見ても同じパターンが繰り返されているのがわかるだろう。これは各桁xiyi そして下からの繰り上がり値の和を求め、その1桁目を対応する桁の答えの値ziとし、2桁目を新たな繰り上がりの値とする。これを繰り返しているのである。

5:足し算を行なう回路

2進列のデータを処理する回路の例として、4ビットの2進数の和を求める回路を図6に示す。計算したい4ビットの2進数の各桁が、各々x4x3x2x1y4y3y2y1に与えられたとき、その和がz5z4z3z2z1に計算される。たとえばx4x3x2x11101y4y3y2y10110を入力すると、z5z4z3z2z1として10011が出力される。詳細は省略するが興味のある方は試してみられるとよいだろう。

図中で≥2という印のついたゲートは図3で定義したもの。ゲートは、3変数の排他論理和を行なうゲート。入力中の1の個数が奇数個ならば1、偶数個ならば0を出力する。2変数の排他論理和ゲートを2個組み合わせれば実現できる。

図4順序回路による加算

足し算を行なう順序回路の概念図。入力xiyiに足す数、足される数のiビット目が、i=1から順次来ると、ziに答えのiビット目が求まる。それと同時に桁上がりがAで計算され、それが次の入力が来るタイミングでBに送られて足しこまれる。

したがって、この計算を繰り返すような仕組みができれば、1つの回路でどんな桁数の足し算も、原理的には可能になる。その仕組みを取り入れた回路が図4のような順序回路である。

図4は、かなり概念的な図であるが、それでも順序回路の仕組みと特徴が表わされている。第一に、本当の入力であるnビットの2数、x= xnx1y= yny1に対して、適当な順序で(この場合にはx1y1からの順で)入力ビットが順次、回路に渡される、という仕組みである。第二に、ある時点で計算されたものを、同じ回路の入力ビットとして与えることができる、という点である。ただし、この場合、現時点での入力ビットではなく、次の時点の入力と同時に与えられる。

図4は、こうした仕組みを仮定した概念図であるが、実際にはその実現のために、いろいろな技術が必要である。(以下に興味のある方のために、関連技術の簡単な解説を付け加えた。)

解説2:順序回路のための技術

図4のような計算を実際に実現しようとしたときの一番の問題は、0や1などの入力信号がどのタイミングで来るか?という点である。このようにタイミングをとることを同期をとるという。

現在使われているほとんどの回路では、クロックという仕組みで実際に同期をとるようになっている。簡単に言えば、「いっせいの、せっ!」と掛け声をかけてくれる誰かがいて、その掛け声に合わせて信号が次の素子に送られる、という仕組みである。当然、この掛け声かけのタイミングが回路の計算の最小時間になる。そのタイミングの頻度を表わすのにもHzが使われている。たとえば、1.2GHzというと、1秒間に1.2×10回(12億回)、掛け声をかけるという意味である。したがって、1.2GHzの回路では、一番簡単な(基本的な)演算ならば、1秒間に12億回できるかもしれないが、それより早い計算はできない。

 

2.2.3 計算化への道(その3):プログラムもデータである!という発見

ここまで計算化のために「計算」の基本要素について説明してきた。つまり、基本的な計算を行なう論理演算ゲートと順序回路の繰り返しの仕組みである。この二つの要素を、もう少し抽象的に考えてみよう。

抽象的に「繰り返し」を議論するための鍵となるのが「状態」である。順序回路が組み合わせ論理回路と大きく違う点は、時間経過の概念が入ってきている点である。時間経過は「繰り返し」を議論するために必須である。計算を時間を追って行っていく中で変化するものが「状態」であり、次の時点に計算途中の情報を伝えるのも「状態」である。

具体的に説明しよう。プログラムでは変数という概念が登場する。これは数学における変数とは異なる。データをたくわえておく「箱」と思った方がよいだろう。たとえば、数が一つしまわれている、と考えてもよい。このような箱(変数)をたくさん用意しておき、その値を順次書き換える(上書きする)ことによって、計算途中の値をしまっておくのである。

この変数の値が「状態」である。変数を通して、ある時点の計算で得られた値を「繰り返し」の次の時点に引き継ぐのである。たとえば、足し算の計算を図4のような「繰り返し」で行なうときに、iビット目同士の和によって生じる繰り上がりを保持するのが変数である。それが次の繰り返しでi+1ビット目の計算に用いられるのである。

解説3:プログラムにおける変数

プログラムでは「変数」という概念が登場する。これは数学で用いられる変数とは異なる。数学では一度決まると変数の値は不変だが、計算の世界では代入という操作で値を変えることができる。変数は計算途中の値をしまっておく箱と考えた方がよいだろう。

変数に格納させる値として、ここでは自然数を用いることにする。その場合には論理値の基本演算に対応するものは自然数に対する基本演算である。ここでは+1、-1の計算だけに限ることにしよう。つまり、変数に格納させている値を1増やす/減らす計算である。また順序回路の「繰り返し」に対応するのは、基本演算の組み合わせを必要なだけ繰り返すことである。ここで「必要なだけ」を指定する方法が必要になってくる。これは「ある指定した変数の値が0になるまで」(変数=0になるまでの繰り返し)という指定のやり方のみを考える。

以上の枠組みのもとで計算化の原理を述べよう。

変数に対する±1の計算と単純な繰り返しだけでは、ごく限られたことしかできないように思われる。しかし、組み合わせ論理回路のところでも述べたように、加算ができ、乗算ができる。さらにそれらを組み合わせれば、○○ができ、××ができる、…という具合に単純なものから段階を追って考えれば、どのように複雑な計算も原理的には組み立てることができるのである。

なお、ここではデータの入出力は考えていない。実際には、データを(デジタル化して)対応する変数に格納したり、計算結果として各変数に格納されているデータを、文字や画像に変換して出力する部分が必要である。これについてはここでは省略している。

以上のような計算の組み立てを示すのは、回路ならば回路図であるが、それを文章(数式)で明確に記述したのがプログラムである。ただし、通常の文章とは異なり、曖昧さを完全に排除した人工的な言語―プログラミング言語―に従って記述されるのが普通である(第3章参照)。(次ページにプログラムの簡単な例を示した。興味のある方は参照されたい。)

以上、順序回路という形で表現されていた「計算」を、もっと抽象的に考え、プログラムという形で表わせることを見た。しかしながら、このままでは、その計算を実現するためには、加算には加算の計算回路が、乗算には乗算の計算回路が必要になってしまう。桁数ごとに回路を作る必要はなくなったが、計算ごとに回路は必要である。

この問題を解決したのが「プログラムもデータである」という考え方の発見である。

  

5 プログラム解釈実行器

プログラム解釈実行器の概念図、実行したプログラム解釈実行器の概念図。実行したいプログラムPとPに与えるデータをDの二つを共にデータとして受け取り、プログラムPのデータDに対する実行を行なうのが解釈実器である。現在のコンピュータの基本構造である。

プログラムそれ自身も文字列であるから2進列で表現できる。その2進列を処理するのがプログラム解釈実行器と呼ばれているものである。プログラミングの分野では、あるプログラミング言語で書かれたプログラムを解釈実行するプログラムを「インタプリタ」というが、プログラム解釈実行器はその原型といえるだろう。

このプログラム解釈実行器を回路化しておけば、どのような計算も、それをプログラム化して解釈実行器にデータとして与えることにより実現することができる。概念的には、これが現在のコンピュータという電子回路なのである。

6:単純なプログラムの例

加算と乗算の計算を、計算化の原理にある(1)、(2)操作のみで表わしてみよう。

プログラム自身もデータとして与えることのできる現代型のコンピュータ(プログラム内蔵方式コンピュータ)の本格的なものはイギリスで1949年に始動したEDSAC(Electronic Delay Storage Automatic Calculatorの略)である。フォン・ノイマンのEDVACの提案に触発されて作られた。このEDSACの前にも電子計算機の一号機ともいえるMark IやENIACが開発されていたが、プログラムをデータと同様に扱うことにより、計算のプログラム化を本格的に実現するコンピュータはEDSACが最初である。この成功により、プログラムを使って計算を設計する、といった考え方が進展し、コンピュータの爆発的な発展が可能となったのである。

用語解説3:フォン・ノイマン

J. フォン・ノイマン(1903~1957)は量子力学の基礎理論のための数学を築いた研究などで有名な数学者であるが、プログラム内蔵方式のコンピュータの創始者としても有名である。

実際、現在のプログラム内蔵型のコンピュータはフォン・ノイマン型コンピュータとも呼ばれている。これはフォン・ノイマンが計算機EDVAC設計レポートで、その考え方を提唱したからである。ただし、最初の発想者は諸説あり、EDVAC設計プロジェクトの中で出てきた考え方、といった方が正しいようである。またチューリングの研究(次節参照)の影響を強く受けた、という説もある。