4x4 Bit Approximate Multiplier

This repository presents an approximation technique for a 4x4 bit multiplier based on the methods described in the paper Design and Analysis of Approximate Multipliers. The final implementation satisfies the following criteria:

• Mean relative error: Less than 10%
• Number of LUTs: Less than 12

Overview

Approximation Techniques

Half Adder

The exact half adder is approximated as follows:

• Exact Implementation:
  • Sum = A $\oplus$ B
  • C_out = A $\cdot$ B
• Approximated Implementation:
  • Sum = A $+$ B
  • C_out = A $\cdot$ B

Truth Table Comparison

A	B	Exact		Approximate
		Sum	Cout	Sum	Cout
1	1	0	1	1	1

1 out of 4 cases has an error in Sum.

Full Adder

The exact full adder is approximated as follows:

• Exact Implementation:
  • Sum = A $\oplus$ B $\oplus$ C_in
  • C_out = (A $\cdot$ B) $+$ (B $\cdot$ C_in) $+$ (C_in $\cdot$ A)
• Approximated Implementation:
  • Sum = B
  • C_out = A
  • C_in is not used.

Truth Table Comparison

A	B	Cin	Exact		Approximate
			Sum	Cout	Sum	Cout
0	0	1	1	0	0	0
0	1	1	0	1	1	0
1	0	0	1	0	0	1
1	1	0	0	1	1	1

4 out of 8 cases have errors: 4 in Sum and 2 in C_out.

Partial Product Transformation

The approximation involves the transformation of partial product terms a_m,n and a_n,m ( a_m,n = a[m] $\times$ b[n] ) into propagate and generate terms:

• p_m,n = a_m,n $+$ a_n,m
• g_m,n = a_m,n $\cdot$ a_n,m
• a_m,m terms are retained.

Partial Product Reduction with Compressors

A compressor is used to simplify the partial product tree. It takes 4 input bits and a carry-in (C_in) bit and generates Sum, Carry, and Carry-out (C_out) bits. The exact compressor uses two full adders:

1. The first full adder takes 3 input bits and generates:
   • Intermediate Sum
   • Carry-out (C_out)
2. The second full adder takes:
   • Intermediate Sum
   • 4th input bit
   • Carry-in (C_in)
     and generates the final Sum and Carry bits.

Approximated Compressor

The approximated compressor is defined as:

• Carry = C_in
• Sum = (A $\oplus$ B) $+$ (C $\oplus$ D)
• Carry-out (C_out) = (A $\cdot$ B) $+$ (C $\cdot$ D)

Truth Table Comparison

A	B	C	D	Cin	Exact			Approximate
					Sum	Carry	Cout	Sum	Carry	Cout
0	0	0	0	1	1	0	0	0	1	0
0	0	0	1	1	0	1	0	1	1	0
0	0	1	0	1	0	1	0	1	1	0
0	0	1	1	0	0	1	0	0	0	1
0	0	1	1	1	1	1	0	0	1	1
0	1	0	0	1	0	1	0	1	1	0
0	1	0	1	0	0	1	0	1	0	0
0	1	1	0	0	0	0	1	1	0	0
0	1	1	0	1	1	0	1	1	1	0
0	1	1	1	1	0	1	1	1	1	1
1	0	0	0	1	0	1	0	1	1	0
1	0	0	1	0	0	1	0	1	0	0
1	0	1	0	0	0	0	1	1	0	0
1	0	1	0	1	1	0	1	1	1	0
1	0	1	1	1	0	1	1	1	1	1
1	1	0	0	1	1	0	1	0	1	1
1	1	0	1	1	0	1	1	1	1	1
1	1	1	0	1	0	1	1	1	1	1
1	1	1	1	0	0	1	1	0	0	1
1	1	1	1	1	1	1	1	0	1	1

20 out of 32 cases have errors: 16 in Sum, 8 in Carry and 6 in C_out.

Half Adder: , Full Adder: , Compressor: , C_out: & Carry:

The C_out for the last half adder is always 0.

Final Summation

After the partial product reduction, the remaining Sum and Carry-out bits are processed using half adders and full adders to generate the final output.

---

Results and Analysis

The following images demonstrate that the design meets the specified criteria for:

1. Error: Mean relative error = 8.23% (less than 10%)

2. Power Utilization: 40 mW for logic (Efficient power usage)

3. LUT Utilization: Number of LUTs = 9 (less than 12)

---

Feel free to clone this repository and explore the implementation!