２進からBCDへの変換回路 のバックアップ差分(No.3)
更新- 追加された行はこの色です。
- 削除された行はこの色です。
[[公開メモ]] #contents * 概要 [#y15acbf7] marsee さんから頂いたお題で、通常の「２進数符号なし整数」を「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 のときは、 +１０００で割った商を始めの桁に +その余りを１００で割って、その商を次の桁に +その余りを１０で割って、その商を次の桁に +その余りを１で割って、その商を最後の桁に（本当は割る必要ないのだけれど） となってます。 ステートを工夫して最後の割り算を飛ばしたり、 BCD１桁あたりのクロック数を削ったりもできそうですが、 速度が要求される部分でもないでしょうから、 回路規模を優先してそのままにしています。 合成結果は Spartan3 で - BITS = 8 のとき、 42 スライス程度 - BITS = 10 のとき、 52 スライス程度 - BITS = 16 のとき、 67 スライス程度 - BITS = 32 のとき、 124 スライス程度 でした。ちゃんと回路図書いたらもっと小さくできる・・・かな？？？ アルゴリズム、コーディングスタイルその他に関するアドバイス、大歓迎です。 * ソース [#ebed19cc] LANG:verilog(linenumber) // ２進数を BCD に直す回路 // bin に変換元の符号なし整数をセットして start に１を立てる // 次クロックで busy が立つので、降りるまで待って bcd を読む // BITS により、任意ビット数に対応可能 // 計算時間は BITS * 6 クロック程度 // 計算時間は 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 * テストベンチ [#tc58bda1] LANG:verilog(linenumber) module bin2bcd_test; // ここを変えれば異なるビット数についてもテスト可能 parameter BITS = 10; 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) ); // value を入力して expect が出てくることを確かめる task test_with; // 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; input [BCD_DIGITS*4-1:0] expect; 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_with(123, 'h123); // まず境界値的な値をチェック 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 // 境界的な値を重点的にチェック test_with(0, 'h0); test_with(1023, 'h1023); test_with(255, 'h255); test_with(128, 'h128); test_with(127, 'h127); test_with(64, 'h64); test_with(63, 'h63); test_with(100, 'h100); test_with(99, 'h99); test_with(10, 'h10); test_with(9, 'h9); // あとは適当にチェック for(i=0; i<10000-1; i=i+1) test($random); $display("*** done"); $stop(); end endmodule * 改良 [#i6f7bd6f] 最後の桁を求める際に「１で割る」無駄な操作を無くし、 さらに桁数あたりのステート数を１つ削りました。 ソースは多少ごちゃごちゃしましたが、回路は逆に小さくなるようでした。 LANG:verilog(linenumber) // ２進数を BCD に直す回路 // bin に変換元の符号なし整数をセットして start に１を立てる // 次クロックで 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 に受けているのが良いらしい [#c036e8cc] 上記ソースから、quotient および bcd_connection を無くして、 割り算結果を直接 bcd にシフトインしていけば、 Verilog ソースをかなり単純化できることに気づいたのですが、 上記ソースから、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) // ２進数を BCD に直す回路 // bin に変換元の符号なし整数をセットして start に１を立てる // 次クロックで 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 * コメント [#h185d7db] #article_kcaptcha **２進数からBCDへの変換回路 [#a6f91af8] >[marsee] (2010-10-27 (水) 10:23:32)~ ~ こんにちは。わざわざ変換回路を作っていただいて、ありがとうございました。~ 私の２進数からBCDへの変換回路も恥ずかしいですが、ブログに貼っておきました。~ http://marsee101.blog19.fc2.com/blog-entry-1628.html~ // - marsee さんの回路、拝見しました。かなり目からうろこでした。が、ちょっと一般化はしづらそうですかね。主要な定数をパラメータ化した module を書こうとすると、verilog の不思議な制約に引っかかってしまっていつも苦労しています・・・ -- [武内（管理人）] &new{2010-10-27 (水) 11:40:50}; #comment_kcaptcha
Counter: 25860 (from 2010/06/03),
today: 1,
yesterday: 0