1. Exact Multiplication using Booth Encoding

Booth encoding ⁽⁸⁾ and its later forms, referred to as modified Booth or radix-$\textit{r}$ Booth encoding, where $\textit{r}$ is a power of 2, is a method of encoding the bits of a multiplier in a special nonbinary format of $\textit{n}$ digits. These $\textit{n}$ special multiplier digits can be used to form partial products in a manner that results in the need to use fewer addition or subtraction operations to form the same final product than with unencoded binary multiplication. Fewer adds and subtracts implies a shorter critical path delay and lower power usage. The effect of the reduction in add/subtracts is partially offset by the extra logic and delay required to produce the necessary radix-$\textit{r}$ Booth encoded partial products, as shown in ⁽⁹⁾-⁽¹³⁾.

By using radix-$\textit{r}$ Booth encoding, the number of partial products that need to be added or subtracted can be reduced from $\textit{n}$ to $n/\log _{2} r$. By using this simple logic, it would seem that it would be most beneficial to use the largest value of $\textit{r}$ that can be accommodated. In fact, Jiang ${et}$ ${al}$. has used this logic to argue for radix-$\textit{r}$ Booth encoding with very large $\textit{r}$ values ⁽⁶⁾. However, in general, because increasingly more complex logic is required to form the partial product terms with values of $\textit{r}$ greater than 4, radix-4 Booth encoding is the most commonly used encoding method. In radix-4 Booth encoding, new partial product terms $PP_{k}$ terms are formed based on the encoded forms of $b_{2i}$ and $b_{2i+1}$, with $k=i/2$. Then the final product $P$ is the sum of all $PP_{k}$ terms, which are half as many as the original $P_{i}$ terms.

Previous researchers have proposed successively better methods, shown in Fig. 1 for $\textit{n}$=8 (selected to simplify the exposition), for re-encoding the partial products $PP_{k}$ such that only about $\textit{n}$+2 bits need to be considered for each partial product. Fig. 1(a) shows the original set of $n/2$ $PP_{k}$ partial product rows. Each $PP_{k}$ is one of 0, $P_{k}$, $2P_{k}$, $-P_{k}$, or $-2P_{k}$. For those partial product rows that require the use of $-A$, partial product bits $\overline{a_{j}}$ $(0\leq j\leq \mathrm{n}-1)$ are used and $neg_{k}=1$ is added on the “next” partial product row to achieve the same effect as a 2's complement operation. Blank spaces are 0 bits. ${\blacksquare}$ is a partial product bit, which is always 0, $a_{j}$, or $\overline{a_{j}}$ $(0\leq j\leq n-1)$. The sign of $PP_{k}$ is denoted as ▲ and is 0 or the msb of $A$ or $-A$. Although Fig. 1 shows encodings for $\textit{n}$ = 8-bit multiplication, the encodings for larger $n$ values are essentially the same (the main differences are in the number of ${\blacksquare}$ terms and partial product rows).

The successive improvements adopted in Figs. 1(a)-(d) are as follows. In Fig. 1(b), the duplicated sign bits are eliminated by using the inverse of the sign bit and 1 ⁽⁹⁾. Fig. 1(c) shows how the $neg_{k}$ entry can be simplified by using special $c_{k}$ and $\tau _{k,0}$ terms ⁽¹⁰⁾. Finally, Fig. 1(d) shows how the extra $PP_{4}$ partial product row can be eliminated altogether by using special $\tau _{\left\lceil \frac{n}{2}\right\rceil -1,1}$, $\alpha _{0}$, $\alpha _{1}$, and $\alpha _{2}$ terms. Kuang ${et}$ ${al}$. ⁽¹¹⁾ derived the logic equations and digital logic implementations for the $\tau _{\left\lceil \frac{n}{2}\right\rceil -1,1}$, $\alpha _{0}$, $\alpha _{1}$, and $\alpha _{2}$ terms required. These terms are defined such that circuits based on Fig. 1(d) always produce the exact same results as Fig. 1(a).

2. Exact Partial Product Bit Equations

