kivantium活動日記

プログラムを使っていろいろやります

加算器 その2

この記事はkivantium Advent Calendarの4日目です。

昨日は半加算器・全加算器・リップルキャリーアダーを紹介しました。
リップルキャリーアダーはゲートがたくさん直列に並んでいるため遅いです。
そこで今回は高速な加算器を実装する話です。

キャリールックアヘッドアダー

リップルキャリーアダーの問題点は、第 nbitのフルアダーのキャリー入力を決定するために第 n-1bitのキャリー出力が必要になるという依存関係があることでした。
キャリールックアヘッドアダーは、キャリー入力を高速に決定することでこの問題を解決します。

入力 x,  yの第 ibitを x_i,  y_iとし、第 ibitのフルアダーのキャリー入力を c_iとします。( c_0=0としておきます)
このとき、フルアダーの真理値表

A B Cin Cout S
0 0 0 0 0
0 1 0 0 1
1 0 0 0 1
1 1 0 1 0
0 0 1 0 1
0 1 1 1 0
1 0 1 1 0
1 1 1 1 1

から、第 i+1bitのキャリー出力 c_{i+1}
 {\displaystyle
\begin{align}
c_{i+1} &= x_iy_i + x_ic_i + y_ic_i\\
&=x_iy_i + c_i(x_i+y_i)
\end{align}
}
と書けます。(ここ以降で積はAND、和はORを表します。また、数式と同じようにANDを先に計算します。)

ここで、generateと呼ばれる信号線 g_iとpropagateと呼ばれる信号線 p_i
 {\displaystyle
\begin{align}
g_i &= x_iy_i \\
p_i &= x_i + y_i
\end{align}
}
とおくことで、
 {\displaystyle
\begin{align}
c_{i+1} = g_i + p_ic_i
\end{align}
}
と書き直すことが出来ます。

 g_i g_i=1のとき「第 ibitでは必ずキャリーが発生する」という意味を持つ信号線です。
 p_i p_i=1のとき「第 ibitでキャリーが発生する可能性がある」という意味を持つ信号線です。
 g_i,  p_iはともに x_i,  y_iのみの情報で確定できます。

これらを使って具体的にキャリーがどのように計算されるか見ていきます。
まず c_1は、
 {\displaystyle c_1 = g_0 + p_0c_0}
となります。これは x_0,  y_0,  c_0のみから確定します。

 c_2
 {\displaystyle
\begin{align}
c_2 &= g_1 + p_1c_1 \\
&= g_1 + p_1(g_0+p_0c_0) \\
&= g_1 + p_1g_0 + p_1p_0c_0
\end{align}
}
となります。 c_1の情報を使わずに c_2を決定することができました!
こうして得た c_1を第1bitの全加算器の入力に使えば、下位の全加算器のキャリー出力が決定するのを待たずに加算が実行できるのでリップルキャリーアダーよりも高速な足し算ができます。
また、全加算器のキャリー出力は使わないので、全加算器のSを出力する部分(入力2本とキャリーのXOR)だけ使えば答えが得られます。

 c_3,  c_4についても同様の展開ができます。
 {\displaystyle
\begin{align}
c_3 &= g_2 + p_2c_2 \\
&= g_2 + p_2(g_1+p_1g_0+p_1p_0c_0) \\
&= g_2 + p_2g_1 + p_2p_1g_0 + p_2p_1p_0c_0\\
\\
c_4 &= g_3 + p_3c_3 \\
&= g_3 + p_3(g_2 + p_2g_1 + p_2p_1g_0 + p_2p_1p_0c_0) \\
&= g_3 + p_3g_2 + p_3p_2g_1 + p_3p_2p_1g_0 + p_3p_2p_1p_0c_0
\end{align}
}

ここまで見て分かるように高いbitのキャリーを決定するにはたくさんのゲートが必要なので回路規模が大きくなってしまいます。
しかし、このキャリールックアヘッドの考え方をそのまま使えば、4bit加算器を4つ並べることで16bit加算器を作ることができます。

各4bit加算器について全体の P G
 {\displaystyle
\begin{align}
P &= (x_0+y_0)(x_1+y_1)(x_2+y_2)(x_3+y_3) \\
&= p_0p_1p_2p_3 \\ \\
G &= x_3y_3 + x_2y_2(x_3+y_3) + x_1y_1(x_2y_2)(x_3y_3)
     + x_0y_0(x_1+y_1)(x_2+y_2)(x_3+y_3) \\
&= g_3 + g_2p_3 + g_1p_2p_3 + g_0p_1p_2p_3
\end{align}
}
のように求め、それぞれの4bit加算器のキャリー入出力を上と同じゲートで計算すればキャリーをリップルキャリーアダーよりも高速に計算できます。(具体的には16bitの場合でリップルキャリーアダーはゲートが47段、キャリールックアヘッドアダーでは8段とWikipediaにあった)

ではSystemVerilogで書いてみて動くかどうか確かめてみます。
まずは4bit版のキャリールックアヘッドアダーを書いてみます。(テストベンチ部分は昨日と同じ)

