2進からBCDへの変換回路

(2170d) 更新

公開メモ

概要

(2010-10-28) すみません、回路サイズの見積もりなどで間違っていた部分があったので、大幅に記述を見直しました。

marsee さんから頂いたお題で、通常の「2進数符号なし整数」を「BCD (二進化十進表現)」 に変換する回路を書いてみました。

BCD (二進化十進表現)とは
http://ja.wikipedia.org/wiki/%E4%BA%8C%E9%80%B2%E5%8C%96%E5%8D%81%E9%80%B2%E8%A1%A8%E7%8F%BE

採用したアルゴリズムは非常に単純なもので、たとえば BITS = 10 のときは、

  1. 1000で割った商を始めの桁に
  2. その余りを100で割って、その商を次の桁に
  3. その余りを10で割って、その商を次の桁に
  4. その余りを1で割って、その商を最後の桁に(本当は割る必要ないのだけれど)

となってます。

ステートを工夫して最後の割り算を飛ばしたり、 BCD1桁あたりのクロック数を削ったりもできそうですが、 速度が要求される部分でもないでしょうから、 回路規模を優先してそのままにしています。

合成結果は Spartan3 で

  • BITS = 8 のとき、 42 スライス程度
  • BITS = 10 のとき、 52 スライス程度
  • BITS = 16 のとき、 67 スライス程度
  • BITS = 32 のとき、 124 スライス程度

でした。ちゃんと回路図書いたらもっと小さくできる・・・かな???

入力ビット数を 32 にしてもクロックは 100MHz 以上で回るようです。
まあ、主には引き算と比較しかしていないから当然か。

アルゴリズム、コーディングスタイルその他に関するアドバイス、大歓迎です。

模範解答がこちらにあるそうです

このページの以下の部分は、「私がやったらこうなった」という意味で残しておきますが、 もっとずっと効率の良いアルゴリズムが FPGA の部屋 で紹介されていました。

[ame_feb4さんに教えていただいた回路] という部分に書かれている
http://jjmk.dk/MMMI/Lessons/06_Arithmetics/No6_Conversion/Index.htm
のページです。

動作周波数、回路規模のどちらをとっても、 ここで紹介した回路とは比較にならないほど優れていますので、 実用的な回路を求めている方はそちらをお使いください。

自前の回路で 苦労した 工夫した点

特に、ビット数を parameter 化して、自由に設定できるようにするのは大変でした。

  1. localparam を計算してから input / output のビット幅を記述するため、 古い C 言語のような module 定義になっている点
  2. BCD_DIGITS_BITS の求め方がちょっとアレな件 (もっと良い方法はないものか???)
  3. initialize for による ROM の初期化
  4. 多ビットレジスタへの部分代入はできないため、一旦 bcd_internal に受けて、bcd につなぎ直している点
  5. bcd につなぐ際、generate for 中で +: を使っている点
  6. テストベンチでの値の比較に != ではなく !== を使っている点

あたりが最近覚えたテクニックだったりします。

ビット指定していない演算がいくつかあるので BITS > 32 ではちゃんと動かないと思います。ご注意ください。

