2進からBCDへの変換回路 の履歴(No.3)
更新概要†
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 のときは、
- 1000で割った商を始めの桁に
- その余りを100で割って、その商を次の桁に
- その余りを10で割って、その商を次の桁に
- その余りを1で割って、その商を最後の桁に(本当は割る必要ないのだけれど)
となってます。
ステートを工夫して最後の割り算を飛ばしたり、 BCD1桁あたりのクロック数を削ったりもできそうですが、 速度が要求される部分でもないでしょうから、 回路規模を優先してそのままにしています。
合成結果は Spartan3 で
- BITS = 8 のとき、 42 スライス程度
- BITS = 10 のとき、 52 スライス程度
- BITS = 16 のとき、 67 スライス程度
- BITS = 32 のとき、 124 スライス程度
でした。ちゃんと回路図書いたらもっと小さくできる・・・かな???
アルゴリズム、コーディングスタイルその他に関するアドバイス、大歓迎です。
ソース†
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で割る」無駄な操作を無くし、 さらに桁数あたりのステート数を1つ削りました。
ソースは多少ごちゃごちゃしましたが、回路は逆に小さくなるようでした。
LANG:verilog(linenumber) // 2進数を BCD に直す回路 // bin に変換元の符号なし整数をセットして start に1を立てる // 次クロックで busy が立つので、降りるまで待って bcd を読む // BITS により、任意ビット数に対応可能 // 計算時間は (BCD_DIGITS-1) * 5 クロック程度 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; // 計算結果を保持するレジスタ reg [3:0] bcd_internal[1:BCD_DIGITS-1]; always @(posedge clk) if (rst) begin state <= stIdle; end else case (state) stIdle: begin digit <= BCD_DIGITS; if (start) begin numerator <= bin; state <= stDivide0; end end stDivide0: begin // 分母に 10^n << 3 を用意する denominator <= denominators[digit-1] << 3; // 結果を格納して次へ(初回は無駄な動作になる) bcd_internal[digit] <= quotient; if (digit==1) begin state <= stIdle; end else begin digit <= digit - 1; state <= stDivide1; end 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; if (state!=stDivide4) begin state <= state + 1; end else begin state <= stDivide0; end end endcase // 出力に繋ぐ assign busy = state != stIdle; generate genvar j; for (j=1; j<BCD_DIGITS; j=j+1) begin: bcd_connection assign bcd[j*4 +: 4] = bcd_internal[j]; end endgenerate assign bcd[3:0] = numerator[3:0]; endmodule
一旦 quotient に受けているのが良いらしい†
上記ソースから、quotient を無くして、 割り算結果を直接 bcd_internal にシフトインしていけば、 下記のように Verilog ソースをかなり単純化できることに気づいたのですが、
実際に変更を加えて合成してみると、、、使用スライス数が大幅に増えてしまいました。(滝汗
Verilog ソースを単純化することと、 実際の回路を最小化することとは別なんだということを 思い知らされました。
BITS = 10 で比較すると Spartan 3A DSP では
- 上記回路 (BCD_DIGITS-1) x 5 + 2 クロック, 最大146MHz, 45 スライス
- 下記回路 (BCD_DIGITS-1) x 5 + 1 クロック, 最大164MHz, 67 スライス
でした。
LANG:verilog(linenumber) // 2進数を BCD に直す回路 // bin に変換元の符号なし整数をセットして start に1を立てる // 次クロックで busy が立つので、降りるまで待って bcd を読む // BITS により、任意ビット数数値を変換可能 // 計算時間は (BCD_DIGITS-1) * 5 クロック程度 module bin2bcd #( parameter BITS = 32 ) (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; 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; 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; if (state!=stDivide4) begin state <= state + 1; end else begin if (digit!=1) begin state <= stDivide0; end else begin state <= stIdle; end digit <= digit - 1; end end endcase // 出力に繋ぐ assign busy = state != stIdle; assign bcd = { bcd_internal, numerator[3:0] }; endmodule
コメント†
2進数からBCDへの変換回路†
[marsee] (2010-10-27 (水) 10:23:32)
こんにちは。わざわざ変換回路を作っていただいて、ありがとうございました。
私の2進数からBCDへの変換回路も恥ずかしいですが、ブログに貼っておきました。
http://marsee101.blog19.fc2.com/blog-entry-1628.html
- marsee さんの回路、拝見しました。かなり目からうろこでした。が、ちょっと一般化はしづらそうですかね。主要な定数をパラメータ化した module を書こうとすると、verilog の不思議な制約に引っかかってしまっていつも苦労しています・・・ -- [武内(管理人)]