加算器とキャリー伝搬構造

一桁の足し算を二つの結果ビットで表す

$a_i,b_i,c_i$ の和は 0～3 なので、和 $s_i$ と次の桁へのキャリー $c_{i+1}$ が必要です。三入力のうち 1 が奇数個なら和ビットは 1、二つ以上ならキャリーは 1 です。

$g_i=a_ib_i$ を generate、$p_i=a_i\oplus b_i$ を propagate と定義すると、$c_{i+1}=g_i+p_ic_i$ になります。ここで $+$ は OR です。半加算器はキャリー入力のない特別な場合で、和は XOR、キャリーは AND です。

三つの入力を変え、a+b+cin = sum+2×cout が常に成り立つか確認してください。キャリーは次の桁の入力となり、sum と同じ重みのビットではありません。

キャリーはどこまで伝わるか

4 ビットの 1111 + 0001 を考えます。bit 0 でキャリーが生じ、残りの三桁へ伝わります。格納する和は 0000、最上位のキャリーは 1 です。リップルキャリー構造では、上位桁の計算が下位桁からのキャリーを待つ場合があります。

このように式を展開すると、キャリーを並列に計算できる可能性が見えてきます。実際の高速加算器はグループの propagate/generate を組み合わせますが、ファンイン・配線・セルライブラリを含め、面積と遅延のトレードオフが生じます。RTL の + が必ず一つのリップルキャリー回路になるとは限りません。

和の幅を設計に明示する

logic [3:0] a, b, sum;
logic cin, cout;
logic [4:0] wide_sum;
assign wide_sum = {1'b0, a} + {1'b0, b} + {4'b0000, cin};
assign sum = wide_sum[3:0];
assign cout = wide_sum[4];

$15+15+1=31$ まで表せるので 5 ビットで十分です。下位の和だけでよいか、キャリーを次段へ伝えるか、飽和が必要かを先に決めます。この実習は一桁の全加算器の真理値表^{i真理値表 可能な入力組合せをすべて列挙し、各組合せの出力を記した表です。時間に伴う変化は波形で別途確認します。 詳しく見る}を確認するもので、実際の合成結果の遅延を測るものではありません。