２進からBCDへの変換回路 の履歴(No.6)
更新概要†
(2010-10-28) すみません、回路サイズの見積もりなどで間違っていた部分があったので、大幅に記述を見直しました。
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 スライス程度
でした。ちゃんと回路図書いたらもっと小さくできる・・・かな？？？
入力ビット数を 32 にしてもクロックは 100MHz 以上で回るようです。
まあ、主には引き算と比較しかしていないから当然か。
アルゴリズム、コーディングスタイルその他に関するアドバイス、大歓迎です。
模範解答がこちらにあるそうです†
このページの以下の部分は、「私がやったらこうなった」という意味で残しておきますが、 もっとずっと効率の良いアルゴリズムが FPGA の部屋 で紹介されていました。
[ame_feb4さんに教えていただいた回路] という部分に書かれている
http://jjmk.dk/MMMI/Lessons/06_Arithmetics/No6_Conversion/Index.htm
のページです。
動作周波数、回路規模のどちらをとっても、 ここで紹介した回路とは比較にならないほど優れていますので、 実用的な回路を求めている方はそちらをお使いください。
自前の回路で 苦労した 工夫した点†
特に、ビット数を parameter 化して、自由に設定できるようにするのは大変でした。
- localparam を計算してから input / output のビット幅を記述するため、 古い C 言語のような module 定義になっている点
- BCD_DIGITS_BITS の求め方がちょっとアレな件 (もっと良い方法はないものか？？？)
- initialize for による ROM の初期化
- 多ビットレジスタへの部分代入はできないため、一旦 bcd_internal に受けて、bcd につなぎ直している点
- bcd につなぐ際、generate for 中で +: を使っている点
- テストベンチでの値の比較に != ではなく !== を使っている点
あたりが最近覚えたテクニックだったりします。
ビット指定していない演算がいくつかあるので BITS > 32 ではちゃんと動かないと思います。ご注意ください。
一生懸命ビット指定してもうまく動かせなかったので、 手抜きのままになっています（汗
ソース†
LANG:verilog(linenumber)
// ２進数を BCD に直す回路
// bin に変換元の符号なし整数をセットして start に１を立てる
// 次クロックで 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
改良†
最後の桁を求める際に「１で割る」無駄な操作を無くしました。
ソースは多少ごちゃごちゃしましたが、回路は逆に小さくなるようでした。
LANG:verilog(linenumber)
// ２進数を BCD に直す回路
// bin に変換元の符号なし整数をセットして start に１を立てる
// 次クロックで 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)
// ２進数を BCD に直す回路
// bin に変換元の符号なし整数をセットして start に１を立てる
// 次クロックで 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 ほど増えてしまうようでした。
コメント†
yCwZWbCvkkwE†
[Celina] (2013-01-05 (土) 06:03:34)
All of these artliecs have saved me a lot of headaches.
２進数からBCDへの変換回路†
[marsee] (2010-10-27 (水) 10:23:32)
こんにちは。わざわざ変換回路を作っていただいて、ありがとうございました。
私の２進数からBCDへの変換回路も恥ずかしいですが、ブログに貼っておきました。
http://marsee101.blog19.fc2.com/blog-entry-1628.html
- marsee さんの回路、拝見しました。かなり目からうろこでした。が、ちょっと一般化はしづらそうですかね。主要な定数をパラメータ化した module を書こうとすると、verilog の不思議な制約に引っかかってしまっていつも苦労しています・・・ -- [武内（管理人）]
Counter: 28476 (from 2010/06/03),
today: 2,
yesterday: 3