把二進制變成BCD碼需要幾步？——漫談大四加三算法的Verilog實現

把二進制變成BCD碼需要幾步？——漫談大四加三算法的Verilog實現

Hi，大家好！我是至芯科技的李老師。
今天講課的題目比較有意思，它是一個小問題：把二進制變成BCD碼需要幾步？
請大家思考一下。有同學可能回答需要三步，為什么��？
因為啊，把大象放進冰箱里需要三步，第一步，把冰箱門打開，第二步，把大象放進去，第三步，把冰箱門關上。
類似的，把二進制變成BCD碼，也需要三步。
blablablabla ......
當然啦，這是開玩笑了。不過，歪打正著，答案確實是三步。
究竟是怎么回事呢？我們下面細細說來，原理說透之后，我們演示一下具體的Verilog實現過程。

首先，看一下下面這張表格，把二進制（8’hFF）轉換為BCD（12’h255）的步驟列表。

什么是二進制轉BCD？有什么用？

4位二進制是16進制數，而生活中常用的數制是10進制數。
怎么樣用計算機來理解、表達生活中的10進制數？這就需要進行16進制數與10進制數的相互轉換了。
而BCD碼（Binary-Coded Decimal）正是計算機常用的一種表達方式。
它是一種以二進制表示的十進制數碼。
比如說，至芯科技ZX-1開發板上的六位數碼管顯示數字可以是16進制的000000~FFFFFF，但是更為方便的方法是000000~999999。
六位數碼管顯示六位數字用十六進制，比如說是0F423F，誰也不知道是多少，但是它對應的十進制數999999，大家肯定很熟悉。
很多場合，我們和機器之間溝通用10進制更方便，但計算機是用01編碼的。需要進行人機之間的溝通和轉換。
解決的方法就是用二進制的方式來存儲、計算數值，但是用10進制的方式來顯示這些數值，BCD碼就起到了橋梁的作用。
注意，16進制屬于二進制的一種形式，希望大家理解這點，包括8進制也是。


當然，道理容易明白。但究竟機器又是怎樣實現二進制和BCD碼的轉換的呢？
注意，轉換是雙向的，既可以把二進制轉換成BCD碼，也可以把BCD碼轉換成二進制數。
可以想象BCD碼轉成二進制相對比較簡單。
舉個例子吧，比如說BCD碼255，要轉換成二進制。
計算機里面存的BCD碼是12'h255（對應二進制為12'b0010_0101_0101），肯定不能直接進行運算，必須要轉換成機器識別的二進制數值12'h0FF（對應二進制為12'b0000_1111_1111）。
先算前兩位，直接2*10+5，得到結果25，然后再將結果*10+下一位，即25*10+5，最終結果為255，完了。
就這么簡單。當然這里255只有三位BCD位，如果更多的話，以此類推。
將前一步結果*10+下一位，得到當前結果。
當然實現起來還有一些小的技巧，x*10要占用乘法器資源，如果乘法器資源足夠那無所謂，但在資源有限的情況下通常用(x<<3)+(x<<1)（對應x*8+x*2）來實現。
即用移位和加法來代替乘法操作。
當然也可以把BCD數字的每一位直接變成各種左移數值的組合，比如x*100 = x*64 + x*32 * x*4 = (x<<6) +( x<<5) + (x<<2)。
上面就是BCD碼轉成二進制的實現原理，這個比較簡單，我們這里略微帶過。

本課重點講解的是反過來怎么實現，即怎么把二進制轉換成BCD碼？
比如說，二進制數12'h0FF，要轉換成BCD碼255。
這個有點難，常見的做法是使用上圖中提到的大四加三算法。
當然你可以用查表法，比如說256以內的數值，直接用查表的方式，一一對應，就像我們FPGA采用LUT表實現真值表那樣，或者說用ROM表來根據不同輸入得到不同輸出。
這樣當然也是可以的，不過，它的范圍往往比較有限，不適于數量比較大的情況。

下面，我們就隆重有請本次課堂的主角——大四加三算法，隆重登場。

大四加三算法

如果前面那張表格，大家能看懂的話，我們就可以直入主題了。
從表中我們可以看到，把二進制變成BCD碼，也需要三步。

首先，明白問題的輸入和輸出要求，這是最起碼的，即輸入二進制數（比如8’hFF），要求輸出對應的BCD碼（對應為BCD碼12'h255）。
大四加三算法就是實現的過程。

