2.1 Exact 4-2 Compressor

Since an exact 4-2 compressor has five inputs (denoted as x1, x2, x3, x4, C_IN) and three outputs (SUM, CARRY, C_OUT), it is called a (5,3) counter. In Fig. 1, SUM has the same weight as the inputs, while CARRY and C_OUT have double the weight. C_OUT is independent of C_ IN. For instance, C_OUT of column i column i becomes C_IN of column i+1, and this feature is used in tree multipliers. The usual implementation of an exact 4-2 compressor is represented by using two full adders ^[9].

Fig. 1. An exact 4-2 compressor with two full adders.

2.2 Momeni Approximate 4-2 Compressor

A Momeni approximate 4-2 compressor starts with a truth table. CARRY from the truth table of an exact 4-2 compressor has the same value with the C_IN, 24 out of 32 states. Therefore, CARRY is simplified to C_IN to design an approximate 4-2 compressor. The SUM and C_OUT output equation is simplified to reduce the complexity of the circuit. The expressions are described below.

If C_OUT is always equal to C_IN, C_OUT and C_IN can be ignored in the circuit to design a simpler one, so we replace C_OUT on the left side of Eq. (3) with CARRY on the left side of Eq. (1). Then, the output equation can be more straightforward, and the circuit design is simpler. Therefore, the critical path delay and power consumption are expected to improve compared with an exact 4-2 compressor. The result of the Momeni design ^[1] is shown in Table 1. Fig. 2 shows the gate-level implementation of the Momeni approximate 4-2 compressor, and output equations are described below.

In Table 1, the design has four incorrect results out of 16 outputs, so its error rate is 25%, but it has a significant defect. Because it has an incorrect result at x4x3x2x1=0000, the probability of this order is 0.32, which is higher than the others. This will make significant relative errors for small operand operations when the Momeni compressor is used in the multiplier.

Fig. 2. Gate-level implementation of Momeni approximate 4-2 compressor[1].

2.3 Proposed 4-2 Compressor

The proposed 4-2 compressor is introduced to improve the error rate, the delay, and the power consumption. In order to improve the performance of the compressor, the importance of the input order should be analyzed and understood first. The partial product from the AND gate has the same probability of being 1. The probability is 1/4. This partial product becomes the input of the 4-2 compressor in the multiplier, so the probability of x4x3x2x1 = 0001 and the probability of x4x3x2x1 = 0111 are different.

For example, the probability of x4x3x2x1 = 0001 is 27/256, and that of x4x3x2x1 = 0111 is 3/256. If x4x3x2x1 = 0001 and x4x3x2x1 = 0111 are the error order input of approximate 4-2 compressor, the x4x3x2x1 = 0001 order will make more error than x4x3x2x1 = 0111 order due to the probability in the multiplier. Therefore, an input order that makes an error result, like x4x3x2x1 = 0000 and x4x3x2x1 = 0001, is not recommended. Instead, the input orders x4x3x2x1 = 0011 and x4x3x2x1 = 0111 are recommended. To improve the performance of the approximate 4-2 compressor, we assume C_ IN and C_OUT of the proposed design have the same weight as in the Momeni design ^[1].

First, making the correct output is needed when the input ordering is x4x3x2x1 = 0000, x4x3x2x1 = 0001, x4x3x2x1 = 0010, x4x3x2x1 = 0100, and x4x3x2x1 = 1000. The AND of x1 and x2 can make correct CARRY outputs from the order of inputs with high probability, but it makes eight incorrect outputs. Eight incorrect outputs are reduced to five when combined with the AND of x3 and x4 using OR gates. Using De Morgan’s laws, the CARRY equation uses only NAND, and the following describes the CARRY output.

SUM has to make the correct outputs when the input order has a high probability. The XOR of x1 and x2 produces the correct result except when the input order is x4x3x2x1 = 0100. However, The OR of x3 and x4 has the correct result when combined with the XOR of x1 and x2 using an OR gate. Using De Morgan's laws, the SUM equation uses NAND and NOR to improve the delay and power consumption, and we describe the CARRY output below. Fig. 3 shows the gate-level implementation of the proposed approximate 4-2 compressor.

Table 2 shows the truth table of the proposed approximate 4-2 compressor. There are no incorrect outputs when the input ordering is x4x3x2x1 = 0000, x4x3x2x1 = 0001, x4x3x2x1 = 0010, x4x3x2x1 = 0100, and x4x3x2x1 = 1000, and the proposed compressor has six incorrect outputs out of 16 outputs. It will make fewer errors for small operand operations when the proposed compressor is used in a multiplier. Fig. 3 shows that the number of gates used is reduced compared with the Momeni design ^[1] because a NOR gate is used in the SUM equation of the proposed design instead of an XNOR gate. Therefore, so the proposed compressor will show improvement in the power consumption and delay.

Fig. 3. Gate-level implementation of proposed approximate 4-2 compressor.

3.1 Error Rate Minimization

In the first stage, the 4-2 compressor inputs are partial products and independent of each other. The probability of being 1 is 1/4, but inputs of the second stage for 4-2 compressors come from the first stage, so the approximate 4-2 compressor inputs are dependent, as shown in Figs. 5 and 6. Before understanding the relationship between the input ordering of the approximate 4-2 compressor and the approximate multiplier's error rate, calculating the probability of the output from the first stage is needed.

