radix4_booth_encoder.sv

//
// Copyright 2018 Jeff Bush
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

`include "defines.svh"

import defines::*;

//
// This implements the Modified Booth Encoding, AKA radix-4 encoder.
// It differs from the standard booth encoder in that it evaluates
// bits of the multiplicand in groups of three instead of two.
// This creates half the number of partial products as bits in the
// operands.
//
//   --- --- ---
// 1111111111110
// --- --- ---
//
// See the following for a description:
// Yeh, Wen-Chang, and Chein-Wei Jen. "High-speed Booth encoded parallel
// multiplier design." IEEE transactions on computers 49, no. 7 (2000):
// 692-701.
//
module radix4_booth_encoder
    #(parameter WIDTH = 32,
    parameter NUM_PARTIAL_PRODUCTS = WIDTH / 2)
    (input[WIDTH - 1:0]                                 multiplier,
    input[WIDTH - 1:0]                                  multiplicand,

    // Note extra bit in partial product (because we may multiply by two)
    // This is always the positive magnitude. The corresponding neg
    // bit indicates if it is negative.
    output logic[NUM_PARTIAL_PRODUCTS - 1:0][WIDTH:0]  partial_product,
    output logic[NUM_PARTIAL_PRODUCTS - 1:0]           neg);

    genvar pp_idx;
    genvar bit_idx;

    generate
        // For each partial product
        for (pp_idx = 0; pp_idx < NUM_PARTIAL_PRODUCTS; pp_idx++)
        begin : partial_product_gen
            logic bit0;
            logic bit1;
            logic bit2;
            logic x;
            logic x2;

            // Select three bit grouping in multiplicand to evalute.
            // Insert a zero bit to the right of the least significant bit
            if (pp_idx == 0)
                assign bit0 = 0;
            else
                assign bit0 = multiplicand[pp_idx * 2 - 1];

            assign bit1 = multiplicand[pp_idx * 2];
            assign bit2 = multiplicand[pp_idx * 2 + 1];

            // Based on these three bits, set values:
            // - neg[]: if true, subtracts (negative partial product) else adds
            // - x: partial product is multiplier
            // - x2: partial product is multiplier times 2
            // x and x2 will never both be set. If both are clear, the partial
            // product is zero.
            always @*
            begin
                $display(">> %d %b", pp_idx, {bit2, bit1, bit0});
                unique case ({bit2, bit1, bit0})
                    // No string of 1s, +0
                    3'b000: {x, x2, neg[pp_idx]} = 3'b000;

                    // End of a string of 1s, +x
                    3'b001: {x, x2, neg[pp_idx]} = 3'b100;

                    // A string with a single 1, +x
                    3'b010: {x, x2, neg[pp_idx]} = 3'b100;

                    // End of a string of 1s, +2x
                    3'b011: {x, x2, neg[pp_idx]} = 3'b010;

                    // Beginning of a string of 1s, -2x
                    3'b100: {x, x2, neg[pp_idx]} = 3'b011;

                    // End and beginning of two strings, -x
                    3'b101: {x, x2, neg[pp_idx]} = 3'b101;

                    // Beginning of a string of 1s, -x
                    3'b110: {x, x2, neg[pp_idx]} = 3'b101;

                    // Center of a string of 1s, -0
                    3'b111: {x, x2, neg[pp_idx]} = 3'b000;

                    default: {x, x2, neg[pp_idx]} = 3'b000;
                endcase
            end

            assign partial_product[pp_idx] =
                x ? {multiplier[31], multiplier} :
                x2 ? ({multiplier, 1'b0}) :
                0;
        end
    endgenerate
endmodule