3.1 The Compressor

As shown in Fig. 1, an exact 4-2 compressor generally consists of two full adders with five inputs (x$_{1}$, x$_{2}$, x$_{3}$, x$_{4}$, and cin) and three outputs (sum, carry, and cout) ^[13]. The number for logic 1 in five inputs is counted by the output according to (1), (2), and (3):

The four inputs, x$_{1}$, x$_{2}$, x$_{3}$, and x$_{4}$, and the output sum have the same weight, whereas the weights of cout and carry are one binary bit order higher ^[12,14]. Therefore, cout and carry are delivered to the next module of higher significance.

In this work, the proposed 4-2 compressor (Fig. 2) is derived by modifying the truth table of the exact compressor to obtain simpler logic expressions, as seen in (4) and (5), along with ignoring signals cin and cout for design efficiency, as seen in previous work ^[2]. Input x$_{1}$ and x$_{2}$ are also omitted to simplify the compressor and greatly reduce the energy and critical path delay further. Thus, it has only OR and XNOR gates. Although the omission of x$_{1}$ and x$_{2}$ introduces certain errors, the proposed compressors are only used for the approximate part in multipliers, which has little impact on computing accuracy. Thus, attention will be paid more to the hardware/accuracy trade-off of the multipliers, rather than only a specific indicator.

As seen in the truth table in Table 1, the proposed design has eight erroneous outputs out of 16 outputs. Error is defined as the arithmetic distance between the exact and approximate values ^[15]. For example, when all inputs are 1, the exact output is 4, and the proposed compressor produces a 1 for both sum and carry. In this case, the decimal output is 3, so the error distance is 1. The maximum error generated by this design is 1 (-1), which could avoid unacceptable results when the compressor is applied to approximate multipliers. Besides, in the structure of a multiplier, error distance with opposite signs of -1 and 1 will counteract each other ^[5].

Fig. 1. The conventional 4-2 compressor.

Fig. 2. The proposed 4-2 compressor.

3.2 The Approximate Multipliers

To investigate the impact of the proposed compressor on multiplication, 8${\times}$8 Dadda multipliers with various levels of accuracy are designed. The basic structure of the approximate Dadda multiplier was described in ^[2] where the multiplier uses AND gates to generate all partial products in the first step, and then uses approximate compressors to compress them into, at most, two rows. In the last step, an exact ripple carry adder computes the results.

In designing multipliers, the second step plays a critical role in terms of delay, power consumption, and area. The proposed multipliers are denoted M${\alpha}$${\beta}$${\gamma}$, where ${\alpha}$, ${\beta}$, and ${\gamma}$, respectively, represent the number of columns using exact compressors, approximate compressors, and truncation to compress partial products. To find an effective way to improve the performance of multipliers, the least significant bits of the partial products are truncated. In some applications, such as image processing, it is not desirable to obtain more than a certain level of accuracy. Furthermore, the related exact operations consume relatively high amounts of energy. Therefore, exact compressors are utilized for the most significant bits to make up for the lack of computing accuracy, while the proposed approximate compressors are applied to the middle of the partial products to reduce the hardware cost. To investigate the trade-off between hardware cost and accuracy, a set of multipliers was designed. Obviously, M7${\beta}$${\gamma}$ and M6${\beta}$${\gamma}$ aim at improving computing accuracy, while M5${\beta}$${\gamma}$ is used to reduce the hardware cost.

For example, the partial product reduction step of the proposed M654 is shown in Fig. 3, where each dot represents a partial product bit. In the first two stages, three half adders, three full adders, 10 of the proposed imprecise 4-2 compressors, and six exact 4-2 compressors are utilized. In the last stage, a half adder and nine full adders are applied to compute the results.

Fig. 3. Partial product reduction of the proposed M654.

4.1 The Approximate Compressor

A comparison of the proposed compressor and the existing exact and approximate compressors in terms of area, power, and delay is shown in Table 2. For clarity, the three designs proposed in ^[3] are represented by ^[3]1, ^[3]2, and ^[3]3, and the three methods in ^[6] are denoted ^[6]1, ^[6]2, and ^[6]3. To comprehensively evaluate efficiency from the proposed design, power-delay product (PDP) and energy-delay product (EDP) are also listed ^[9,16].

