Binary Multiplier

The computer performs Multiplication in the same way we perform the operation with pen and paper.

Step 1:  Multiplicand is multiplied by each bit of the multiplier, starting from the least significant bit.

Step 2:  Each multiplication result forms a partial product. Successive partial products are shifted one position to the left.

Step 3:  The final product is obtained from the sum of the partial products.

Example:

A circuit that will implement the multiplication described above in binary is given in figure 1:

Figure 1: 2-bit x 2-bit binary Multiplier

In practice, there are more bits in the partial products and it is necessary to use full adders to produce the sum of the partial products. A combinational circuit binary multiplier with more bits can be constructed in a similar fashion. For J multiplier bits and K multiplicand bits, we need (J×K) AND gates and (J-1) K-bit adders to produce a product of (J+K) bits.

The rest of this short tutorial will illustrate binary multiplier with a 4×4 bits example, design the circuit, code its implementation in Verilog HDL and simulate it in ModelSim software.

Let the multiplicand by x₃x₂x₁x₀ and the multiplier be y₃y₂y₁y₀

With this example our K = 4 and J = 4, we will need (4×4=16) AND gates and (4-1=3) 4-bits adders, our result will produce a product of (4×4=16) bits.

:  AND gates

: 4-bits binary adders

:  Carry bit and the Sum MSB to LSB+1

Figure 2:  An algorithm diagram for 4×4 bit binary Multiplier 

Figure 3:  Logic Circuit Diagram of a 4×4 bits binary multiplier

//--------------------------------------------------

//Verilog Code for Binary Multiplier Logic Circuit Design

module binary_multiplier (C, x, y);

input [3:0] x, y;

output [7:0] C;

wire w1, w2, w3, w4, W5, W6, W7, W8;

wire w9, w10, w11, w12, w13,  w14, w15,w16;

and (w1, y[0], x[0]);

and (w2, y[1], x[0]);

and (w3, y[2], x[0]);

and (w4, y[3], x[0]);

and (w5, y[0], x[1]);

and (w6, y[1], x[1]);

and (w7, y[2], x[1]);

and (w8, y[3], x[1]);

and (w9, y[0], x[2]);

and (w10, y[1], x[2]);

and (w11, y[2], x[2]);

and (w12, y[3], x[2]);

and (w13, y[0], x[3]);

and (w14, y[1], x[3]);

and (w15, y[2], x[3]);

and (w16, y[3], x[3]);

xor (w0, w1, w1);

wire [3:0] S1, A1, B1;

wire C4_1, C0_1;

wire [3:0] S2, A2, B2;

wire  C0_2;

wire [3:0] S3, A3, B3;

wire  C0_3;

assign C[0]=w1;

four_bit_adder F_1 (S1, C4_1, A1, B1, C0_1);

four_bit_adder F_2 (S2, C4_2, A2, B2, C0_2);

four_bit_adder F_3 (S3, C4_3, A3, B3, C0_3);

assign A1[0] = w0;

assign A1[1] = w2;

assign A1[2] = w3;

assign A1[3] = w4;

assign B1[0] = w5;

assign B1[1] = w6;

assign B1[2] = w7;

assign B1[3] = w8;

assign C0_1= w0;

assign C[1] = S1[0];

assign A2[0] = S1[1];

assign A2[1] = S1[2];

assign A2[2] = S1[3];

assign A2[3] = C4_1;

assign B2[0] = w9;

assign B2[1] = w10;

assign B2[2] = w11;

assign B2[3] = w12;

assign C0_2= w0;

assign C[2] = S2[0];

assign A3[0] = S2[1];

assign A3[1] = S2[2];

assign A3[2] = S2[3];

assign A3[3] = C4_2;

assign B3[0] = w13;

assign B3[1] = w14;

assign B3[2] = w15;

assign B3[3] = w16;

assign C0_3= w0;

assign C[3] = S3[0];

assign C[4] = S3[1];

assign C[5] = S3[2];

assign C[6] = S3[3];

assign C[7] = C4_3;

endmodule

//-------------------------------------------------

 //------------------------------------------------------------------------

