論理回路
はじめに
この記事では、論理回路について説明します。
論理回路を導入するモチベーション
まず、論理回路を導入するモチベーションをいいます。そもそも、コンピュータを利用する目的は何でしょうか。もちろんそれは人によってまちまちでしょうが、ざっくりと一言で言ってしまうと計算させるためであると言えると思います。では、どのようにしたら機械に計算させることができるでしょうか。また、そもそも”計算”とは何でしょうか。
まずは、人間が計算をするときの基本戦略を考えてみましょう。ここでは、掛け算の筆算を例にして考えます。掛け算の筆算は、まず最初に１の位を計算して、次に１０の位を計算して、・・・と言うようにひと桁同士の掛け算を覚えておき（例えば筆算では、下に記録しておく）、その結果を足し合わせることで、答えを導き出しています。
実は、実際のコンピュータの計算でもこのようなアプローチを利用しています。
つまり、プリミティブな計算表を準備しておき、それらを組みあわせることで複雑な演算を実現しているのです。
掛け算の例に戻ると、人間（日本人）の場合は九九の表覚えていて、その表に書いてある答えを組み合わせることで、複雑な掛け算を実現しています。そして、コンピュータは、記憶力がいいので、九九よりももっと多くの計算結果を覚えさせておくことができます。
実際の計算では、この表として、真理値表という形式を使っています。真理値表とは、次のような個の入力変数の列と、
個の出力変数の列からなる表で、それぞれの変数は、
または
の値を取ります。したがって全ての入力を網羅するために、真理値表は、
個の行を持ちます。そして、この真理値表を現実世界で具体的に実現する手段として、デジタル回路を用います。真理値表の各変数が2進数で表現されているように、すべてのデータは2進数で表現します。また、2進数の一つ一つの桁のことをビットといいます。（なぜ2進数を採用するのかは、2進数で表現するのが一番実装しやすいからであると僕理解しています。）
数の表現方法
では、具体的にコンピュータでは、二進数でどのように数を表現しているのか見ていきましょう。
負の数の表現
負の数を二進数で表現するために、一般にコンピュータでは、負の補数表現という方法が採用されています。負の補数表現では、2進数で正負を表現するために、一番頭のビットを正負を表すのに使います。一番先頭のビットが0ならば、正、1ならば負とします。そして、正の数（及び0）は、通常通り定義します。なので、例えば、4bitの場合を例として考えると、次のように、正の数および０は表わせます。
| 数 | 二進数表現 |
|---|---|
| 0 | 0000 |
| 1 | 0001 |
| 2 | 0010 |
| 3 | 0011 |
| 4 | 0100 |
| 5 | 0101 |
| 6 | 0110 |
| 7 | 0111 |
次に負の数を考えます。さてどのように負の数を定義してあげるのが、一番都合がいいでしょうか。ここで、次のような例として、という計算を考えてみましょう。この右辺を二進数で表すと、0010 - 0110となります。そこで、
を表す二進数表現を????と書くと、（?には0または1が入ります。）右辺の6を移行してきて
となります。すなわち、0010 = 0110 + ????が成立してほしいわけです。これを満たすように、????をさだめると、 ???? = 1010のとき、0110 + 1010 = 10010 となり、繰り上がりを切り捨てることで、2を表す、0010と一致します。このようにして負の数も定めてあげると、負の数は以下の表のように定義できます。
| 数 | 二進数表現 |
|---|---|
| -1 | 1111 |
| -2 | 1110 |
| -3 | 1101 |
| -4 | 1100 |
| -5 | 1011 |
| -6 | 1010 |
| -7 | 1001 |
| -8 | 1000 |
小数の表現
実数は指数関数を利用することで定義します。例えば単精度浮動点小数では、小数を表現するのに32ビット使いますが、次のようにその32ビットの中で、役割が分かれています。ちなみに、この浮動点というのは、誤差が生じるという意味です。
| 占有ビット | 名称 | 役割 | | ---- | ---- | ---- | |0~22ビット | fraction | 仮数部(符号なし整数) | 23~30ビット | exponent | 指数部（符号付き整数） | 31ビット | s | 符号部 |
そして、以下の式によって10進法の数字と対応付けます。
データの精度は232ですが、指数部分があるおかげで大きな数も表せるようになっています。
ブール代数
2進数の演算を実装するにあたって、まずはその演算規則、つまり代数を知る必要があります。我々は、2進数の代数としてブール代数を採用しています。この代数系は電気回路で実現しやすいというメリットがあります。
ブール代数の構成
ブール代数では、全ての変数は、0か1のうちのどちらかとなります。そして、典型的な構成では、次の3つの演算子を定義します。
Logical Sum（論理和）
まず一つ目は、Logical Sum（論理和）です。論理和の標準的な表現法としては、次の3パターンがあります。
- C = A OR B
- C = A + B
- C = A v B
上の表現から分かるように、論理和は、2つの元から1つの元への射影となっています。その射影規則は真理値表によって下のように表せます。
| A | B | C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
- Logical Product（論理積）
二つ目はLogical Product（論理積）です。論理積も論理和と同様に主に3パターンの表現方法があります。
- C = A AND B
- C = A ・ B
- C = A ^ B
| A | B | C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
- Logical Negation（論理否定）
C = NOT A
C = A- C = A`
| A | C |
|---|---|
| 1 | 0 |
| 0 | 1 |
これらの結合で、あらゆる真理値表を実現できる。
想定されるすべての変数を含む論理積を最小項と呼ぶ。
最小項の論理和で表した論理関数のことを加法標準形または論理和標準形という。
例：Z = !ABC + A!BC + AB!C + ABCは加法標準形。
!ABC, A!BC, AB!C, ABCは最小項。ただし!XはXの否定を表す。
組み合わせ回路
組み合わせ回路とはブール代数を実現する回路のことです。
Gates
2入力1出力 AND,OR,NOTをどのようにして表すか。
簡単な論理演算回路（リレー回路） （電気回路） AND＞直列 OR＞並列 NOT＞電磁石で離れるようにすればいい。
＞＞リレー回路は動作が不安定（時間がかかったら、埃が入ると動かなくなったりする）
そこで、トランジスタの登場 AND Gate,OR Gate, NOT Gate（電子回路）
演算の実装
必要な計算の例 - 四則演算 - 論理演算 - シフト演算 - 比較演算
四則計算
足し算
半加算器 真理値表による表現
| x | y | C | S |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
論理回路への実装
いろいろな回路が組める。（ブール代数の式の恒等変換をする。）
全加算器の真理値表
z:繰り上がりしてきた入力
| x | y | z | C | S |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | |
| 0 | 1 | 0 | 1 | |
| 1 | 0 | 0 | 1 | |
| 1 | 1 | 1 | 1 |
これを32個並べると、32bitのコンピュータが実現できる。
キャリー先読み論理回路 ＞桁上げだけ先に計算させてしまう。
引き算
半減算器、全減算器の真理値表を作って、同じように論理回路に実装する。
コンピュータ制御でよく使われる回路
- Decoder, Encoder
- Multiplexer(Selector), De-multiplexer
Parity Check
多数決回路(Majority Circuit)
Decoder
命令を2進数で0~7で定義して、Inputを与えるとそれに応じたシグナルを出す。つまり[tex:｛0,1｝｛0,1｝｛0,1｝ \rightarrow ｛0,1,2,3,4,5,6,7｝]という写像。 機械語の命令を翻訳するのに使う。
Multiplexer
スイッチング。selectorの入力によって、input0とinput1のどちらを流すかを決める。電気信号の流れを制御する。
2-to-1
真理値表による表現
| Input0 | Input1 | Selector | Output |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
ブール代数による表現
[tex: C=(A!S) + (BS)]
電気回路
Parity Checker
エラーがあったときに誤り訂正するための符号化をチェックするやつ。 1bitだけ余分に付加して、必ず信号が偶数になるように符号化する。 1bitの誤りならば、奇数になっているので気付ける。
ALU (Arithmetic Logic Unit)
1bit数を扱う、4bit後の計算機の命令
| op1 | op0 | a | b |
- op1,op0 ... 2bitの命令
00 ... a ^ b
01 ... a v b
10 ... a + b
11 ... NOP
and,or,加算器をくみあわせる。
- 32個つなげれば、32bitの計算機ができる。
- 入力を4bitより増やせばよりたくさんの命令を搭載できる。
PLA(Programmable Logic Array)
どんな演算でもいらないところをユーザーが焼き切ってしまえば、実現できる。
カルノーマップ
加法標準形から回路を作ると、回路の数が大きくなってしまう。 カルノーマップ...回路を簡略化するための表 カルノーマップは4入力が限界、、、。それ以上はコンピュータに計算させる必要がある。
