論理ゲート
コンピュータシステムの理論と実践の学習内容のダンプ。
すべての要素は論理ゲートからできている。これは記憶媒体も同じ
ブールゲート
ブール関数を物理的に実現したもの。
ブール式
AND , OR, NOT から成る。
AND（論理積）: どちらも1でTrue
OR（論理和）: どちらか1でTrue
NOT（否定）: 0だったらTrue
正準表記
すべてのブール関数は、少なくともひとつの正準表現から構築できる。
こんな感じのやつ
x = 0, y = 1, z = 0 なら、
つまり、どのようなブール関数であってもAND OR NOTで表現できる。
AND OR NOTの回路があればすべての論理ゲートを構築できることになる。
入力のブール関数
さらに、面白いことにAND OR NOT はずべてNand (または Nor)から作ることができる。Nandさえあればどのような論理ゲートも形成できる。
論理ゲート
ブール関数を実装するための物理デバイス。
n個の変数を受け取り、m個のバイナリを返すブール関数
最も単純なゲートは、トランジスタと呼ばれこれが無数に合わさっている。
ハードウェア記述言語 (HDL)
ゲートの回路をソフトウェア上でシュミレートし、回路を作ることができるやつ
Nandゲート
Nandは、Not Andなので、a, b どちらも1の時０となり他のパターンはすべて1となる。
これを使用して論理ゲートを作成していく。
基本論理ゲート
・コツは、論理式を書いていって、それをNANDで表現すること。ド・モルガンの法則とNOT AND = NANDという性質を使う
Not
1入力のNotゲートはインバータと呼ばれる
0 -> 1, 1 -> 0 に変換する
NOT A = A Nand A
Nand回路に同じ入力をすれば否定になる
And
式で表現すると
A AND B = NOT(NOT(A AND B)) = NOT(A NAND B)
よって
(A NAND B) NAND (A NAND B)
となる
Or
ド・モルガンの法則より
であるから、NOT A and NOT B 全体の否定を取ることで ORが表現できる
つまり、
(A Nand A) Nand (B Nand B) となる
Xor
双方が異なるときにTrueとなる
論理式で表すと以下
$ ({A} \land \neg{B}) \lor (\neg{A} \land {B})$
つまり、(A AND NOT B ) OR (NOT A AND B) を表現すればいい
ド・モルガンの法則を適用すると
$ ({A} \land \neg{B}) \lor (\neg{A} \land {B})$ = $ ({A} ; {NAND} ; \neg{B}) ; {NAND} ; (\neg{A} ; {NAND} ; {B})$ となる
NOT A = A Nand A であるから、あとはこれを書いていくだけ
マルチプレクサ
3入力回路。選択ビットと呼ばれる入力が加わる。選択bitで入力を選びそちらを出力する。0 => a, 1 => b
論理式は以下。Sは選択bit
であるから、
\neg S = S \, \text{NAND} \, S A \land \neg S = A \, \text{NAND} \, (S \, \text{NAND} \, S) B \land S = B \, \text{NAND} \, S Y = (A \, \text{NAND} \, (S \, \text{NAND} \, S)) \, \text{NAND} \, (B \, \text{NAND} \, S)
となる
デマルチプレクサ
入力が一つ行われると、選択bitにしたがって２つの出力に変換される。0 => a=in, b=0, 1 => a=0, b=in
出力は２つ
Y_0 = \overline{S} \land D Y_1 = S \land D
多ビットの基本ゲート
複数のビットからなる配列を操作する「バス」という基本単位から作られている
32bitAND回路は、32bitの入力が2本、32bitの出力が1本ある。前段の基本ゲートを束ねて適切なピンアサインをすればOK。
これは先程作った論理ゲートを必要本数束ねることで実現される
多入力の基本ゲート
複数の入力に対して論理演算を行うゲート。これも上記基本ゲートを束ねればOK
多入力OR
n入力のnビットの少なくとも1つが1であれば1を出力する。それ以外は0。
CHIP Or8Way {
IN in[8];
OUT out;
PARTS:
Or(a=in[0], b=in[1], out=out0);
Or(a=out0, b=in[2], out=out1);
Or(a=out1, b=in[3], out=out2);
Or(a=out2, b=in[4], out=out3);
Or(a=out3, b=in[5], out=out4);
Or(a=out4, b=in[6], out=out5);
Or(a=out5, b=in[7], out=out);
}
こんな漢字で、全体のORを取れば実現できる
多入力マルチプレクサ
複数の入力と複数の選択bitによって出力を一つに選択する。これもMuxの重ね合わせで実現できる
CHIP Mux8Way16 {
IN a[16], b[16], c[16], d[16],
e[16], f[16], g[16], h[16],
sel[3];
OUT out[16];
PARTS:
Mux16(a=a, b=b, sel=sel[0], out=out1);
Mux16(a=c, b=d, sel=sel[0], out=out2);
Mux16(a=e, b=f, sel=sel[0], out=out3);
Mux16(a=g, b=h, sel=sel[0], out=out4);
Mux16(a=out1, b=out2, sel=sel[1], out=sout1);
Mux16(a=out3, b=out4, sel=sel[1], out=sout2);
Mux16(a=sout1, b=sout2, sel=sel[2], out=out);
}
いきなり複数の選択bitを考えると混乱する。
ポイントは、選択bitを順次使用して束ねて行くこと。一回選択bitが使われるたびにまとまっていく感覚
多入力デマルチプレクサ
一つの入力を複数のピンに出力する。選択方法は選択bitによって行われる。
これもDemuxを使用して表現できる。
CHIP DMux8Way {
IN in, sel[3];
OUT a, b, c, d, e, f, g, h;
PARTS:
DMux(in=in, sel=sel[2], a=abcd, b=efgh);
DMux(in=abcd, sel=sel[1], a=ab, b=cd);
DMux(in=efgh, sel=sel[1], a=ef, b=gh);
DMux(in=ab, sel=sel[0], a=a, b=b);
DMux(in=cd, sel=sel[0], a=c, b=d);
DMux(in=ef, sel=sel[0], a=e, b=f);
DMux(in=gh, sel=sel[0], a=g, b=h);
}
これも、いきなり複数の選択bitを考えると混乱する。
イメージとしては、最上位選択bitから一歩ずつ分割を行っていくことを考える。
Discussion