In the following, “logical or" is represented by ${\vee}$, “logical and" is represented by ${\wedge}$, the exclusive-OR operation is denoted by ${\oplus}$, and the exclusive-NOR operation is denoted by ${\odot}$. In a partial product array, for each $k$-th row between 1 to ${\lceil}$$\textit{n}$/2${\rceil}$${-}$1, the $neg_{k}$, $one_{k}$, and $two_{k}$ common intermediate terms are defined as follows ⁽¹¹⁾, ⁽¹⁴⁾.

\begin{align*} \begin{array}{c} neg_{k}=b_{2k+1}\wedge \overline{\left(b_{2k}\wedge b_{2k-1}\right)}\\ \overline{one_{k}}=b_{2k}\odot b_{2k-1}\\ \overline{two_{k}}=\overline{\left(\overline{b_{2k+1}}\wedge b_{2k}\wedge b_{2k-1}\right)\vee \left(b_{2k+1}\wedge \overline{b_{2k}}\wedge \overline{b_{2k-1}}\right)}\\ na_{k,j}=a_{j}\odot b_{2k+1}\\ \overline{\epsilon }=\begin{cases} \\ \end{cases} \begin{array}{cc} a_{1} & \mathrm{if} \left(\overline{a_{0}\wedge b_{n-1}}==0\right)\\ \overline{a_{1}} & \text{otherwise} \end{array}\\ d_{\left\lceil \frac{n}{2}\right\rceil -1}=\left(\overline{\overline{b_{n-1}}\vee a_{0}}\right)\wedge $\overline{\left(b_{n-1}\vee a_{1}\right)\wedge \left(b_{n-2}\vee a_{1}\right)\wedge \left(b_{n-2}\vee b_{n-3}\right)}\end{array} \end{align*}

Using the intermediate terms defined above, the following logic equations can be derived for the exact forms of the partial product bits $p_{k,j}$ (${\blacksquare}$), sign bits $s_{k}$ (▲), and special bits.

\begin{align*} \begin{array}{c} p_{k,j}^{\left(\textit{exact}\right)}=\overline{\left(na_{k,j-1}\vee \overline{two_{k}}\right)\wedge \left(na_{k,j}\vee \overline{one_{k}}\right)}\\ s_{k}^{\left(\textit{exact}\right)}=\overline{\left(na_{k,n-1}\vee \overline{two_{k}}\right)\wedge \left(na_{k,n-1}\vee \overline{one_{k}}\right)}\\ c_{k}^{\left(\textit{exact}\right)}=\overline{\overline{neg_{k}}\vee \left(one_{k}\wedge a_{0}\right)}\\ \tau _{k,0}^{\left(\textit{exact}\right)}=\overline{\overline{one_{k}}\vee \overline{a_{0}}}\\ \tau _{\left\lceil \frac{n}{2}\right\rceil -1,1}^{\left(\textit{exact}\right)}=\overline{\left(\overline{one_{\left\lceil \frac{n}{2}\right\rceil -1}}\vee \overline{\epsilon }\right)\wedge \left(\overline{two_{\left\lceil \frac{n}{2}\right\rceil -1}}\vee \overline{a_{0}}\right)}\\ \alpha _{2}^{\left(\textit{exact}\right)}=\overline{s_{0}\wedge \overline{d_{\left\lceil \frac{n}{2}\right\rceil -1}}}\\ \alpha _{1}^{\left(\textit{exact}\right)}=\overline{\alpha _{2}^{\left(\textit{exact}\right)}}\\ \alpha _{0}^{\left(\textit{exact}\right)}=s_{0}\odot \overline{d_{\left\lceil \frac{n}{2}\right\rceil -1}} \end{array} \end{align*}

3. Approximate Radix-4 Booth Multiplication

An approximate radix-4 Booth multiplier can be designed by using approximate Booth encoding starting from one of the Booth encodings shown in Fig. 1. The method proposed by Liu ${et}$ ${al}$. ⁽²⁾ uses approximate designs for the terms in the Booth encoding shown in Fig. 1(b), while the method proposed in this paper uses approximate designs for the terms in the Booth encoding shown in Fig. 1(d). The determination of which is the best method is ultimately determined by the power, delay, and accuracy characteristics of the resulting circuit.

