何年も付けていなかった家計簿を今月になって付け始めたタイラです。
さて、唐突ではありますが、今回は4bit加算器についてお話しようと思います。
4bit加算器と聞くと学生の時にやったという方もおられるかと思います。
加算器というのは2進数の足し算を行う回路の事です。
今回はそれを4bit分接続したものになります。
最もシンプルな加算器は以下の図の回路です。
桁上げ伝搬加算器(Ripple Carry Adder) といい、桁上げ情報を次のビット計算へ順番に送っていく方法です。
私が学校でやったのはこの回路でした。
この回路では下位ビットが計算されないと上位ビットが計算されないので、
桁数が増えるとそれに比例して計算時間も増大していきます。
4bitの計算を行う場合、最上位ビットが計算されるまで6段階の処理が必要になります。
64bitを計算しようとすると最上位ビットでは127段の処理が必要になってしまいます。
その問題を解消する方法の一つに桁上げ先見加算器(Carry Look-ahead Adder) というのがあります。
桁上げ情報を別で計算して各ビットへ送ることで高速に上位ビットの計算が可能になります。
更にこの回路ではどんなに桁数が増えても4段分の計算時間で完結します。
先ほどの回路と比較すれば約32倍の高速化ということになります
プログラムでもこれくらい劇的に高速化出来るアルゴリズムはないかとよく考えますが、なかなか難しいです。
C言語で書けば
c = a + b;
で終わってしまうことですが、
こういった工夫があるからこそ、今のハードの性能があるのだと思います。
他にも幾つか手法があるようなので、一度調べてみてはいかがでしょうか。
私もそういった工夫を常に心がけながら、プログラムを行っていきたいと思います。
では