一生懸命ビット指定してもうまく動かせなかったので、 手抜きのままになっています(汗

ソース

LANG:verilog(linenumber)
// 2進数を BCD に直す回路
// bin に変換元の符号なし整数をセットして start に1を立てる
// 次クロックで busy が立つので、降りるまで待って bcd を読む
// BITS により、任意ビット数に対応可能
// 計算時間は BCD_DIGITS * 6 クロック程度
module bin2bcd #(
    parameter  BITS        = 10
    ) (clk, rst, start, busy, bin, bcd);

    // log 16 = 1.20412 < 1205/1000 を使って BCD 表現に必要な桁数を求める
    localparam BCD_DIGITS  = BITS * 1205 / 1000 / 4 + 1; 
    localparam BCD_DIGITS_BITS 
                           = BCD_DIGITS < 2   ? 1 :
                             BCD_DIGITS < 4   ? 2 :
                             BCD_DIGITS < 8   ? 3 :
                             BCD_DIGITS < 16  ? 4 :
                             BCD_DIGITS < 32  ? 5 :
                             BCD_DIGITS < 64  ? 6 :
                             BCD_DIGITS < 128 ? 7 : 8;

    input  wire clk;
    input  wire rst;
    input  wire start;
    output wire busy;
    input  wire [BITS-1:0]         bin;
    output wire [BCD_DIGITS*4-1:0] bcd;

    // 割り算用レジスタ
    reg [BITS-1:0]   numerator;     // 分子
    reg [BITS+3-1:0] denominator;   // 分母
    reg [3:0]        quotient;      // 商

    // 10^n を保持する ROM
    reg [BITS-1:0] denominators[0:BCD_DIGITS-1];
    integer i;
    initial // ROM の初期化
        for (i=0; i<BCD_DIGITS; i=i+1) 
            denominators[i] = 10 ** i;

    // ステートマシンは state, digit を変数として動作する

    reg [2:0] state;
    reg [BCD_DIGITS_BITS-1:0] digit;

    localparam stIdle    = 0;
    localparam stDivide0 = 1;
    localparam stDivide1 = 2;
    localparam stDivide2 = 3;
    localparam stDivide3 = 4;
    localparam stDivide4 = 5;
    localparam stNext    = 6;

    // 計算結果を保持するレジスタ
    reg [3:0] bcd_internal[0:BCD_DIGITS-1];

    always @(posedge clk) 
        if (rst) begin
            state <= stIdle;
        end else
        case (state)
        stIdle: begin
                numerator   <= bin;
                digit       <= BCD_DIGITS - 1;
                if (start)
                    state <= stDivide0;
            end
        stDivide0: begin
                // 分母に 10^n << 3 を用意する
                denominator <= denominators[digit] << 3;
                state <= stDivide1;
            end
        stDivide1, stDivide2, stDivide3, stDivide4: begin
                // 割り算して商を得る
                if (numerator >= denominator) begin
                    quotient <= { quotient, 1'b1 };
                    numerator <= numerator - denominator;
                end else begin
                    quotient <= { quotient, 1'b0 };
                end
                denominator <= denominator >> 1;
                state <= state + 1;
            end
        stNext: begin
                // 結果を格納して次へ
                bcd_internal[digit] <= quotient;
                if (digit==0) begin
                    state <= stIdle;
                end else begin
                    digit <= digit - 1;
                    state <= stDivide0;
                end
            end
        endcase

    // 出力に繋ぐ
    assign busy = state != stIdle;
    generate
        genvar j;
        for (j=0; j<BCD_DIGITS; j=j+1) begin: bcd_connection
            assign bcd[j*4 +: 4] = bcd_internal[j];
        end
    endgenerate

endmodule

テストベンチ

LANG:verilog(linenumber)
module bin2bcd_test;

    // ここを変えれば異なるビット数についてもテスト可能
    parameter BITS = 16;
    localparam BCD_DIGITS  = BITS * 1205 / 1000 / 4 + 1; // log 16 = 1.20412

    // Inputs
    reg clk;
    reg rst;
    reg start;
    reg [BITS-1:0] bin;

    // Outputs
    wire busy;
    wire [BCD_DIGITS*4-1:0] bcd;

    // Instantiate the Unit Under Test (UUT)
    bin2bcd #(BITS) uut (
        .clk(clk), 
        .rst(rst), 
        .start(start), 
        .busy(busy), 
        .bin(bin), 
        .bcd(bcd)
    );

    // bin2bcd の function バージョン
    function [BCD_DIGITS*4-1:0] bin2bcd_func;
        input [BITS-1:0] bin;
        integer i;
        reg [BCD_DIGITS*4-1:0] result;
        begin
            for (i=BCD_DIGITS-1; i>=0; i=i-1) begin
                result[i*4 +: 4] = bin / 10**i;
                bin = bin % 10**i;
            end
            bin2bcd_func = result;
        end
    endfunction

    // value を入力して正しい値が出てくることを確かめる
    task test;
        input [BITS-1:0] value;
        reg [BCD_DIGITS*4-1:0] expect;
        begin
            bin = value; 
            start = 1; 
            @(posedge clk); 
            start = 0;

            @(negedge busy); 
            expect = bin2bcd_func(value);
            if (bcd!==expect) 
                $display("*** ERROR: expecting %x (%d) but found %x.",
                    expect, value, bcd);
        end
    endtask

    // クロック
    always #5 clk = !clk;

    integer i;
    initial begin
        // Initialize Inputs
        clk = 0;
        rst = 1;
        start = 0;
        bin = 0;

        // Wait 100 ns for global reset to finish
        #100;
        
        // Add stimulus here
        rst = 0;

        repeat(10) @(posedge clk);

        // まず境界値的な値をチェック
        test({BITS{1'b0}});             // 0
        test({BITS{1'b1}});             // (1 << BITS) - 1
        test({1'b1, {BITS-1{1'b0}}});   // (1 << (BITS-1))
        test({1'b0, {BITS-1{1'b1}}});   // (1 << (BITS-1)) - 1

        // あとは適当にチェック
        for(i=0; i<10000-1; i=i+1)
            test($random);

        $display("*** done");
        $stop();
    end
      
endmodule

改良

最後の桁を求める際に「1で割る」無駄な操作を無くしました。

ソースは多少ごちゃごちゃしましたが、回路は逆に小さくなるようでした。

LANG:verilog(linenumber)
// 2進数を BCD に直す回路
// bin に変換元の符号なし整数をセットして start に1を立てる
// 次クロックで busy が立つので、降りるまで待って bcd を読む
// BITS により、任意ビット数に対応可能
// 計算時間は (BCD_DIGITS-1) * 6 クロック程度
module bin2bcd #(
    parameter  BITS        = 10
    ) (clk, rst, start, busy, bin, bcd);

    // log 16 = 1.20412 < 1205/1000 を使って BCD 表現に必要な桁数を求める
    localparam BCD_DIGITS  = BITS * 1205 / 1000 / 4 + 1; 
    localparam BCD_DIGITS_BITS 
                           = BCD_DIGITS < 2   ? 1 :
                             BCD_DIGITS < 4   ? 2 :
                             BCD_DIGITS < 8   ? 3 :
                             BCD_DIGITS < 16  ? 4 :
                             BCD_DIGITS < 32  ? 5 :
                             BCD_DIGITS < 64  ? 6 :
                             BCD_DIGITS < 128 ? 7 : 8;

    input  wire clk;
    input  wire rst;
    input  wire start;
    output wire busy;
    input  wire [BITS-1:0]         bin;
    output wire [BCD_DIGITS*4-1:0] bcd;

    // 割り算用レジスタ
    reg [BITS-1:0]   numerator;     // 分子
    reg [BITS+3-1:0] denominator;   // 分母
    reg [3:0]        quotient;      // 商

    // 10^n を保持する ROM
    reg [BITS-1:0] denominators[1:BCD_DIGITS-1];
    integer i;
    initial // ROM の初期化
        for (i=1; i<BCD_DIGITS; i=i+1) 
            denominators[i] = 10 ** i;

    // ステートマシンは state, digit を変数として動作する

    reg [2:0] state;
    reg [BCD_DIGITS_BITS-1:0] digit;

    localparam stIdle    = 0;
    localparam stDivide0 = 1;
    localparam stDivide1 = 2;
    localparam stDivide2 = 3;
    localparam stDivide3 = 4;
    localparam stDivide4 = 5;
    localparam stNext    = 6;

    // 計算結果を保持するレジスタ
    reg [3:0] bcd_internal[2:BCD_DIGITS-1];

    always @(posedge clk) 
        if (rst) begin
            state <= stIdle;
        end else
        case (state)
        stIdle: begin
                digit <= BCD_DIGITS - 1;
                if (start) begin
                    numerator <= bin;
                    state <= stDivide0;
                end
            end
        stDivide0: begin
                // 分母に 10^n << 3 を用意する
                denominator <= denominators[digit] << 3;
                state <= stDivide1;
            end
        stDivide1, stDivide2, stDivide3, stDivide4: begin
                // 割り算して商を得る
                if (numerator >= denominator) begin
                    quotient <= { quotient, 1'b1 };
                    numerator <= numerator - denominator;
                end else begin
                    quotient <= { quotient, 1'b0 };
                end
                denominator <= denominator >> 1;
                state <= state + 1;
            end
        stNext: begin
                // 結果を格納して次へ
                bcd_internal[digit] <= quotient;
                if (digit==1) begin
                    state <= stIdle;
                end else begin
                    digit <= digit - 1;
                    state <= stDivide0;
                end
            end
        endcase

    // 出力に繋ぐ
    assign busy = state != stIdle;
    generate
        genvar j;
        for (j=2; j<BCD_DIGITS; j=j+1) begin: bcd_connection
            assign bcd[j*4 +: 4] = bcd_internal[j];
        end
    endgenerate
    assign bcd[7:4] = quotient;
    assign bcd[3:0] = numerator[3:0];

endmodule

一旦 quotient に受けているのが良いらしい

上記ソースから、quotient を無くして、 割り算結果を直接 bcd_internal にシフトインしていけば、 下記のように Verilog ソースをかなり単純化できることに気づいたのですが、

実際に変更を加えて合成してみると、、、使用スライス数が若干ですが増えてしまいました。(汗

Verilog ソースを単純化することと、 実際の回路を最小化することとは別なんだということを 思い知らされました。

BITS = 10 で比較すると Spartan 3A DSP では

  • 上記回路 (BCD_DIGITS-1) x 6 + 1 クロック, 最大147MHz, 47 スライス
  • 下記回路 (BCD_DIGITS-1) x 6 + 1 クロック, 最大145MHz, 49 スライス

でした。

まあ、この程度は誤差なので、実際には単純に書ける方を選ぶべきかも?

LANG:verilog(linenumber)
// 2進数を BCD に直す回路
// bin に変換元の符号なし整数をセットして start に1を立てる
// 次クロックで busy が立つので、降りるまで待って bcd を読む
// BITS により、任意ビット数数値を変換可能
// 計算時間は (BCD_DIGITS-1) * 6 クロック程度
module bin2bcd #(
    parameter  BITS = 10
    ) (clk, rst, start, busy, bin, bcd);

    // log 16 = 1.20412 を使って BCD 表現に必要な桁数を求める
    localparam BCD_DIGITS  = BITS * 1205 / 1000 / 4 + 1; 
    localparam BCD_DIGITS_BITS 
                       = BCD_DIGITS < 2   ? 1 :
                         BCD_DIGITS < 4   ? 2 :
                         BCD_DIGITS < 8   ? 3 :
                         BCD_DIGITS < 16  ? 4 :
                         BCD_DIGITS < 32  ? 5 :
                         BCD_DIGITS < 64  ? 6 :
                         BCD_DIGITS < 128 ? 7 : 8;

    input  wire clk;
    input  wire rst;
    input  wire start;
    output wire busy;
    input  wire [BITS-1:0]         bin;
    output wire [BCD_DIGITS*4-1:0] bcd;

    // 割り算用レジスタ
    reg [BITS-1:0]   numerator;     // 分子
    reg [BITS+4-1:0] denominator;   // 分母

    // 10^n を保持する ROM
    reg [BITS-1:0] denominators[1:BCD_DIGITS-1];
    integer i;
    localparam [BITS-1:0] ten = 10;
    initial // ROM の初期化
        for (i=1; i<BCD_DIGITS; i=i+1) 
            denominators[i] = ten ** i;

    // ステートマシンは state, digit を変数として動作する

    reg [2:0] state;
    reg [BCD_DIGITS_BITS-1:0] digit;

    localparam stIdle    = 0;
    localparam stDivide0 = 1;
    localparam stDivide1 = 2;
    localparam stDivide2 = 3;
    localparam stDivide3 = 4;
    localparam stDivide4 = 5;
    localparam stNext    = 6;

    reg [(BCD_DIGITS-1)*4-1:0] bcd_internal;

    always @(posedge clk) 
        if (rst) begin
            state <= stIdle;
        end else
        case (state)
        stIdle: begin
                digit <= BCD_DIGITS - 1;
                if (start) begin
                    numerator <= bin;
                    state <= stDivide0;
                end
            end
        stDivide0: begin
                // 分母に 10^n << 3 を用意する
                denominator <= denominators[digit] << 3;
                state <= stDivide1;
            end
        stDivide1, stDivide2, stDivide3, stDivide4: begin
                // 割り算して商を得る
                if (numerator >= denominator) begin
                    bcd_internal <= { bcd_internal, 1'b1 };
                    numerator <= numerator - denominator;
                end else begin
                    bcd_internal <= { bcd_internal, 1'b0 };
                end
                denominator <= denominator >> 1;
                state <= state + 1;
            end
        stNext: begin
                if (digit!=1) begin
                    state <= stDivide0;
                end else begin
                    state <= stIdle;
                end
                digit <= digit - 1;
            end
        endcase

    // 出力に繋ぐ
    assign busy = state != stIdle;
    assign bcd = { bcd_internal, numerator[3:0] };

endmodule

上記の stNext にほとんど内容がないので、 動作を stDivide4 に押し込めてしまうことで、 遅延を (BCD_DIGITS-1) x 5 + 1 に減らせますが、 スライス数が 10 ほど増えてしまうようでした。

コメント




2進数からBCDへの変換回路

[marsee] (2010-10-27 (水) 10:23:32)

こんにちは。わざわざ変換回路を作っていただいて、ありがとうございました。
私の2進数からBCDへの変換回路も恥ずかしいですが、ブログに貼っておきました。
http://marsee101.blog19.fc2.com/blog-entry-1628.html

  • marsee さんの回路、拝見しました。かなり目からうろこでした。が、ちょっと一般化はしづらそうですかね。主要な定数をパラメータ化した module を書こうとすると、verilog の不思議な制約に引っかかってしまっていつも苦労しています・・・ -- [武内(管理人)]

Counter: 15923 (from 2010/06/03), today: 9, yesterday: 0