As can be seen from Table 2, the proposed approximate compressor has a 74% reduction in area, a 27% reduction in delay, and a 91% reduction in PDP, compared to the exact 4-2 compressor. Besides, it is noteworthy that the proposed compressor has the lowest area and power, compared to state-of-the-art 4-2 compressors. Although PDP is a little higher than ^[5], EDP is equal. In summary, the proposed approximate 4-2 compressor has an advantage in hardware overhead, owing to the optimized structure using only one OR gate and one XNOR gate. Although the compressor in ^[5] has better delay and power than the one proposed here, the approximate multiplier in ^[5] is inferior to the multipliers proposed here, as is explained later.

4.2 The Approximate Multipliers

4.2.2 Computing Accuracy

To evaluate the output quality from approximate multipliers, error rate (ER), mean error distance (MED), and normalized mean error distance (NMED) were computed by applying all 65,536 possible input combinations ^[16]. ER is the possibility of producing an erroneous result, and MED is calculated with (6):

(6)

$ MED=\frac{1}{2^{2N}}\sum _{i=1}^{2^{2N}}\left| ED_{i}\right| $

where N is the bit width of a multiplier, and ED$_{i}$ represents the arithmetic difference between approximate and exact results. NMED from the maximum output of the exact multiplier is expressed in (7):

(7)

$ NMED=\frac{1}{\left(2^{N}-1\right)^{2}}\sum _{i=1}^{2^{2N}}\frac{\left| ED_{i}\right| }{2^{2N}} $

The accuracy metrics of the proposed multipliers are listed in Table 4. In the three types of multiplier, M7${\beta}$${\gamma}$ has a relatively small ER, MED, and NMED. Besides, all the multipliers have a high ER, mainly due to the truncated structure. ER decreases as the number of truncated columns increases. As for MED and NMED, they decrease as ${\gamma}$ increases, and drop to a minimum when ${\beta}$ is 2, then increase again. When the number of truncated columns reached the highest level, the multipliers had the worst computing accuracy, but the accuracy of M717 was higher than M663, and M618 was better than M573 due to the exact part of the most significant bits.

Table 4. ER, MED, and NMED of approximate 8${\times}$8 multipliers.

Design	ER (%)	MED	NMED
M753	99.77	1.96×10$^{2}$	3.01×10$^{-3}$
M744	99.83	1.88×10$^{2}$	2.89×10$^{-3}$
M735	99.80	1.68×10$^{2}$	2.58×10$^{-3}$
M726	99.51	1.31×10$^{2}$	2.01×10$^{-3}$
M717	99.22	1.72×10$^{2}$	2.65×10$^{-3}$
M663	99.89	3.49×10$^{2}$	5.36×10$^{-3}$
M654	99.91	3.41×10$^{2}$	5.25×10$^{-3}$
M645	99.91	3.22×10$^{2}$	4.95×10$^{-3}$
M636	99.83	2.81×10$^{2}$	4.33×10$^{-3}$
M627	99.66	2.63×10$^{2}$	4.04×10$^{-3}$
M618	99.51	4.29×10$^{2}$	6.60×10$^{-3}$
M573	99.95	6.78×10$^{2}$	10.42×10$^{-3}$
M564	99.95	6.71×10$^{2}$	10.32×10$^{-3}$
M555	99.95	6.55×10$^{2}$	10.08×10$^{-3}$
M546	99.92	6.11×10$^{2}$	9.40×10$^{-3}$
M537	99.85	5.64×10$^{2}$	8.67×10$^{-3}$
M528	99.83	4.79×10$^{2}$	7.36×10$^{-3}$
M519	99.80	8.01×10$^{2}$	12.33×10$^{-3}$
[2]	99.10	3.15×10$^{3}$	48.46×10$^{-3}$
[3]1	87.19	3.62×10$^{3}$	55.73×10$^{-3}$
[3]2	87.19	4.17×10$^{3}$	64.2×10$^{-3}$
[3]3	97.26	5.91×10$^{3}$	90.92×10$^{-3}$
[4]	85.73	2.24×10$^{3}$	34.41×10$^{-3}$
[5]	99.82	4.94×10$^{2}$	7.60×10$^{-3}$
[6]1	55.34	0.70×10$^{2}$	1.07×10$^{-3}$
[6]2	17.96	0.17×10$^{2}$	0.26×10$^{-3}$
[6]3	3.59	0.03×10$^{2}$	0.04×10$^{-3}$

