2011年06月22日

除算回路

こんにちはひらめき
タイラです。

今回も回路図シリーズをお届けします。
4回目の今回は四則演算で最も難関と言われる除算回路を紹介したいと思います。パンチ

除算回路は前回の積算回路と似たような考え方で、
シフトをしながら引き算を行っていくやり方になります。

今まで使っていた加算器では減算出来る事が前提となっていた為、
減算出来なかった場合が想定されていないので、
それを可能にした全加算器が以下の図になります。

20110622_FA2.png

入力Dが0の場合、演算結果の出力Sが入力Aをそのまま出力するようになっています。
その他基本的な部分は通常の加算器と同様の動きを行います。
実はこの部分さえ出来てしまえば、減算回路と積算回路の考え方で除算回路を作成することが出来ます。

そして、除算用に改良した全加算器を4x4個並べてた以下の図が除算回路になります。わーい(嬉しい顔)

20110622_DIV2.png

前々回に触れた引き算の際には入力のビットを反転させて2の補数を作ると紹介しましたが、
今回も同じように2の補数を利用して各ビットの減算を行っています。
各ビットにそれぞれシフトしながら減算を行っています。
減算出来なかった場合は入力Dが0になる為、入力Aの値がそのまま下位ビットに渡されます。
4回この計算を繰り返す事で4bit分の除算を行う事が出来ます。


今回の回路ですと、上位ビットの計算結果を出す為に一度計算した値で再度計算を行う必要があるので、
下位ビットに値が渡されるまでに時間がかかってしまいます。

プログラムをする際でも割り算は遅いと耳にするのは、より多くの計算手順を踏む必要があるからです。
加算減算と比べて格段に遅いのもこのためです。ふらふら

みなさんもプログラムをする際には、四則演算ごとの処理負荷を気にかけてみてはいかがでしょうか?
それでは手(パー)

posted by 管理人 at 21:31 | 回路図

2011年05月20日

積算回路

こんにちは
最近自宅のCPUをSandy Bridgeにしたタイラです。わーい(嬉しい顔)

さて、CPU繋がりで今回も回路図シリーズをお届けします。
3回の今回は積算回路です。

積算:掛け算 の最も簡単なものは2進数での筆算を考えて頂ければと思います。


20110520_筆算.JPG


この計算をそのまま回路図にしたものが以下になります。

0110520_mul_1.PNG
※全加算器を展開した状態で書いてきましたが、あまりにも巨大になる為、今回は省略した形で書いています。


今回も4bitの回路なので 4x4 の16個の全加算器を使用していますが、
64bitの回路を作ろうとすると 4096個の全加算器が必要になります。ふらふら
図は書きたくないですね。あせあせ(飛び散る汗)

コンパイラの最適化によって自動的に置き換わってしまう場合もありますが、
掛け算の代わりにシフト演算を使った方が速いといわれるのはこの為です。

もちろん市販のCPUにこのままの回路が入っている訳ではないですが、
積算は加算に比べ、計算量がこのくらい増えるのだというイメージを持つことは出来るのではないでしょうか。ひらめき

みなさんも、プログラムで掛け算をする際には少し気にかけてみては如何でしょうか。わーい(嬉しい顔)
それではまた。手(パー)

posted by 管理人 at 20:36 | 回路図

2011年04月15日

減算回路

こんにちは
この4月で2年目になりました。タイラです。わーい(嬉しい顔)


さて、前回4bit加算回路を取り上げましたが
今回は4bit減算回路について触れてみたいと思います。

加算回路は一度くらい見たことがあるという方もおられたと思いますが、
減算回路はご存じでしょうか?

実は減算回路は加算回路に少し手を加えると出来ます。ひらめき

20110415_RCS.png

入力B(引く値)の各ビットが反転し、入力が1本増えて最下位ビットと計算しています。

引き算でビットを反転と聞くと2の補数をイメージされるのではないでしょうか?
ビットを反転すると「1の補数」、その値に1を加えると「2の補数」です。

この回路では前回紹介した加算回路に
入力Bを反転した「1の補数」と、「2の補数」にする為に1を足して計算しています。

さらに、制御ビットと入力の際のビットを連動させることで、
加算と減算を同じ回路にまとめることができます。

20110415_RCAS.png

これで個別に計算回路を持たなくても加算と減算を同じ速度で行うことが出来ます。るんるん
回路図にしていませんが、前回の高速な4bit加算回路(CLA)にも応用が効きます。グッド(上向き矢印)

今年はプログラム等のソフトウェア部分だけでなく、それらを動かす基になっている
ハードウェアに関する知識も増やしていこうと思います。
いずれはArduinoを利用して何かツールでも作りたいですね。パンチ

それではまた。手(パー)

posted by 管理人 at 20:37 | 回路図

2011年02月17日

4bit加算器

こんにちは手(パー)
何年も付けていなかった家計簿を今月になって付け始めたタイラです。

さて、唐突ではありますが、今回は4bit加算器についてお話しようと思います。

4bit加算器と聞くと学生の時にやったという方もおられるかと思います。
加算器というのは2進数の足し算を行う回路の事です。
今回はそれを4bit分接続したものになります。

最もシンプルな加算器は以下の図の回路です。
桁上げ伝搬加算器(Ripple Carry Adder) といい、桁上げ情報を次のビット計算へ順番に送っていく方法です。

20110217_RCA.PNG

私が学校でやったのはこの回路でした。
この回路では下位ビットが計算されないと上位ビットが計算されないので、
桁数が増えるとそれに比例して計算時間も増大していきます。

4bitの計算を行う場合、最上位ビットが計算されるまで6段階の処理が必要になります。
64bitを計算しようとすると最上位ビットでは127段の処理が必要になってしまいます。がく〜(落胆した顔)

その問題を解消する方法の一つに桁上げ先見加算器(Carry Look-ahead Adder) というのがあります。

20110217_CLA.PNG

桁上げ情報を別で計算して各ビットへ送ることで高速に上位ビットの計算が可能になります。
更にこの回路ではどんなに桁数が増えても4段分の計算時間で完結します。わーい(嬉しい顔)

先ほどの回路と比較すれば約32倍の高速化ということになりますグッド(上向き矢印)るんるん
プログラムでもこれくらい劇的に高速化出来るアルゴリズムはないかとよく考えますが、なかなか難しいです。


C言語で書けば
c = a + b;

で終わってしまうことですが、
こういった工夫があるからこそ、今のハードの性能があるのだと思います。
他にも幾つか手法があるようなので、一度調べてみてはいかがでしょうか。
私もそういった工夫を常に心がけながら、プログラムを行っていきたいと思います。パンチ

ではexclamation


posted by 管理人 at 21:14 | 回路図