// Test bench for Binary Multiplier

module t_binary_multiplier;

wire [7:0] C;

reg  [3:0]y, x;

binary_multiplier F1(C, x, y);

initial

begin

   x[3:0] = 4'b0000; y = 4'b0000; 

     

#100 x[3:0] = 4'b1010; y = 4'b1001;

#100 x[3:0] = 4'b0010; y = 4'b1001;

end

initial #300 $finish;

endmodule

//--------------------------------------------

Figure 3: Simulation of binary multiplier in modelSim Showing initial value of x, y and C.

In figure 3 above,

x = 0000,

y= 0000

C = x×y=00000000 in binary,  0×0 = 0 in decimal.

Figure 4: Figure 3: Simulation of binary multiplier in modelSim Showing the value of x, y and C at 100ns.

In figure 4;

                                    x = 1010₂ =10 (decimal),

                                    y = 1001₂ =9 (decimal),

                                    C= x×y = 10×9 = 01011010₂

                                                 = 2⁶+2⁴+2³+2¹

                                                 = 64+16+8+2 = 90.

Figure 5: Figure 3: Simulation of binary multiplier in modelSim Showing the value of x, y and C at 200ns.

In figure 5;

                                    x = 0010₂ =2 (decimal),

                                    y = 1001₂ =9 (decimal),

                                    C= x×y = 2×9 = 00010010₂

                                                 = 2⁴+2¹

                                                 = 16+2 =18.

BCD Adder design and simulation with Verilog HDL Code in ModelSim

Computers understand binary number system while humans are used to arithmetic operations in decimal number systems. To enhance Computer-Human relationship in this perspective, arithmetic operations are performed by the computer in a binary coded decimal, (BCD) form.

In this article I’ll analyse and design a BCD adder which requires a minimum of nine inputs and five outputs, four bits are require to code the aguend and the addend making eight bits, and the circuit input carry makes the nine inputs. The four bit sum output and the output carry represents the five outputs.

Consider adding 9+9+1 in decimal, the result is 19, in straight binary this should produce an output 10011₂, this is an invalid number in BCD, because in BCD code the group of four bit binary only represent decimal numbers 0-9. The table bellow shows decimal numbers 0-19 with their corresponding binary and BCD codes. The K and C in the table are the respective binary carry and BCD carry bits.

     

     

Bellow the ruled level on the table, the BCD adder should detect that the binary codes are unusable in BCD coding system and provide the necessary correction. The conditions for the levels on the table where correction is required a;

1. Point where binary sum has output carry K =1 or,
2. where Z₈ and Z₂ are both = 1 or,
3. where Z₈ and Z₄ are both = 1.

The gives the expression for correction requirement:  C_or = K + Z₈Z₄ +Z8Z₂

When Cor = 1, it is necessary to add 0110 to the binary sum and provide an output carry for the next stage.

For example:

Adding:      

Figure 1:  Block diagram of BCD adder

When an output carry K  = 0 nothing happens as the out S₈S₄S₂S₁ is added to 0000 in the second 4-bit adder, but when K=1 OR Z₈&Z₄ OR  Z₈&Z₂ is equal to ‘1’, the output carry generates a ‘1’, thus “0110” is added to the output of the first 4-bit adder. The MSB 0 and LSB 0 in the “0110” to be added is generate by the EXOR gate which accept the output carry at its two input, either the output carry is 0 or 1 the EXOR generates a ‘0’ (both its input are equal).

The C_BCD   is the carry generated by the BCD adder, whenever the output of the OR-gate is ‘1’ a carry is generated by the BCD adder to the next four-bit group of the BCD code, carry output generated by the 4-bit adder of the second stage is discarded as it will provided by C_BCD as required. Bellow is the Verilog HDL code for BCD adder and figure 2,3, and four shows the simulations changing the bits value at 100ns, 200ns and 300ns.

//-----------------------------------------------------

module BCD_adder(S, C, A, B, C0);

input [3:0] A, B;

input  C0;

output  [3:0] S;

output  C;

wire C1, C2, C3, C4, C5;

