原理

跟基2的算法一样，假设A和B是乘数和被乘数，且有：

$\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_{−1}$ 是末尾补的0， $a_{2n},a_{2n+1}$ 是扩展的两位符号位。可以将乘数A表示为：

$A=(−1⋅a_{2n−1})2^{2n−1}+a_{2n−2}⋅2^{2n−2}+⋯+a_1⋅2+a_0$

同样可以将两数的积表示为：

$\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}$

红色部分即为基4booth的编码方式。

算法实现

乘数位 $a_{2k−1}+a_{2k}−2a_{2k+1})$	编码操作
000	0
001	+B
010	+B
011	+2B
100	-2B
101	-B
110	-B
111	0
所有操作过后都会移位两次。

Verilog 代码

`timescale 1ns / 1ps

module 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 @* begin
        next_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;
        endcase
    end

    always @(posedge clk or negedge rstn) begin
        if (!rstn) begin
            {add1, sub1, add_x2, sub_x2, p_dct, count, done} <= 0;
        end else begin
            case (current_state)
                IDLE: begin
                    add1   <= {{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;
                end
                ADD: begin
                    case (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;
                    endcase
                    count <= count + 1;
                end
                SHIFT: 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: begin
                    done <= 1;
                end
            endcase
        end
    end

    assign mul_out = p_dct[WIDTH_M+WIDTH_R:1];

endmodule

testbench:

`timescale 1ns / 1ps

module booth4_mul_tb ();
    `define TEST_WIDTH 8

    parameter 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 begin
        clk          = 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) begin
            for (j = 0; j < (1 << `TEST_WIDTH); j = j + 1) begin
                vld_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 begin
                    num_good = num_good + 1;
                end
                multiplicand = multiplicand + 1;
            end
            multiplier = multiplier + 1;
        end
        $display("sim done. num good = %d", num_good);
        $finish;

    end

    booth4_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();
    end

endmodule

仿真波形图：
在这里插入图片描述