kivantium活動日記

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

加算器 その1

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

昨日はNANDゲートから任意のゲートを作れることを確認しました。
ここからは何回かに分けて四則演算などの基本的な計算を行う回路の実現方法を書いていきます。

四則演算は組み合わせ回路として書けるので、NANDであらゆるゲートを作れる以上実現できることは明らかなのですが、使用するトランジスタの数を減らしたり計算を高速にしたりするためにいろいろな方法が考えられています。

2進数による正の整数の表現

デジタル回路では電圧のH/Lに対応した1/0の2値で全ての情報を表します。2値で数字を表すために2進数を使います。

a_iを0または1として、a_na_{n-1}a_{n-2} \dots a_1a_0のように並べた数字が\sum_{i=0}^n a_i 2^iという値を表すように取り決めるのが2進数です。
2進数での桁のことをbit (BInary digiT)と呼び、2進数で8桁の数字を「8bitの数」のようにいいます。

4bitの場合の2進数と10進数の対応関係を書いておきます。

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

1bit 半加算器 (HA, half adder)

1bit半加算器は1bitの数の足し算を行う回路です。入力Aと入力Bが与えられたときに和Sと繰り上がりC (carry out)を出力します。真理値表は

A B C S
0 0 0 0
0 1 0 1
1 0 0 1
1 1 1 0

のようになります。

半加算器を2入力2出力のゲートと考えれば、NANDゲートをうまく組み合わせて作れます。
実際にはNANDゲートだけで作るのは面倒なので一例として以下のように作ります。

この回路図ではXORゲートが使われています。XORゲートは

A B Y
0 0 0
0 1 1
1 0 1
1 1 0

という真理値表を持つゲートです。XORゲートの記号は

です。

1bit 全加算器 (FA, full adder)

全加算器は繰り上がりも含めて加算を行う回路です。入力をA・Bと前の桁の繰り上がりCinの3本、出力を和Sと繰り上がりCoutの2本とすると、真理値表は

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

のようになります。

これを実現する回路は一例として

があります。

nbit 全加算器

1bitの加算器をいくつも集めることで複数bit同士の足し算を行う加算器を作ることができます。nbitの入力x, yの和sを計算する回路は例えば以下のようになります。（FAは全加算器を表しています）

x0はxの第0bit、x1は第1bit……のように入力の各bitを表しています。（全体のCinは0に固定しておきます）
このように下の桁の全加算器のCoutを上の桁の全加算器のCinにつないで作る加算器をリップルキャリーアダーといいます。

この回路でも結果は正しいのですが、例えば64bitの足し算を行おうとすると全加算器を直列に64個つなぐことになります。
全加算器はゲートをつないで作っていますが、そのゲートはトランジスタをつないで作っています。
トランジスタは電圧を加えてからスイッチングが起こるまでに若干の遅れがあります。そのためゲートの入力電圧が変わってから出力が変わるまでにゲート遅延と呼ばれる遅れが発生します。（例えばNANDゲートのICである74HC00では10nsくらいです）これは人間的スケールでは一瞬なのですが、2GHzなどの超高速で動くCPUの世界ではこのゲート遅延は非常に問題になります。（1GHzのクロックは1ns間隔です）

次のクロックが起こるまでに演算を終わらせようと思うと、なるべくゲートを直列につなぐ数を減らす必要があります。このために高速な何種類も加算器が提案されています。次回はキャリールックアヘッドアダーと呼ばれる高速化した加算器を紹介します。

SystemVerilogでの実装

ここまで紹介した回路をSystemVerilogというハードウェア記述言語で書いてみます。SystemVerilogの基本文法については以前の記事を参照してください。
kivantium.hateblo.jp

実行環境

FPGAなどで実際に回路を動かすのは大変なので、この記事ではシミュレータで動作を確認します。
シミュレータには何種類かあるので好きなものを使ってください。

Icarus Verilog

オープンソースのシミュレータです。
インストール方法はInstallation Guideを見てください。

SystemVerilogはUbuntu 14.04のレポジトリにあるバージョンでは動かなかったのでソースコードからコンパイルしました。g++, gcc, bison, flex, gperfを入れておけばいつものsh autoconf.sh && ./configure && make && make installで環境構築ができました。

また、SystemVerilogを動かすには