Another useful technique used for approximate radix-4 Booth multiplication is the use of approximation and accurate regions, with these regions defined by partitioning the columns of the partial product addition array. Thus, the columns of the partial product addition array can be partitioned into two regions starting from the rightmost bits: a truncated region and an exact (circuit) region ⁽³⁾, ⁽⁵⁾ or an approximate region and an exact region ⁽²⁾.

The reason the focus is placed on partitioning based on columns is that the rightmost columns correspond to the least significant bits and the leftmost columns correspond to the most significant bits of the final product. Thus, if a final product bit is incorrect, it will only change the result by a small amount (from the correct result) if the incorrect product bit is one of the rightmost bits in the final product. Higher power savings can be achieved (at the cost of higher error levels) by using more bits in the truncated and approximate regions and by using more aggressive approximation circuits. Thus, in the proposed design, as shown in Fig. 2, the partial product array is partitioned into three parts from the leftmost to the rightmost bits: accurate, approximated, and truncated.

1. Approximated Partial Product Bits

The complete proposed approximate radix-4 Booth multiplier design is shown in Fig. 2. Although an 8-bit multiplier is shown, n-bit multipliers with larger n values will follow the same patterns. This multiplier uses the knowledge accumulated from previous designs in order to arrive at a design suitable for error-resilient applications such as those using DNNs. The \textit{novel} aspect of this approach is the introduction of new approximation circuitry that use \textit{multi-level} logic and \textit{shared intermediate terms} in order to produce designs with better power/accuracy trade-offs than the previous best designs.

The proposed multiplier consists of three stages. In Stage 1, the partial product bits are partitioned into three regions: exact, approximate, and truncated. The \textit{new} approximate logic circuits proposed in this paper are used in the approximate region of Stage 1. The cut-off lines for the exact, approximate, and truncated regions can be adjusted to produce multipliers with varying degrees of accuracy and power usage. In Stage 2, 4-2 compressors ⁽¹⁵⁾ are used in one or more phases to reduce the partial products to two final partial products ⁽²⁾. In Stage 3, a 2-1 compressor, such as a hierarchical carry lookahead adder, is used to produce the final 2$\textit{n}$${-}$bit product ⁽²⁾.

Unlike Liu ${et}$ ${al}$.'s method ⁽²⁾, which bases its approximate circuits on the partial product terms shown in Fig. 1(b), this paper proposes new approximate circuits based on the partial product terms shown in Fig. 1(d), which is the encoding proposed by Kuang ${et}$ ${al}$. ⁽¹¹⁾. Another major difference in the proposed approach is that new approximate circuits are proposed for the $p_{k,j}$ partial product bits (denoted by ${\blacksquare}$ in Fig. 1) and the “special” terms $\tau _{\left\lceil \frac{n}{2}\right\rceil -1,1}$$\textit{,}$ $\alpha _{0}$$\textit{,}$ $\alpha _{1}$$\textit{,}$ and $\alpha _{2}$ in Fig. 1(d). Since these latter special terms all require fairly “heavy” digital logic implementations for exact calculations, using simplified circuits for such special terms has a significant effect on the overall circuit complexity.

In general, a partial product term in the set of partial product rows produced by a radix-4 Booth encoding method is dependent on six variables: $b_{2k+1}$$\textit{,}$ $b_{2k}$$\textit{,}$ $b_{2k-1}$$\textit{,}$ $a_{j}$$\textit{,}$ $a_{j-1}$$\textit{,}$ and $a_{n-1}$.

Since a 2-level AND-OR circuit with six variables can be quite “heavy,” Huang ${et}$ ${al}$. ⁽¹⁴⁾ proposed a sequence of equations that can be used to produce multi-level circuit implementations of the required partial product terms that has the additional advantage of reusing intermediate terms for all elements in a partial product row. This paper proposes new approximate circuits based on modifications of these multi-level circuits with shared intermediate terms.