第一步：準備階段。
我們將輸入二進制數在高位補齊全0的BCD位，生成二進制全序列的初始狀態。
BCD部分對應二進制位數為4的整數倍，最大數值上限不得小于輸入值位數對應上限。

第二步：移位階段。
第二步比較復雜。這一步分為多個小步，每小步將二進制全序列進行一次組合的左移操作。
之所以稱之為組合的左移操作，是因為包括一次移位的預操作（即BCD位大四加三）和單純的全序列左移操作。
具體這一步的操作過程，我們后面還會細講。
實際上大象那個比喻，也是第二步比較復雜。呵呵。
一旦原理明白了，我們編寫Verilog代碼想必也就水到渠成了。后面就是Verilog語言練習和具體實現的事了。

第三步：輸出階段。
這一步，最簡單，實際上第二步的最后環節已經得出結果了，只不過它包含在全序列里面，我們只要取出需要的BCD部分，輸出即可。

大四加三算法原理簡介

我們再回到第二步上來，實質上也是大四加三算法上來。
第一步、第三步就是準備和結束的階段，等同于打開冰箱門、關閉冰箱門。重點還是在于大象怎么放到冰箱里的。

第二步里面分為多個小步，每小步依次進行a、b操作，小步次數 = 輸入二進制位數。
        a操作：BCD位如果大于四，則加三。
        b操作：全序列左移一位。

大四加三，準確的說是≥5加3，實質上是≥10加6，或者說大9加6。
因為BCD碼各位是從0到9，而4位二進制數的范圍是0到15，將16進制數轉換為10進制數時，從0到9不必變化，10到15加6變成16到21，對應BCD碼為10到15。
之所以不叫大九加六，是因為大四加三（≥5加3）就是大九加六的一半（≥10加6），左移一位時通過后面的進位（0/1），可以確定該BCD位左移一位之后是奇數還是偶數。
而且BCD只有為5/6/7時（此時>4，而<8）才進行加三操作，變成8/9/10（對應BCD碼1000/1001/1010），高位均為1，通過左移一位，正好對左邊高位BCD位產生進位。

這樣說有點抽象，那張表格如果大家沒有一步步演變清楚的話，可以先弄清楚了。這樣有助于理解這個算法。
當然這個算法嚴謹的證明過程肯定也是有的，李凡老師也提到過，有興趣的話可以深入鉆研一下。
這里，我們就先用歸納的方法，檢驗這種算法確實是能一步步將二進制數轉換成BCD碼。
表中輸入的是8位二進制數，位數更多，實質上原理是一樣的，每位之間的遞進關系是2倍，每四位之間的遞進關系是16倍，你在增加位數，遞進的關系都是一樣的。
當然我們也可以自己推導一下12位二進制數，或者更多位，滿足一下我們的好奇心和求知欲。
就像圖示的表格一樣，只不過位數增加了而已。

本堂課要解決的課題

原理講過之后，我們要做一個更多位數的例子。
也就是開發板六位數碼管顯示的的問題，我們讓六位數碼管循環顯示十進制數000000~999999。

十進制數000000~999999在計算機里面，用于顯示實際上是BCD碼000000~999999，而用于計算處理則是二進制數20'h00000~20'hF423F（對應20'd0~20'd99999）。
在循環顯示的時候，我們控制部分要對計數器進行加一操作，這時候是對二進制數進行操作。
在顯示輸出的時候，我們將二進制數轉換為BCD碼，輸出給數碼管進行顯示。這時候，就用到了二進制數轉換為BCD碼的操作，也就是大四加三算法。
所以說，這個例子對大四加三算法模塊的輸入輸出要求是，輸入20位的二進制數20'h00000~20'hF423F（對應20'd0~20'd99999），要求輸出對應的6位BCD碼000000~999999，對應二進制位數是24位。
顯然這里的20位輸入24位輸出，比表格中的8位輸入12位輸出要多了很多，當然我們不是手工推導，而是要用FPGA來做，用Verilog代碼來建模。

建模主體框架

首先建立工程文件夾b2bcd，編寫頂層模塊b2bcd.v文件。

