kivantium活動日記

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

減算器

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

昨日までで足し算ができるようになったので今度は引き算を考えます。
引き算は A-B = A + (-B)という関係から負の数の足し算として考えれば加算器をそのまま流用することができそうです。
しかし、2進数での負の数をどう定義するか決めていなかったので、まずはそこから考えます。

2進数での負の数の表現

負の数を表す方式として

  • 絶対値+符号bit (最上位bitが0→正・1→負と取り決め、残りのbitで絶対値を表す)
  • 1の補数表現(最上位bitが0→正・1→負と取り決め、残りのbitは正の場合絶対値、負の場合は絶対値の0と1を反転する)
  • 2の補数表現(1の補数表現に1を足したもの)

などが考案されましたが、現在のCPUではたいてい2の補数表現が使われています。

例として4bitの-3を考えてみます。
10進数での3を4bitの2進数で表すと0011となります。
これを1の補数表現に直すと最上位bitを負を意味する1に、残りのbitを絶対値011を反転した100にすることで、1100となります。
さらにこれに1を足して、2の補数表現による-3として1101を得ます。

実際に3 + (-3)を実行してみると

   0011
+) 1101
-------
  10000

となります。4bitで考えているので最上位の1は無視されて結果は0000となります。このように2の補数で表した負の数は、元になった正の数と足すと0になります。

一般に、 N-1bit以下で表せる2進数 Xに対する Nbitでの1の補数は、正の数として見ると (2^N-1)-Xになります。(1の補数はbit反転なので元の数と足すと11...11と1が N個連続する数、すなわち 2^N-1になります)
2の補数表現はこれに1を足すので正の数としてみると 2^N-Xに相当する値になります。

 2^N-X Yを足すと 2^N+Y-Xになりますが、 Nbitで考えると 2^Nは無視されるので結果として Y-Xの計算結果と同じ値が得られることになります。

また、2の補数表現で表した負の数に対して再び「bit反転+1」という操作をすると 2^N - (2^N-X) = Xより元の数に戻ることからもこの表現が妥当であることが分かります。

このように、2の補数表現を考えると加算器と同一の回路で引き算を行えることが分かります。

符号付き4bit整数と10進数の対応を表にしておきます。

2進数 10進数 2進数 10進数
0000 0
0001 1 1111 -1
0010 2 1110 -2
0011 3 1101 -3
0100 4 1100 -4
0101 5 1011 -5
0110 6 1010 -6
0111 7 1001 -7
1000 -8

加算器を減算器にする

2の補数表現で負の数が表せることが分かったので、加算器を少し書き換えて減算器にします。

最上位bitが0の正の数が与えられたとき、2の補数表現による負の数の作り方は「bit反転+1」でした。bit反転はNOTゲートで簡単に行うことができます。問題は+1の部分なのですが、これも簡単です。前回作った16bit加算器をよく見るとせっかく作ったキャリー入力を0に固定しています。ここを1に固定すれば+1が簡単に実現できます。
加算器を減算器に改造する方法のイメージはこんな感じです。


というわけで16bit加算器を使った16bit減算器のコードは以下のようになります。

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

  subtractor_16bit diff(.A(a), .B(b), .S(result), .Cout(carry));
  assign answer = a-b;

  initial begin
    $monitor("%016b-%016b -> %016b (%d-%d=%d)", a, b, result, a, b, result);
    for (i = 0; i<100; i++) begin
      j = $random; a = j[14:0]; // 正の数にするために15bitのみ使う
      j = $random; b = j[14:0];
      #1;
      if(result != answer) $display("wrong answer!");
    end
    $finish;
  end
endmodule

module subtractor_16bit (
  input [15:0] A, B,
  output [15:0] S,
  output Cout
);
  logic [15:0] notB;
  assign notB = ~B;
  adder_16bit adder(.A(A), .B(notB), .Cin(1'b1), .S(S), .Cout(carry));
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

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

結果は

0011010100100100-0101111010000001 -> 1101011010100011 (13604-24193=-10589)
0101011000001001-0101011001100011 -> 1111111110100110 (22025-22115=   -90)
(中略)
0110010011111010-0110111001100001 -> 1111011010011001 (25850-28257= -2407)
0000100100010111-0111100010100001 -> 1001000001110110 ( 2327-30881=-28554)

になって正しそうだと分かります。

キャリーとオーバーフロー

同じ2進数でも符号なしと見ているのか、符号付きと見ているのかで意味が全く異なる場合があります。以下全て4bitで考えます。最初に見た

   0011
+) 1101
-------
  10000

を考えます。これを符号付き整数同士の加算と考えると 3+(-3)=0という正しい計算ですが、符号なし整数同士の加算と考えると 3+13 = 0という間違った計算になります。コンピュータから見ればどちらも正当な2進数の操作ですが、人間から見ると全く違う結果になります。

このような人間から見ると"正しくない"計算結果を検出するためにアーキテクチャによってはキャリーフラグやオーバーフローフラグと言われるものが用意されています。

キャリーフラグは加算でキャリーが発生した時に1となります。符号なし整数同士の加算をしているときにキャリーが発生すると計算結果がそのbit数で表せる範囲を超えたという意味なので計算結果が人間的には"間違っている"ことを意味します。
ちなみに、現在のキャリーフラグも含めて足す命令があるアーキテクチャも存在し、多倍長演算に使われます
0000-0001 = 1111のような計算では存在しない桁からの桁下がりが起こっているように見えますが、これをボローと言います。ボローが発生するときにはボローフラグを立てることがありますが、ボローフラグがキャリーフラグと共通のアーキテクチャもあり、アーキテクチャによって対応はいろいろです

オーバーフローフラグは同符号同士の加算または異符号同士の減算によって最上位bitが変更された場合に1になります。符号なし整数同士の演算でこのような最上位bitの変更が起こると人間的には"間違っている"ことを意味します。

これらのフラグがあるアーキテクチャではフラグを使って計算結果を確認します。

次回は掛け算に必要な順序回路について書きます。