wire [3:0]X, Z;

and (C1, Z[3], Z[2]);

and (C2, Z[3], Z[1]);

or  (C, C3, C1,C2);

xor (C5, C, C);

assign X[2] = C;

assign X[1] = C;

assign X[3] = C5;

assign X[0] = C5;

//four bit adder body from instance of full_adder

four_bit_adder F_1 (Z, C3, A, B, C0);

four_bit_adder F_2 (S, C4, X, Z, C0);

endmodule

//----------------------------------------------------------

//-------------------------------------------------------------

// Test bench for BCD_Adder

module t_BCD_adder;

wire [3:0] S;

wire  C;

reg  [3:0]A, B;

reg   C0;

BCD_adder F1(S, C, A, B, C0);

initial

begin

   A[3:0] = 4'b0000; B = 4'b0000; C0 = 1'b0;

     

#100 A[3:0] = 4'b1001; B = 4'b1001; C0 = 1'b0;

#100 A[3:0] = 4'b1000; B = 4'b0011; C0 = 1'b0;

#100 A[3:0] = 4'b0100; B = 4'b0011; C0 = 1'b0;

end

initial #400 $finish;

endmodule

//--------------------------------------------

Figure 2: Simulation showing the initial bits value of A: 0000, B: 0000, Sum S: 0000 and Carry C: 0 for the BCD adder (i.e. 0 + 0 = 0 0).

Figure 3: Simulation showing the bits value at 100ns for  A: 1001, B: 1001, Sum S: 1000 and Carry C: 1 for the BCD adder (i.e. 9 + 9 = 1 8 ).

Figure 4: Simulation showing the bits value at 300ns for  A: 1000, B: 0011, Sum S: 0001 and Carry C: 1 for the BCD adder (i.e. 8+ 3 = 1 1 ).

Figure 5: Simulation showing the bits value at 300ns for  A: 0100, B: 0011, Sum S: 0111 and Carry C: 0 for the BCD adder (i.e. 4+ 3 = 0 7 ). Reference Mano M. Morris and Ciletti D. Michael; “Digital Design With and Introduction to the Verilog HDL – Fifth Edition” Copyright © 2013, 2007, 2002, 1991, 1984 Person Education, Inc., publishing as Prentice Hall, One Lake Street, Upper Saddle River, New Jersey 07458.

Digital Arithmetic Circuits with Verilog HDL

HALF ADDER CIRCUIT DESIGN

An adder or summer is a digital circuit that performs addition of numbers. In digital computing and processing, the use of adders is not limited to arithmetic logic unit(s) alone but also in processor calculation of addresses, table indices, and similar operations.

Half adder is a combinational arithmetic circuit that adds two numbers and produces a Sum bit (S) and Carry bit (C) as the output. 

Table 1: Truth Table Analysis of Half Adder

A	B	S	C
0	0	0	0
0	1	1	0

1	0	1	0
1	1	0	1

A :  augends

B:  addend

S:   Sum output

C:  Carry output

Sum-of-products expression of half adder from the truth table is given by:

………… equation (1a).

               …………….....  equation (1b).

Logic Circuit of and Half Adder:

Figure 1a: Half Adder Logic circuit

Figure 1b: Block Diagram of Half adder

//-------------------------------------------------------------------------

//Verilog Hardware Description Language (HDL) code for Half Adder

//Structural model of Module_1 (Half adder) with Verilog HDL

module  H_Adder      (S, C, A, B);

input                A, B;

output               C, S;

xor                  (S, A, B);

and                  (C, A, B);

endmodule

//-------------------------------------------------------------------------

//-----------------------------------------------------------------------

// Test bench for H_Adder

module t_H_Adder;

wire C, S;

reg  A, B;

H_Adder H_A1 (S, C, A, B); // Instance name required

initial

begin

A = 1'b0; B = 1'b0;

#100 A = 1'b0; B = 1'b0;

#100 A = 1'b0; B = 1'b1;

#100 A = 1'b1; B = 1'b0;

#100 A = 1'b1; B = 1'b1;

end

initial #500 $finish;

endmodule

