情報ラボ ＞ 論理回路
コンピュータの中では、スイッチの組み合わせだけで計算が行われています。
いま選んでいる状態の行が、黄色く光っています。
XOR と AND を1つずつ組み合わせるだけで、足し算ができます。スイッチを押してみてください。
2進数では 1 + 1 = 10 です。下の桁が S、上の桁（くり上がり）が C にあたります。
半加算器は、下の桁からのくり上がりを受け取れません。入力を3つにしたものが全加算器です。 中身は、半加算器2つとOR回路1つでできています。
数字をクリックして、2つの4ビットの数を決めてください。くり上がりが右から左へ伝わっていく様子が見えます。
コンピュータの中で計算をしているのは、無数の小さなスイッチです。電気が流れているか、いないか。この2つの状態を1と0に対応させ、その組み合わせであらゆる処理を行っています。
このスイッチの働きを整理したものが論理回路です。入力の組み合わせに対して、出力がどうなるかというルールを持っています。
論理回路の基本は、AND・OR・NOT の3種類です。この3つを組み合わせれば、どんな複雑な処理も作れることが知られています。
入力が両方とも1のときだけ、出力が1になります。「AもBも」という条件です。
身近な例では、電子レンジがあります。「スタートボタンが押されている」かつ「扉が閉まっている」の両方が満たされたときだけ動きます。
入力のどちらか一方でも1なら、出力が1になります。「AまたはB」という条件です。
非常ベルが分かりやすい例です。1階のボタンか2階のボタンか、どれか1つでも押されれば鳴ります。
入力を逆にします。1が入れば0を、0が入れば1を出します。入力は1つだけです。
| 名前 | 意味 | 出力が1になるとき |
|---|---|---|
| NAND | ANDの否定 | 両方が1のとき以外 |
| NOR | ORの否定 | 両方が0のときだけ |
| XOR（排他的論理和） | どちらか一方だけ | 2つが異なるとき |
XORは「違っていれば1」という回路で、誤り検出や暗号でよく使われます。2つの値が同じかどうかを調べるのに便利だからです。
入力のすべての組み合わせに対して、出力がどうなるかを一覧にした表を真理値表といいます。
入力が2つなら、組み合わせは 00・01・10・11 の4通りです。入力が3つなら8通り、n個なら2のn乗通りになります。真理値表を作れば、その回路の動きを完全に説明できます。
論理回路で本当に計算ができるのか。実際に確かめてみましょう。1桁の2進数の足し算を考えます。
| 計算 | 結果 | 和（S） | くり上がり（C） |
|---|---|---|---|
| 0 + 0 | 0 | 0 | 0 |
| 0 + 1 | 1 | 1 | 0 |
| 1 + 0 | 1 | 1 | 0 |
| 1 + 1 | 10 | 0 | 1 |
ここで、和（S）の列をよく見てください。2つが異なるときだけ1になっています。これはXORとまったく同じです。
次に、くり上がり（C）の列を見ます。両方が1のときだけ1です。これはANDそのものです。
つまり、XORとANDを1つずつ並べるだけで、1桁の足し算ができる回路になります。これを半加算器といいます。上のツールで実際に動かせます。
半加算器が足せるのは、A と B の2つだけです。しかし2桁目より上では、下の桁からのくり上がりも足さなければなりません。入力が3つ必要です。
そこで、A・B・下からのくり上がり（Cin）の3つを足して、和（S）と上へのくり上がり（Cout）を出す回路を作ります。これが全加算器です。
全加算器は、半加算器を2つ使って作れます。まず A と B を1つ目の半加算器で足し、その和と Cin を2つ目の半加算器で足します。2つの半加算器のどちらかでくり上がりが出たら、それが Cout になります。「どちらか」なので OR 回路でまとめます。
半加算器には弱点があります。下の桁からのくり上がりを受け取れないのです。そこで入力を3つ（A、B、下からのくり上がり）にした全加算器を作り、それを桁数だけ並べます。
8桁の足し算なら全加算器を8個、64桁なら64個。実際のCPUの中では、この構造がびっしりと並んでいます。あらゆる計算の土台が、AND・OR・NOTの組み合わせでできているのです。
これらの回路は、トランジスタという小さな部品を組み合わせて作られています。トランジスタは電気の流れを制御するスイッチで、現代のCPUには数百億個が詰め込まれています。
興味深いことに、NANDだけですべての論理回路を作れることが知られています。ANDもORもNOTも、NANDの組み合わせで表現できるのです。この性質を完全性といい、実際の製造でも、同じ部品を並べればよいという利点があります。
論理回路の考え方は、ハードウェアだけの話ではありません。プログラムの条件分岐でも同じ論理が使われます。
これはANDです。多くのプログラミング言語では、ANDを「and」や「&&」、ORを「or」や「||」、NOTを「not」や「!」と書きます。表現は違っても、考え方は論理回路と同じです。
論理には、便利な変換の決まりがあります。代表的なのがド・モルガンの法則です。
言葉で確かめてみましょう。「雨でも雪でもない」は「雨でない、かつ、雪でない」と同じです。逆に「雨と雪が両方ではない」は「雨でない、または、雪でない」になります。
この法則は、条件式を書きかえるときに役立ちます。プログラムの条件が複雑になったとき、より読みやすい形に整理できるのです。回路の設計でも、使う部品の種類を減らすために使われます。
ここまでの回路には、共通する性質があります。入力が決まれば出力が決まり、それ以前の状態は関係ありません。こうした回路を組み合わせ回路といいます。
しかしコンピュータには、値を覚えておく仕組みも必要です。そこで、出力を入力に戻す構造を作ります。すると回路が状態を保持できるようになり、1ビットの記憶装置になります。これをフリップフロップといい、順序回路と呼ばれます。
メモリやレジスタは、この記憶回路を大量に並べたものです。計算する回路と記憶する回路。この2つが揃って、コンピュータが成り立っています。