この記事では，組み合わせ回路についてのメモを書いていく．
Turning Completeをプレイしているうちに自分の知識が足りないと感じ，勉強しました．
今回は算術回路について主にまとめている
この記事は，自分用のメモなので勉強したいならうさぎ先生ととり先生の計算機工学の動画を見るとよいと思います．
また，使っている画像もうさぎ先生ととり先生の計算機工学の動画から参照しています．
加算器
計算機の中では２値信号が使われる．２値信号とは，０と１だけ，電圧が高いか低いかの信号．それらを組み合させて２進数をあつかう．
カルノー図を書けば，好きな回路は作ることができるが，とても大変．
算術演算には規則性があり，それを上手に扱えばよい．
加算は下の桁から順に１ビットずつ行っていく．それを行うために１ビット同士をの加算を行う半加算器がある．
また，用語としてキャリーアウトという単語がある．キャリーアウトとは，繰り上がりのことである．
下が半加算器の真理値表である．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までである．それを超えるとオーバーフローとなる．
加算器でオーバーフローの検出をするには最上位桁のキャリー発生を観測することで検出できる．
負の整数
計算機の中では”２値信号”が使われる．
符号(+と-)はビットの最上位桁を符号ビットとして使用して表している．
最上位ビットが０なら正数，１なら負数．
負の整数の表現法
よく知られる負数の表現法は３種類ある．
- 絶対値表現
- １の補数表現
- ２の補数表現
| 10進数 | 絶対値表現 | 1の補数表現 | 2の補数表現 |
|---|
| +3 | 00000011 | 00000011 | 00000011 |
| +2 | 00000010 | 00000010 | 00000010 |
| +1 | 00000001 | 00000001 | 00000001 |
| 0 | 00000000 | 00000000 11111111 | 00000000 |
| -1 | 10000001 | 11111110 | 11111111 |
| -2 | 10000010 | 11111101 | 11111110 |
| -3 | 10000011 | 11111100 | 11111101 |
絶対値表現は最も直感的であるが，最も使わない．
１の補数表現では表現したい数-Xについて２進数表記したXの全ビットを反転させて表現
例えば，-2の１の補数表現を考えると，＋２は00000010であるため全ビットを反転させると，11111101となる．
２の補数表現では負の整数を１の補数表現で表しているものに＋１してやればもとまる．
例えば，-2の２の補数表現を考えると，-2の１の補数表現は11111101であるため，それに＋１をして11111110となる．
計算機中では２の補数表現が圧倒的によく使われる．
理由は加減算が楽にできるからである．
符号ありか符号なしかで表現できる範囲は変わる．
符号あり：-128~127まで
符号なし：0~255まで
符号ありの場合，+128は表現できない．これは，0がある分表現できる正数は負数より１戸少なくなるからである．
また，注意点として符号ありの場合異なるビット数の足し算をしてはいけない．必ず計算前に桁の拡張を行って，少ない方のビット数を多い方のビット数に合わせる必要がある．
桁の拡張
符号なしの場合：追加した桁を０で埋める
符号なしの場合：符号ビットの値をコピーし，追加した桁までその値で埋める．
符号あり加算器
符号あり加算器は，符号なし加算器と同様に計算することができる．
ただ，オーバーフローに関しては符号なし加算器のようには判定できない．
つまり，符号なしと符号ありとではオーバーフローの判定は異なるのである．
また，オーバーフローが発生したとき，符号ビットは正しい結果と比較し反転している．
結論から言うと，符号あり加算器の場合，オーバーフローが発生しているときは最上位桁でのキャリーと１桁下でのキャリーの一方のみが発生する．
これを判定するには，最上位桁でのキャリーと１桁下でのキャリーで排他的論理和をとればよい．
減算器
符号ありの場合も符号なしの場合も減数の符号を反転させて，加算を行えばよい．
Yの全ビットを反転させたものY’とすると，-Y = Y’+1 よりX – Y = X + (-Y) = X + Y’ + 1
また，この式はYが負の時でも成り立つ．全ビット反転させて１を足したものを元に戻すには，また全ビット反転させて１を足すと元に戻る．
加算器を使って作ると，式より全ビット反転させているので，インバータを使って加算器に入力する前に反転させればよい．＋１に関しては，加算器のキャリー入力に１を入れる．＋１をすることは最初の桁で繰り上がりを考えることと同義である．(ずっと最初の桁の繰り上がりを考慮する加算器の必要性がわからなかったが，このために使うのだなと納得した．あと，４ビットと４ビットの加算器を組み合わせて８ビットの加算器を作るときも使うのか)
そして，キャリー出力の扱いだが，その前にボローについて説明する．
加算器での桁上がり，繰り上がりをキャリーといったが，減算器の桁借り，繰り下がりをボローという．
加算を用いて減算を行ったときキャリーが発生する(しない)桁では，元の減算においてボローは発生しない(する)
このことから，キャリー出力を反転させればボローがあったかわかるボロー出力になる．
また，加算器にキャリー入力を持たせることができたように減算器でもボロー入力を持たせることができる．通常の減算器は加算器のキャリー入力に１を入れて作った．ボロー入力が欲しいときは加算器のキャリー入力を反転させてボロー入力BIとする．
BIが０なら下位桁らの桁借りが発生してないということ．(通常の減算器とボロー入力付きの減算器を組み合わせることでnビットの減算器を作ることができる．)
オーバーフローについて
符号なし減算においては減算器のボロー出力を観測することで，検出できる．
符号あり減算は減数の符号を反転させて，加算を行うため，オーバーフローの検出法は符号あり加算と同じで最上位桁とその下の桁の排他的論理和をとればいい．
比較器
２入力A，Bを比較する回路
A<B
A-Bを計算し，A-Bが負ならA＜B
符号なしの場合，A-Bが負ならオーバーフロー発生．つまり，ボロー発生する．
符号ありの場合，A-Bが負A-Bの最上位桁が１ただしオーバーフローが起きている場合は符号ビットが反転しているので注意．
オーバーフローが発生したとき符号ビットは反転する．
このことから，オーバーフローが発生＞＞＞符号ビットを反転させて正負を確認
オーバーフローが発生しない＞＞＞そのまま符号ビットの正負を確認
オーバーフローは最上位桁とその下の加算でキャリーが生じているか確認すればいいから排他的論理和を取ればいい．そして，符号ビットを反転させるには下のようなマルチプレクサで表される．
そして，マルチプレクサの論理式Z = A0・not(S)+A1・Sより，下のようなマルチプレクサは排他的論理和であることがわかる．
つまり，符号を反転させるのも排他的論理和でよい．
A=B
A=Bのとき１を出力するには，すべてのビットが互いに等しいことを調べる．
＞＞＞一致回路(XNOR)をつかい，AND(入力１が入力数のとき，１を返すのしきい値関数)を取ればいい．
また，減算器を設けている場合は一致回路は使わないでA-B=0のとき１を出力する回路を作ってもよい．
A-Bのすべてのビットが０であることを調べる．
＞＞＞NORゲートはすべての入力が０であるとき１
A=(定数)
A=(定数)のとき１を出力する回路
出力が１となるのは１行だけであるから，最小項から回路を作るとよい．
インクメンタ・デクリメンタ
インクメンタはA+1，デクリメンタはA-1を計算する回路．
加算器の一方の入力に00…01，11…11を入力することでもとまる．
算術演算回路
算術演算回路とは，制御信号S_0，S_1の値によって加算器，減算器，インクメンタ，デクリメンタになる回路．
コンピュータには五大装置があり，制御・演算・記憶・入力・出力である．
演算装置は制御信号に応じた演算を行い，制御信号は制御装置が送る．
加減算器
加算器と減算器，どちらの演算もできる組み合わせ回路を加減算器という．
マルチプレクサを使うことで作ることができる．
制御信号の値によって加算器としても減算器としても働くことができる．
制御信号Sが０のとき，AとBの値をそのまま加算器に入力，キャリー入力には制御信号をS，つまり０を入力
制御信号Sが１のとき，Bのビットを反転させて入力，キャリー入力には制御信号をS，つまり１を入力
また，マルチプレクサを見てもらうと気付いてほしいのだが，このマルチプレクサはXORゲートで置き換えられる．
ビット論理演算回路
ビット論理演算を行う回路
C言語における&, |, ~, ^
ビットごとに論理演算を行えばよい．
算術演算回路と同様，制御信号の値に応じてAND，OR，XOR，NOTのビット論理演算を行う
AND，OR，XOR，NOT，これらは４通りであるから，制御信号は２入力あれば４通りになる．
算術論理演算ユニット(ALU)
算術演算(加減算)とビット論理演算を行う
制御信号に応じて算術演算とビット論理演算を切り替える
シフタ
１ビット左シフトする回路
配線だけで作ることができる
２のべき乗を乗ずるまたは，２のべき乗で除するときに使用できる
後で説明する乗算器を使うより簡単
２進数では左シフトすることに２倍
右シフトするごとに２で割ったことになる
右シフトについて注意しないといけないことがある
それは，右シフトする値の符号だ
符号なしの値には純粋に右シフトでいいのだが，符号ありの場合は算術右シフトをしないといけない
算術右シフトとは，新しい最上位ビットには前の最上位ビットを残して右シフトするというやり方だ．
バレルシフタ
指定された回数分シフトする回路
シフタを多段接続して作る
シフタはマルチプレクサを用いて制御信号によって制御する
乗算器
定数倍なら，左シフタと加算器を用いれば実現可能である
例．５A = 4A+A
変数×変数をやりたければ，乗算器を使う必要がある
乗算器は筆算と同じ要領で作ることができる
各桁でANDを取ってあげて(部分積)，加算器で足してあげればよい
オーバーフローを考慮するなら被乗数，乗数をbビットとするとき，積を２bビットで表現すればオーバーフローは発生しない
キャリーセーブ加算器
たくさんの数の総和を求めたいときに使える
単に２数の和を求めたいときには使えない
和を求めることはできないが，加算の対象を３個から２個に減らすことができる
なぜそのようなことができるのかというと，次のような性質があるからである
２CO＋S ＝ A＋B+CI
右辺(入力)は変数が３個
左辺(出力)は変数が２個
このことから，キャリーセーブ加算器は乗算のとき部分積の和を取るときに変数を減らすことで加算の数を減らすことができる
このような上の写真の右の回路をWallace木と呼ぶ
複数のキャリーセーブ加算器が並列に配置され，高速な加算を実現しているのが特徴
８ビットでは恩恵を感じにくいかもしれないが，ビット数が増えるとわかりやすいかも
Wallace木を用いて部分積の加算を行う乗算器をWallace乗算器と呼ぶ
符号あり乗算器
符号あり乗算は，素直に筆算すると値が変わる
これらは，被乗数と乗数の桁の拡張をしてあげるとよい
拡張する桁は，被乗数，乗数をbビットとするとき，2bビットまで拡張すればよい
符号あり乗算器を実現する方法でもっといい方法がある
それは，２の補数表現における数の一般式から得られるらしい(あんま理解できてない)
式は上のように表される
結果だけいうと下写真のように筆算すれば求まる
MAC演算
D += A × Bという演算をMAC演算と呼ぶ
ニューラルネットワークや画像処理などで非常によく使う計算である
非常にニーズが強いため，よく議論されているらしい
今回はスルーする
コメント