この記事では，組み合わせ回路についてのメモを書いていく．
Turning Completeをプレイしているうちに自分の知識が足りないと感じ，勉強しました．
今回は最後らへんに加算器についてまとめてある．
この記事は，自分用のメモなので勉強したいならうさぎ先生ととり先生の計算機工学の動画を見るとよいと思います．
XOR
奇数パリティの回路 (XOR)
奇数パリティの回路
１となる変数の数が奇数個のとき１になる回路
f = x1⊕x2⊕x3⊕・・・
奇数パリティの回路はXORを使って作られる．
例えば，Y = A⊕B⊕Cは3入力の奇数パリティで１の数が１，３のとき１を出力し，０，２のとき０を出力する．
ここで大切なのが，XORは多入力AND，ORと違って多入力XORゲートを作ることができないので，2入力XORを組み合わせて作るsかない．
偶数パリティの回路 (XNOR)
これは，奇数パリティの回路に否定をとれば実装できる．
つまり，XNORを使う．
例えば，Y = not(A⊕B⊕C)は3入力の偶数パリティで１の数が１，３のとき０を出力し，０，２のとき１を出力する．
XORとインバータの数
上のようなゲートと等価なゲートを考える．
1番上のゲートは入力に否定をとってXORに入力している．
真理値表を考えればわかるが，式で考えると以下のようになる．
よって，1番上のゲートはXORである．
真ん中のゲートは1番上のゲートに否定を取っただけなので，XNORである．
1番下のゲートも式変形していくと下のようになる．
よって，1番下はXORゲートである．
このことから，わかるのが排他的論理和は交換則が成り立つため，どこに否定を取ろうが関係ないのである．
インバータの数が奇数であれば⊕１になるのでXNOR
インバータの数が偶数であれば⊕０になるのでXOR
となる．
XORのゲートを構築
XORは下のような回路で表される
Z = not(A・B＋not(A+B))
= not(A・B＋not(A)・not(B))
= not(not(A⊕B))
= A⊕B
この回路は2入力NANDゲートの2.5倍である．
また，下のような回路でもXORを実装できる．
以前まではNAND4個分であるからこの回路が最も面積を取らないと思っていたが，これはNAND4個分であるため上の回路よりも面積をとる．
このことからもTurning Complete(論理ゲートを組むゲーム)で最も効率的な回路を考えるとトランジスタのことまで考えないといけないのでやめた方がいい．
一致回路
一致回路
すべての入力が一致するとき１を出力する回路
２入力ならXNORゲート
下の真理値表は3入力の一致回路．
一致回路は入力がすべて０とすべて１の場合についての最小項を足す
Z = A・B・C・…＋not(A)・not(B)・not(C)・…
2入力ならXNORゲートで表され，以下の式で表されるため上の式と同じ形であるとわかる
Z = A⊕B ＝ A・B＋not(A)・not(B)
| A | B | C | 出力 (Equality) |
|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
m and only m回路
m and only m回路
1である入力がm個のとき1を出力する回路
2入力でm = 1ならXORゲート
下の真理値表は3入力の1 and only 1回路
一致回路と違い項の最小項の数が組み合わせの数なので多くなる．
よってあまり使われない．
2入力の1 and only 1回路なら
| A | B | C | 1の数 (Σ1) | 出力 (m=1 の場合) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 2 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 2 | 0 |
| 1 | 1 | 0 | 2 | 0 |
| 1 | 1 | 1 | 3 | 0 |
マルチプレクサ(セレクタ)
マルチセレクタ
入力を選択する回路
制御信号Sが０のとき，出力ZはA0と同じ値
制御信号Sが１のとき，出力ZはA1と同じ値
マルチプレクサはプログラミングの条件演算ifを実現している．
↑マルチプレクサの記号
上の写真はマルチプレクサ – 組み合わせ回路 – うさぎ先生ととり先生の計算機工学から参照
| S (選択) | A0 | A1 | Z (出力) |
|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
n本の入力から１本を選ぶマルチプレクサをn-1マルチプレクサと呼ぶ．
今までのは2-1マルチプレクサ
多入力マルチプレクサは例題でやったように2-1マルチプレクサを組み合わせて作ることができる
下が4-1マルチプレクサと真理値表
s0を2進数の1桁目，s1を2進数の2桁目と考えると，その2進数を10進数に考えたものがAの添え字と対応していることに注意．
上の写真はマルチプレクサ – 組み合わせ回路 – うさぎ先生ととり先生の計算機工学から参照
マルチプレクサという名前は，通信工学の多重送信の送信機のマルチプレクサからきている．
パラレルに来たデータをシリアル転送したいとき，送信機(マルチプレクサ)で多重化し1本にならべシリアル送信．受信機(デマルチプレクサ)で多重化したデータを元に戻す．
シリアル送信
1本の信号線や回線を使って1ビットずつ順番にデータを送受信する伝送方式
上の写真はマルチプレクサ – 組み合わせ回路 – うさぎ先生ととり先生の計算機工学から参照
マルチプレクサ(セレクタ)の論理式はカルノー図を使って考えると，2-1マルチプレクサは以下のような式になる
Z = A0・not(S)+A1・S
マルチプレクサを使って色々な論理ゲートを実装することもできる(ANDやOR)
スリーステートバッファ
スリーステートバッファ
０と１以外に高インピーダンス状態と呼ばれる第3の状態を出力する回路
EN(制御信号)が１のときは通常のバッファとして動作
ENが０のときは入力値に関わらず高インピーダンス状態になる
Zは高インピーダンス状態の意味
高インピーダンス状態とは，インピーダンスは「交流抵抗」，つまり高インピーダンスとは「断線に近い状態」である．
| A (入力) | EN (制御信号) | 出力 Y |
|---|
| 0 | 0 | Z |
| 0 | 1 | 0 |
| 1 | 0 | Z |
| 1 | 1 | 1 |
スリーステートバッファはバスとのインターフェースによく使われる．
出力同士を直接繋いでしまうとショートする．しかし，スリーステートバッファをつなげば出力同士をつなぐことができる．それは，高インピーダンスで出力を制御できるためである．
また，バッファ以外のゲートについてもスリーステートゲートにすることができる．
また，マルチプレクサはスリーステートバッファを使って作ることができる．
上の写真はマルチプレクサ – 組み合わせ回路 – うさぎ先生ととり先生の計算機工学から参照
しきい値関数回路
しきい値関数を実現．多数決関数回路も広く見ればしきい値関数回路とみれる．
入力の１の数がある値(しきい値)以上なら１を出力する回路
しきい値が１ならORゲート．
m個の変数からなる積項をすべて列挙し，足すことで論理式が得られる．
上の写真は多数決回路／エンコーダ・デコーダ – 組み合わせ回路 – うさぎ先生ととり先生の計算機工学から参照
エンコーダ・デコーダ
エンコーダ・デコーダとはエンコード・デコードを行う装置
エンコードとは，データを一定の規則で別のデータに変換すること(画像・音声などのデータ圧縮など)
デコードとは，エンコードされたデータをもとに戻すこと
論理回路においてエンコーダはよく下のような真理値表を示す．
入力は１ビットだけえ１，あとは０．それ以外の入力は禁止入力
１となる入力の添え字を２進数字で表現して出力
| A0 | A1 | A2 | A3 | y2 | y1 |
|---|
| 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 1 | 1 |
論理回路においてデコーダはよく下のような真理値表を示す．
エンコーダの真理値表の入力と出力を交換しただけ．
入力の添え字を２進数字と解釈し，それを添え字にもつ出力だけ１，その他の出力を０
| x2 | x1 | y0 | y1 | y2 | y3 |
|---|
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 |
まとめると，エンコーダは入力が10進数，出力が２進数
デコーダは入力が２進数，出力が10進数
エンコーダの論理式は，y2 = x2+x3，y1 = x0+x1となる．
デコーダの論理式は，y0 = not(x2)・not(x1)，y1 = not(x2)・x1，y2 = x2・not(x1)，y0 = x2・x1
エンコーダの入力，デコーダの出力のように１ビットだけで１で，他は０となるものをワン・ホットという．
また，プライオリティエンコーダというものがある．
プライオリティエンコーダとは，添え字が最も大きい入力だけ着目し，それ以外の添え字が小さい入力を無視するエンコーダである．
７セグメントディスプレイについて
７セグメントディスプレイとは，アラビア数字などを７個のLEDで表示する表示装置
７セグメントディスプレイでは，表示させたい数字をそのまま入力するのではなく，光らせたいLEDに対応する場所を１にすればよい．しかし，このままでは使いずらいので，７セグメントデコーダを使う．７セグメントデコーダを使えば，表示したい数字を入力するだけで，光らせたLEDが点灯する．
例えば，eを光らせるような論理式を考えると下のような真理値表を作成でき，カルノー図を作成し，論理式を立式するとe = not(x0)・not(x1)+x2・not(x1)となる．
10~15まではドントケア項で表す．
加算器
計算機の中では２値信号が使われる．２値信号とは，０と１だけ，電圧が高いか低いかの信号．それらを組み合させて２進数をあつかう．
カルノー図を書けば，好きな回路は作ることができるが，とても大変．
算術演算には規則性があり，それを上手に扱えばよい．
加算は下の桁から順に１ビットずつ行っていく．それを行うために１ビット同士をの加算を行う半加算器がある．
また，用語としてキャリーアウトという単語がある．キャリーアウトとは，繰り上がりのことである．
下が半加算器の真理値表である．S(sum)はXOR，CO(carry out)はANDで表されることがわかる．
| A (入力) | B (入力) | S (sum) | CO (carry out) |
|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
加算において，下の桁からの桁上がりを考えることがある．しかし，半加算器は下からの桁上がりを受ける入力がない．桁上がりを受けられるようにつくれれた１ビット加算器を全加算器という．
A，B，CIの３数の加算を考える．全加算器は，半加算器を組み合させることで実現が可能．
１．A，Bの和を半加算器で計算する HA１
２．その和とCIの和を半加算器で計算する HA２
３．HA１とHA２のキャリー同士の和を半加算器で計算する HA３
ただ，もう少し簡単化できる．
HA１でのC１とS１は半加算器の真理値表を見ればわかるが，同時に１になることはない．C１と１と仮定すると，S１は必ず０になりHA２で出力されるC２は必ず０となる．そして，HA３に入力はC１が１でC２が０となる．
逆にC１を０と仮定すると，HA３の入力はC１が０でC２が０か１となる．
この結果から，最後のHA３は繰り上がりを考慮しなくてよい．よって最後のHA３はXORゲートに変えても構わない．
さらに，HA３に入力される値が同時に１となる場合はないため，ORゲートに変えても構わない．XORとORの違いは同時に１となるときだけである．
そして，XORはORより約1.5倍大きいのでORを使った方がいい．
論理式を使って表すと，
CO = A・B+(A⊕B)・CI = A・B＋A・C＋B・C (多数決関数)
S = A⊕B⊕CI
| A (入力) | B (入力) | Cin (キャリー入力) | Sum (和) | Cout (キャリー出力) |
|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
また，１個の半加算器と(n-1)個の全加算器を使ってnビット加算器を作ることができる．
キャリー入出力を数珠繋ぎする．リップルキャリー加算器ともよぶ．
繰り上がりがない１桁目はHAを使って他の桁はFAを使っている．
n個の全加算器を使ってキャリー入力付きnビット加算器を作ることができる．(Turning Completeで出た)
オーバーフロー
計算機の中では通常扱うデータの桁数をあらかじめ決めておく
演算結果が表現できる範囲外の場合正常な演算ができない．
これをオーバーフローという．
例えば，８ビット(１バイト)の表現できる値は0~255までである．それを超えるとオーバーフローとなる．
加算器でオーバーフローの検出をするには最上位桁のキャリー発生を観測することで検出できる．
コメント