FPGA基础知识极简教程（10）二进制到BCD转换算法

写在前面

FPGA基础知识极简教程（9）讲到了七段数码管的显示Verilog设计，我们都知道，要在数码管上显示的数字，使用BCD编码是具有优势的（或者是最正确的）。拿数字时钟来说，如果你的时钟是12点，难道你会让数码管显示C？
如果你愿意如此，那就给自己家里安装一个这样的时钟吧！
如果是23点呢？不用BCD编码的数字恐怕不能显示了吧。
采用BCD码的数字，十位用一个数码管显示，个位用一个数码管显示，例如23点，则2和3分别显示，这样才符合人类的思维。

尽管如此，存在这样一个问题，我们在设计计数器的时候，习惯于直接设计二进制计数器，这样的计数器计数结果是二进制的，我们需要将其转换成BCD码，这就是今天我们需要讨论的问题。

当然，值得讨论的是这种方式是不是多此一举呢？如果仅仅对于数字时钟来说，时需要BCD编码的模24计数器，分以及秒则需要BCD编码的模60计数器。
这都很容易实现，例如上篇博客就是直接实现的BCD编码的模60以及模24计数器。之后送入数码管显示模块即可。
那么我们还有必要设计二进制转BCD码的必要吗？
有的！

首先这是一种方法，也算经典，它的另外一个名字叫：
Double-Dabble Binary-to-BCD Conversion Algorithm
我也不知道怎么翻译合适！
其次，如果一个计数模块，即用到了二进制计数，又必须把它显示到数码管上，我们恐怕就不能直接将这个计数器设计为BCD码计数器了，更方便的方式是设计一个二进制计数器，需要显示的话，在调用二进制转BCD码模块，接入数码管显示模块即可。
你可能会说，可以设计一个BCD码计数器，之后转换成二进制！
呃，你认为这个工作量会小一点吗？
最后，我认为这个算法还提供了一个思想，如何处理Verilog中的循环问题？

我参考了互联网上的资料，形成了本文，这里将分享一种双重循环的设计方法，以及一种将循环转化为隐似的处理方法，也就是状态机的方式来实现！

一起来看看吧。

正文

快速认识

为了快速了解这个算法，我觉得先看一个小例子比较合适：
我们假设的二进制数为8位（11110011），如何将其转换为BCD码呢？
8位2进制数最大能表示的数字为255，用BCD码表示，需要12位来表示。上面的二进制数是1111_0011，对应的十进制为243，我们知道，它的BCD码形式为：0010_0100_0011。
有了这些先验知识，我们来看看如何转换的！

首先，先将BCD码计数器清零，之后将二进制数和BCD码计数器统统左移，二进制数移出来的最高位放到BCD码计数器的最低位，如下表所示！

百	十	个	二进制	操作
0000	0000	0000	11110011	Initialization
0000	0000	0001	11100110	Shift
0000	0000	0011	11001100	Shift
0000	0000	0111	10011000	Shift
0000	0000	1010	10011000	Add 3 to ONES, since it was 7
0000	0001	0101	00110000	Shift
0000	0001	1000	00110000	Add 3 to ONES, since it was 5
0000	0011	0000	01100000	Shift
0000	0110	0000	11000000	Shift
0000	1001	0000	11000000	Add 3 to TENS, since it was 6
0001	0010	0001	10000000	Shift
0010	0100	0011	00000000	Shift
2	4	3

每一次移位之后都判断下，BCD码计数器的十、分以及个位是否大于4，如果任何一位（4bit）大于4，则对其加3，之后继续移位，如此下去，直到移位次数为二进制数的位数之后，停止移位，此时得到的BCD码计数值便是转换后的值。

实现方式一

维基百科：给出了一种Verilog的实现方式：