2. Efficient Approximations for Partial Product Bits Terms

When logic circuits based on the exact equations shown in the previous subsection are used, the resulting circuits are particularly complex (with longer resulting delays and increased power consumption) for the $\tau _{\left\lceil \frac{n}{2}\right\rceil -1,1}^{(\textit{exact})}$$\textit{,}$ $\alpha _{0}^{(\textit{exact})}$$\textit{,}$ $\alpha _{1}^{(\textit{exact})}$ and $\alpha _{2}^{(\textit{exact})}$ terms. Also, the $p_{k,j}^{(\textit{exact})}$ terms constitute the most heavily used terms in the partial product array of Fig. 1(d), upon which the proposed design is based. Thus, efficient approximate circuits are proposed for these five types of partial product terms.

Targeting the $\tau _{\left\lceil \frac{n}{2}\right\rceil -1,1}^{(\textit{exact})}$ term first, the complexity of the logic for this term derives mainly from the use of $\overline{\epsilon }$, which is used for only $\tau _{\left\lceil \frac{n}{2}\right\rceil -1,1}^{(\textit{exact})}$. However, by referring to Table 1 and Fig. 3, it can be seen that $\tau _{\left\lceil \frac{n}{2}\right\rceil -1,1}^{(\textit{exact})}$can be approximated without using $\overline{\epsilon }$ with changes to only 2 (out of 8) truth table entries.

Next, for the $\alpha _{0}, \alpha _{1}, $ and $ \alpha _{2}$ terms, efficient approximations can be derived by using the K-maps shown in Tables 2-4 and Fig. 4. The complexity of these terms derive mainly from the use of $d_{\left\lceil \frac{n}{2}\right\rceil -1}$. By using the K-maps shown, it can be seen that $d_{\left\lceil \frac{n}{2}\right\rceil -1}$can be approximated by the much simpler expression $d^{(\textit{approx})}$ = $\mathrm{a}_{1}\vee \mathrm{a}_{0}\vee \overline{\mathrm{b}_{\mathrm{n}-1}}$.

Finally, the all-important $p_{k,j}^{\left(\textit{exact}\right)}$term can be approximated by using the truth table of Table 5. This table shows various possible ways (with equations shown below) for approximating $p_{k,j}^{\left(\textit{exact}\right)}$ without incurring too much error.

\begin{align*} \begin{array}{rr} p_{k,j}^{\left(1\right)} & =\left(two_{k}\right)\vee \left(one_{k}\wedge \overline{na_{k,j}}\right)\\ p_{k,j}^{\left(2\right)} & =\left(\overline{na_{k,j-1}}\right)\vee \left(one_{k}\wedge \overline{na_{k,j}}\right)\\ p_{k,j}^{\left(3\right)} & =\left(one_{k}\wedge \overline{na_{k,j}}\right)\\ p_{k,j}^{\left(4\right)} & =\left(two_{k}\wedge \overline{na_{k,j-1}}\right)\vee \left(\overline{na_{k,j}}\right)\\ p_{k,j}^{\left(5\right)} & =\left(two_{k}\wedge \overline{na_{k,j-1}}\right)\vee \left(one_{k}\right)\\ p_{k,j}^{\left(6\right)} & =\left(two_{k}\wedge \overline{na_{k,j-1}}\right) \end{array} \end{align*}

Referring to the equations shown above and Table 5, it can be seen that these approximations result in 2 or 4 different entries (out of 8 entries) in this truth table. Of the approximations that result in 2 different entries, $p_{k,j}^{\left(3\right)}$ results in the simplest logic circuit. Thus, the approximate circuit based on $p_{k,j}^{\left(3\right)}$ , shown in Fig. 5, is used.

To summarize, the simplified logic equations for the approximations used in the proposed circuit are as shown below.

