比特對(duì)編碼與比特對(duì)編碼乘法器的設(shè)計(jì)

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

比特對(duì)編碼原理

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

一個(gè)數(shù)我們考慮從低位向高位對(duì)其進(jìn)行編碼，使其變成4進(jìn)制（基4）的表示形式，每?jī)晌欢M(jìn)制表示一位的四進(jìn)制數(shù)。

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

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

下面給出比特對(duì)編碼規(guī)律，如下表和圖所示，圖為一個(gè)實(shí)例，是對(duì)1011_1111的編碼，其表示-65。比特對(duì)編碼結(jié)果為 -1 00-1,故其表示的十進(jìn)制d為：

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

再舉個(gè)例子，比如對(duì)0001_1001進(jìn)行比特對(duì)編碼，得到編碼為：

+2-2+1

故其表示的十進(jìn)制計(jì)算如下：

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

=32+8+1=41

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

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

從中可以得出，對(duì)于8位二進(jìn)制數(shù)0101_0101，經(jīng)過比特對(duì)編碼后，得到的是 +1 +1 +1 +1，其表示的數(shù)為：

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

64+16+4+1=85

此時(shí)只需要進(jìn)行3次加法運(yùn)算，不會(huì)存在booth編碼所存在的問題。

同時(shí)發(fā)現(xiàn)對(duì)于數(shù)據(jù)位寬非偶數(shù)的數(shù)，我們需要將其在最高位補(bǔ)填一位符號(hào)位，再進(jìn)行比特對(duì)編碼。

比特對(duì)編碼（對(duì)乘數(shù)進(jìn)行編碼）乘法器，需要進(jìn)行的加法次數(shù)為乘數(shù)位寬的一半。

比特對(duì)編碼乘法器設(shè)計(jì)

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

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

（其中prd_r[1]為上一個(gè)時(shí)鐘product的第二位）進(jìn)行編碼，得出本次操作是加1、加2，減1，減2，還是不用做加減法（編碼為0）（代碼中上述五種操作對(duì)應(yīng)的標(biāo)志信號(hào)分別為add_1,add_2,sub_1,sub_2，noneed_add）。并將加法結(jié)果每次存到product寄存器的高位。

這里有個(gè)巧妙的思想就是，每個(gè)時(shí)鐘周期通過對(duì)product右移2位，再將其高DW_A位與a或者a*2進(jìn)行相加或者相減操作，正好相當(dāng)于每次product不動(dòng)，把a(bǔ)或者a*2左移2位（乘以4）。這個(gè)思想源于《Verilog HDL 高級(jí)數(shù)字設(shè)計(jì)》中的精簡(jiǎn)寄存器時(shí)序乘法器設(shè)計(jì)。

注意，這里是有符號(hào)數(shù)乘法器，每次左移需要在高位補(bǔ)符號(hào)位，故左移不能簡(jiǎn)單的用 >> 描述（>>左移默認(rèn)高位填0），具體描述見代碼。

其中減法采用加上這個(gè)數(shù)的補(bǔ)碼的方式；通過一個(gè)計(jì)數(shù)器（cnt）來指示什么時(shí)候結(jié)束運(yùn)算；其中運(yùn)算控制狀態(tài)機(jī)采用《狀態(tài)機(jī)的第四種描述方式》編寫；條件選擇多采用與或方式實(shí)現(xiàn)。

設(shè)計(jì)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

如果乘數(shù)b位寬為奇數(shù)，請(qǐng)補(bǔ)一位符號(hào)位，變成偶數(shù)位寬，再輸入。

原文標(biāo)題：比特對(duì)編碼與比特對(duì)編碼乘法器的設(shè)計(jì)

文章出處：【微信公眾號(hào)：FPGA之家】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。