加算器の入力ゲートと出力ゲートの話

　授業で出てきた加算器でちょっと自分が考えたことを話します。

　入力がnゲートあるとき、加算した結果は $\lceil \log_2 n \rceil$ の中に納まりますが、果たしてHalf Adder(以降HA)とFull Adder(以降FA)で回路を組んだ時本当に出力ゲート数は $\lceil \log_2 n \rceil$ の中に納まるかという話です。
　HAとFAについては以下のサイトなどを参考にしてみてください。簡単に言うと、HAは2つのbit入力を受け取ってその加算結果を2つのbitに出力するもので、FAは3つのbit入力を受け取ってその加算結果を2つのbitに出力するものです。
http://www.cs.shinshu-u.ac.jp/Lecture/LogicCirc/chap9/chap9.html
　で、何が問題なのかというとHAは2つのbit入力を受け取ってその加算結果を2つのbitに出力するのですが、HAの出力結果は0, 1, 2の3通りしかなく、2つのbitで出力すると無駄にリソースを食らっていることになります。よって、HAを使いすぎてしまうと出力ゲート数が $\lceil \log_2 n \rceil$ を超えてしまいかねません。FAはリソースに無駄がないのでHAを使わなければよいのですが、例えば入力ゲートが4のときを考えてみるとHAを多少なりとも使わなくてはいけないことがわかります。

　結果から言うと、出力ゲート数はちゃんと上式に納まります（多分）。
　以下僕の考えた粗い証明です（間違ってたらpingお願いします）。
　まず、 $n = 2^m-1$ と表せる場合を考えます（この場合はHAを一度も使えません）。最下位bitに注目すると、FAを一回実行すると最下位bitの数は2減ります。最終的に最下位bitは1つ残ればよいので、最下位bitについてのFAは $2^{m-1}-1$ 回実行されます。このFAによって下から二番目のbitの数も $2^{m-1}-1$ 個生成されます。後は再帰的に処理していけばHAを一度も用いることなく回路を構成できます。よって、 $n = 2^m-1$ のときは問題ありません。
　次に、 $2^{m-1} \leq n < 2^m-1$ のとき下から二番目のbitの数を $n=2^{m-1}-1$ にできることを示します。最下位bitの加算によって下から二番目のbitの数を1増やすにはFAを用いるかHAを用いるかの二通りですが、HAを用いると最下位bitを1だけ節約することができます。よって $x = 2^m-1-n$ とおくと、x個HAを用いることができれば下から二番目のbit数を $n=2^{m-1}-1$ にできます。明らかにnが小さく、xが大きいときほどHAを消費しにくくなるので $n = 2^{m-1}$ のときを考えます。HAを一回用いるごとに最下位bitの数は1減るのでHAは $2^{m-1}-1$ 回実行できます。また、 $x = 2^m-1-n = 2^m-1-2^{m-1} = 2^{m-1}-1$ であり、実行可能なHAの回数と一致します。よって、下から二番目のbitの数を $n=2^{m-1}-1$ にすることができました。後は再帰的に処理をするだけです。
　よって、全てのnについて出力ゲート数は $\lceil \log_2 n \rceil$ に納まることがわかりました。（終）

おわりに

　今回は回路の構成自体は適当を極めていますが、stage数とかAdderの数とか考えると色々と深そうでこれからの講義が楽しみです。（何を優先するかで変わってきそう？）