\begin{align*} \begin{array}{rr} \tau _{\left\lceil \frac{n}{2}\right\rceil -1,1}^{\left(\textit{approx}\right)} & =\overline{\left(\overline{one_{\left\lceil \frac{n}{2}\right\rceil -1}}\vee \overline{a_{1}}\right)\wedge \left(\overline{two_{\left\lceil \frac{n}{2}\right\rceil -1}}\vee \overline{a_{0}}\right)}\\ d^{\left(\textit{approx}\right)} & =a_{1}\vee a_{0}\vee \overline{b_{n-1}}\\ \alpha _{2}^{\left(\textit{approx}\right)} & =\overline{s_{0}\wedge d^{\left(\textit{approx}\right)}}\\ \alpha _{1}^{\left(\textit{approx}\right)} & =s_{0}\wedge d^{\left(\textit{approx}\right)}\\ \alpha _{0}^{\left(\textit{approx}\right)} & =s_{0}\odot d^{\left(\textit{approx}\right)}\\ p_{k,j}^{\left(\textit{approx}\right)} & =\overline{na_{k,j}\vee \overline{one_{k}}}\\ s_{k}^{\left(\textit{approx}\right)} & =p_{k,n-1}^{\left(\textit{approx}\right)} \end{array} \end{align*}

The proposed multiplier design was compared to the most recent comparable approximate radix-4 Booth approximate multiplier designs: the two designs proposed by Liu ${et}$ ${al}$. ⁽²⁾ and the high-radix approximate design proposed by Leon ${et}$ ${al}$. ⁽⁷⁾. The reason that only these previous designs were compared to the proposed design is because Leon ${et}$ ${al}$. ⁽⁷⁾ and Liu ${et}$ ${al}$. ⁽²⁾ have already shown that their designs were better than all previously proposed approximate radix-4 Booth multiplier designs.

The four approximate radix-4 Booth multiplier designs compared are labeled R4ABM1, R4ABM2, RAD, and R4IABM (proposed). The two designs proposed by Liu ${et}$ ${al}$., R4ABM1 and R4ABM2, offer a trade-off between power and accuracy. To implement a single partial product bit $p_{k,j}$, R4ABM2 uses one exclusive-OR gate while R4ABM1 uses the AND of the output of two exclusive-OR gates. Thus, R4ABM2 offers lower power usage at the expense of a decrease in output accuracy as opposed to R4ABM1. The design proposed by Leon ${et}$ ${al}$. , RAD, uses approximate radix-$2^{l}$ encoding for the least significant $l$ bits and exact radix-4 encoding for the most significant $\textit{n}$ ${-}$$l$ bits of the multiplier. Finally, the R4IABM (proposed) design incorporates all of the approximate partial bit designs proposed in this paper.

1. Evaluation Metrics

The metrics used to evaluate the multiplier designs under comparison are the power required, the worst-case multiplication delay, circuit area and the degree of error introduced by the approximation circuits used. In order to estimate power and delay, the designs being compared have all been implemented at the logic gate level using Verilog HDL, and synthesized with Synopsys Design Compiler using a CMOS 65nm cell library, 1.25V supply voltage, and room temperature operating conditions. All possible input parameter combinations were evaluated.

Traditionally, the quality of a digital circuit design targeted for ASIC implementation is evaluated by measuring the chip area, power, and critical path delay. An overall evaluation design quality measure that is typically used is the ${power}$ ${delay}$ ${product}$ ${(PDP)}$, which is the product of the power required with the critical path delay.

\begin{equation*} PDP=\textit{Power}\times \textit{Delay} \end{equation*}

For an approximate digital logic circuit design, the accuracy of the output produced by the approximate circuit, when compared to the output of an exact circuit, is clearly of importance. For an approximate multiplier, accuracy can be measured with respect to the ${error}$ ${rate}$ ${(ER)}$, the ${normalized}$ ${mean}$ ${error}$ ${distance}$ ${(NMED)}$, and the ${mean}$ ${relative}$ ${error}$ ${distance}$ ${(MRED)}$. ER is the ratio of possible input vectors that result in incorrect outputs. NMED is the mean absolute difference between correct and approximate results (error distance) normalized by the maximum output of the exact design. MRED is the average of the error distances divided by the absolute exact output values.

