1. Basic Structures

One of the advantages of SC is that it can be implemented as a simple circuit for complex operations. However, the need for a large number of SNGs, which occupies a large area in SC, is in violation of SC's orientation in terms of power and area. For instance, image processor based on SC requires many SNGs, which constitutes more than 80% of the total circuit for image frames ⁽¹⁴⁾. In addition, when generating bitstreams, sharing the LFSR or attaching the inverter of the output of the LFSR cannot provide accurate results compared with using various LFSRs ⁽¹⁵⁾. Fig. 2 shows various SNG schemes: (a) dedicated LFSRs are used for each input ⁽⁸⁾, (b) one LFSR is shared ⁽¹²⁾, (c) an inverter is used with one LFSR when converting operands with stochastic numbers ⁽¹⁴⁾ and (d) one LFSR is shared with a fully-connected cube network, which is our proposed scheme. Therefore, reducing the area of the SNG that generates the correct bitstream is important in SC.

Fig. 3. Various network architecture (a) partial mesh, (b) fully connected mesh, (c) cube network, (d) fully connected cube network (the proposed method).

Sharing LFSRs with other comparators has been considered to reduce the hardware overhead of SNGs ⁽¹⁶⁾. This allows K SNGs to share only one LFSR and reduce the area to 1/k. In addition, sharing an LFSR with an inverter has been proposed. However, the value of SCC was either the maximum or converged to the minimum, respectively.

We propose generating enhanced bitstreams and reducing hardware size, by changing the output of the LFSR based on the fully connected cube network with a mesh architecture. The mesh architecture, which is a kind of network typology, is typically used in public data communication networks ⁽¹⁹⁾. This is distinguished by a partial mesh with only some nodes connected, as shown in Fig. 3(a) and a fully connected network with all nodes connected, as shown in Fig. 3(b).

The existing n-cube network, also called hypercube, is an interconnect function with $n = log_2N$. n is called the dimension of the n-cube network and N means the total number of nodes ^(20,21). When the node addresses are considered as the corners of an n-dimension cube, the network connects each node to its n neighbors. In an n cube, individual nodes are uniquely identified by n-bit addresses ranging from 0 to N-1. Given a node with binary address b, this node is connected to all nodes whose binary addresses differ from b by exactly one bit and it is defined as follows:

$C_{i}\left(b_{n-1} b_{n-2} \cdots b_{i} \cdots b_{1} b_{0}\right)=b_{n-1} b_{n-2} \cdots b_{i}^{\prime} \cdots b_{1} b_{0}$ $\left(n=\log _{2} N, 0 \leq i<n\right)$

For instance, in a 3-cube network, in which eight nodes exist, node 000$_2$ (0) is connected to nodes 001$_2$ (1), 010$_2$ (2), and 100$_2$ (4), as shown in Fig. 3(c).

Assume that the node of the n-cube network is a fully connected mesh with each neighbor. Given a node with a binary address b, this node is connected to all nodes except itself; therefore, the ith mesh (Mi) is defined as follows:

