コンピュータの動作原理（５）順序回路

>六本木順序ぅ派。

セレクタ
----
コンピュータの動作原理を考える上で大事な回路にセレクタがあります。マルチプレクサとも言います。複数の信号のうち1つを選択する回路です。

Sが0の時はAを、Sが1の時はBを出力する回路、つまりSでAのBどちらを選択するか指定できる回路を考えてみましょう。
例によって真理値表から。

|S|A|B|→|Y|
|:-:|:-:|:-:|:-:|:-:|
|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|

<img src="https://qiita-image-store.s3.amazonaws.com/0/136856/021788ee-a43c-9f54-e136-d77690203e76.jpeg" width="240px">

Sが選択信号で、S=0の時はAが、S=1の時はBが出力Yに出てきます。
この回路は真理値表のY（出力）が1になる項目が4つありますが、これは言葉で説明すると、
・Sが0なら、Bが0でも1でも、Aが1の時には1を出す。
・また、Sが1なら、Aが0でも1でも、Bが1の時には1を出す。
・どちらでもない場合は0を出す。
という回路で、その通りに出来ています。

数を増やして、4本の信号から1つを選択するなら、下のような回路になります。
S0とS1の2本（つまり選択信号は2ビット）でA～Dのどれを出力するか選びます。
<img src="https://qiita-image-store.s3.amazonaws.com/0/136856/f2de3052-859e-e0db-f5d0-7317edf661f9.jpeg" width="340px">

　※ALUは常に結果を全部出してると（１）で触れました。全部出てるけど、結果は1つだけしか必要ないので、セレクタなどでそのうち1つを採用します。この選択信号は、やはりどこかの回路から出力されています。（１）の図にある制御信号のうちの1つがこれです。
　※複数本の信号から1本を選択して出力する方法としては、この他に tristate buffer というモノを使う方法もあります。これにはこのシリーズ（２）でちらっと出てきたCMOSを使います。出力側のMOSFETを、電源側もGND側もOFFにするというやり方です。こうすると出力が電気的につながっていない状態を作ることが出来ます。ON,OFF以外の第三の状態を作る事が出来るのでトライステート（三種類の状態）です。詳しくはトライステートバッファでぐぐってみてください。


加算
----
加算についてもやっておきます。といっても、加算器についてはちょっと探せば解説がたくさん出てきますからそっちにまかせて、ここでは「コンピュータは減算」と言った流れで加算をどう解釈するかについてだけ解説します。

加算は減算回路があれば A+B → A-(0-B) にすればいい事は前回解説しました。
もう１つ、加算は繰り上がりがあるので、繰り上がりが発生したら1を上の桁に伝えるようにしたいです。加算の場合には、減算器で「下へ貸した」と表現していた**信号の解釈を変え**ます。
つまり、

減算：下の桁に貸して帰ってきたか → 0:帰ってこなかった　1:帰ってきた
加算：下の桁から桁上がりがあったか → 0:無かった　1:桁上がりがあった

という事です。

減算回路は下の桁への貸し=0の時は貸しちゃったぶんの1を引く回路になっていますから、加算の場合に引かないようにするには、**減算器の結果の各桁に1を足せばいい**事になります。
ではどこで足すかというと、加算と減算の切り替えは B か (0-B)かの選択ですから、(0-B)を計算するところで一緒にやっちゃいます。

A+B → A-(0-B)+1 変形して A-(0-B-1) ですね(まだ減算回路しかやってないですし)。
あとは減算か加算かを選択するセレクタのSのような信号を増やして、Bと(0-B-1)とを切り替えれば、加算と減算とどっちにもなる回路が出来ます。

まず0-Bの真理値表です。

|B|→|r|Y|
|:-:|:-:|:-:|:-:|
|0||1|0|
|1||0|1|

上の桁から借りた1と、引かれる数0は省略してあります。rとYは合わせて2桁です。

ここから更に1を引きます。入力は上の表の出力ですから2通りしかありません。また、上の表と同じ桁ですから、上の桁からの借りはさっき借りた分でまかないます。合わせると

|B|→|r|Y|→|(r:Y)-1|
|:-:|:-:|:-:|:-:|:-:|:-:|
|0||1|0||1|
|1||0|1||0|

