本シリーズは、論理回路で電卓を作ろうと思い、そのために勉強した結果を残しているものだ。
前回は、いきなりだが少し横道に逸れ、2進数について色々と解説した。
特に、マイナスの表現である2の補数は、計算において非常に重要な考え方だ。
まだ実際に使うのはしばらく先になるとは思うが、しっかり覚えておこう。
以下がその記事だ。
さて、今回はまた論理回路に戻ってくる。
初回、3つの基本となる回路を紹介した。
覚えているだろうか、AND、OR、NOTだ。
その3つだけでも大丈夫…なのだが、他にもタイトルに入れてある3つは非常に使うものだ。
これも、覚えておくと回路がよりシンプルに書けるようになることがある。
また、初回にあまり解説せずに使ってしまっていた表や式などについても、改めて見ていく。
それぞれの表記にも、少しずつ慣れていこう。
追加の3回路
さて、では早速3つの追加から見ていこう。
XOR
一つ目はこのXOR(eXclusive OR：イクスクルーシブオア)。
日本語で言うと、排他的論理和、というものだ。
これは何かというと、ANDやORと同じく2つの入力を受け取り、1つの出力をする回路なのだが、出力がちょっと面白い。
何かというと、2つの入力が異なる時に、1を出力する。
前々回の言葉で言えば、2つのスイッチが異なる状態の時に、ランプが点灯するのだ。
入出力の関係を以下の表に示そう。
| 入力1 | 入力2 | 出力 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
…さて、どこかで見たことがあるかもしれないというか見覚えがあってほしい。
これ、実は初回の例で出した、2か所スイッチがある廊下の電気の例そのままなのだ。
つまり、このXORを知っていれば、廊下の電気はこれで実現されている、と即答できる。
まあ…それを知っていても、日常生活で使う機会があるかは知らない。
NAND、NOR
さて、この二つは同時に見てしまおう。
それぞれ、ANDとORの先頭にNがついている。
読みはナンドとノア。
これらはいずれも2入力を受け取り、ANDやORの結果を否定した(=0と1を入れ替えた)ものが出力になる。
そのため、AND、もしくはORとNOTを組み合わせることでも実現は可能だ。
表にまとめると以下の通り。
| 入力1 | 入力2 | NAND | NOR |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
実は、NAND、もしくはNORの1種類だけでもAND、OR、NOTの全てを表現でき、初回にも書いた通り、この3つで大体の回路は実現できる。
この性質は完全性と呼ばれていたりするが、今回の電卓にはあまり関係がないので、軽くオマケで補足するに留め、詳細は飛ばしてしまおう。
もし、NANDもしくはNORオンリー縛りで回路を組みたい方がいらっしゃったら、まずはそれのみでAND、OR、NOTを作るところから始めてみよう。
それができればあとは普通に回路を作った後置き換えるだけでいいので、面倒なだけでそこまで難しくなかったりもする。
論理演算
ここまでで6種類の回路が分かり、それらを組み合わせることもできるようになった。
…が、これだけでいきなり回路を組むのも難しいだろう。
そこで、幾つかある方法で、何をどう組み合わせて期待する結果を得るための回路をつくるかを考えなければいけない。
まあ、初回の最後の方にやった、表書いて式を求めて論理回路図を書いて、みたいなことを想像してもらえばいいだろう。
それを、改めてもう一度見直していこう。
真理値表
一つ目は、真理値表というもの。
これは、考えられる入力と出力の組合せを全て表形式にまとめたものだ。
ANDからNAND、NORまでそれぞれの説明時に、入力がこうだったら出力はこうなるよ、という表を毎回出していたと思う。
それが真理値表だと思ってくれて構わない。
左側に入力を全て並べ、その右に出力を並べる。
その下から入力の0、1と、それに対して期待する結果を同じ行に書く、という感じだ。
この利点は、モレ、ダブりなく入出力の関係を正確に表せること。
入力は2進数の考え方で並べていけば、全てを網羅することができるだろう。
欠点は、入力が多くなるとそれだけ表も膨大になること。
入力が1つ増えるごとに、行は2倍になっていく。
例えば6入力になると、その行数は64行だ。
これならまだいいが、今回作りたい電卓は最低でも16入力。
内訳は0から9に対応するボタンと四則演算、イコール、リセットのボタン。
本当は電卓の動きは真理値表では書き表せないのだが、もし可能だったとしても、この時点で6万行を超える表となってしまう。
他にも作りたいなと思っているものがあるので、さらに倍増する可能性もある。
さすがに、これを作るのは現実的ではないだろう
改めて、今回までに紹介した6つの基本回路の真理値表を出しておこう。
| 入力1 | 入力2 | AND | OR | NOT(入力1のみ記載) | XOR | NAND | NOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
ブール代数
聞き馴染みは薄いと思うが、初回にやった数式での表現がこのブール代数だ。
各入力を変数として持ち、その式の計算結果で出力を表すというもの。
これも正確に表現でき、かつ直感的にもある程度分かりやすいのがメリットだろう。
基本的な書き方は初回に書いてしまったので、こちらを参照してほしい。
ここでは、6つの基本回路を改めて書いておく。
なお、XORにはまた別の記号が用意されている。
これもよく使うので、覚えておいて欲しい。
$$\begin{eqnarray}
AND(S_1, S_2) & = & S_1 S_2 \\
& = & S_1 \cdot S_2
\end{eqnarray}$$
$$OR(S_1, S_2) = S_1 + S_2$$
$$NOT(S_1) = \overline{S_1}$$
$$\begin{eqnarray}
XOR(S_1, S_2) & = & S_1 \oplus S_2 \\
& = & S_1 \overline{S_2} + \overline{S_1} S_2
\end{eqnarray}$$
$$\begin{eqnarray}
NAND(S_1, S_2) & = & NOT(AND(S_1, S_2)) \\
& = & \overline{S_1 S_2}
\end{eqnarray}$$
$$\begin{eqnarray}
NOR(S_1, S_2) & = & NOT(OR(S_1, S_2)) \\
& = & \overline{S_1 + S_2}
\end{eqnarray}$$
なお、今各素子の後ろに括弧で入力を表しているが、これは分かりやすくするためのものだ。
論理回路図
他にもMIL記法と呼ぶらしいが、図で各演算を組み合わせるのがこの論理回路図だ。
これも具体例をこれまでに出しているので、そんなに問題ないと思う。
…と思ったが、まだ今回紹介した3回路については記号を紹介していなかった。
以下に載せておくので、参考にしてほしい。
左からXOR、NAND、NORだ。
なお、初回に触れたORの記号が正確じゃないかも、という話。
今出したうち、XORとNORについても同じ形が入っていて、そこも該当する。
これなのだが、初回の内容はやはり正確ではなかった、申し訳ない。
厳密には、この先頭から出る出力の部分(NORは丸がくっついている部分)は、今出した図のように丸ではなく尖っている。
今回からDigitalという論理回路シミュレータを使って進めさせてもらうので、正確な形になっているはずだ。
さて、改めて論理回路図の書き方を見ていこう。
入力から線で回路記号を繋いでいき、最後は出力へ。
線が分岐するところは黒丸を置き、ただ線が交差しているところは互いに影響を与えない。
大まかな書き方はこれだけだろう。
これからも具体例を書いていくので、それを見て慣れていただきたい。
ブール代数の演算規則
さて、今紹介したうちの一つ、ブール代数について。
計算式で表現しているので、幾つか変形に使える規則があると嬉しいだろう。
ということで、基本的な変換規則をざっと紹介していこう。
まずは一つの入力\(S\)に関するもの。
$$S + 0 = S$$
$$S \cdot 0 = 0$$
$$S + 1 = 1$$
$$S \cdot 1 = S$$
$$S + S = S$$
$$S \cdot S = S$$
$$S + \overline{S} = 1$$
$$S \cdot \overline{S} = 0$$
$$\overline{\overline{S}} = S$$
このあたりは、意味を考えれば自明だろう。
次に、2入力\(S_1, S_2\)に関するもので、まずは交換法則。
$$\begin{eqnarray}
S_1 + S_2 & = & S_2 + S_1 \\
S_1 \cdot S_2 & = & S_2 \cdot S_1
\end{eqnarray}$$
ようは、ANDとORは演算子の前後を入れ替えても結果は変わらないよというもの。
今は二つしか書かなかったが、XOR、NAND、NORも成り立つ。
次に、入力を3つ(\(S_3\)を追加)に増やして結合法則。
$$\begin{eqnarray}
S_1 + (S_2 + S_3) & = & (S_1 + S_2) + S_3 \\
S_1 \cdot (S_2 \cdot S_3) & = & (S_1 \cdot S_2) \cdot S_3
\end{eqnarray}$$
通常の計算の加算、乗算と同じく、同じ演算ならどこからその演算をしても結果は変わらないよというものだ。
これにより、今後3つ以上の入力に対して全てANDやORを取る場合は、以下のように括弧を省略することにしよう。
$$S_1 \cdot (S_2 \cdot S_3) = S_1 S_2 S_3$$
そして、分配法則。
$$\begin{eqnarray}
S_1 \cdot (S_2 + S_3) & = & S_1 \cdot S_2 + S_1 \cdot S_3 \\
S_1 + (S_2 \cdot S_3) & = & (S_1 + S_2) \cdot (S_1 + S_3)
\end{eqnarray}$$
通常の計算のイメージに引きずられると下がちょっと違和感があるかもしれないが、このようになっているので気を付けよう。
これは、真理値表を見た方が分かりやすいかもしれない。
一つ目の式については以下の通り。
| \(S_1\) | \(S_2\) | \(S_3\) | \(S_2 + S_3\) | \(S_1 \cdot (S_2 + S_3)\) | \(S_1 \cdot S_2\) | \(S_1 \cdot S_3\) | \(S_1 \cdot S_2 + S_1 \cdot S_3\) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
左から5列目と一番右の列がそれぞれ式の左辺、右辺になっている。
これが一致していることが分かるだろう。
二つ目の式は以下だ。
| \(S_1\) | \(S_2\) | \(S_3\) | \(S_2 \cdot S_3\) | \(S_1 + (S_2 \cdot S_3)\) | \(S_1 + S_2\) | \(S_1 + S_3\) | \((S_1 + S_2) \cdot (S_1 + S_3)\) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
同じく、左から5列目と一番右を見比べてみると、一致していることが分かるだろう。
最後、有名なド・モルガンの定理。
$$\begin{eqnarray}
\overline{S_1 + S_2} & = & \overline{S_1} \cdot \overline{S_2} \\
\overline{S_1 \cdot S_2} & = & \overline{S_1} + \overline{S_2}
\end{eqnarray}$$
これも、真理値表で比べてもらうと分かりやすいと思う。
| \(S_1\) | \(S_2\) | \(S_1 + S_2\) | \(\overline{S_1 + S_2}\) | \(\overline{S_1} \cdot \overline{S_2}\) | \(S_1 \cdot S_2\) | \(\overline{S_1 \cdot S_2}\) | \(\overline{S_1} + \overline{S_2}\) |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
組合せ回路と順序回路
折角なので、ここまで進んでしまおう。
組合せ回路とは、これまで紹介した内容で出力を行う回路のこと。
もう少し書くと、入力が決まると出力が一意に、それまでの状態に関係なく決まる回路…と言えばいいだろうか。
というのも、後の方で順序回路というものが出てくる。
こちらは、現在の出力を再度入力に使い回し、情報の記憶などが行えるようにしたものだ。
これと対比させると分かりやすいかなと思う。
例えば、初回にも出した廊下の電気スイッチ。
これは、2つの入力が異なっていれば電気がつき、同じなら消えた。
つまり、スイッチの状態のみで電気がつくかどうかが決まるので、組合せ回路だ。
それに対し、電卓では一度入力された内容を保持しておき、その後入力した別の内容と計算する必要が出てくる。
この、保持するという部分により、その時点での入力が同じでも別の結果になることがあるので、順序回路になる。
この順序回路からが論理回路の本当に面白いところ…なのだが、実際に内容に入るのはまだもうちょっと先になりそうだ。
おわりに
今回は追加で3つの回路XOR、NAND、NORを紹介し、3つの論理演算を改めて解説した。
特に論理演算は今後も回路の表現に使うので、それも通して慣れていこう。
さて、次回はいよいよ計算を始めていこうと思う。
前回も書いた通り、計算は2進数で行い、さらに四則演算の全てを加算のみで行うことができる。
その加算を行う回路には、半加算器、全加算器という名前がついており、それを次回解説していこう。
2021/11/24追記
次回の内容を公開した。
予定通り半加算器と全加算器、そしてそれらを組み合わせて4桁の加算の実装。
そして、結果がおかしくなるオーバーフローの検出と、ついでに減算までできるようにしてみた。
ほんの少しだが、電卓に近づいた…だろうか。
オマケ：完全性
さて、本文中にさらっと書いてしまった完全性というものを少しだけ補足しておこう。
この完全性とは、その回路のみで任意の組合せ回路を実現できる性質のことだ。
初回、AND、OR、NOTで大体の回路が実現できると書いたが、この「大体」は組合せ回路のことを意図して書いたものだ。
この証明は省略するが、ようはこの3つだけで、組合せ回路は全て作れる。
…実はANDとNOTでORを、ORとNOTでANDを実現できるので、この2通りでも完全性を持っている。
やり方は、ド・モルガンの定理の両辺をNOTにするだけだ。
$$\begin{eqnarray}
S_1 \cdot S_2 & = & \overline{\overline{S_1} + \overline{S_2}} \\
S_1 + S_2 & = & \overline{\overline{S_1} \cdot \overline{S_2}}
\end{eqnarray}$$
で、これも詳細は省くが、本編にも書いた通りNAND単体、あるいはNOR単体でもAND、OR、NOTを実現できる。
そして、この3つで完全性があるため、機械的に置き換えることでNAND、NOR単体も完全性を持つことになるのだ。
正直電卓にはあまり影響がないのでここでは解説しないが、気になれば証明方法などを調べてみると面白いだろう。
コメント