$M_{i}\left(b_{n-1} b_{n-2} \cdots b_{i} b_{i-1} \cdots b_{1} b_{0}\right)$$=M_{j}\left(b_{n-1} b_{n-2} \cdots b_{j}^{\prime} b_{j-1}^{\prime} \cdots b_{1} b_{0}\right)\left\{\begin{array}{c}i f\left(k_{m}=1\right), b_{j}=b_{i}^{\prime} \\ e l s e b_{j}=b_{i}\end{array}\right.$ $\left(n=\log _{2} N, 1 \leq i, j<N, i_{10}=\sum_{m=0}^{n-1} k_{m} \times 2^{m}\right)$

For example, in a 3-cube network with eight nodes, node $000_2$ (0) is connected to nodes between $001_2$ (1) and $111_2$ (7), as shown in Fig. 3(d). Assume that b is the output number from the LFSR and uses a modified random number for stochastic number generation. For instance, we can use each of the different eight outputs for stochastic number generation when one LFSR with an 8-bit output exists by selecting one according to Mi formula. This is shown in Table 1. The diagram of this design is shown in Fig. 2(d). In this design, the output of the LFSR is exchanged by a fully connected cube network and it is connected to the comparator, while the output of the LFSR is fed to another comparator with no exchange. Compared to sharing an LFSR, this technique does not require any hardware overhead because it just inverts the output bit address from a random number generator by selecting one according to M formula.

2. Simulation Results

We synthesized the system using Quartus ⁽²²⁾ and Verilog HDL to compare the error characteristics of the adder and multiplier through various SNGs. To verify operation errors, 100,000 randomly generated 8-bit numbers were used. The average SCC was calculated by . The error distance (ED) is $S C C_{\text {arg}}=\frac{\sum_{i=0}^{N} S C C\left(X_{i}, Y_{i}\right)}{N}$ defined as ED = |ACC-APP|, where ACC is the result by the obtained accurate operator, and APP is the result of the stochastic operator; the relative error (RE) is calculated by $R E=\frac{E D}{A C C}$ . The RE histogram of each adder is shown in Fig. 4(a), and the results of the multipliers are presented in Fig. 4(b). Compared with the conventional method, the average SCC, maximum ED, average absolute RE, and standard deviation (SD) were enhanced by the proposed design, as shown in Table 2 and Fig. 4. The average SCC for the inverting method is close to -1, which implies a highly negative correlation. Furthermore, the average SCC for the sharing is 1, which indicates a highly positive correlation. However, the average SCC for the dedicated method and the average of the proposed method is half the SCC in the sharing method. It is noteworthy that the proposed method does not require any overhead compared with the dedicated method. In the SC adder, the proposed structure ($M_{2}$) exhibits a reduced average ED (AVG_ED) by 29%, maximum ED (MAX_ED) by 37%, average absolute RE (AVG_ABS_RE) by 25%, and SD by 15% compared with the inverter method. Furthermore, the multiplier based on the proposed structure ($M_{2}$) has an improved RE AVG by 3× and SD by 20% compared with the sharing method.

Fig. 4. Comparison of various absolute relative error distributions (a) stochastic adder, (b) stochastic multiplier generated with various stochastic numbers, as shown in Fig. 2.

For a comparison with an application specific integrated circuit (ASIC), the area and power of the stochastic multiplier and accurate multipliers (i.e., binary, Wallace tree, and behavior multipliers) were analyzed using the 45-nm Nangate library in Design Compiler ^(23,24). The results are summarized in Table 3. As shown, the proposed design requires a smaller area and lower power than the accurate multiplier. For example, only 1/11 of power is required by the proposed design compared with the Wallace tree multiplier. In addition, the proposed design enables an approximately 25% reduction in the total area compared to the behavior multiplier

1. Basic Structures

We applied this technique to edge detection to clarify the effect. Edge detection algorithms such as Sobel can generate acceptable results in addition to offering relative simplicity and error tolerance; hence, they have been widely used in image processing. In general, the basic edge detection algorithm uses the horizontal and vertical gradients of an image to calculate based on the first- or second-order derivative of the digital level image. The gradient of an image, ∇f(x, y), in point (x, y) is defined as follows:

$\nabla f(x, y)=[\partial f / \partial x, \partial f / \partial y]=[G x, G y]$

The magnitude of this vector, which is described by ∇$f$, can reduce the noise effect owing to the smoothing operation by averaging the image gradient values, and the following methods are typically used for absolute value approximation:

$\operatorname{mag}(\nabla f)=\sqrt{G_{x}^{2}+G_{y}^{2}}=|G x|+|G y|$

The Sobel edge detection algorithm obtains an image gradient by calculating the partial derivatives x and y per pixel position that can be obtained from different masks, which are the horizontal mask ($Gx$) and vertical mask ($Gy$), around the pixel ⁽²⁵⁾. In the Sobel algorithm, given a picture, for each pixel (i, j), the value ∇f is calculated from the brightness of the pixels, including (i-1, j-1), (i-1, j), (i-1, j+1), (i-1, j), (i+1, j), (i+1, j-1), (i+1, j), and (i+1, j+1):

$G_{x}=\left(\mid\left(x_{i+1, j-1}+2 x_{i+1, j}+x_{i+1, j+1}\right)+\left(x_{i-1, j-1}+2 x_{i-1 j}+x_{i-1, j+1}\right)\right) \mid$ $G_{y}=\left(\left|\left(y_{i-1, j-1}+2 y_{i-1, j}+y_{i+1, j-1}\right)+\left(y_{i-1, j+1}+2 y_{i, j+1}+y_{i+1 j+1}\right)\right|\right)$

where $x_{i,j}$ and $y_{i,j}$ denote the brightness of pixel (i, j). When mag(∇$f$) is large, pixel (i, j) can detect an edge.

1. Basic Structures

The image quality and design specifications were analyzed and compared between an accurate Sobel edge detection method (i.e., accurate adder, subtractor, multipliers, and absolute unit) and the stochastic edge detection method using various SNGs. Because the Sobel edge detection requires 16 SNs, we used 16 LFSRs in the dedicated method and only one LFSR in the other methods (i.e., sharing, inverter, and the proposed method) ⁽¹⁵⁾. In Fig. 5, the accurate Sobel edge detection circuit is shown in (a) and the stochastic computing edge detection circuit in (b) ⁽¹⁵⁾.

Fig. 5. Sobel edge detection circuit (a) accurate operators, (b) stochastic operators ⁽¹⁵⁾.

The Sobel edge detection was designed with Verilog HDL and analyzed using an FPGA device, DE1-SoC board, and Cyclone V (5CSEMA4F31C6) from Terasic ⁽²⁶⁾. In addition, the designs were synthesized using a 45-nm Nangate open-cell library in Design Compiler for hardware metrics comparison in ASIC. Fig. 6 shows the original image of 512×512 pixels and the results obtained using various edge detection methods. The method using accurate operators is shown in (b), and the stochastic operation results are shown in (c-k), which are the conventional methods (c, d, and e) and the proposed method (f-i). In conventional methods, sharing method and inverter methods use a single RNG for Sobel edge detection input. However, the dedicated method uses 16 RNGs to generate SNs for the 16 inputs of the Sobel edge detection, which can give accurate results by using more SNGs. As shown, the images obtained using the proposed SC technique is better than those by the other stochastic methods and is similar to the image obtained by the accurate edge detection. Table 4 shows the hardware design metrics and error metrics after the synthesis of the Sobel edge detection technique using an accurate design and the various stochastic designs including the proposed method. As shown, up to 65% of logic utilizations and 63% of power were saved on average in the FPGA compared with the accurate edge detection. When compared with the dedicated LFSR method, the proposed design average can achieve up to a 46% area reduction and 71% power reduction in the ASIC. The relative power signal noise ratio (PSNR) and the root-mean-square error (RMSE) of the proposed method average were 14.83 and 42.05 for the five sample images, respectively. The percentage difference between the images of the proposed design's average with respect to the image after an accurate Sobel edge detection was approximately 12%, which shows the high accuracy of the proposed design. Furthermore, the proposed design average can enhance the PSNR by 18%, reduce the RMSE by 21%, and decrease the percentage difference between images by 25% compared with the sharing and sharing with inverter methods.

Fig. 6. Original image and images obtained using various edge detection techniques (a) original image, (b) accurate Sobel edge detection, (c) stochastic Sobel edge detection by sharing the LFSR, (d) stochastic Sobel edge detection using an inverter, (e) stochastic Sobel edge detection using multiple LFSRs, and the proposed stochastic edge detection using (f) $M_{1}$, (g) $M_{2}$, (h) $M_{3}$, (i) $M_{4}$, (j) $M_{5}$, (k) $M_{6}$, and (l) $M_{7}$ in Fig. 2.