二进制到BCD码转换–权值变换法
在上节内容中介绍加减计数法实现二进制（16进制）到BCD码（十进制）的转换，实现方法非常简单，但是其缺点也很明显，（1）计算速度慢，特别在利用软件进行计算式时速度更慢，（2）功耗大，由于计算速度慢，当数值较大时，无论硬件（FPGA或ASIC）还是软件，系统长期处在计算中，因此动态平均功耗都比较大。在数值较大要求快速计算或低功耗系统中时不能满足要求，因此提出一种快速算法–权值变换法。下面介绍权值变换的基本原理。
1. 二进制带有权值的加法可以由移位替代
无论采用哪种变换，基本要求是转换后的数值与转换前的数值表达的含义不变，如X=4’b1111，转换成BCD码后为15，用两个4位二进制表示为 A=4’b0101, B =4’b0001, 其中A为低位， B为高位；B的权值为10，A的权值为1。即X=BA =B *10 + A。由于4位二进制与10进制的关系比较简单，通过观察的方法就可以实现，当数字大于4位后，二者的对应关系就不直观，因此需要一种通用的计算方法实现。下面还是以X=4’b1111为例，观察数据的特点找出对应关系。X=4’b1111可以表示为：
X=1 * 23 + 1 * 22 + 1 * 21 + 1 * 20 （1） 注：* 表示乘法
式（1）可以等效变换为：
X=（（（1 * 20）* 2 + 1 * 20）* 2 + 1 * 20）* 2 + 1 * 20 （2）
式（2）可以理解为用如下步骤实现：
Tn = Y[3:0] , 用T 来表示Y在每一个步骤下的值
赋初值： X = 4’b1111; Y = 4’b0000
- 将X[3]取出，放入新的4位二进制Y中的最低位， 用T0表示，T0 = 4’b0001;
- 将T0 * 2（乘2在逻辑上可以用移位实现）， 用T1表示， T1 = 4’b0010；
- T1 + X[2]， 用T2表示，T2 = 4’b0011；
- T2 * 2（左移一位）， 用T3表示 ，T3 = 4’b0110；
- T3 + X[1]， 用T4表示， T4 = 4’b0111;
- T4 * 2（左移一位）， 用T5表示，T5 = 4’b1110;
- T5 + X[0]， 用T6表示，T6 = 4’b1111;
上面通过左移和加法实现了带权值的计算过程，最终结果T6与原给定的值相同。上面的操作步骤可以用表1的方式描述。
表1
| 步骤 | Tn | 计算后结果（Y） | 原始4位2进制数（X） | 等效操作 | 描述 | ||||||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | X= 4’b1111; Y = 4’b0000 | 原始数据 | |
| 1 | T0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | {Y, X} = {Y, X} << 1 | X的最高位放入Y的最低位中，X 左移一位 |
| 2 | T1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | Y = Y << 1 | Y左移一位 |
| 3 | T2 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | Y= Y + X[3]; X = X << 1 | X的最高位+Y，X 左移一位 |
| 4 | T3 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | Y = Y << 1 | Y左移一位 |
| 5 | T4 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | Y= Y + X[3]; X = X << 1 | X的最高位+Y，X 左移一位 |
| 6 | T5 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | Y = Y << 1 | Y左移一位 |
| 7 | T6 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | Y= Y + X[3]; X = X << 1 | X的最高位+Y，X 左移一位 |
表1也可以简化为表2的方式，只用4步就可以完成（ {Y, X} = {Y, X} << 1 ）。
表2
| 步骤 | T | 计算后结果（Y） | 原始4位2进制数（X） | 描述（将X的值逐位移到Y中） | ||||||
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 原始数据 | |
| 1 | T0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | X 左移一位，Y左移一位 |
| 2 | T1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | X 左移一位，Y左移一位 |
| 3 | T2 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | X 左移一位，Y左移一位 |
| 4 | T3 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | X 左移一位，Y左移一位 |
可见，移位加完全可以由移位替代实现带有权值为2的加法计算。上面的给出4位二进制的移位加的算法，其实这个算法可以完全适用于n位二进制。
对于通用的一个n位二进制数，例如X[n-1:0] = {An-1, An-2, … A1, A0}； Ak（k = 0，1，… n-1）的值可以为1或是0。类似于上述的式子（1），X可以表示为：
X=An-1 * 2n-1 + An-2 * 2n-2 + An-3 * 2n-3 +… + A1 * 21 + A0 * 20 （3 ）
式（3）可以化简表示为：
同样的，式（3）可以等效变换为：
X=（（（（（An-1 * 20）* 2 + An-2 * 20）* 2 + An-3 * 20）…) * 2 + A1 * 20 ）* 2 + A0 * 20 （4）
用上述步骤同样通过左移和加法也可以实现式（4）（可通过扩展表1，表2实现）。
2. 4位2进制转换为权值为10的BCD
4位二进制表达的16进制数与10进制BCD码的关系分为两个部分，当数值小于等于9，16进制与十进制相同，而当数值大于9时需要两位BCD码表示，其中高位的BCD的权值为10，见表3。
表3
| 序号 | 4位2进制 | 16进制 | BCD高位 | BCD低位 | 10进制数 | 描述
16进制关系与BCD |
| 0 | 4’b0000 | 4’h0 | 4’b0000 | 4’b0000 | 4’d00 | 相同 |
| 1 | 4’b0001 | 4’h1 | 4’b0000 | 4’b0001 | 4’d01 | 相同 |
| 2 | 4’b0010 | 4’h2 | 4b0000 | 4’b0010 | 4’d02 | 相同 |
| 3 | 4’b0011 | 4’h3 | 4’b0000 | 4’b0011 | 4’d03 | 相同 |
| 4 | 4’b0100 | 4’h4 | 4’b0000 | 4’b0100 | 4’d04 | 相同 |
| 5 | 4’b0101 | 4’h5 | 4’b0000 | 4’b0101 | 4’d05 | 相同 |
| 6 | 4’b0110 | 4’h6 | 4’b0000 | 4’b0110 | 4’d06 | 相同 |
| 7 | 4’b0111 | 4’h7 | 4’b0000 | 4’b0111 | 4’d07 | 相同 |
| 8 | 4’b1000 | 4’h8 | 4’b0000 | 4’b1000 | 4’d08 | 相同 |
| 9 | 4’b1001 | 4’h9 | 4’b0000 | 4’b1001 | 4’d09 | 相同 |
| 10 | 4’b1010 | 4’ha | 4’b0001 | 4’b0000 | 4’d10 | +6 |
| 11 | 4’b1011 | 4’hb | 4’b0001 | 4’b0001 | 4’d11 | +6 |
| 12 | 4’b1100 | 4’hc | 4’b0001 | 4’b0010 | 4’d12 | +6 |
| 13 | 4’b1101 | 4’hd | 4’b0001 | 4’b0011 | 4’d13 | +6 |
| 14 | 4’b1110 | 4’he | 4’b0001 | 4’b0100 | 4’d14 | +6 |
| 15 | 4’b1111 | 4’hf | 4’b0001 | 4’b0101 | 4’d15 | +6 |
从表3的描述可以看出，4位2进制数到BCD的转换非常简单，因为16进制的权值为16，比10进制的权值大6，如果4位2进制数大于9，只要将该数+6产生进位就可以使用16进制数表示BCD码了。公式如下：
式（5）中M为大于9的4位二进制数，B = 1，C小于6的4位二进制数，B，C为4位二进制数表达的BCD码（10进制数）。
4’hM = 1 * 10 + C （6）
从式（6）可以看出10进制的高位为1已经确定，C = 4’hM – 10, 对于模16的运算减10与加6（4’b1010的补码）相同，即C = 4’hM + 6，4’hM + 6丢弃进位位的结果就是C的值。
3. 多位十进制的移位加运算
假设X为8位二进制数， KMN为12位二进制数组成的BCD码，其中K，M，N都是4位二进制数，K的权值为102，M的权值为101，N的权值为100。十进制的移位加法运算与2进制加法运算非常类似，只是确保每个4位BCD都是逢10进1。
例：将二进制数8’b1101_1011转换成对应的BCD码。
表4
| 步骤 | BCD码 | 8位二进制数 | 描述 | |||||
| K | Mcy | M | Ncy | N | P | Q | ||
| 0000 | 0 | 0000 | 0 | 0000 | 1101 | 1011 | 赋初值 | |
| 1 | 0000 | 0 | 0000 | 0 | 0001 | 1011 | 0110 | 左移一位 |
| 2 | 0000 | 0 | 0000 | 0 | 0011 | 0110 | 1100 | 左移一位 |
| 3 | 0000 | 0 | 0000 | 0 | 0110 | 1101 | 1000 | 左移一位 |
| 4 | 0000 | 0 | 0000 | 0 | 1101 | 1011 | 0000 | 左移一位，N = 1101 > 9，将+6调整 |
| 5 | 0000 | 0 | 0001 | 0 | 0011 | 1011 | 0000 | 4’b1101 + 4’b0110，调整后的结果为
N = 4’b0011，M = M + 1 |
| 6 | 0000 | 0 | 0010 | 0 | 0111 | 0110 | 0000 | 左移一位 |
| 7 | 0000 | 0 | 0100 | 0 | 1110 | 1100 | 0000 | 左移一位，N = 1110 > 9，将+6调整 |
| 8 | 0000 | 0 | 0101 | 0 | 0100 | 1100 | 0000 | 4’b1110 + 4’b0110，调整后的结果为
N = 4’b0100，M = M + 1 |
| 9 | 0000 | 0 | 1010 | 0 | 1001 | 1000 | 0000 | 左移一位，M = 1010 > 9，将+6调整 |
| 10 | 0001 | 0 | 0000 | 0 | 1001 | 1000 | 0000 | 4’b1010 + 4’b0110，K = K + 1 |
| 11 | 0010 | 0 | 0000 | 1 | 0011 | 0000 | 0000 | 左移一位，{Ncy，N} = 5’b10011 > 9，将+6调整 |
| 12 | 0010 | 0 | 0001 | 0 | 1001 | 0000 | 0000 | 5’b10011 + 4’b0110，
调整后的结果为 N = 4’b1001，M = M + 1 |
| 13 | 0010 | 0 | 0001 | 0 | 1001 | 0000 | 0000 | 十进制BCD
KMN = 219 |
Ncy和Mcy都表示临时进位位，当某个BCD码为８或９时（如步骤10中N 为4’b1001，最高位为1），由于该值小于10因此没有达到调整的条件，但在下次移位加时将超过16，因此需要保留该进位保持移位后数据不会丢失。表4经过12步的移位加及进位调整，最终将计算结果十进制219正确计算出来了，但也可以看出，上面的计算步骤需要在BCD的高位前保留一个进位位，同时权值调整是通过加１实现的，因此这个算法虽然易于理解，但不易通过简洁程序实现。
4. 移位运算中实现权值调整
上面介绍了两部分内容，（1）二进制数可以表示为移位加的过程，（2）进制转换时利用二者的权值差进行调整。只要将上面的两个步骤合并，在移位加的过程中只要能进行权值调整就可以完成二进制到十进制的转换。但在移位加的过程中应注意调整也是动态的。
-
超前预测权值调整
在4位二进制到10进制的调整中，当4位二进制的值大于9时应加6并将进位位计入高位的十进制的，但这种处理方式非常繁琐，因为每个BCD码需要保留临时的进位位，同时低位十进制运算的进位会引起多个高位的连锁计算。那么如何像二进制移位加那样只需要移位并通过权值调整实现呢？答案是可以通过超前预测进行权值调整。上面的计算主要出现在当某个BCD码为８或９时，由于该值小于10因此没有达到调整的条件，但在下次移位加时将超过16，因此需要保留该进位，从而保证移位后数据不会丢失。
超前预测的算法是判断
1）BCD码是否大于等于 5，如果大于等于 5，下次移位加的结果一定会产生进位，也就是向高位BCD码进位，因此可以提前进行权值调整，当下次移位加时从低位BCD码到高位BCD码的进位通过移位自动实现。
2）BCD码是否小于等于 4，只有移位，不需要调整
假设B，A为4位二进制BCD码，B为高位，且B < 5，这里我们只是讨论A的步骤如下：
-
- 判断A是否大于等于5，如果大于等于5则进入步骤2； 否则 正常移位（没有加法），保持步骤1
- 根据权值调整A + Xadj
- 移位加 （A + Xadj） * 2 + Y = A * 2 + Xadj * 2 + Y
- B左移并加1，B * 2 + 1
- 计算Xadj； 由于Xadj *2 = 6（权值差），因此Xadj = 3，即Xadj = 4’b0011;
注： Xadj表示调整值，Y是从二进制数移位过来的单比特数
步骤3中由于A + Xadj的结果使A的最高位为1，左移后会自动将1移到BCD的高位Ｂ中，而A也由于对A * 2 + Y进行Xadj * 2的调整回归到正常的BCD码范围内。如果B > 4，对B采用同样的算法。算法测试见表5
表5
| 步骤 | BCD码 | 8位2进制数 | 描述 | |||
| C | B | A | M | N | ||
| 0000 | 0000 | 0000 | 1101 | 1011 | ||
| 1 | 0000 | 0000 | 0001 | 1011 | 0110 | 左移一位 |
| 2 | 0000 | 0000 | 0011 | 0110 | 1100 | 左移一位 |
| 3 | 0000 | 0000 | 0110 | 1101 | 1000 | 左移一位 |
| 0000 | 0000 | 1001 | 1101 | 1000 | 4’b0110 >= 5; A +3 | |
| 4 | 0000 | 0001 | 0011 | 1011 | 0000 | 左移一位 |
| 5 | 0000 | 0010 | 0111 | 0110 | 0000 | 左移一位 |
| 0000 | 0010 | 1010 | 0110 | 0000 | 4’b0111 >= 5; A+3 | |
| 6 | 0000 | 0101 | 0100 | 1100 | 0000 | 左移一位 |
| 0000 | 1000 | 0100 | 1100 | 0000 | 4’b0101 >= 5; B+3 | |
| 7 | 0001 | 0000 | 1001 | 1000 | 0000 | 左移一位 |
| 0001 | 0000 | 1100 | 1000 | 0000 | 4’b1001 >= 5; A+3 | |
| 8 | 0010 | 0001 | 1001 | 0000 | 0000 | 左移一位 |
| 最后一次移位后，尽管4’b1001 >= 5，A不需要再调整 | ||||||
| 0010 | 0001 | 1001 | 0000 | 0000 | 十进制BCD
CBA=219 |
|
表5所示的例子虽然使用了具体的二进制数的例子来演示，但是算法具有普遍性，可以实现任意16进制数到BCD码的转换。
5. 移位加Verilog算法
利用移位加及权值调整算法可以实现任意位2进制到BCD的转换。Verilog的算法实现可以参照例1的方式实现。
例1：利用Verilog 实现32位二进制数到BCD的转换。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
`timescale 1ns / 1ps module HEX2BCD ( input rst, input sys_clk, input start, input [ 31: 0 ] hex, output reg [ 3: 0 ] ones, output reg [ 3: 0 ] tens, output reg [ 3: 0 ] hundreds, output reg [ 3: 0 ] thousands, output reg [ 3: 0 ] ten_thousands, output reg [ 3: 0 ] hund_thousands, output reg [ 3: 0 ] million, output reg [ 3: 0 ] ten_million, output reg [ 3: 0 ] hund_million, output reg [ 3: 0 ] th_million, output reg rdy ); reg [ 3: 0 ] count; reg [ 31: 0 ] hex_reg; integer i; always @ ( * ) begin hex_reg = hex; ones = 0; tens = 0; hundreds = 0; thousands = 0; ten_thousands = 0; hund_thousands = 0; million = 0; ten_million = 0; hund_million = 0; th_million = 0; for ( i = 31; i >= 0; i = i - 1 ) begin if ( th_million >= 5 ) th_million = th_million + 3; if ( hund_million >= 5 ) hund_million = hund_million + 3; if ( hund_million >= 5 ) ten_million = ten_million + 3; if ( million >= 5 ) million = million + 3; if ( hund_thousands >= 5 ) hund_thousands = hund_thousands + 3; if ( ten_thousands >= 5 ) ten_thousands = ten_thousands + 3; if ( thousands >= 5 ) thousands = thousands + 3; if ( hundreds >= 5 ) hundreds = hundreds + 3; if ( tens >= 5 ) tens = tens + 3; if ( ones >= 5 ) ones = ones + 3; th_million = th_million << 1; th_million[ 0 ] = hund_million[ 3 ]; hund_million = hund_million << 1; hund_million[ 0 ] = ten_million[ 3 ]; ten_million = ten_million << 1; ten_million[ 0 ] = million[ 3 ]; million = million << 1; million[ 0 ] = hund_thousands[ 3 ]; hund_thousands = hund_thousands << 1; hund_thousands[ 0 ] = ten_thousands[ 3 ]; ten_thousands = ten_thousands << 1; ten_thousands[ 0 ] = thousands[ 3 ]; thousands = thousands << 1; thousands[ 0 ] = hundreds[ 3 ]; hundreds = hundreds << 1; hundreds[ 0 ] = tens[ 3 ]; tens = tens << 1; tens[ 0 ] = ones[ 3 ]; ones = ones << 1; ones[ 0 ] = hex_reg[ 31 ]; hex_reg = { hex_reg[ 30: 0 ], 1'b0 }; end end reg [ 1: 0 ] st; always@( posedge sys_clk or posedge rst ) if ( rst ) begin count <= 0; rdy <= 0; st <= 0; end else begin rdy <= 0; if ( count == 3 ) begin count <= 0; rdy <= 1'b1; end else count <= count + 1; case ( st ) 0: begin if ( start ) st <= 1; end 1: begin if ( count == 2 ) begin count <= 0; st <= 2; end else count <= count + 1; end 2: begin st <= 0; rdy <= 1'b1; end default: st <= 0; endcase end endmodule |
顶层设计文件：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
`timescale 1ns / 1ps module top( input OSC_CLK, input start, input [ 31: 0 ] hex, output [ 3: 0 ] ones, output [ 3: 0 ] tens, output [ 3: 0 ] hundreds, output [ 3: 0 ] thousands, output [ 3: 0 ] ten_thousands, output [ 3: 0 ] hund_thousands, output [ 3: 0 ] million, output [ 3: 0 ] ten_million, output [ 3: 0 ] hund_million, output [ 3: 0 ] th_million, output rdy ); wire clk_100m; wire locked; clk_wiz_0 instance_name ( // Clock out ports .clk_out1(clk_100m), // output clk_out1 // Status and control signals .reset(1'b0), // input reset .locked(locked), // output locked // Clock in ports .clk_in1(OSC_CLK) // input clk_in1 ); wire sys_rst = ~locked; HEX2BCD HEX2BCD_inst ( .rst (sys_rst ), .sys_clk (clk_100m ), .start (start ), .hex (hex ), .ones (ones ), .tens (tens ), .hundreds (hundreds ), .thousands (thousands ), .ten_thousands (ten_thousands ), .hund_thousands (hund_thousands), .million (million ), .ten_million (ten_million ), .hund_million (hund_million ), .th_million (th_million ), .rdy (rdy ) ); endmodule |
仿真文件：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
`timescale 1ns / 1ps module sim_tb( ); reg clk = 0; always clk = #10 ~clk; reg start = 0; reg [ 31: 0 ] hex = 0; wire rdy; integer i; initial begin start = 0; hex = 0; #100; while (top_inst.sys_rst) @(posedge top_inst.clk_100m); for(i = 0; i< 999999; i = i + 1) begin start = 1; hex = i; @(posedge top_inst.clk_100m); start = 0; while (!rdy) @(posedge top_inst.clk_100m); end #2000; $stop; end wire [ 3: 0 ] ones; wire [ 3: 0 ] tens; wire [ 3: 0 ] hundreds; wire [ 3: 0 ] thousands; wire [ 3: 0 ] ten_thousands; wire [ 3: 0 ] hund_thousands; wire [ 3: 0 ] million; wire [ 3: 0 ] ten_million; wire [ 3: 0 ] hund_million; wire [ 3: 0 ] th_million; top top_inst ( .OSC_CLK (clk ), .start (start ), .hex (hex ), .ones (ones ), .tens (tens ), .hundreds (hundreds ), .thousands (thousands ), .ten_thousands (ten_thousands ), .hund_thousands (hund_thousands), .million (million ), .ten_million (ten_million ), .hund_million (hund_million ), .th_million (th_million ), .rdy (rdy ) ); endmodule |
仿真波形图：
图1 仿真波形图
从图1中可以看出仿真波形结果是正确的。当前16进制数转换成BCD码主要是由组合逻辑实现的，理论上，每个时钟周期都可以完成计算。但是如果提高时钟主频，比如大于100 MHz，那么组合逻辑链过长，很难满足FPGA的时序收敛。后续文章会优化Verilog实现，以满足时序收敛。
对应视频：