//------------------------------------------------------------------------

Figure 2: Simulation output for Half adder Verilog HDL in ModelSim

FULL ADDER CIRCUIT DESIGN

A full adder adds binary numbers and accounts for values carried in as well as out. A one-bit full adder adds three one-bit numbers, often written as A, B, and C_in, is a bit carried in from the next less significant stage. In practical, the full-adder is usually a component in a cascade of adders, for the addition of 8, 16, 32, etc. bits binary numbers. The circuit produces a two-bit output, output carry and sum typically represented by the signals C_out and S.  The truth table for a 1-bit full adder is described in table 2 bellow.

Table 2: Truth Table for 1-bit Full adder

A	B	Cin	S	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Simplification Using K-Map:

Sum:

Carry:

Substituting for half adder equations in that of Full adder, let’s denote Sum of half adder by S_H and Carry for Half adder as C_H.  We can deduce that;

Figure 3: Full adder Logic circuit

Figure 3b: Full adder implementation with two Half adder circuits

Figure 3c: Full adder block diagram

//--------------------------------------------------------------------

//Full adder verilog HDL Code using the half adder instance

module  F_Adder (S, Cout, A, B, Cin);

output  S,Cout;

input  A, B, Cin;

wire   S1, C1, C2;

H_Adder HA1 (S1, C1, A, B);

H_Adder HA2 (S, C2, Cin, S1);

or  (Cout, C1, C2);

endmodule

//--------------------------------------------------------------------

//--------------------------------------------------------------------

// Test bench for F_Adder

module t_F_Adder;

wire S, Cout;

reg  A, B, Cin;

F_Adder F_A1 (S, Cout, A, B, Cin); // Instance name required

initial

begin

A = 1'b0; B = 1'b0; Cin=1'b0;

#100 A = 1'b0; B = 1'b0; Cin = 1'b0;

#100 A = 1'b0; B = 1'b0; Cin = 1'b1;

#100 A = 1'b0; B = 1'b1; Cin = 1'b0;

#100 A = 1'b0; B = 1'b1; Cin = 1'b1;

#100 A = 1'b1; B = 1'b0; Cin = 1'b0;

#100 A = 1'b1; B = 1'b0; Cin = 1'b1;

#100 A = 1'b1; B = 1'b1; Cin = 1'b0;

#100 A = 1'b1; B = 1'b1; Cin = 1'b1;

end

initial #900 $finish;

endmodule
//-------------------------------------------------------------------

Figure 4: Full adder HDL Simulation with ModelSim

FOUR-BIT BINARY ADDER

Given a 4-bit binary augend  A₃ A₂ A₁ A₀ and the addend B₃ B₂ B₁ B₀. We can perform binary addition A+B using a cascade of adders shown in figure 4, bellow;

Figure 4: Four-bit adder design

Figure 4b: Four-bit adder block diagram

//-----------------------------------------------------

//Verilog HDL Code for 4-bit adder

module four_bit_adder(S, C4, A, B, C0);

input [3:0] A, B;

input  C0;

output  [3:0] S;

output  C4;

wire C1, C2, C3;

//four bit adder body from instance of full_adder

F_Adder  F_A1 (S[0], C1, A[0], B[0], C0);

F_Adder  F_A2 (S[1], C2, A[1], B[1], C1);

F_Adder  F_A3 (S[2], C3, A[2], B[2], C2);

F_Adder  F_A4 (S[3], C4, A[3], B[3], C3);

endmodule

//----------------------------------------------------------

//--------------------------------------------------------------

// Test bench for 4_bit_Adder

module t_four_bit_adder;

wire [3:0] S;

wire  C4;

reg  [3:0]A, B;

reg   C0;

four_bit_adder F1(S, C4, A, B, C0);

initial

begin

   A[3:0] = 4'b0000; B = 4'b0000; C0 = 1'b0;

     

#100 A[3:0] = 4'b1010; B = 4'b1001; C0 = 1'b0;

#100 A[3:0] = 4'b0010; B = 4'b1001; C0 = 1'b1;

end

initial #300 $finish;

endmodule

