understanding a binary multiplier using gate-level diagram

user_8776167 0
Viewed 1156

I am having problem understanding the following code (bimpy.v) that does unsigned 2-bit multiply operation.

Edit: Added comment from one of my friend: the following modification does the same thing with fewer logic !!

o_r <= (i_a[0] ? i_b : 2'b0) + ((i_a[1] ? i_b : 2'b0) << 1);

What are the purposes of the two signals (w_r and c) in bimpy.v ?

assign  w_r =  { ((i_a[1])?i_b:{(BW){1'b0}}), 1'b0 }
            ^ { 1'b0, ((i_a[0])?i_b:{(BW){1'b0}}) };

assign  c = { ((i_a[1])?i_b[(BW-2):0]:{(BW-1){1'b0}}) }
        & ((i_a[0])?i_b[(BW-1):1]:{(BW-1){1'b0}});

The code does not match the 2-bit by 2-bit binary multiplier gate-level diagram , please correct me if wrong

2-bit by 2-bit binary multiplier

I am also attaching a working waveform from bimpy.v for a simple 2x2 unsigned multiplier.

bimpy.v waveform

I have also generated a gate-level representation diagram for bimpy.v

gate-level representation of bimpy.v

 ////////////////////////////////////////////////////////////////////////////////
//
// Filename:    bimpy
//
// Project: A multiply core generator
//
// Purpose: An unsigned 2-bit multiply based upon the fact that LUT's allow
//      6-bits of input, but a 2x2 bit multiply will never carry more
//  than one bit.  While this multiply is hardware independent, it is
//  really motivated by trying to optimize for a specific piece of
//  hardware (Xilinx-7 series ...) that has 4-input LUT's with carry
//  chains.
//
// Creator: Dan Gisselquist, Ph.D.
//      Gisselquist Technology, LLC
//
////////////////////////////////////////////////////////////////////////////////
//
// Copyright (C) 2015,2017-2019, Gisselquist Technology, LLC
//
// This program is free software (firmware): you can redistribute it and/or
// modify it under the terms of  the GNU General Public License as published
// by the Free Software Foundation, either version 3 of the License, or (at
// your option) any later version.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTIBILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License along
// with this program.  If not, see <http://www.gnu.org/licenses/> for a
// copy.
//
// License: GPL, v3, as defined and found on www.gnu.org,
//      http://www.gnu.org/licenses/gpl.html
//
//
////////////////////////////////////////////////////////////////////////////////
module  bimpy(i_clk, i_reset, i_ce, i_a, i_b, o_r);
    parameter   BW=2, LUTB=2;
    input               i_clk, i_reset, i_ce;
    input       [(LUTB-1):0]    i_a;
    input       [(BW-1):0]  i_b;
    output  reg [(BW+LUTB-1):0] o_r;

    wire    [(BW+LUTB-2):0] w_r;
    wire    [(BW+LUTB-3):1] c;

    assign  w_r =  { ((i_a[1])?i_b:{(BW){1'b0}}), 1'b0 }
                ^ { 1'b0, ((i_a[0])?i_b:{(BW){1'b0}}) };
    assign  c = { ((i_a[1])?i_b[(BW-2):0]:{(BW-1){1'b0}}) }
            & ((i_a[0])?i_b[(BW-1):1]:{(BW-1){1'b0}});

    initial o_r = 0;
    always @(posedge i_clk)
        if (i_reset)
            o_r <= 0;
        else if (i_ce)
            o_r <= w_r + { c, 2'b0 };

endmodule
synthesis multiplication fpga verilog binary
1 Answers

Note on MUXes

Recall that ? describes a multiplexer (MUX), so the statement:

out = sel ? x : y

is equivalent in a gate-level implementation to:

out = (sel & x) | (~sel & y)

(when sel=1, out <= x, when sel=0, out <= y)

If y=0, then the MUX reduces to an AND between x and sel: out = (sel & x) | (~sel & 0) = sel & x

Deriving w_r

Assuming BW=2 and LUTB=2 w_r is a 4-bit signal. Let's break it down:

w_r = w_rL ^ x_rR

w_rL = { ((i_a[1])?i_b:{(BW){1'b0}}), 1'b0 }

w_rR = { 1'b0, ((i_a[0])?i_b:{(BW){1'b0}}) }

Note how both "else" values of the MUX are zero'ed, so the MUXes are simplified to ANDs, as in the Note above:

w_rL = { BW{i_a[1]} & i_b, 1'b0 } = { A1 & B1, A1 & B0, 0 }

w_rR = { 1'b0, BW{i_a[0]} & i_b } = { 0, A0 & B1, A0 & B0}

I replaced i_a = {A1, A0} and i_b = {B1, B0} to simplify the representation. Eventually, by XORing them bitwise:

  • w_r[0] = 0 ^ (A0 & B0) = A0 & B0

  • w_r[1] = (A1 & B0) ^ (A0 & B1)

  • w_r[2] = (A1 & B1) ^ 0 = A1 & B1

  • w_r[3] = 0 (set implicitly)

Deriving c

Similarly, for the 1-bit c signal:

c = cL & cR

cL = i_a[1] ? i_b[(BW-2):0]:{(BW-1){1'b0}} = {A1 & B0}

cR = i_a[0] ? i_b[(BW-1):1]:{(BW-1){1'b0}} = {A0 & B1)

Eventually:

  • c = {A1 & B0 & A0 & B1}

Deriving o_r

If we break down o_r bits:

  • o_r[0] = 0 + w_r[0] = A0 & B0

  • o_r[1] = 0 + w_r[1] = (A1 & B0) ^ (A0 & B1)

  • o_r[2] = c + w_r[2] = (A1 & B0 & A0 & B1) + (A1 & B1) -- if we add them, then the sum is their XOR, and the carry is their AND, i.e: o_r[2] = (A1 & B0 & A0 & B1) ^ (A1 & B1)

  • o_r[3] = <carry from o_r[2] addition> = A1 & B0 & A0 & B1 & A1 & B1 = A1 & B0 & A0 & B1 (remember, ANDing with myself equals myself, i.e. x & x = x)

Gate-Level diagram outputs

Your gate-level diagram depicts the following equations:

C0 = A0 & B0 (=o_r[0])

C1 = (A0 & B1) ^ (A1 & B0) (=o_r[1])

C2 = (A0 & B1 & A1 & B0) ^ (A1 & B1) (=o_r[2] sum)

C3 = (A0 & B1 & A1 & B0) & (A1 & B1) = A0 & B1 & A1 & B0 (=o_r[3] carry)

Why is the implementation so weird?!

Code comments indicate that the multiplier cell is built for a specific FPGA architecture, and it looks like the original coder's intention was to fit each multiplier cell in a single LUT for that architecture. So my bet is that the original coder was trying to "guide" an old, dumb tool to build the multiplier in an FPGA-efficient way, which is usually not a gate-level-efficient way. I think that such "manual" RTL-level optimizations are useless with today's EDA tools (hopefully!).

user_6751890
Related