How can I iteratively create buses of parameterized size to connect modules also iteratively created?

Question

I am trying to create a Multiplier module in verilog using the Combinational Logic approach, so that there is no clock involved. I want the module to have a generic definition, that is, I want the Multiplier to receive two factors of size M and N bits respectively and return a product of size M+N bits.

The basic idea is to compute the sum of partial products, each one shifted to left a certain amount of bits according to its level. To understand this idea, look at the following example:

A = A3 A2 A1 A0 and B = B2 B1 B0

Then, A X B would be computed like this:

                  A3*B0  A2*B0  A1*B0 A0*B0
           A3*B1  A2*B1  A1*B1 A0*B1
+   A3*B2  A2*B2  A1*B2 A0*B2
____________________________________________

To make the sum of the partial products, I need to make the sum of the first two products (A times B0) + ([A times B1] << 1), which can be easily made by means of a RippleCarryAdder [many concatenated FullAdders], and then use the ouput of this sum together with the following shifted partial product ([A times B2] << 2) as the two inputs of a second RippleCarryAdder.

More generally, to compute the product A[M-1:0] times B[N-1:0], we would need to use N-1 RippleCarryAdder's (each one defined for one bit more than the previous one) and somehow use the output of each one as one of the two inputs for the next one.

So far, this is my uncomplete verilog code:

First, the RippleCarryAdder parameterized, this works correctly

module RippleCarryAdder#(parameter N = 4)(A,B,Cin,S,Cout);

input [N-1:0] A;
input [N-1:0] B;
input Cin;
output [N-1:0] S;
output Cout;
wire [N:0] CC;

assign CC[0] = Cin;
assign Cout = CC[N];
genvar i;
generate
for (i=0; i < N; i=i+1)
begin: addbit
    FullAdder unit(A[i],B[i],CC[i],S[i],CC[i+1]);
end
endgenerate

endmodule

The incomplete code for the Multiplier

module Multiplier #(parameter M = 4, N = 4)(A,B,P);

input [M-1:0] A; //Input A, size M
input [N-1:0] B; //Input B, size N
output [M+N-1:0] P;  //Output P (product), size M+N

wire [N-1:0] CC; //Bus for the carries of the RippleCarryAdders

assign CC[0] = 1'b0;

RippleCarryAdder#(M+1) adder0({1'b0,A&{M{B[0]}}},{A&{M{B[1]}},1'b0},CC[0], /*insert bus P0 here*/);

/*I want bus P0 =  (0 A[N-1]&B[0] ... A[0]&B[0]) + (A[N-1]&B[1] ... A[0]&B[1] 0) + CC[0], with CC[0] = 0 because it is the first sum */

genvar i;
generate
for (i=2; i < N; i=i+1)
begin: addPartialProduct
    RippleCarryAdder#(M+i) adder({A&{M{B[i]}},{(i{1'b0}}},/*{CC[i-1],P[i-2]}*/,CC[i-2],/*P[i-1]*/,CC[i-1]);

//When I do {CC[i-1],P[i-1]}, I mean the concatenation of the carry CC[i] (1 bit) with the product P[i-1] (several bits)


end
endgenerate

//Finally, I want P = P[N-1], the output of the last RippleCarryAdder

endmodule

So my question is: How can I define these P[i] buses of parameterized size so that they can be used to connect the inputs and outputs of each pair of consecutive RippleCarryAdder's? Notice that each bus P[i] would have size (M+i+1), for i = 0, ..., N-1

If it is not possible, which other solutions there exist to make a parameterized Multiplier only using Combitional Logic (without clocks involved)?

Thanks in advance.

PS: I know there are efficient solutions using clocks, but the challenge is not to use them.

Greg · Accepted Answer · 2013-12-13 20:18:28Z

0

Create daisy chain array of sums/partial-products, similar to the chain of carries used in the ripple adder. This chain will need to be a 2-dimentional array. The packed portion of the chain array will be the sum/partial-product and the unpacked will be the level. Using a 2D array will mean some bits will never be used, for example S[0][M+N-1:M+1]. The unused bits will be optimized out during synthesis. The following code snip-it demonstrate the desired behavior of an unsigned multiplier implemented with ripple adders.

wire [M+N-1:0] S [N-1:0]; // chain of sums / partial-products

assign S[0][M:0] = { 1'b0 , { A & {M{B[0]}} } };
// assign S[0][M+N-1:M+1] = {(N-1){1'b0}}; // uncomment to make probing readable
assign P = S[N-1]; // Product

genvar i;
generate
for (i=1; i < N; i=i+1)
begin: addPartialProduct
    //if (i+1<N) assign S[i][M+N-1:M+i+1] = {(N-i){1'b0}}; // uncomment to make probing readable
    RippleCarryAdder#(M+i) adder(
        .A   ( S[i-1][M+i-1:0] ),
        .B   ( { A & {M{B[i]}} , {i{1'b0}} } ),
        .Cin ( 1'b0 ),
        .S   ( S[i][M+i-1:0] ),
        .Cout( S[i][M+i] ) );
end
endgenerate

answered Dec 13, 2013 at 20:18

Greg

19.3k6 gold badges51 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Pablo Messina Over a year ago

This is a good idea, actually I thought of using bidimensional arrays as a possible solution. I tried out your code and indeed the optimization process trimmed the unused wires, but when I compiled the project and programmed it into the Basys 2 fpga, somehow it didn't work. So what I finally did was simply use a fixed size of M+N for all the RippleCarryAdder's and deleted the Cout output of their definition, and it worked. However, I would like to know if there is a way to create bidimensional arrays of wires but with different dimensions,e.g, first row of size 2, second of size 3, and so on.

alex.forencich Over a year ago

You can't do that in Verilog as far as I know. But it really isn't a big deal as any unused wires will be trimmed.

Greg Over a year ago

@PabloMessina The full answer to eliminating unused bit and multidimensional unique size array is to complex for a comment. I created a self-answer here: stackoverflow.com/questions/20625784/…

Collectives™ on Stack Overflow

How can I iteratively create buses of parameterized size to connect modules also iteratively created?

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related