module testbench;
  logic [3:0] a, b, result, answer;
  logic [4:0] result5;
  logic carry;
  int i, j;

  adder_4bit adder(.A(a), .B(b), .S(result), .C(carry));
  assign answer = a+b;
  assign result5 = {carry, result}; // result5の最上位bitをcarry, 3-0bitをresultにする

  initial begin
    $monitor("%04b+%04b -> %05b (%d+%d=%d)", a, b, result5, a, b, result5);
    for (i = 0; i<=15; i++) begin
      for (j = 0; j<=15; j++) begin
        a = i; b = j;
        #1;
        if(result != answer) $display("wrong answer!");
      end
    end
    $finish;
  end
endmodule

module adder_4bit (
  input [3:0] A, B,
  output [3:0] S,
  output C
);
  logic [4:0] c;
  logic [3:0] p, g;
  
  genvar i;
  generate
    for(i=0; i<4; i=i+1) begin
      assign p[i] = A[i] | B[i];
      assign g[i] = A[i] & B[i];
      assign c[i+1] = g[i] | (p[i] & c[i]);
      assign S[i] = A[i] ^ B[i] ^ c[i];
    end
  endgenerate
  assign c[0] = 1'b0;
  assign C = c[4];
endmodule

次はP, G出力付きの4bit加算器を使って16bitキャリールックアヘッドアダーを作る例です。

module testbench;
  logic [15:0] a, b, result, answer;
  logic [16:0] result16;
  logic carry;
  int i, j;

  adder_16bit adder(.A(a), .B(b), .Cin(1'b0), .S(result), .Cout(carry));
  assign answer = a+b;
  assign result16 = {carry, result};

  initial begin
    $monitor("%04b+%04b -> %05b (%d+%d=%d)", a, b, result16, a, b, result16);
    for (i = 0; i<100; i++) begin
      j = $random; a = j[15:0];
      j = $random; b = j[15:0];
      #1;
      if(result != answer) $display("wrong answer!");
    end
    $finish;
  end
endmodule

module adder_4bit_pg (
  input [3:0] A, B,
  input Cin,
  output [3:0] S,
  output P, G
);
  logic [4:0] c;
  logic [3:0] p, g;
  
  genvar i;
  generate
    for(i=0; i<4; i=i+1) begin
      assign p[i] = A[i] | B[i];
      assign g[i] = A[i] & B[i];
      assign c[i+1] = g[i] | (p[i] & c[i]);
      assign S[i] = A[i] ^ B[i] ^ c[i];
    end
  endgenerate
  assign c[0] = Cin;
  assign P = p[0] & p[1] & p[2] & p[3];
  assign G = g[3] | g[2]&p[3] | g[1]&p[2]&p[3] | g[0]&p[1]&p[2]&p[3];
endmodule

module adder_16bit (
  input [15:0] A, B,
  input Cin,
  output [15:0] S,
  output Cout
);
  logic [4:0] c;
  logic [3:0] p, g;

  genvar i;
  generate
    for(i=0; i<4; i=i+1) begin
      assign c[i+1] = g[i] | (p[i] & c[i]);
      adder_4bit_pg add4(.A(A[i*4+3:i*4]), .B(B[i*4+3:i*4]), .Cin(c[i]), .S(S[i*4+3:i*4]), .P(p[i]), .G(g[i]));
    end
  endgenerate
  assign c[0] = Cin;
  assign Cout = c[4];
endmodule

結果は

0011010100100100+0101111010000001 -> 01001001110100101 (13604+24193= 37797)
1101011000001001+0101011001100011 -> 10010110001101100 (54793+22115= 76908)
(中略)
1110010011111010+1110111001100001 -> 11101001101011011 (58618+61025=119643)
0000100100010111+0111100010100001 -> 01000000110111000 ( 2327+30881= 33208)

となり正しいことが確認できます。

パラレルプリフィックスアダー

先ほどまでのキャリールックアヘッドアダーでは4bitごとにP, G信号の計算を行いましたが別に4bitにこだわる必然性はありません。
キャリールックアヘッドアダーの一般形は

のように書くことができます。

キャリー計算回路の中身としては効率化のために様々なものが考案されていて、まとめてパラレルプリフィックスアダーと呼ばれているようです。

例をあげると

  • Kogge-Stone Adder
  • Sklansky Adder
  • Ladner-Fischer Adder
  • Han-Carlson Adder
  • Brent-Kung adder
  • Lynch-Swartzlander Spanning Tree adder

があります。

特にKogge-Stone Adderが人気らしいです。実装は余裕があったら追加します。

ここではキャリーを先に計算しましたが、逆にキャリーを無視して計算しておいてキャリーの分を後で足すキャリースキップアダーというものもあるそうです。

明日は引き算について書きます。

参考文献

コンピュータ設計の基礎

コンピュータ設計の基礎

定本 ASICの論理回路設計―高速・高信頼ディジタル・システムのための設計ノウハウ

定本 ASICの論理回路設計―高速・高信頼ディジタル・システムのための設計ノウハウ