`timescale 1ns / 1ps
module binTobcd
 #( parameter                W = 18)  // input width
  ( input      [W-1      :0] bin   ,  // binary
    output reg [W+(W-4)/3:0] bcd   ); // bcd {...,thousands,hundreds,tens,ones}

  integer i,j;

  always @(bin) begin
    for(i = 0; i <= W+(W-4)/3; i = i+1) bcd[i] = 0;     // initialize with zeros
    bcd[W-1:0] = bin;                                   // initialize with input vector
    for(i = 0; i <= W-4; i = i+1)                       // iterate on structure depth
      for(j = 0; j <= i/3; j = j+1)                     // iterate on structure width
        if (bcd[W-i+4*j -: 4] > 4)                      // if > 4
          bcd[W-i+4*j -: 4] = bcd[W-i+4*j -: 4] + 4'd3; // add 3
  end

endmodule

该实现方式采用了双重循环的组合逻辑实现，我对其进行了行为仿真，如下：

仿真图

看起来貌似没有任何问题，但不得不考虑的是，行为仿真时不考虑延迟的，如果在实际的电路中，这种实现方式会不会影响时序呢？
答案几乎是肯定的，请看下面的RTL原理图，这种组合逻辑的延迟链很长！如果位宽更大，则延迟也随着增大。

RTL原理图

实现方式二

参考资料给出了一种状态机的实现方式。

其原理也是：
它以输入的二进制数为起点。它将它一次移位一位到BCD输出向量中。然后，它将独立查看每个4位BCD数字。如果任何数字都大于4，则该数字将增加3。对于输入二进制向量中的每个位，此循环都会继续。请参见下图，以直观方式描述有限状态机的编写方式。

状态机

根据此状态机以及转换原理，得到的Verilog设计为：

module bin2bcd #(
    parameter INPUT_WIDTH = 6,
    parameter DECIMAL_DIGITS = 2
    )(
    input i_Clock,
    input [INPUT_WIDTH - 1 : 0] i_Binary,
    input i_Start,
    output [DECIMAL_DIGITS * 4 - 1 : 0] o_BCD,
    output o_DV
    );


    parameter s_IDLE = 3'b000, s_SHIFT = 3'b001, s_CHECK_SHIFT_INDEX = 3'b010, s_ADD = 3'b011,
          s_CHECK_DIGIT_INDEX = 3'b100, s_BCD_DONE = 3'b101;

    reg [2:0] r_SM_Main = s_IDLE;
   
  // The vector that contains the output BCD
    reg [DECIMAL_DIGITS*4 - 1 : 0] r_BCD = 0;
    
  // The vector that contains the input binary value being shifted.
  reg [INPUT_WIDTH-1:0] r_Binary = 0;
      
  // Keeps track of which Decimal Digit we are indexing
  reg [DECIMAL_DIGITS-1:0] r_Digit_Index = 0;
    
  // Keeps track of which loop iteration we are on.
  // Number of loops performed = INPUT_WIDTH
  reg [7:0] r_Loop_Count = 0;
 
  wire [3:0] w_BCD_Digit;
    reg r_DV = 1'b0;                       
    
  always @(posedge i_Clock) begin
      case (r_SM_Main) 
  
        // Stay in this state until i_Start comes along
        s_IDLE :
          begin
            r_DV <= 1'b0;
             
            if (i_Start == 1'b1)
              begin
                r_Binary  <= i_Binary;
                r_SM_Main <= s_SHIFT;
                r_BCD     <= 0;
              end
            else
              r_SM_Main <= s_IDLE;
          end
                 
  
        // Always shift the BCD Vector until we have shifted all bits through
        // Shift the most significant bit of r_Binary into r_BCD lowest bit.
        s_SHIFT :
          begin
            r_BCD     <= r_BCD << 1;
            r_BCD[0]  <= r_Binary[INPUT_WIDTH-1];
            r_Binary  <= r_Binary << 1;
            r_SM_Main <= s_CHECK_SHIFT_INDEX;
          end          
         
  
        // Check if we are done with shifting in r_Binary vector
        s_CHECK_SHIFT_INDEX :
          begin
            if (r_Loop_Count == INPUT_WIDTH-1)
              begin
                r_Loop_Count <= 0;
                r_SM_Main    <= s_BCD_DONE;
              end
            else
              begin
                r_Loop_Count <= r_Loop_Count + 1;
                r_SM_Main    <= s_ADD;
              end
          end
                 
  
        // Break down each BCD Digit individually.  Check them one-by-one to
        // see if they are greater than 4.  If they are, increment by 3.
        // Put the result back into r_BCD Vector.  
        s_ADD :
          begin
            if (w_BCD_Digit > 4)
              begin                                     
                r_BCD[(r_Digit_Index*4)+:4] <= w_BCD_Digit + 3;  
              end
             
            r_SM_Main <= s_CHECK_DIGIT_INDEX; 
          end       
         
         
        // Check if we are done incrementing all of the BCD Digits
        s_CHECK_DIGIT_INDEX :
          begin
            if (r_Digit_Index == DECIMAL_DIGITS-1)
              begin
                r_Digit_Index <= 0;
                r_SM_Main     <= s_SHIFT;
              end
            else
              begin
                r_Digit_Index <= r_Digit_Index + 1;
                r_SM_Main     <= s_ADD;
              end
          end
         
  
  
        s_BCD_DONE :
          begin
            r_DV      <= 1'b1;
            r_SM_Main <= s_IDLE;
          end
         
         
        default :
          r_SM_Main <= s_IDLE;
            
      endcase
    end // always @ (posedge i_Clock)  
 
   
  assign w_BCD_Digit = r_BCD[r_Digit_Index*4 +: 4];
       
  assign o_BCD = r_BCD;
  assign o_DV  = r_DV;
      
endmodule // Binary_to_BCD

需要注意两个位宽问题，一是输入二进制数的位宽INPUT_WIDTH，还有一个参数DECIMAL_DIGITS表示的是BCD码的个数，这里的个数指的是写成十六进制后的个数，每4位二进制数算一个。（表达真特么别扭）

如果细心看这段代码的话，会发现状态机是真的强大，我们常听说一切皆可状态机，关键是你的状态机设计的是否正确，之后是否巧妙！

代码中，从s_SHIFT状态到s_CHECK_DIGIT_INDEX 是构成循环的部分。如下：

 s_SHIFT :
          begin
            r_BCD     <= r_BCD << 1;
            r_BCD[0]  <= r_Binary[INPUT_WIDTH-1];
            r_Binary  <= r_Binary << 1;
            r_SM_Main <= s_CHECK_SHIFT_INDEX;
          end          
         
  
        // Check if we are done with shifting in r_Binary vector
        s_CHECK_SHIFT_INDEX :
          begin
            if (r_Loop_Count == INPUT_WIDTH-1)
              begin
                r_Loop_Count <= 0;
                r_SM_Main    <= s_BCD_DONE;
              end
            else
              begin
                r_Loop_Count <= r_Loop_Count + 1;
                r_SM_Main    <= s_ADD;
              end
          end
                 
  
        // Break down each BCD Digit individually.  Check them one-by-one to
        // see if they are greater than 4.  If they are, increment by 3.
        // Put the result back into r_BCD Vector.  
        s_ADD :
          begin
            if (w_BCD_Digit > 4)
              begin                                     
                r_BCD[(r_Digit_Index*4)+:4] <= w_BCD_Digit + 3;  
              end
             
            r_SM_Main <= s_CHECK_DIGIT_INDEX; 
          end       
         
         
        // Check if we are done incrementing all of the BCD Digits
        s_CHECK_DIGIT_INDEX :
          begin
            if (r_Digit_Index == DECIMAL_DIGITS-1)
              begin
                r_Digit_Index <= 0;
                r_SM_Main     <= s_SHIFT;
              end
            else
              begin
                r_Digit_Index <= r_Digit_Index + 1;
                r_SM_Main     <= s_ADD;
              end
          end

从状态转移图中也可以清晰看出这个循环：

状态转移图

先对二进制以及BCD码寄存器进行移位，

s_SHIFT :
          begin
            r_BCD     <= r_BCD << 1;
            r_BCD[0]  <= r_Binary[INPUT_WIDTH-1];
            r_Binary  <= r_Binary << 1;
            r_SM_Main <= s_CHECK_SHIFT_INDEX;
          end

之后判断循环结束了吗？

s_CHECK_SHIFT_INDEX :
          begin
            if (r_Loop_Count == INPUT_WIDTH-1)
              begin
                r_Loop_Count <= 0;
                r_SM_Main    <= s_BCD_DONE;
              end
            else
              begin
                r_Loop_Count <= r_Loop_Count + 1;
                r_SM_Main    <= s_ADD;
              end
          end

循环条件是循环次数，我们都知道，循环次数是二进制数的位数。
如果循环结束，则进入下一个状态s_BCD_DONE：

s_BCD_DONE :
          begin
            r_DV      <= 1'b1;
            r_SM_Main <= s_IDLE;
          end

在这个状态内，我们可以使用BCD值，r_DV是一个标志，有效则代表BCD值可以使用了。

如果没有结束循环，则进入状态s_ADD，

s_ADD :
          begin
            if (w_BCD_Digit > 4)
              begin                                     
                r_BCD[(r_Digit_Index*4)+:4] <= w_BCD_Digit + 3;  
              end
             
            r_SM_Main <= s_CHECK_DIGIT_INDEX; 
          end

判断BCD码的个位是否大于4，如果大于4，则加3，之后进入状态：s_CHECK_DIGIT_INDEX

 s_CHECK_DIGIT_INDEX :
          begin
            if (r_Digit_Index == DECIMAL_DIGITS-1)
              begin
                r_Digit_Index <= 0;
                r_SM_Main     <= s_SHIFT;
              end
            else
              begin
                r_Digit_Index <= r_Digit_Index + 1;
                r_SM_Main     <= s_ADD;
              end
          end

如果BCD码只有个位，则进入s_SHIFT状态，移位，判断循环结束了没！
否则，还有十位，甚至百位，则继续进入s_ADD，判断是否大于4，如果大于4，加3，直到遍历了BCD的各个位（这里的位指的是4位二进制数组成的一位BCD码）。

讲到这里，大概程序就没什么问题了。

最后还需要注意的是，程序里面的输入输出，寄存器变量以及wire变量，以及参数的命名方式都遵循博文所提倡的代码风格。

做一个简单的仿真：

仿真文件：

`timescale 1ns / 1ps