2. Evaluation Results

The accuracy and resource usage data for 8/16-bit multipliers designed using ⁽²⁾, ⁽⁷⁾ and the proposed method have been evaluated in Figs.~6 and 7 and Tables 6 and 7. These results are shown with various values for the approximation factor $\textit{p}$ and $l$ for the previous designs and the region separation factors $q_{1}$ and $q_{2}$ (note that $p=q_{1}$) for the proposed designs. Since there are 153 (561) possible combinations of $q_{1}$ and $q_{2}$ values for 8-bit (16-bit) multipliers, only a representative subset of these combinations are shown in the figures and tables. However, in our experiments, all 153 (561) multipliers have been implemented at the logic gate level and synthesized one by one.

3. Comparison Summaries

From the figures shown, several observations can be made regarding the various approximate multipliers that have been compared. Except for a very few versions of the R4IABM (proposed) designs, ${all}$ of the approximate radix-4 Booth multipliers have extremely high error rates ER, ranging from about 40% to almost 100%. However, by referring to the NMED plots, it can be seen that the average error ${distance}$ (difference from the correct products) is fairly small (NMED values of less than about 0.1) for most of the designs shown. This shows that approximate radix-4 Booth multipliers tend to produce a high ratio of incorrect product results, but the ${magnitude}$ of those errors can be quite small on average.

Overall, the proposed approximate radix-4 Booth multiplier design shows clear improvements over other recently proposed alternative designs. For a fixed level of accuracy (modeled by NMED), the power and delay characteristics (modeled by PDP) show improvements of up to 30.3% (96.4%) over the previous 8-bit (16-bit) designs proposed by Liu et al. and up to 13.4% (88.9%) over Leon et al.’s 8-bit (16-bit) designs. These design points are on the dashed lines shown in Figs.~6(b) and ~7(b).

Tables 6 and 7 show that, given the same number of columns for the exact and approximate regions, R4IABM occupies a smaller area than the previous methods in almost all cases. The R4IABM methods result in lower area than the previous R4ABM methods in all cases. There are a few cases when the ${RAD}$ $2^{\kappa }$ methods result in lower area than the R4IABM methods. According to ⁽⁷⁾, ${RAD}$ $2^{\kappa }$ ${reduces}$ $\frac{\kappa }{2}-1$ partial product rows. The ${RAD}$ $2^{\kappa }$ methods reduce rows while the proposed R4IABM method reduces columns. Thus, although the area requirements of the two types of methods are not directly comparable, it can nevertheless be seen that the ${RAD}$ $2^{\kappa }$ methods can sometimes produce lower area overhead designs than R4IABM. However, the R4IABM still has an advantage over the ${RAD}$ $2^{\kappa }$ methods in terms of power, delay, and accuracy as shown in Figs. 6 and 7.

4. An Image Multiplication Example

Given the levels of ER, NMED, and MRED achieved by the proposed method, it is reasonable to question whether approximate multiplier designs based on the proposed method ${can}$ be used in actual applications ⁽¹⁶⁾. In order to answer this question, the authors have implemented the proposed method in software and used it to test an example image processing application.

In the target image processing application, the two images shown in Figs. 8(a) and (b) were multiplied together in a pixel by pixel manner to produce a combined image. The result figures and ${Peak}$ ${Signal-to-Noise}$ ${Ratio}$ ${(PSNR)}$ are shown in Figs.~8(c) and (d) for approximate radix-4 multiplication (only two $q_{1}$ and $q_{2}$ combinations are shown here for brevity). Upon close inspection, it was observed that for combinations less than about ($q_{1}=12$, $q_{2}=6$), there was hardly any distortion, while slight distortions were detectable for larger $q_{1}$ and $q_{2}$ values, as evidenced by the multiplication result with ($q_{1}=16$, $q_{2}=8$), which resulted in PSNR = 39.5~dB. These results validate the practicality of the proposed approach.