The probability that the sum of half adder is 1 is: P(sum) = p(x1x2 = 01) + p(x1x2 = 10) = (3/4)(1/4) + (1/4)(3/4) = 0.375. The probability that carry becomes 1 is: P(carry) = p(x1x2 = 11) = (1/4)(1/4) = 0.062. In the Momeni design, the probability that sum is 1 is: P(sum) = 1 – p(x4x3x2x1 = 0101) – p(x4x3x2x1 = 0110) – p(x4x3x2x1 = 1001) – p(x4x3x2x1 = 1010) = 0.859. The other probabilities are also calculated in this way. P(carry) of the Momeni design being 1 is 0.191. In the proposed design, the probability that sum is 1 is P(sum) = 0.648, and the probability that carry is 1 is P(carry) = 0.168.

To minimize the error rate of an approximate multiplier, an input order that makes the minimal probability of an error result in the second stage of the PPST is needed. In the Momeni compressor, the orders x4x3x2x1 = 0000, x4x3x2x1 = 0011, x4x3x2x1 = 1100, and x4x3x2x1 = 1111 show error results. The probability of the orders of x4x3x2x1 = 0000 and x4x3x2x1 = 1111 is independent of the input order, but the probability of the orders x4x3x2x1 = 0011 and x4x3x2x1 = 1100 has an input order dependency.

At 5 bits, three partial products have the same probability, so the sum of the half adder from the first stage does not affect the result. P(sum) of the Momeni design is relatively high at 6 bits and 7 bits in Fig 5. Therefore, P(sum) has to pair up with the input with the lowest probability at those bits in x1x2 or x3x4. The input order that makes a minimal error result is shown in Fig. 5.

Fig. 5. Partial product probability of the second stage of the multiplier ofFig. 4(b)using Momeni design. This shows the input ordering that minimizes the error probability for MUL2 in the second stage.

In the proposed compressor, the orders x4x3x2x1 = 0101, x4x3x2x1 = 0110, x4x3x2x1 = 1001, x4x3x2x1 = 1010, x4x3x2x1 = 1100, and x4x3x2x1 = 1111 show error results. x4 and x3 make an error four times when x4 and x3 values are 1. x1 and x2 make an error three times when x1 and x2 values are 1. To minimize the error probability, the first and second lowest probabilities should have an input of x4 and x3. The input orders that make a minimal error result are shown in Fig. 6. The objective of the proposed design is to reduce the error rate compared with MUL2. Input order x4x3x2x1 = 0000 of the Momeni approximate compressor used in MUL2 will make significant relative errors for small operand operations, but the proposed approximate compressor has a correct result at x4x3x2x1 = 0000 and will show a better error rate than MUL2.

Fig. 6. Partial products probability of the second stage of the multiplier of Fig. 4(b) using the proposed design. This figure shows the input ordering that minimizes the error probability for the proposed multiplier in the second stage.

4.1 Approximate Compressor

One exact compressor and two approximate compressors were simulated. The simulation results of the delay, power consumption, and power-delay product (PDP) are summarized in Table 3. As shown in Table 3, the proposed design has the best delay, power consumption, and PDP. The proposed approximate compressor is 81.71% faster than the exact compressor and 22.51% faster than Momeni approximate compressor. The power consumption shows 63.2% improvement compared to the exact compressor and 4.24% reduction compared to the Momeni approximate compressor. The speedup and decrease in power consumption in the proposed compressor are attributed to reducing the number of transistors. The proposed approximate compressor shows a 61.91% reduction from the exact compressor and a 23.81% reduction compared to the Momeni approximate compressor.

4.2 Approximate Multiplier

Three multipliers were simulated: exact, MUL2, and the multiplier with proposed compressors, and the results are summarized in Table 4. As shown in Table 4, the proposed design has the best delay, power consumption, and PDP. In Table 4, there is no significant delay improvement in the proposed multiplier compared with the exact and MUL2 multipliers because the critical paths among all three multipliers are the same. However, the proposed multiplier’s power consumption shows an 18.65% improvement compared to the exact multiplier and a 4.18% reduction compared to the approximate MUL2. The decrease in power consumption is attributed to reducing the transistors in the PPST stage. The proposed method shows a 13.44% reduction compared to MUL1 and a 2.9% reduction compared to MUL2 in terms of the number of transistors.

4.3 Error Metrics

MUL2 and the proposed multiplier were simulated to compare the error metrics for an 8${\times}$8 unsigned Dadda approximate multiplier. The Error Rate (ER), Mean Error Distance (MED), and Normalized Mean Error Distance (NMED) are summarized in Tables 5 and 6. Assuming E and A, the results were produced by an exact and an approximate multiplier. First, we define the Error Distance ^[10], ED = ${\sum}$|E-A|, and the Max Out for unsigned multiplier, Max Out = (2$^{\mathrm{n}}$-1)$^{2}$. The error metrics considered in this paper are:

· Error Rate (ER): the percentage of the multiplication result for which ED > 0.

· Mean Error Distance (MED): ED/2$^{\mathrm{2n}}$ = ${\sum}|E-A|/2$$^{2n}$.

· Normalized Error Distance (NMED): the average value of ED divided by Max Out.

As shown in Table 7, the proposed multiplier shows better accuracy than MUL2. As mentioned, MUL2 shows a 93.43% error rate because incorrect order x4x3x2x1 = 0000 of the Momeni approximate compressor results in significant relative errors for small operand operation. However, the proposed design shows a 15.54% improvement in ER compared with MUL2 because the input order x4x3x2x1 = 0000 of the proposed approximate design results in an exact value of 0. The proposed multiplier also provides better error performance in MED and NMED than MUL2.

To prove the robustness of the proposed design for multiplication between small operands compared with the Momeni method (i.e., MUL2), multiplication results from 0${\times}$0 to 63${\times}$63 were investigated and are summarized in Table 8. It is worth noting that the improvement compared with MUL2 becomes larger for smaller operands. From this result, the multiplier using the Momeni compressor is more susceptible to multiplication between small operands, but the multiplier with the proposed compressor is not.