Hatena::ブログ(Diary)

言語ゲーム このページをアンテナに追加 RSSフィード Twitter

とあるエンジニアが嘘ばかり書く日記
ホームページ | blog | twitter

2009-12-02

[] 半加算器とは何か?

P1060931

この日記に制作過程をアップしてる半加算器について書きます。

コンピュータが二進法で動いている!という話はみんなも聞いた事があると思います。私たちが普段計算する時は十進法というのを使います。数字が 0 から 9 まであって、9 に 1 を足すと桁が繰り上がって 10 になるという物です。これが二進法だと、数字が 0 と 1 しか無くて、1 に 1 を足すと桁が繰り上がって 10 になります。すこし十進法と二進法の数字を並べるとこんな感じです。

十進法二進法
00
11
210
311
4100

めまぐるしく繰り上がりが起こるので忙しいけど、電気で計算するには二進法の方が都合が良いので、コンピュータは二進法を使って計算します。この二進法の足し算の基本となる、一桁の足し算だけをする仕組みを半加算器と呼びます(たまーに二進法以外でも半加算器という言葉を使うらしいです)。具体的に半加算器が出来る計算を書きます。括弧の中は十進法です。

  • 0 + 0 = 00 (0)
  • 0 + 1 = 01 (1)
  • 1 + 0 = 01 (1)
  • 1 + 1 = 10 (2)

という風に、入力が二つの二進数。出力が二桁の二進数になります。ここで、何故「半」加算器と呼ぶかと言うと、この半加算器を二つ繋げた物を全加算器と呼ぶからです。詳しくは wikipediaをみてください。この半加算器を沢山並べると、大きな数の足し算でも出来るようになります。

だれが半加算器を発明したのでしょう?とても気になる疑問ですが、実は私も知りません。加算器の発明者としては 17 世紀のパスカルが有名です。でもパスカルの十進法の加算器と二進法の加算器の間に大きな飛躍があると思うのです。十進法の計算器が人間の計算をただ模倣した物なのに対して、二進法には、論理(ある事実が「ある」か「ない」かを考える事)と計算の同一視という決定的に新しい視点があります。例えて言うと、長年鳥の模倣をして羽ばたき飛行機を作って失敗した発明家が、羽ばたきをやめて始めて上手く飛べたように、計算器が人間の模倣をやめて二進法を採用した事が始めて大規模な計算機に結びついたのです。

そんな大切な半加算器ですが、発明者が謙虚すぎたのか同時多発的に複数の人が思いついたのか、発明扱いされていない事は大変残念だと思います。もし他に二進数の半加算器(もしくは XOR 回路)の発明者をご存知の方がいらしたら教えてください!

さて、ふつうの半加算器は電子回路で出来ていますが、私が作ってるのはそれを木で作ったモデルです。トランジスタで出来た物も、木で出来た物も半加算器である事に違いは無いので、「モデル」では無くて「本物」の半加算器と言っても良いと思います。このような物に一体どういった意味があるのでしょうか?

私の最初の動機は、半加算器の基礎である論理演算について具体的なイメージを心の中に作りたかったからです。論理演算はプログラマに絶対必要な物ですし、今後普通に教養として必要になって来ると思います。

論理演算について考えるとき、一般的には比喩として、真偽値と接続詞を使います。「真かつ偽ならば真」とかいうやつです。この方式の欠点は、「かつ」「ならば」という用語が、日常の意味とは微妙に違う事と、二つの論理演算同士の関係を捉える事が難しい事です。例えば、ド・モルガンの法則をこのやり方で書くと、

  • (P または Q)の否定 = Pの否定 かつ Qの否定

となりますが、これでは何の事やら分かりません。しかし、例えばこれをメカ的に作ると、ド・モルガンの法則というのはようするに同じ回路のラベルを変えただけだという事がすぐに分かります。言葉とメカで何が違うかというと、言葉を使った理解には P と Q それぞれの真偽値について一つ一つ例を挙げて確認してゆく必要がありますが、人間はすでに機械の動作について心理的モデルが程度出来上がっているので、一旦メカと真偽値の状態を対応してしまえば、あり得る状態の全てを四次元(時間+空間)的スナップショットとして捉えるのは簡単だからです。

また、論理という抽象的な物をメカに変換していく中で、面白い事が沢山ありました。一つ挙げると、半加算器が左右対称形だと言う点です。加算器の一桁目を現す論理である XOR を真理表で書いて下半分を反転させると上下対称になるので、それが反映されているだけですが、普段加算と対称性を結びつけて考えた事がなかったのでちょっと新鮮でした。

ABA XOR B
000
011
101
110

論理を機械で作るだけで何か新しい発見があるとは思いませんが、論理を手に触れられる物として作る事で、訓練された人でないと難しい論理の領域に普通の人が辿り着くための強力な手引きになるのでは無いかと思います。これが私が論理機械を作る理由です。

トラックバック - http://d.hatena.ne.jp/propella/20091202/p1

カレンダー
<< 2009/12 >>
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
最新コメント一覧