iverilog -g2012 -o test test.sv
vvp test

のようにコンパイル時にオプションを指定する必要がありました。

Vivado

XilinxのページからVivadoを落としてくればシミュレータがついてきます。

ModelSim

よく使われている有名なシミュレータです。


この記事のコードはIcarus VerilogとVivadoで動作確認しています。

半加算器

HAモジュールは半加算器を紹介した回路図の通りに作っています。
テストベンチでは真理値表のようなものを出力しています。

module testbench;
  logic a, b, c, s;
  HA adder(.A(a), .B(b), .C(c), .S(s));

  initial begin
    $display("A B    C S");
    $monitor("%b %b -> %b %b", a, b, c, s);
    a = 0; b = 0; #10;
    a = 0; b = 1; #10;
    a = 1; b = 0; #10;
    a = 1; b = 1; #10;
    $finish;      
  end
endmodule

module HA(
  input A, B,
  output S, C
);
  assign S = A ^ B;
  assign C = A & B;
endmodule

結果は

A B    C S
0 0 -> 0 0
0 1 -> 0 1
1 0 -> 0 1
1 1 -> 1 0

のようになり、期待通り動くことが分かりました。

全加算器

半加算器と同様です。

module testbench;
  logic a, b, cin, s, cout;
  FA adder(.A(a), .B(b), .Cin(cin), .S(s), .Cout(cout));

  initial begin
    $display("A B Ci   Co S");
    $monitor("%b %b %b -> %b  %b", a, b, cin, cout, s);
    a = 0; b = 0; cin = 0; #10;
    a = 0; b = 1; cin = 0; #10;
    a = 1; b = 0; cin = 0; #10;
    a = 1; b = 1; cin = 0; #10;
    a = 0; b = 0; cin = 1; #10;
    a = 0; b = 1; cin = 1; #10;
    a = 1; b = 0; cin = 1; #10;
    a = 1; b = 1; cin = 1; #10;
    $finish;      
  end
endmodule

module FA(
  input A, B, Cin,
  output S, Cout
);
  assign S = (A ^ B) ^ Cin;
  assign Cout = ((A ^ B) & Cin) | (A & B);
endmodule

結果は以下の通りです。

A B Ci   Co 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

4bit リップルキャリーアダー

全加算器を4つつなげてadder_4bitというモジュールを作っています。

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

  adder_4bit adder(a, b, result, 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 FA(
  input A, B, Cin,
  output S, Cout
);
  assign S = (A ^ B) ^ Cin;
  assign Cout = ((A ^ B) & Cin) | (A & B);
endmodule

module adder_4bit(
  input [3:0] A, B,
  output [3:0] S,
  output C
);
  logic [3:0] carry;
  
  FA fa0(A[0], B[0], 1'b0, S[0], carry[0]);
  FA fa1(A[1], B[1], carry[0], S[1], carry[1]);
  FA fa2(A[2], B[2], carry[1], S[2], carry[2]);
  FA fa3(A[3], B[3], carry[2], S[3], C);
endmodule

結果は

0000+0000 -> 00000 ( 0+ 0= 0)
0000+0001 -> 00001 ( 0+ 1= 1)
0000+0010 -> 00010 ( 0+ 2= 2)
0000+0011 -> 00011 ( 0+ 3= 3)
(中略)
1111+1101 -> 11100 (15+13=28)
1111+1110 -> 11101 (15+14=29)
1111+1111 -> 11110 (15+15=30)

のようになりました。

4bitリップルキャリーアダーはgenerate文を使うと以下のようにも書けます。

module adder_4bit #(parameter SIZE = 4) (
  input [SIZE-1:0] A, B,
  output [SIZE-1:0] S,
  output C
);
  logic [SIZE-2:0] carry;
  
  FA fa0(A[0], B[0], 1'b0, S[0], carry[0]);
  genvar i;
  generate
  for(i=1; i<SIZE-1; i=i+1) begin: GenerateAdder
    FA fa(A[i], B[i], carry[i-1], S[i], carry[i]);
  end
  endgenerate
  FA fa_msb(A[SIZE-1], B[SIZE-1], carry[SIZE-2], S[SIZE-1], C);
endmodule

SIZEを変えればより大きい加算器も作れます。

参考ページ

広告コーナー