上接乘法器介绍
原理
跟基2的算法一样，假设A和B是乘数和被乘数，且有：
A = ( a 2 n + 1 a 2 n ) a 2 n − 1 a 2 n − 2 … a 1 a 0 ( a − 1 ) B = b 2 n − 1 b 2 n − 2 … b 1 b 0 \begin{align}A=&(a_{2n+1}a_{2n})a_{2n−1}a_{2n−2}…a_1a_0(a_{−1})\\ B=&b_{2n−1}b_{2n−2}…b_1b_0\end{align} A=B=(a2n+1a2n)a2n−1a2n−2…a1a0(a−1)b2n−1b2n−2…b1b0
其中， a − 1 a_{−1} a−1是末尾补的0， a 2 n , a 2 n + 1 a_{2n},a_{2n+1} a2n,a2n+1是扩展的两位符号位。可以将乘数A表示为：
A = ( − 1 ⋅ a 2 n − 1 ) 2 2 n − 1 + a 2 n − 2 ⋅ 2 2 n − 2 + ⋯ + a 1 ⋅ 2 + a 0 A=(−1⋅a_{2n−1})2^{2n−1}+a_{2n−2}⋅2^{2n−2}+⋯+a_1⋅2+a_0 A=(−1⋅a2n−1)22n−1+a2n−2⋅22n−2+⋯+a1⋅2+a0
同样可以将两数的积表示为：
A B = ( a − 1 + a 0 − 2 a 1 ) × B × 2 0 + ( a 1 + a 2 − 2 a 3 ) × B × 2 2 + ( a 3 + a 4 − 2 a 5 ) × B × 2 4 + … + ( a 2 n − 1 + a 2 n − 2 a 2 n + 1 ) × B × 2 2 n = B × [ ∑ k = 0 n ( a 2 k − 1 + a 2 k − 2 a 2 k + 1 ) ⋅ 2 2 k ] = B × V a l ( A ) \begin{align}AB&=(a_{−1}+a_0−2a_1)×B×2^0+(a_1+a_2−2a_3)×B×2^2\\ &+(a_3+a_4−2a_5)×B×2^4+…\\ &+(a_{2n−1}+a_{2n}−2a_{2n+1})×B×2^{2n}\\ &\red{=B×[∑_{k=0}^n(a_{2k−1}+a_{2k}−2a_{2k+1})⋅2^{2k}]}\\ &=B×Val(A)\end{align} AB=(a−1+a0−2a1)×B×20+(a1+a2−2a3)×B×22+(a3+a4−2a5)×B×24+…+(a2n−1+a2n−2a2n+1)×B×22n=B×[k=0∑n(a2k−1+a2k−2a2k+1)⋅22k]=B×Val(A)
红色部分即为基4booth的编码方式。
算法实现
| 乘数位 ( a 2 k − 1 + a 2 k − 2 a 2 k + 1 ) (a_{2k−1}+a_{2k}−2a_{2k+1}) (a2k−1+a2k−2a2k+1) | 编码操作 |
|---|---|
| 000 | 0 |
| 001 | +B |
| 010 | +B |
| 011 | +2B |
| 100 | -2B |
| 101 | -B |
| 110 | -B |
| 111 | 0 |
| 所有操作过后都会移位两次。 |
Verilog 代码
`timescale 1ns / 1psmodule booth4_mul #(parameter WIDTH_M = 8,parameter WIDTH_R = 8
) (input clk,input rstn,input vld_in,input [ WIDTH_M-1:0] multiplicand,input [ WIDTH_R-1:0] multiplier,output [WIDTH_M+WIDTH_R-1:0] mul_out,output reg done
);parameter IDLE = 2'b00, ADD = 2'b01, SHIFT = 2'b11, OUTPUT = 2'b10;reg [1:0] current_state, next_state;reg [WIDTH_M+WIDTH_R+2:0] add1;reg [WIDTH_M+WIDTH_R+2:0] sub1;reg [WIDTH_M+WIDTH_R+2:0] add_x2;reg [WIDTH_M+WIDTH_R+2:0] sub_x2;reg [WIDTH_M+WIDTH_R+2:0] p_dct;reg [ WIDTH_R-1:0] count;always @(posedge clk or negedge rstn)if (!rstn) current_state = IDLE;else if (!vld_in) current_state = IDLE;else current_state <= next_state;always @* beginnext_state = 2'bx;case (current_state)IDLE: if (vld_in) next_state = ADD;else next_state = IDLE;ADD: next_state = SHIFT;SHIFT: if (count == WIDTH_R / 2) next_state = OUTPUT;else next_state = ADD;OUTPUT: next_state = IDLE;default: next_state = IDLE;endcaseendalways @(posedge clk or negedge rstn) beginif (!rstn) begin{add1, sub1, add_x2, sub_x2, p_dct, count, done} <= 0;end else begincase (current_state)IDLE: beginadd1 <= {{2{multiplicand[WIDTH_R-1]}}, multiplicand, {WIDTH_R + 1{1'b0}}};sub1 <= {-{{2{multiplicand[WIDTH_R-1]}}, multiplicand}, {WIDTH_R + 1{1'b0}}};add_x2 <= {{multiplicand[WIDTH_M-1], multiplicand, 1'b0}, {WIDTH_R + 1{1'b0}}};sub_x2 <= {-{multiplicand[WIDTH_M-1], multiplicand, 1'b0}, {WIDTH_R + 1{1'b0}}};p_dct <= {{WIDTH_M + 1{1'b0}}, multiplier, 1'b0};count <= 0;done <= 0;endADD: begincase (p_dct[2:0])3'b000, 3'b111: p_dct <= p_dct;3'b001, 3'b010: p_dct <= p_dct + add1;3'b101, 3'b110: p_dct <= p_dct + sub1;3'b100: p_dct <= p_dct + sub_x2;3'b011: p_dct <= p_dct + add_x2;default: p_dct <= p_dct;endcasecount <= count + 1;endSHIFT: p_dct <= {p_dct[WIDTH_M+WIDTH_R+2], p_dct[WIDTH_M+WIDTH_R+2], p_dct[WIDTH_M+WIDTH_R+2:2]};OUTPUT: begindone <= 1;endendcaseendendassign mul_out = p_dct[WIDTH_M+WIDTH_R:1];endmodule
testbench:
`timescale 1ns / 1psmodule booth4_mul_tb ();`define TEST_WIDTH 8parameter WIDTH_M = `TEST_WIDTH;parameter WIDTH_R = `TEST_WIDTH;reg clk;reg rstn;reg vld_in;reg [ WIDTH_M-1:0] multiplicand;reg [ WIDTH_R-1:0] multiplier;wire [WIDTH_M+WIDTH_R-1:0] mul_out;wire done;//输入 ：要定义有符号和符号，输出：无要求wire signed [ `TEST_WIDTH-1:0] m1_in;wire signed [ `TEST_WIDTH-1:0] m2_in;reg signed [ 2*`TEST_WIDTH-1:0] product_ref;reg [ 2*`TEST_WIDTH-1:0] product_ref_u;assign m1_in = multiplier[`TEST_WIDTH-1:0];assign m2_in = multiplicand[`TEST_WIDTH-1:0];always #1 clk = ~clk;integer i, j;integer num_good;initial beginclk = 0;vld_in = 0;multiplicand = 0;multiplier = 0;num_good = 0;rstn = 1;#4 rstn = 0;#2 rstn = 1;repeat (2) @(posedge clk);for (i = 0; i < (1 << `TEST_WIDTH); i = i + 1) beginfor (j = 0; j < (1 << `TEST_WIDTH); j = j + 1) beginvld_in = 1;wait (done == 0);wait (done == 1);product_ref = m1_in * m2_in;product_ref_u = m1_in * m2_in;if (product_ref != mul_out) begin$display("multiplier = %d multiplicand = %d proudct =%d", m1_in, m2_in, mul_out);@(posedge clk);$stop;end else beginnum_good = num_good + 1;endmultiplicand = multiplicand + 1;endmultiplier = multiplier + 1;end$display("sim done. num good = %d", num_good);$finish;endbooth4_mul #(.WIDTH_M(WIDTH_M),.WIDTH_R(WIDTH_R)) U_BOOTH_RADIX4_0 (.clk (clk),.rstn (rstn),.vld_in (vld_in),.multiplicand(multiplicand),.multiplier (multiplier),.mul_out (mul_out),.done (done));initial begin$fsdbDumpfile("tb.fsdb");$fsdbDumpvars;$fsdbDumpMDA();$dumpvars();endendmodule
仿真波形图：