module bin2bcd_tb(

    );
    parameter INPUT_WIDTH = 6;
    parameter DECIMAL_DIGITS = 2;

    reg i_Clock;
    reg [INPUT_WIDTH - 1 : 0] i_Binary;
    reg i_Start;
    wire [DECIMAL_DIGITS * 4 - 1 : 0] o_BCD;
    wire o_DV;


    initial begin
        i_Clock = 0;
        forever begin
            #5 i_Clock = ~i_Clock;
        end
    end

    initial begin
        i_Start = 0;

        i_Binary = 31;

        repeat(5) @(posedge i_Clock);
        i_Start = 1;

        repeat(6) @(negedge i_Clock);
        i_Binary = 18; 

    end


    bin2bcd #(.INPUT_WIDTH(INPUT_WIDTH), .DECIMAL_DIGITS(DECIMAL_DIGITS))
    inst_bin2bcd(
        .i_Clock(i_Clock),
        .i_Binary(i_Binary),
        .i_Start(i_Start),
        .o_BCD(o_BCD),
        .o_DV(o_DV)
        );


endmodule

仿真波形：

仿真波形

好了，就到这里吧，相信你已经很明白了。

写在最后

最近在忙毕业的事情，还有入职前租房子的各种事情，所以，博客落下了几天，断断续续地准备这个话题，终于可以发了一篇。
对了，这里面的代码也用到了一个2001之后新增语法：

 assign w_BCD_Digit = r_BCD[r_Digit_Index*4 +: 4];

可以在下面这篇博客里找到解释！有人说这个语法，花里胡哨，但是到今天，我发现这种用法很常见，因此，学着去用吧。

参考资料语法解释

最后的最后，推荐下我的微信公众号：FPGA LAB，可以关注我，没事，我都会每天推送文章，阅读更方便。