比特對編碼與比特對編碼乘法器的設計

今天一起看看比特對編碼（有的也把它稱為基4booth編碼，名字不重要，主要是思想），可以解決上文中提到的問題

比特對編碼原理

booth重編碼的主要問題在于不能過濾掉010這樣序列。故考慮將通過連續相鄰兩位進行編碼，每次從低位向高位移動1位的方式（即booth比編碼），變成連續相鄰3位進行編碼，每次從低位向高位移動2位的方式（比特對編碼）。先討論其原理。

一個數我們考慮從低位向高位對其進行編碼，使其變成4進制（基4）的表示形式，每兩位二進制表示一位的四進制數。

3（2'b11）比4少1，2(2'b10)比4少2。在4進制數中，2需要向前進位則需要減去2再向前進位；3需要向前進位則需要減去1再向前進位。

我們的比特對編碼就是基于上述原理來的。

下面給出比特對編碼規律，如下表和圖所示，圖為一個實例，是對1011_1111的編碼，其表示-65。比特對編碼結果為 -1 00-1,故其表示的十進制d為：

d=-4^3 -4^0= -65

再舉個例子，比如對0001_1001進行比特對編碼，得到編碼為：

+2-2+1

故其表示的十進制計算如下：

d=2*(4^2) -2*(4^1) +4^0

=32+8+1=41

其中的乘2與乘4都可以通過移位操作來實現，這就是為什么需要這么編碼的原因。

可以看到，每相鄰三位進行編碼，其中的最低位mi-1 其實表示來自前面的進位。故當其為 001時，得到的編碼為 +1(表示4)，011時最低位1表示進位，故編碼為1+1=+2。

從中可以得出，對于8位二進制數0101_0101，經過比特對編碼后，得到的是 +1 +1 +1 +1，其表示的數為：

4^3 + 4^2 + 4^1 + 4^0 =

64+16+4+1=85

此時只需要進行3次加法運算，不會存在booth編碼所存在的問題。

同時發現對于數據位寬非偶數的數，我們需要將其在最高位補填一位符號位，再進行比特對編碼。

比特對編碼（對乘數進行編碼）乘法器，需要進行的加法次數為乘數位寬的一半。

比特對編碼乘法器設計

設計思想概敘：定義位寬為DW_A+DW_B+2的product寄存器（DW_A為被乘數a的位寬，DW_B為乘數b的位寬）。當in_valid與in_ready同時為高時，將乘數b（位寬為b）加載到product的低DW_B位。然后在計算狀態下（executing），將每次加法器的輸出放到product的高位，并每個時鐘周期將product右移2位。每個時鐘周期，通過對

m={product[1:0],prd_r[1]}

（其中prd_r[1]為上一個時鐘product的第二位）進行編碼，得出本次操作是加1、加2，減1，減2，還是不用做加減法（編碼為0）（代碼中上述五種操作對應的標志信號分別為add_1,add_2,sub_1,sub_2，noneed_add）。并將加法結果每次存到product寄存器的高位。

這里有個巧妙的思想就是，每個時鐘周期通過對product右移2位，再將其高DW_A位與a或者a*2進行相加或者相減操作，正好相當于每次product不動，把a或者a*2左移2位（乘以4）。這個思想源于《Verilog HDL 高級數字設計》中的精簡寄存器時序乘法器設計。

注意，這里是有符號數乘法器，每次左移需要在高位補符號位，故左移不能簡單的用 >> 描述（>>左移默認高位填0），具體描述見代碼。

其中減法采用加上這個數的補碼的方式；通過一個計數器（cnt）來指示什么時候結束運算；其中運算控制狀態機采用《狀態機的第四種描述方式》編寫；條件選擇多采用與或方式實現。

設計Verilog如下（dff_with_en為寄存器）：

module radix4_mul #(  parameter  DW_A = 16,  parameter  DW_B = 8)(   input  clk,   input  rst_n,
   input  in_valid,   output in_ready,   input  flush,
   output o_valid,   input o_ready,
   input [DW_A-1:0] a,   input [DW_B-1:0] b,
   output [DW_A+DW_B-1:0] mul_res);