です。この-1は減算回路として考えると下の桁への貸しが0（貸しっぱなし）という意味です。貸しが0の前提ですから、更に上の桁も、つまりどの桁も下からは返ってこない前提です。という事はわざわざ上に0を渡す必要は無いので真理値表では省略します。0からBと1を引くのですから、どっちみち上には返せませんし。

上の表の結果を見ると NOT B ですね。
という事で下が加算と減算の切り替えを追加した回路です。BとNOT Bをセレクタで切り替えるようにしてあります。OPが減算か加算かを選択する信号、uが下への貸し又は加算の場合下からの繰り上がりです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/136856/f4611925-b42b-5ca2-edcc-f4c2c6614f1b.jpeg" width="460px">

　※回路が一部間違っていたので訂正

　※OPはBを反転するか、しないかの選択ですから、単にXORを入れても同じです。XORは片方の入力でもう片方を反転するかしないかを指定するゲートと考えることも出来ますし、そういう意味で使っている回路もあります。
　※前回から今回ここまでの回路は　[SUB_ADD.circ](http://qv80.cocolog-nifty.com/blog/files/sub_add_v2.circ)　に入っています。

#### 「加算しか出来ない」の謎
前回と今回で示した回路、減算回路と加算回路は、本質的な違いは全くありません。

1つのプロセッサ（ダイ）に10数億個のトランジスタの乗る現在では、工夫をして加算と減算を1つの回路で実現する意味はあまりありません。符号ビット＋絶対値でもいいわけです。けど、昔のトランジスタ数の節約が必要だった頃のプロセッサ（例えば1974年発表のi8080は、6μmのNMOSでトランジスタ数5000個）では、ちょっとした工夫でトランジスタが節約できる方法は必要でした。1ビットの加算回路に30個以上のトランジスタが使われているわけですから。それ以前の真空管の時代には、もっと切実だったはずです。
その事が、加算器を利用して減算も行う→コンピュータは加算しか出来ない、と間違って伝わったのではないかと思います。

　※そもそも「減算を加算で行う」というのが間違いです、2の補数は定義から減算なのは明らかなので、正しくは「減算を加算器を利用して行う」です。足し算と加算器を利用することとは分けて考えるべきです。

　※一部の計算モデルでは整数を関数の適用回数や集合の要素の数で定義するものがあります。この場合加算は連結で出来ますが、減算は簡単ではありません。こういった場合は「減算は加算ほど簡潔ではない」と言えるでしょう。

整数の加減算を加算と減算に場合分けしているHDLのソースを見たことがあります。FPGAのメーカーが提供しているソフトIPのプロセッサコアでした。

順序回路
----
今まで解説したものは、入力が変わるとそれにあわせて出力もすぐに変わる回路でした。こういう回路を「組み合わせ回路」と言います。
ストアードプログラム方式のプロセッサはどうしても一時的な記憶が必要です。例えば、これから実行しようとしているマシンコードを指すための、プログラムカウンタとかインストラクションポインタとか言うアレですね。
一時的に状態を記憶する回路というとラッチやフリップフロップ（Flip-Flop（FF)）と呼ばれるものがあります。探すと色々出てきます。そういったものを利用した回路を「順序回路」と呼びます。
順序回路はRSラッチというやつから入るのが正しい順番の様ですが、それはこのシリーズの目的から外れるので、プロセッサに必要なD-Flip-Flopについて解説します。


D-Flip-Flop
----
心がふわっと天に届くみたいな話ではありません。入力と制御信号を受け入れる回路で、0か1かを一時的に取って置く事ができます。制御信号によってコントロールします。たとえば下がDFFの例でCLKが制御信号です。
<img src="https://qiita-image-store.s3.amazonaws.com/0/136856/9d86a4a7-ef60-dd94-b178-d67c685dde79.jpeg" width="240px">

これは、CLKが1の時はINがそのままOUTに出ます、CLKを1から0にすると、その瞬間のINがOUTに出たままになり、CLKが0の間はINを変えてもOUTは変化しません。メモリー（のうちSRAMと呼ばれているもの）は基本的にこの回路です。この回路は0と1の真理値表は書けません。動作を表す時は0か1かを書くかわりにCLKが0→1に変化した時やその逆の時の記号を使います。

