Wallace Tree Reduction Technique

Multipliers have gained the significant importance with the introduction of the digital computers. Multipliers are most often used in digital signal processing applications and microprocessors designs. In contrast to process of addition and subtraction, multipliers consume more time and more hardware resources. With the recent advances in technology, a number of multiplication techniques have been implemented for fulfilling the requirement of producing high speed, low power consumption, less area or a combination of them in one multiplier. Speed and area are the two major constraints which conflict each other. Therefore, it is the designer’s task to decide proper balance in selecting an appropriate multiplication technique as per requirements. Parallel multipliers are the high speed multipliers. Therefore, the enhanced speed of the multiplication operation is achieved using various schemes and Wallace tree is one of them.

There are three phases in the multiplier architecture:
1. The first phase is the generation of partial products.
2. Accumulation of partial product in second phase.
3. The third phase is the final addition phase.

Wallace multiplier is an efficient parallel multiplier. In the conventional Wallace tree multiplier, the first step is to form partial product array (of 𝑁2 bits). In the second step, groups of three adjacent rows each, is collected. Each group of three rows is reduced by using full adders and half adders. Full adders are used in each column where there are three bits whereas half adders are used in each column where there are two bits. Any single bit in a column is passed to the next stage in the same column without processing. This reduction procedure is repeated in each successive stage until only two rows remain. In the last step, the remaining two rows are added using a carry propagating adder. An example of a representation of the conventional 8-bit by 8-bit Wallace tree multiplier is shown in Fig. 1. The three row groupings are shown .

Figure 1. Conventional 8-bit by 8-bit Wallace Reduction

Hardware Implementation:
A below figure show 6x6 multipler hardware.

Parallel Multiplier Verilog HDL code

Verilog Code for Parallel Multiplier:

A parallel multiplier is a type of digital circuit that performs multiplication on two numbers in parallel, using multiple arithmetic units in parallel. This allows the circuit to perform multiplication faster than a serial multiplier, which performs multiplication using a single arithmetic unit.

fpga verilog code example

Code For Parallel Multiplier.

//parallel multiplier (n = 8)

module parallel_Multiplier (Product, multiplicand, Multiplier);

input [7: 0] multiplicand, Multiplier;

output reg [15: 0] Product;

always @ (multiplicand, Multiplier)

Product1 = multiplicand*Multiplier;

endmodule

module Algorithmic-Binary-Multiplier #(parameter dp-width =5) (

output [2*dp_width -1 : 0] Product, Input [dp-width -1 : 0] multiplicand, Multiplier);

reg [dp-width -1: 0] A, B, Q; //Sized for datapath

reg C;

Integer k;

assign Product1 = {C, A, Q};

always @ (multiplicand, Multiplier) begin

Q = Multiplier;

B = multiplicand;

C=0;

A=0;

for(k= 0; k <= dp-width-1; k= k+ 1)
begin

if (Q[0]) {(C, A) = A + B;

{C, A, Q) = {C, A, Q} >> 1;

end

end

endmodule

module t-Algorithmic-Binary-Multiplier;

parameter dp-width = 5; // Width of data path

wire [2* dp-width -1: 0] Prdct;

reg [dp-width -1: 0]multiplicand, Multiplier;

integer Exp-Value;

reg Error;

Algorithmic-Binary-Multiplier M0 (Product, multiplicand, Multiplier);

// Error detection

initial# 1030000 finish:

always @ (Product) begin

Exp-Value =multiplicand, Multiplier;

Error = Exp-Value ^ Product;

end

initial begin

#5 multiplicand= 0;

 Multiplier = 0;

repeat (32)# 10 begin  Multiplier =  Multiplier + 1;

repeat (32) #5 multiplicand= multiplicand + 1 :

end

end

endmodule

Here is an example of VHDL code for a parallel multiplier:

library IEEE; use IEEE.STD_LOGIC_1164.ALL; entity parallel_multiplier is Port ( a : in STD_LOGIC_VECTOR (3 downto 0); b : in STD_LOGIC_VECTOR (3 downto 0); p : out STD_LOGIC_VECTOR (7 downto 0)); end parallel_multiplier; architecture Behavioral of parallel_multiplier is begin p <= a * b; end Behavioral;

This code defines a parallel multiplier module called "parallel_multiplier" with two inputs "a" and "b" and an output "p". The inputs are 4-bit vectors and the output is 8-bit vector. The architecture uses the built-in multiplication operator to perform the multiplication of the inputs in parallel.

Here is an example of Verilog code for a parallel multiplier:

module parallel_multiplier(input [3:0] a, input [3:0] b, output [7:0] p); assign p = a * b; endmodule

This code defines a parallel multiplier module called "parallel_multiplier" with two inputs "a" and "b" and an output "p". The inputs are 4-bit vectors and the output is 8-bit vector. The assign statement is used to perform the multiplication of the inputs in parallel.

Please note that this is a basic example and the actual code will depend on the specific requirements of your design, the width of the inputs, and the width of the output. Some designs may require more complex implementation and also this is a combinational multiplier and not a pipelined multiplier.

Verilog Code for 8-bit Booth’s Multiplier

This is a Multiplication algorithm which multiplies two binary numbers's in 2's Compliment.

Following is the 8-bits Booth's Multiplier verilog code:

fpga verilog code example

VHDL of 8-bit Booth’s Multiplier

module 8_bit_booth_mult(prd, busy, mc, mp, clk, start);
output [15:0] prd;
output busy;
input [7:0] mc, mp;
input clk, start;
reg [7:0] A, Q, B;
reg Q_1;
reg [3:0] count;
wire [7:0] sum, difference;
always @(posedge clk)
begin
if (start) begin
A <= 8'b0;
B <= mc;
Q <= mp;
Q_1 <= 1'b0;
count <= 4'b0;
end
else begin
case ({Q[0], Q_1})
2'b0_1 : {A, Q, Q_1} <= {sum[7], sum, Q};
2'b1_0 : {A, Q, Q_1} <= {difference[7], difference, Q};
default: {A, Q, Q_1} <= {A[7], A, Q};
endcase
count <= count + 1'b1;
end
end
alu adder (sum, A, B, 1'b0);
alu subtracter (difference, A, ~B, 1'b1);
assign prd = {A, Q};
assign busy = (count < 8);
endmodule
//For alu.
//It is an adder, but capable of subtraction:
//Recall that subtraction means adding the two's complement
//a - b = a + (-b) = a + (inverted b + 1)
//The 1 will be coming in as Cin (carry-in)
module alu(out, a, b, cin);
output [7:0] out;
input [7:0] a;
input [7:0] b;
input cin;
assign out = a + b + cin;
endmodule

Testbench for Booth’s Multiplier

module testbench;

reg clk, start;

reg [7:0] a, b;

wire [15:0] ab;

wire busy;

booth_multiplier multiplier1(ab, busy, a, b, clk, start);

initial begin

clk = 0;

$display("first example: a = 3 b = 17");

a = 3; b = 17; start = 1; #50 start = 0;

#80 $display("first example done");

$display("second example: a = 7 b = 7");

a = 7; b = 7; start = 1; #50 start = 0;

#80 $display("second example done");

$finish;

end

always #5 clk = !clk;

always @(posedge clk) $strobe("ab: %d busy: %d at time=%t", ab, busy, $stime);

endmodule