//--------------------------------------------

Figure 5: Four-bit adder simulation 

CARRY LOOKAHEAD LOGIC CIRCUIT DESIGN

In the four-bit circuit design above, the output of the adder cannot be completely determined until the carry propagates through the full adders. Carry lookahead logic, is the technology that is widely used to reduce the propagation time of adder circuits and make their arithmetic operations faster.

Figure 6: Full adder circuit showing P and G signals

In the circuit of described in figure 5, “the signals at Pi and Gi settle to their steady-state values after they propagate through their respective gates”, (Mano, 2013). The two signals are common to half adders and depend on only the input augend and addend bits, (Mano, 2013).

The carry propagation time is a very important attribute of an adder as it determines the speed at which it adds two numbers, (Mano, 2013). All other arithmetic operation in digital system can be performed by successive additions, this makes the time take required for addition process critical to digital arithmetic operations. By trading complexity of equipments for speed, we use the carry lookahead logic for reducing the carry propagation time in a parallel adder as described bellow.

Considering the circuit in figure 6;

The output sum and carry can respectively be expressed as:

From equation (4),  we can deduce that if;

            C0 = input carry

With the equations above, we can deduce that not minding the cost and complexity of the circuit, we may not need to wait for the carries (C1,C2,C3) to propagate through the circuit before getting the result of our addition. Figure 7 bellow shows the logic circuit diagram for the carry lookahead generator.

Figure 7:  Carry lookahead Generator

//---------------------------------------------------------------------

//Carry lookahead generator model with Verilog HDL

module  Carry_lookahead_gen (C1,C2,C3, P0, P1, P2, G0, G1, G2, C0);

input     P0, P1, P2, G0, G1, G2, C0;

output   C1,C2,C3;

wire     w1, w2, w3, w4, w5, w6;

and   (w1, P0, C0);

or    (C1, w1, G0);

and   (w2, P1, G0);

and   (w3, P0, P1, C0);

or    (C2, w2, w3, G1);

and   (w4, P2, G1);

and   (w5, P1, P2, G0);

and   (w6,  P0, P1, P2, C0);

or    (C3, w4, w5, w6);

endmodule

//-------------------------------------------------------------------------

If we study figure 7 critically with figure 6, we will notice that P_i and G_i are the Sum and Carry output of the first half adder in the module while (Pi exor Gi) is the Sum of the whole Full adder module. In the design of a four-bit binary adder employing the carry lookahead generator, in this circuit, our C1, C2, C3 (carry output from adder 1, 3, and 3 respectively) are available immediately we have the four bit augend A₀A₁A₂A₃ and the addend B₀B₁B₂B₃ with the initial carry-in to the Lowest Significant Binary (LSB) and thus reduce the carry propagation delay time figure 8, bellow.

Figure 8: Four-bit adder with carry lookahead generator

Figure 9: Signal waveform for 4 bits adder with carry lookahead generator from ModelSim simulation for the first 100ns.

In figure 9, the first change of bits at 100ns depicted by the yellow line, C₄ = 1, S₃,S₂,S₁,S₀  = 0011,  A₃A₂A₁A₀ = 1010, B₃B₂B₁B₀ = 1001, and C₀ = 0

Figure 10: Signal waveform for 4 bits adder with carry lookahead generator from ModelSim simulation for the second 100ns.

FOUR-BIT BINARY ADDER/SUBTRACTOR

We can perform subtraction of unsigned numbers conveniently by means of 2’s complements. A-B = A+(-B) and –B = 2’s complement of B. The 2’s complement can be obtained by taking the 1’s complement and adding 1 to the least significant pair of bits.

The circuit described in figure 11 bellow is designed to perform addition and subtraction of four-bit binary in two’s complement.

Figure 11: Four-bit binary Adder/Subtractor