module b2bcd (din, dout);

        input [19:0] din;
       
        output [23:0] dout;
       
        wire [43:0] data [20:0];
       
        assign data[0] = {24'b0, din};                //第一步：準備階段。將輸入二進制數在高位補齊全0的BCD位，生成二進制全序列的初始狀態。

       
        shift s01 (.datain(data[0]), .dataout(data[1]));                //第二步：移位階段。依次進行20個小步操作。具體動作在shift子模塊中描述。
        shift s02 (.datain(data[1]), .dataout(data[2]));
        shift s03 (.datain(data[2]), .dataout(data[3]));
        shift s04 (.datain(data[3]), .dataout(data[4]));
        shift s05 (.datain(data[4]), .dataout(data[5]));
        shift s06 (.datain(data[5]), .dataout(data[6]));
        shift s07 (.datain(data[6]), .dataout(data[7]));
        shift s08 (.datain(data[7]), .dataout(data[8]));
        shift s09 (.datain(data[8]), .dataout(data[9]));
        shift s10 (.datain(data[9]), .dataout(data[10]));
        shift s11 (.datain(data[10]), .dataout(data[11]));
        shift s12 (.datain(data[11]), .dataout(data[12]));
        shift s13 (.datain(data[12]), .dataout(data[13]));
        shift s14 (.datain(data[13]), .dataout(data[14]));
        shift s15 (.datain(data[14]), .dataout(data[15]));
        shift s16 (.datain(data[15]), .dataout(data[16]));
        shift s17 (.datain(data[16]), .dataout(data[17]));
        shift s18 (.datain(data[17]), .dataout(data[18]));
        shift s19 (.datain(data[18]), .dataout(data[19]));
        shift s20 (.datain(data[19]), .dataout(data[20]));

        assign dout = data[20][43:20];                //第三步：輸出階段。取出BCD部分，作為輸出。

endmodule

建模shift移位子模塊

shift移位子模塊shift.v文件如下：

module shift (datain, dataout);

        input [43:0] datain;
       
        output [43:0] dataout;
       
        wire [43:0] data;
       
        assign data[19:0] = datain[19:0];
       
        preshift p0 (.d4in(datain[23:20]), .d4out(data[23:20]));                //對應第二步各小步下的a操作，此處為6個BCD位的大四加三操作。具體動作見preshift移位預操作子模塊。
        preshift p1 (.d4in(datain[27:24]), .d4out(data[27:24]));
        preshift p2 (.d4in(datain[31:28]), .d4out(data[31:28]));
        preshift p3 (.d4in(datain[35:32]), .d4out(data[35:32]));
        preshift p4 (.d4in(datain[39:36]), .d4out(data[39:36]));
        preshift p5 (.d4in(datain[43:40]), .d4out(data[43:40]));
       
        assign dataout = {data[42:0], 1'b0};                //對應第二步各小步下的b操作，此處為全序列的左移移位操作。

endmodule

建模preshift預移位操作子模塊

preshift預移位操作子模塊preshift.v文件如下：

module preshift (d4in, d4out);

        input [3:0] d4in;
       
        output reg [3:0] d4out;
       
        always @ (*)
                begin
                        if (d4in > 4)
                                begin
                                        d4out = d4in + 3;                //如果大于四，則加三
                                end
                        else
                                begin
                                        d4out = d4in;                //如果不大于四，則不變
                                end
                end

endmodule

preshift預移位操作子模塊，也可以這樣寫

module preshift (d4in, d4out);

        input [3:0] d4in;
       
        output [3:0] d4out;
       
        assign d4out = (d4in > 4) ? d4in + 4'd3 : d4in;         //如果大于四，則加三，否則不變。

//        always (*)
//                begin
//                        if (d4in > 4)
//                                begin
//                                        d4out = d4in + 3;
//                                end
//                        else
//                                begin
//                                        d4out = d4in;
//                                end
//                end

endmodule

編寫Testbench模塊


Testbench模塊b2bcd_tb.v文件如下：

`timescale 1ns/1ps

module b2bcd_tb;

        reg [19:0] din;
       
        wire [23:0] dout;
       
        integer i;
       
        b2bcd dut (.din(din), .dout(dout));
       
        initial
                begin
                        din = 0;
                        for (i=0; i<=999999; i=i+1) #10 din = i;                //六位數碼管循環顯示000000~999999
                       
                        #100 $stop;
                end

endmodule