Compared to previous work, NMED from the proposed multipliers was not the lowest; however, it was acceptable for most image processing applications ^[17]. M528 had the best accuracy, compared to all designs except ^[6]. Although the multipliers in ^[6] have advantages in the accuracy metrics, they carried the highest hardware cost, as shown in Table 3. Therefore, all performance evaluation metrics should be taken into account.

The error distribution of the proposed multipliers, including M7${\beta}$${\gamma}$, M6${\beta}$${\gamma}$, and M5${\beta}$${\gamma}$, is shown in Fig. 4, where the errors were mainly in the ranges [-600, 600], [\hbox{-}1000, 1000], and [-2000, 1000], respectively, accounting on average for about 83%, 84%, and 84% of the whole range. Thus, the reservation of an appropriate number of the most significant bits will preserve the accuracy of a multiplier.

Fig. 4. Error distance from the multipliers: (a) M5${\beta}$${\gamma}$; (b) M6${\beta}$${\gamma}$; (c) M7${\beta}$${\gamma}$.

As seen from the results above, M5${\beta}$${\gamma}$ had the better hardware metrics but a worse NMED, while M7${\beta}$${\gamma}$ had the better NMED and a worse hardware cost. Thus, to reconcile the trade-off between accuracy and hardware cost, a figure of merit (FOM) was suggested in ^[8]. Due to the relatively small delay from the proposed multiplier, for a fair comparison, delay was removed and modified as seen in (8) ^[5]:

(8)

$ FOM1=PDP\times Area/\left(1-NMED\right) $

Fig. 5 shows FOM1 for the proposed and existing approximate 8${\times}$8 multipliers. The smaller the value of FOM1, the better the trade-off between accuracy and hardware. Thus, M627, M618, M564, M555, M546, M537, M528, and M519 have a lower FOM1 compared with other designs, indicating that most of the proposed multipliers offer a better trade-off than previous designs.

Fig. 5. FOM of approximate 8${\times}$8 multipliers.

4.3 Image Multiplication

To assess the practicality of approximate multipliers in real applications, they were applied to image multiplication as a widely used operation in image processing. The discussed multipliers handled two images, pixel by pixel, thereby combining two images into a single image ^[18-21].

The peak signal-to-noise ratio (PSNR) and the mean structural similarity index metric (MSSIM) ^[22] were computed to evaluate the quality of the processed images. PSNR is expressed in (9):

where w and r are the width and height of the image, $\textit{S'(i, j)}$ and S(i, j) represent the exact and approximate value of each pixel, respectively, and MAX is the maximum pixel value. The larger the PSNR, the better the image. MSSIM is expressed in (10):

where X and Y represent two images. Other parameters can be found in detail in ^[22]. MSSIM reaches 1 when the two processed images are the same.

Table 5 shows PSNR and MSSIM values for five image multiplication examples. All the proposed multipliers achieved PSNR values higher than 30dB for various images, with a PSNR higher than 30dB certified as good enough ^[23]. Besides, the results of MSSIM for all approximate multipliers are very close to the exact design (MSSIM=1). Moreover, both PSNR and MSSIM values increase as the number of exact columns increases.

To visualize the effect of approximate multiplication on image quality, multiplied images LenaRGB and Lena (using the considered multipliers) are shown in Fig. 6. The results indicate no obvious differences between the proposed designs and the exact design.

For comprehensively evaluating the efficiency of the discussed approximate designs in image processing, both hardware cost and image quality should be considered simultaneously, rather than under specific assessment. To intensify the practicability of approximate multipliers, FOM2 is expressed in (11) ^[24]:

Fig. 6. The multiplied images for LenaRGB and Lena using 8${\times}$8 multipliers.

A smaller FOM2 value indicates a better compromise between hardware efficiency and accuracy. Fig. 5 shows FOM2 from the discussed multipliers when saving space. The results indicate a decreasing trend. Among them, M627, M618, M537, M528, and M519 provided a better FOM2 than the other designs. Specifically, FOM2 for M528 takes first place in this regard, with a 63% reduction, on average, compared to the existing designs, followed by M519 and M537.