In the circuit the augend bit i.e. A₀A₁A₂A₃ is added to the addend bit B₀B₁B₂B₃ when the circuit is performing addition, M = 0, and when it is to perform subtraction M=1. When M=0 meaning, the circuit is to perform arithmetic A₃A₂A₁A₀ + B₃B₂B₁B₀, when M=1 then the operation is A₃A₂A₁A₀ – B₃B₂B₁B₀ in the latter case, the circuit actually perform A₃A₂A₁A₀ + (-B₃B₂B₁B₀), (-B₃B₂B₁B₀) is given by 2’complement of - B₃B₂B₁B₀.

In this case, since M=1, the output of the Exclusive-Or gates in the circuit will be 1’complement of B₃B₂B₁B₀, the addition of C0 which is now ‘1’ makes the result the two’s complement of  B₃B₂B₁B₀. The output of the circuit will be S₃S₂S₁S₀, this is the correct answer. In the case of signed binary number, there are some things to be noted, firstly, the Most Significant Binary (MSB) indicates the sign of the binary number 1=> negative, 0=> Positive, and also the output V in the figure 11, if V=0, then there is an overflow, an overflow indicates that the result of the addition or subtraction is beyond the range of representation of the number of binary bits.

It is worth to note at this point that signed binary number of n bit can represent number ranges from -2^n-1 to 2^n-1-1. There is need for some little enhancement of circuit in figure 11, to enable it display correct result for signed binary numbers. It’s waveform output for simple addition and subtraction is given in figures 12 and 13 bellow.

//------------------------------------------------------------------------

// Verilog Code for adder/ subtraction circuit in figure 11

module add_sub(S,V, A, B1, M);

input [3:0] A, B1;

input  M;

output  [3:0] S;

output  V;

wire  [3:0]B;

wire C1, C2, C3;

//four bit adder body from instance of full_adder

F_Adder  F_A1 (S[0], C1, A[0], B[0], M);

F_Adder  F_A2 (S[1], C2, A[1], B[1], C1);

F_Adder  F_A3 (S[2], C3, A[2], B[2], C2);

F_Adder  F_A4 (S[3], C4, A[3], B[3], C3);

xor (B[0], M, B1[0]);

xor (B[1], M, B1[1]);

xor (B[2], M, B1[2]);

xor (B[3], M, B1[3]);

xor (V, C4,C3);

endmodule

//-----------------------------------------------------------------------

//------------------------------------------------------------------------

// Test bench for adder/subtraction circuit

module t_add_sub;

wire [3:0] S;

wire  V;

reg  [3:0]A, B1;

reg   M;

add_sub a_s1 (S,V, A, B1, M);

initial

begin

   A[3:0] = 4'b0000; B1 = 4'b0000; M = 1'b0;

     

#100 A[3:0] = 4'b1010; B1 = 4'b0001; M = 1'b0;

#100 A[3:0] = 4'b1010; B1 = 4'b0001; M = 1'b1;

end

initial #300 $finish;

endmodule

//-------------------------------------------------------------------------

Figure 12: Output Waveform for Adder/Subtractor circuit

 

Reference

Adder (electronics); “From Wikipedia, the free encyclopedia”, LINK

Mano M. Morris and Ciletti D. Michael; “Digital Design With and Introduction to the Verilog HDL – Fifth Edition” Copyright © 2013, 2007, 2002, 1991, 1984 Person Education, Inc., publishing as Prentice Hall, One Lake Street, Upper Saddle River, New Jersey 07458.

Marcus Lloyde George and Lucien Ngalamou; “A Methodology for Effectively Teaching Digital Design to Electrical and Computer Engineering Students of the University of the West Indies (UWI) in Nine Weeks”, Transactions on Eduction.

Peter J. Ashenden (2004);  “VHDL Tutorial”,  EDA Consultant, Ashenden Designs PTY. LTD. www.ashenden.com.au © 2004 by Elsevier Science (USA).

Samir Palnitkar (1996); “Verilog HDL, A guide to Digital Design and Synthesis” SunSoft Press 1996.

Valentino Crespi, Aram Galstyan, Kristina Lerman(3005); “Comparative Analysis of Top-Down and Bottom-up Methodologies for Multi-Agent System Design”, AAMAS’05, July 25-29, 2005, Utrecht, Nertherlands. Copyright 2005 ACM 1-59593-094-9/05/0007…$5.00.