今まで出てきた単純な組み合せ回路とちょっと違うのは、OUTの手前のNAND２つがお互いフィードバックし合っている点です。これがあるので、OUTがINとCLKの組み合わせで決まるのではなくて、CLKが1の時の値をぐるぐる回しながら保持できるのです。

この回路はCLKが1の時にINがOUTにダダ漏れになるので、この回路のOUTがいくつか組み合わせ回路を経由して、ぐるっと回ってこの回路のINにつながっていたら、回路全体が忙しくなります。
そこでこの回路を二段にします。それぞれにCLKの反転と（さらに反転して）CLKを入れてやります。マスタースレーブ方式と言います。

<img src="https://qiita-image-store.s3.amazonaws.com/0/136856/bba9907d-b119-6452-11ac-47f09d87a92c.jpeg" width="340px">

CLK→反転→マスターへ→さらに反転→スレーブになってます。
マスターはCLKが0の時(マスターに入力するCLKが1の時)にINがそのままマスター→スレーブの継ぎ目に出るのですが、スレーブにさらに反転したCLK（マスターへのCLKが1なら、スレーブに来るCLKは0）を入れているので、INが変わってもOUTは変化しません。CLKが1になると、今度はマスターが変化しないのでスレーブ側が入力をそのまま出しても問題ありません。安定ですね。

少し工夫するとGATEを6個に減らせるので（どういう理屈かは私はわかりませんが）ここからはそれを採用して解説します。
<img src="https://qiita-image-store.s3.amazonaws.com/0/136856/4c5e8b0d-d147-070d-d531-58d98560a9ba.jpeg" width="340px">

コレに「非同期リセット」を付けます。何が非同期かというと、CLKが0か1か,INが0か1かに関わらずResetを0にするとすぐにOUTが0になります。そしてResetが0の間はOUTは変わりません。
このReset信号は、コンピュータのリセットスイッチを押したときや電源が入った直後などに内部状態を文字通りリセットするアレと同じ意味です。

こんな感じです。
<img src="https://qiita-image-store.s3.amazonaws.com/0/136856/01ca78c7-7786-acd1-938f-0de1c5cc428a.jpeg" width="340px">

もうひとつ追加します。Enable信号です。
<img src="https://qiita-image-store.s3.amazonaws.com/0/136856/b5a339b6-3070-e233-1e00-c0b2bf869a1f.jpeg" width="340px">
Enable信号が0の時はCLKを遮断するようにDFFを入れてあります。こっちはEnableが1の時にCLKがそのまま出て、Enableが0の時はCLKが変わってもそれが出ないようにしてあります。先のDFFとはCLKの位置が違いますね、確認してください。
これでEnable信号が0の時はこのFFは入力を記憶しない、それより前にEnable=1だった時の値を維持します。
アセンブリ言語の命令で「引き算するけど結果は捨てる」というのは、結果を残す引き算だったらメモリやレジスタに書き込むけれど、結果は捨てる=Enable信号を0にして書き込まないようにする、というやり方です。
もちろん、このEnable信号も、制御信号のうちの1つです。

CLKが0→1になって出力が変わったら、その先に組み合わせ回路がつながっていれば、そっちの出力もそのタイミングで変化します。それを順序回路の入力にフィードバックして、という構成にすると、CLKに同期して全体が先に進んで行きます。この時のCLKが一般にクロックと呼ばれているもので、プロセッサの動作の基本です。


プロセッサを構成する重要な要素について基本を一通り解説しました。次回からはもうすこし具体的にプロセッサの動作について解説していきます。

一覧へ
----
[コンピュータの動作原理](https://qiita.com/niQSun/items/91396b620638e3f44f19#%E3%83%AA%E3%82%B9%E3%83%88)

----

　※以上の回路は　[FLIPFLOP.circ](http://qv80.cocolog-nifty.com/blog/files/FLIPFLOP.circ)　に入っています。 [Logisim](http://www.cburch.com/logisim/)用のドキュメントです。xmlですから右クリで。