Hardware-Efficient Approximate Dividers for Image Processing in WSN Edge Devices ()
1. Introduction
Data collected using a Wireless Sensor Network (WSN) needs to be collected and processed before it can be utilized effectively. For efficient utilization of large WSNs, a lot of this processing can be done in edge devices, before they are sent to a central server for further processing. This paper considers the use of large WSNs for intelligent tasks involving image processing, wherein the image processing tasks involve various types of computer arithmetic operations including division.
In general applications, a division is less heavily utilized than addition or multiplication. However, division circuits tend to have an unusually long latency compared to other arithmetic circuits, so when they are used, the division operation has an inordinate effect on the overall processing delay. In addition, the division requires a large silicon area and a lot of power due to the highly iterative nature of its typical computation method.
The division is primarily used in scientific applications, image processing, and deep learning training and inference. However, highly accurate calculations are typically not required due to the error tolerance of applications such as image processing and recognition [1]. As a result, the promising paradigm of approximate or inaccurate computing has been investigated with great interest. Approximate circuits are typically designed using highly efficient hardware while providing an acceptable level of accuracy [2].
Since division is an infrequently used operation, it is typically implemented using minimal digital logic hardware. Division can be implemented as a sequential or combinational logic circuit. Since pixels in images are typically 8-bit values, a divider in image processing applications does not need to be too large, and thus is typically implemented in a straightforward manner using subtractor cells arranged in a regular 2-dimensional (2-D) array structure, referred to as a restoring divider array, shown in Figure 1. The main drawback of this design is the
![]()
Figure 1. An 8/4 unsigned restoring array divider.
excessively long propagation delay, which is due to the need to traverse almost all of the subtractor cells in the 2-D array, as shown using a red line in Figure 4(a). The need for this long propagation delay is primarily due to the fact that division requires the computation of quotient bits one at a time, followed by conditional subtraction of the divisor.
This paper proposes a new approximate divider design approach based on breaking the “borrow-chain” in the 2-D subtractor array used in a restoring division method. This paper analyzes the horizontal and vertical outputs of subtractor cells, which are the borrow out and difference outputs, respectively, and proposes a divider circuit based on a 2-D subtractor array that uses two novel approximate subtractor cells designs. The quotient bits of a division operation cannot be processed in parallel, unlike the partial product bits of a multiplication operation. So, when the subtractor cell of a division circuit is approximated, it is necessary to consider how such a change will affect the overall quotient. In this paper, two novel approximate subtractor cell designs are proposed, with the aim of breaking the long propagation chain used in division. The characteristics of divider designs based on the proposed approximate subtractor cells are analyzed for various bit lengths, replacement methods, and approximation depths. Since the presented cells are applied to an array-based divider, they can be combined into various arrays and designed to suit the application. The evaluations presented in this paper can be used as a reference for designing for specific criteria.
The rest of the paper is organized as follows. Section 2 introduces the exact design of the typical array divider circuit and reviews the existing approximate divider designs. The two proposed subtractor cells and divider designs using these cells are introduced in Section 3. Section 4 presents a complete analysis based on accuracy, power, latency, and area overhead. Section 5 demonstrates that the proposed designs provide sufficient accuracy by the implementation of two practical applications. Section 6 provides concluding remarks.
2. Background and Related Work
The division A ÷ B of a dividend A and a divisor B is defined as A = B * Q + R, where Q is the quotient and R is the remainder. Multiplication of two n-bit values results in a 2n-bit product. Analogously, a 2n-bit dividend is divided by an n-bit divisor to produce an n-bit quotient and n-bit remainder. In the case of an unsigned restoring divider, the basic subtractor cell shown in Figure 2, consisting of a full subtractor and a multiplexer to select between the current subtraction result and the previous partial result, can be used [3].
In computer arithmetic, the basic algorithm used for division has an inherent delay propagation problem due to the nature of the division problem. Consider the division of two numbers in unsigned binary, such as 00101110 (dividend bits a7a6a5a4a3a2a1a0) divided by 1011 (divider bits b3b2b1b0). The quotient bits are determined one at a time, starting from the most significant bit position, by subtracting the divider—if the result is negative, the quotient bit is 0; otherwise, it is
1. In the next step, if the quotient bit was a 1, then the divider is subtracted from the previous subtraction result. However, if the quotient bit was a 0, then the divider is subtracted from the result before the previous subtraction. Referring to Figure 1 and using the example shown above, in Step 1 (Row 1 of Figure 1), 00101 – 1011 produces 11,000, which is a negative number. Thus, the quotient bit q3 is 0. Then, in Step 2 (Row 2), 01011 (bits a6a5a4a3a2) – 1011 = 00000, which is non-negative. Thus, q2 is 1. Then, in Step 3 (Row 3), the previous subtraction result with the “next” a1 bit appended 00001 – 1011 = 10100, a negative number. Thus, q1 is 0. Then, in Step 4 (Row 4), the previous subtraction result with the “next” a0 bit appended 00011 – 1011 = 00010, which is non-negative. Thus, q0 is 0. The final result is the quotient q3q2q1q0 = 0100 with remainder 0010 (last subtraction result). The “borrow” propagation problem illustrated in this example stems from the fact that when going from Row i to Row i+1, the choice of the number to use to subtract the divisor 0010 depends on the previous subtraction result.
Previous works on approximate divider circuits have focused on different aspects of problems with the basic divider circuit [4] - [11]. Chen et al. approximated a fixed error with inexact subtractor cells [4] [5]. Each cell was approximated in units of transistors, and because only a small portion was approximated, a small error occurred, but the hardware gain was also small. Jiang et al. proposed a method of truncating operands based on leading zeros so that only the most relevant bits are used for calculation [6] [7]. The truncated dividend and divisor are calculated by a narrow width divider, and the error is fixedly determined by this width. Behroozi et al. [8], Melchert et al. [9], and Jeong et al. [10] also used truncated operands, but the accuracy was dynamically scaled during runtime as a multiplicative divider [8] [9] [10]. As the Taylor series approximation method was used, the accuracy could be increased with the number of iterations used. Adams et al. proposed two approximation methods, one involving an approximate subtractor cell that breaks the “borrow chain” and approximates the difference output and the second involving the use of truncation to compute the least significant quotient bits in an approximate manner [11].
3. Proposed Approximate Divider
3.1. Approximate Subtractor Cells
In this paper, two types of approximate subtractor cells, ABSC (approximated borrow subtractor cell) and ADSC (approximated difference subtractor cell) are proposed. The logic diagrams for these two designs are shown in Figure 3, while the truth tables are shown in Table 1. The colored entries in Table 1 show where the accurate output bits and approximate output bits differ for the two designs. ABSC results in approximate borrow and accurate difference outputs, while ADSC results in accurate borrow and approximate difference outputs. In ABSC and ADSC, the number of incorrect output bits is four of the sixteen output entries for the borrow output and difference output, respectively.
![]()
Table 1. Truth table for the two approximate subtractor cell designs.
![]()
Figure 3. The two proposed approximate subtractor designs: (a) ABSC and (b) ADSC.
The ABSC subtractor cell is designed with the purpose of approximating the borrow while maintaining the difference output. This has the effect of breaking the horizontal right-to-left propagation chain. The logic design for this cell is shown in Figure 3(a) and its effect on the propagation delay of an array divider is shown in Figure 4(b). As can be seen, once the first ABSC subtractor cell is encountered, the horizontal right-to-left borrow chain is no longer part of the critical delay path. This should have the effect of breaking the borrow chain while maintaining, to a certain extent, the accuracy of the different outputs in the vertical direction.
![]()
Figure 4. The 2-D restoring divider array with subtractor cells that are (a) fully accurate, (b) ABSC cells, and (c) ADSC cells.
Conversely, the ADSC subtractor cell is designed with the purpose of approximating the difference output while maintaining the borrow output. This has the effect of breaking the vertical downward-direction propagation chain. The logic design for this cell is shown in Figure 3(b) and its effect on the propagation delay of an array divider is shown in Figure 4(c). As can be seen, once the first ADSC subtractor cell is encountered, the vertical downward-direction chain is no longer part of the critical delay path. This should have the effect of approximating the difference output while maintaining, to a certain extent, the accuracy of the borrow chain that leads to the quotient bit outputs.
3.2. Cell Replacement
The approximate divider can be implemented by replacing each cell with one of the approximate subtractor cells proposed in Section III.1, and the number of replaced cells can be expressed as the depth. However, since the cell replacement has different effects depending on the characteristics of the cell used and the location where it is replaced, three cell replacement methods, which reflect the most logical progression of cell replacements, have been utilized as in [4] [5]. The three types of replacement methods used are referred to as horizontal, vertical, and stepwise replacement methods.
· Horizontal Replacement (HR): In this replacement method, cells closer to the LSB (Least Significant Bit) of the Quotient are replaced first. Starting with the lowermost row (the LSB quotient bit), cells are replaced from the right to the left (LSB to more significant bit positions of the difference result in each row). Once the lowermost bit positions have all been replaced, the procedure repeats with the next row above (the next most significant quotient bit). This replacement method is depicted in Figure 5(a). Note that, with this method, accurate quotient bit calculation is possible, using the restoring division procedure, until the first approximate cell is encountered.
· Vertical Replacement (VR): This is a method in which the cells of the array divider are replaced in a vertical manner from right to left. This has the effect of approximating the rightmost part (least significant bit portion) of the 2-D subtractor array. Thus, if the cell at position (i, j) cell is replaced, the cell at position (i+1, j) is replaced next. Then, after the jth row cell of the MSB column is replaced, the cell at position (0, j+1) will be replaced next. This replacement method is shown in Figure 5(b).
· Stepwise Replacement (SR): This replacement method is a combination of HR and VR. When (i, j) is replaced, the next cell to be replaced is (i+1, j−1), which is the directly connected upper column cell. Then, if the replaced (i, j) cell uses the dividend bit as its input instead of the difference bit from its cell, the next replacement occurs at position (0, j+1). This method is illustrated in Figure 5(c).
4. Results
To evaluate the accuracy and circuit characteristics of dividers designed using
![]()
(a)![]()
(b)![]()
(c)
Figure 5. Cell replacement example for depth = 2, 4, 6, and 8 using the (a) horizontal (HR), (b) vertical (VR), and (c) stepwise replacement (SR) method.
the proposed approximate divider circuits, a sequence of successively more approximate dividers using the designs have been implemented in C and VHDL. Successive 2n/n divider designs were implemented with 2n = 4, 8, 12, 16 for each combination of approximate cells and replacement methods. Comparisons were made with an exact divider design and several of the state-of-the-art (SOTA) approximate array divider designs.
4.1. Accuracy Comparison with Accurate Design
Accuracy can be measured using one of several measures that indicate how close the approximate division results are to accurate division results. However, in order to facilitate comparisons with previous SOTA methods, the most common accuracy metrics used in those methods are also used here. The error distance is the absolute difference between the integer values of the outputs that produced by an accurate design and an approximate design. Then, the Mean Relative Error Distance (MRED) is the mean of the error distance values divided by their respective accurate values. Alternatively, the Normalized Error Distance (NED) is the mean of the error distance values divided by the maximum possible error (typically 2n for a 2n/n divider) [12]. The Root Mean Squared Error (RMSE) is the square root of the mean squared error between approximate and exact values.
![]()
Figure 6. Normalized Error Distance (NED) of the proposed approximate divider circuits.
The results for accuracy levels are illustrated in Figure 6 & Figure 7, and the representative 4/2 and 16/8 dividers are shown in Table 2. Factor rapprx shows the approximation rate, where rapprx = depth/number of cells in the divider. With a small bit width, such as 2n = 4, ADSC circuits resulted in lower NEDs than ABSCs. However, for large bit widths 2n = 16, the two lowest NEDs were achieved by ABSC with HR and SR. In general, the NED levels are lowest when using the SR replacement method and highest when using the VR replacement method. The ABSC divider resulted in low MRED values. As in NED, the lowest MRED was observed in ABSC with SR for large bit widths 2n = 16. When nearly 90% of the cells were replaced, the ADSC circuit showed a lower MRED than the ABSC circuit. In terms of MRED, SR is still the best replacement method, but the rest of the methods were affected by the characteristics of the approximate cell used.
4.2. Circuit Characteristic Comparisons with Accurate Design
To measure the circuit characteristics of the proposed designs, silicon area, power dissipation, and propagation delay were used as the primary metrics. In addition,
![]()
Figure 7. Mean Relative Error Distance (MRED) of the proposed approximate divider circuits.
combinations of these metrics were computed to assess the combined effects of the primary metrics. The divider circuits were implemented in Verilog and synthesized in a Samsung 28 nm CMOS cell library. Synopsys Design Compiler was used for synthesis. The supply voltage was 1.1 V, the temperature was 25˚C, and the clock frequency was 200 MHz.
4.2.1. Effect of Subtractor Cell Approximation Method
The overall effect and difference, between the ABSC and ADSC subtractor cell approximation methods were evaluated by examining the results for the extreme case of a 2n = 16 divider with a depth of 64, which corresponds to using all approximate subtractor cell designs. The results are shown in part (g) of Figures 8-10. Although the circuit characteristics were slightly affected by the replacement method used, the results tended to depend on the characteristics of the approximate cell. Although several gates were omitted in ABSC, the approximation and circuit overhead reduction effects of omitting the 2-to-1 multiplexer in ADSC were greater. For this extreme case, the ABSC divider resulted in 98.1% of the area, 70.5% of the power, and 32.0% of the delay when compared to the
![]()
Table 2. Accuracy values of quotient for proposed approximate 4/2 and 16/8 dividers.
accurate divider. The ADSC divider resulted in 41.0% of the area, 20.9% of the power, and 10.1% of the delay when compared to the accurate divider. The accuracy, as reflected by the RMSE, of the ABSC and ADSC dividers were 80.72 and 45.89, respectively.
4.2.2. Effect of Subtractor Cell Replacement Method
Next, to examine the effect of the subtractor cell replacement used with the ABSC and ADSC subtractor cells, the circuit metrics were evaluated for all combinations of bit widths, replacement methods, and depths. As stated in the above subsection, ADSC has a greater circuit overhead reduction effect than ABSC. Accordingly, in Figure 8 & Figure 9, it can be seen that ADSC with HR and SR have the best area and power characteristics for small bit widths while ADSC with HR, VR, and SR perform similarly, in terms of area and power, for the largest bit widths. Figure 10 shows the ADSC method with all 3 replacement methods showing similar levels of delay reduction.
![]()
Figure 8. Area of the approximate divider circuits.
4.2.3. Combined Metric Results for Comparison with Accurate Design
In order to evaluate the combined effects of the primary metrics, the Power Delay Product (PDP) is evaluated for the various designs considered. Figure 11 shows the results.
With respect to the power and propagation delay effects, the PDP results of Figure 11 show that ADSC is superior to ABSC. This is in line with the delay and power measurements of Figure 9 & Figure 10. Circuit delay and overhead values for the representative 4/2 and 16/8 dividers are shown in Table 3.
4.2.4. Comparisons with Previous State-of-the-Art Designs
Comparisons were also made with previous state-of-the-art (SOTA) designs. Although the work by Jeong et al. [10] is the most recent SOTA design, it was an iterative array divider design and thus could not be directly compared with the proposed designs. Thus, the most recent, comparable designs were the AXRD-M1 design proposed by Adams et al. [11], and the AXDr1-3 designs proposed by Chen et al. [5].
Table 4 & Table 5 show a detailed comparison of the proposed ABSC-SR and
![]()
Figure 9. Power of the approximate divider circuits.
ADSC-SR designs with the AXDR-M1 and AXDr1-3 designs. The approximation factor, denoted by p, indicates the number of columns of subtractor cells that use approximate subtractor cells. The p value is shown in red in Table 4 & Table 5.
In Table 4, the accuracies of all methods compared are measured in terms of ER, MRED, NED, and RMSE. The best accuracy results, for each p value, are marked in red. Although the proposed ABSC and ADSC methods do not have the best accuracy results, their values can be seen to be fairly close to the best, with ABSC slightly outperforming ADSC in all cases. The results of all methods showed similar trends for each of the ER, MRED, NED, and RMSE metrics.
Table 5 compares the circuit characteristics for all methods. As can be seen, and marked in red, the proposed ADSC method has the best delay, area, and power characteristics. It thus follows that it also has the best PDP characteristics.
5. Verification Using Practical Applications
The proposed dividers were tested with two kinds of pixel division applications,
![]()
Figure 10. Delay of the approximate divider circuits.
change detection and foreground extraction.
5.1. Change Detection
Consider two almost identical images in which a few objects have been moved or have slightly different shading or color characteristics. Such differences can be caught by an image processing operation referred to as change detection, which can be implemented by simply dividing the pixel values in the first image by the pixel values in the second image. This is demonstrated using two 8-bit grayscale images as illustrated in Figure 12.
The level of inaccuracy that results from using approximate division is quantified using two metrics, peak signal to noise ratio (PSNR) and structural similarity index measure (SSIM), which are the two most commonly used image quality comparison metrics [13]. PSNR is used to evaluate the effect of noise on the image and calculated by a log of the ratio between the possible maximum pixel value and the root mean squared error distance. SSIM is developed to consider the quality perception of the human visual system. When comparing exact and approximate
![]()
Figure 11. PDP of the approximate divider circuits.
![]()
Figure 12. Change detection results for (a) the original input image and (b) the original image with two minor changes (the disk is rotated and one screw has different shading from the first image) using an (c) accurate divider, (d) ABSC with SR and p = 4, and (e) ADSC with SR and p = 4.
output images, two metrices are an approximation to human perception of reconstruction quality. The PSNR and SSIM for all designs are summarized in Table 6. The best results for all p values are shown in red. The best PSNR and SSIM design for p = 6 is the proposed ABSC method. Although the best PSNR and SSIM design are AXDr3 for both p = 4 and 8, Figure 12(d) & Figure 12(e) are visually similar to Figure 12(c), the accurate result.
![]()
Table 3. Delay, area, power, and combined metrics for proposed approximate 4/2 and 16/8 dividers.
![]()
Table 4. Accuracy comparisons for the quotients of the proposed approximate 16/8 dividers with previous state-of-the-art methods.
![]()
Table 5. Delay, area, power, and PDP comparisons of the proposed approximate 16/8 dividers with previous state-of-the-art approximate dividers.
![]()
Table 6. PSNR and SSIM of 16/8 bits approximate dividers for change detection and foreground extraction.
![]()
Figure 13. Foreground extraction results using (a) the original blurry input image and (b) the background noise image are shown using an (c) accurate divider, (d) ABSC with SR and p = 4, and (e) ADSC with SR and p = 4.
5.2. Foreground Extraction
A useful method for clearly viewing an image blurred by background noise or poor lighting conditions is to simply extract the foreground part of the image. This is referred to as foreground extraction and can be implemented by simply dividing the pixels of the original noisy image by a second image composed of only the background noise. This is demonstrated using two 8-bit grayscale images as illustrated in Figure 13.
The PSNR and SSIM of the foreground application for all designs are summarized in Table 6 along with the change detection results. The best PSNR and SSIM design for p = 6 and p = 8 is the proposed ABSC method. Although the best PSNR and SSIM design are AXDr3 for p = 4, the values for ABSC-SR is the second-best design with slightly reduced PSNR and SSIM values. In addition, it can be seen that Figure 13(d) and Figure 13(e), produced using the proposed methods, are visually similar to Figure 13(c).
6. Conclusion
This paper has proposed approximate 2-D unsigned restoring divider designs, named ABSC and ADSC, based on two types of novel approximate subtractor cell designs. These approximate subtractor cells were designed to break the “borrow chain” that resulted in excessive delays and power dissipation in a traditional accurate 2-D restoring divider design. Since the proposed designs are cells, they can be applied to research on other circuits, such as square root, where the same cell can be used, and there is a possibility that they can be applied to sequential design for much longer bit operations. It can also be extended to an application-specific design by applying analysis to the data or algorithm used. If biased data are used, there will be an efficient cell arrangement accordingly, which is worth studying. Comprehensive comparisons were made with an accurate design as well as previous state-of-the-art designs. The results show that the largest ADSC 16/8 approximate divider has a Mean Relative Error Distance (MRED) of 6.30 × 10−4 to 1.91 × 10−2, Normalized Error Distance (NED) of 2.60 × 10−4 to 1.15 × 10−2, and Root Mean Squared Error (RMSE) of 0.185 to 2.441 with 67.2% of the area, 55.5% of the power usage, and 56.2% of the propagation delay when compared to a completely accurate design. In general, the ABSC design had slightly better accuracy than the ADSC design. When compared to previous state-of-the-art designs, the proposed ADSC design had the best hardware characteristics, in terms of delay, area, and power usage.