//state machine for mulwire state;wire [$clog2((DW_B+1)/2):0] cnt;
wire exe_cnt_final = (cnt == (DW_B+1)/2);
wire execute_en = in_valid&in_ready;
localparam GET_DATA = 1'b0;localparam EXECUTING = 1'b1;
wire curr_get_data = (state == GET_DATA);wire curr_executing = (state == EXECUTING);
wire is_executing = curr_executing & (~exe_cnt_final);
wire nxt_get_data_en = (curr_executing & exe_cnt_final & o_ready) | flush;wire nxt_executing = curr_get_data & execute_en;
wire nxt_state = (nxt_get_data_en & GET_DATA) |            (nxt_executing & EXECUTING);
wire tran_en = nxt_get_data_en | nxt_executing;
dff_with_en #(   .DW(1))dff_state(   .clk (clk),   .rst_n (rst_n),   .enable (tran_en),   .d_in (nxt_state),   .q_out (state));
//cnt//wire [$clog2((DW_B+1)/2):0] cnt_nxt = curr_executing ? cnt+1 : 'h0;
dff_with_en #(   .DW($clog2((DW_B+1)/2)+1))dff_cnt(   .clk (clk),   .rst_n (rst_n),   .enable (1'b1),   .d_in (cnt_nxt),   .q_out (cnt));
//get the awire [DW_A-1:0] a_d;wire [DW_A-1:0] nxt_a_d = nxt_executing ? a : a_d;
dff_with_en #(   .DW(DW_A))dff_a(   .clk (clk),   .rst_n (rst_n),   .enable (1'b1),   .d_in (nxt_a_d),   .q_out (a_d));//radix 4 codingwire prd_r;wire [DW_A+DW_B+1:0] product;//wire [DW_B-1:0] b_shift;wire [2:0] m = is_executing ? {product[1:0],prd_r} : 3'b000;
wire add_1 = (m == 3'b001) | (m == 3'b010);wire add_2 = (m == 3'b011);wire sub_1 = (m == 3'b110) | (m == 3'b101);wire sub_2 = (m == 3'b100);
//wire [DW_A+DW_B+1:0] product;
wire [DW_A+1:0] adder_op1 = ( {DW_A+2{add_1}}& { {2{a_d[DW_A-1]}},a_d} )       |                      ( {DW_A+2{add_2}}& { {1{a_d[DW_A-1]}},a_d,1'b0} )  |          ( {DW_A+2{sub_1}}& (~{ {2{a_d[DW_A-1]}},a_d}) )    |          ( {DW_A+2{sub_2}}& (~{ {1{a_d[DW_A-1]}},a_d,1'b0}));
wire add_en = (add_1 | add_2 | sub_1 | sub_2)& is_executing;       wire noneed_add = is_executing & (~(add_1 | add_2 | sub_1 | sub_2));
wire [DW_A+1:0] adder_op2 = product[DW_A+DW_B+1:DW_B];
wire adder_cin = sub_1|sub_2;
wire [DW_A+1:0] adder_res = adder_op1 + adder_op2 + adder_cin;
wire [DW_A+DW_B+1:0] nxt_product = ({DW_A+DW_B+2{add_en}} &{{2{adder_res[DW_A+1]}},adder_res,product[DW_B-1:2]})|                              ({DW_A+DW_B+2{noneed_add}} & {{2{product[DW_A+DW_B+1]}},product[DW_A+DW_B+1:2]}) |           ({DW_A+DW_B+2{o_valid}} & product) |           ({DW_A+DW_B+2{nxt_executing}} & {{DW_A+2{1'b0}},b});
dff_with_en #(   .DW(DW_A+DW_B+2))dff_product(   .clk (clk),   .rst_n (rst_n),   .enable (1'b1),   .d_in (nxt_product),   .q_out (product));
wire prd_nxt = curr_get_data ? 1'b0 : product[1];
dff_with_en #(   .DW(1))dff_prd(   .clk (clk),   .rst_n (rst_n),   .enable (1'b1),   .d_in (prd_nxt),   .q_out (prd_r));assign in_ready = curr_get_data;assign o_valid = exe_cnt_final;assign mul_res = product[DW_A+DW_B-1:0];
endmodule

如果乘數b位寬為奇數，請補一位符號位，變成偶數位寬，再輸入。

原文標題：比特對編碼與比特對編碼乘法器的設計

文章出處：【微信公眾號：FPGA之家】歡迎添加關注！文章轉載請注明出處。