{'fraction_non_alphanumeric': 0.03432756121748417, 'fraction_numerical': 0.012701197650469143, 'mean_word_length': 4.895884866201934, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exploring Multi-Level Composition and Efficient SCM Schemes for an Energy-Efficient Wavelet Haar Architecture

This work explores multi-level fixed-point Haar transform compositions combined with SCM (single constant multiplication) schemes for an energy-efficient hardware architecture. We investigate a set of six lower-level Haar transforms for composing a Haar-9 architecture. The multiple-level Haar transforms use as a base M=1, M=2, and M=3 resolution levels. The processing module (PM) of the Haar explores efficient SCM schemes. The architectures were described in VHDL and synthesized employing the ST 65nm CMOS cell library. The results show that Haar-II architecture presents the lower circuit area results since this architecture requires fewer arithmetic operators. However, the most energy-efficient Haar9 hardware architecture employs a combination of two M=2 with five M=1 blocks with an efficient SCM architecture reduced to only two arithmetic operators.


I. INTRODUCTION
In digital signal processing (DSP) applications, one of the primary operations involves using transforms. In particular, the wavelet transform is a relatively new mathematical approach that has been in evidence recently compared with other classical signal analysis techniques, such as the Fourier transform. The wavelet transform theory has excellent employment in several areas, such as analyzing seismic signals, radar, biomedical, among other applications [1][2][3][4][5][6].
Haar transform is the simplest among the wavelets [7] from a mathematical point of view. It means that its calculations require fewer arithmetic operations [8]. Due to this characteristic, Haar is suitable and commonly employed for embedded systems since the lesser complexity directly conducts less energy consumption in its hardware architecture implementation. Our key challenge is to reduce the Haar Transform's energy consumption with nine decomposition levels in this work. According to the literature [9], this level of resolution is widely used for practical cases in the adaptive filtering and image or video compression area. The paper in [10] proposed a method that adaptive identifies a frequency-rich sparse impulse response in the Haar-9 domain. The application for image or video compression is presented in [11] that discusses the compensation in terms of hardware cost and error of level 7 and 9 DWT decompositions.
We explore the wavelet Haar-9 transform hardware design in two main directions: (i) the implementations through the interconnection of blocks with lower resolution levels, (ii) the exploration of efficient SCM architectures.
We have developed six levels of decomposition to integrate the Haar level 9, using lower blocks. This significant exploration allows us to identify the most suitable arrangement for low-power design. Mainly, the blocks of Haar-1, Haar-2, and Haar-3 are the base for arranging hierarchical architectures for the Haar-9.
One of the inputs of the multipliers, in the Haar transform, is the H coefficient that is represented by 1 √ 2 . We implement this term by using shift-addition operation, by exploring SCM (single constant multiplication) approaches. We use SCM solutions generated by prominent Hcub, BHM, and RAG-n algorithms from the Spiral environment [12]. We also offer our solution for the SCM-based Haar architectures.
The main results show that the herein called Haar-VI (with two M=2 and five M=1 PM modules) combining with our SCM-VI proposal (with two arithmetic operators and critical path equal to 2) presenting the most negligible power dissipation among the explored architectures. Our contributions presented in this paper are as follows: 1. An extensive exploration of multi-level composition Haar blocks for a Haar-9 transform. 2. The simplification of the Haar coefficients exploring various SCM architectures.
The rest of the paper is organized as follows. Section II makes an overview of the wavelet transform, with particular concern to the Haar transform. The SCM approach and a review of the literature are also presented in this section. Section III shows the proposed Haar architectures for 9-levels of decomposition. The synthesis methodology and the main results are shown in Section IV. Finally, Section V concludes the paper.

II. BACKGROUND
This section initially shows an overview of the wavelet transform. After the main aspects of the Haar transform are presented. It also offers a discussion about the SCM approach and discusses the main work from the literature, and puts into perspective the main contributions of this work.

A. Discrete Wavelet Transform
To obtain the discrete wavelet transforms (DWT) of a sign f (n), the shift and scaling parameters are no longer continuous and become discrete [13,14]. In general, Equation 1 represents the DWT. In the equation, ψ is the mother wavelet and parameters a and b, which respectively represent scale and translation as a function of the continuous wavelet transform, are functions of the integer parameters m and n, that is, The parameters m and n are integer values, which control the dilation and translation, respectively. The constants a 0 and b 0 are the lengths of the discrete steps, with a 0 being an expansion parameter whose value is greater than 1, and b 0 a location parameter, with a value greater than zero. Given the definition, the DWT solution consists of dividing the analyzed signal into low-frequency components, called approximation coefficients (A n ), and high-frequency components called detail coefficients (D n ). This division generates two signals with the same number of samples as the original signal, doubling the DWT complexity. Therefore, the decomposition in the DWT goes through a subsampling process that guarantees the approximation coefficients and details with half the original signal. Thus, the decomposition process will always act on the approximation coefficients, creating a wavelet decomposition tree shown in Figure 1, for three levels of decomposition example.
Although the example of Figure 1 shows three levels of decomposition, the procedure repeats until reaching the desired resolution level or until the signal becomes a single sample. In practice, which defines the decomposition level is the nature of the signal, or some criterion, such as entropy [7].

B. Haar Transform
The Haar algorithm is a particular class of the DWT [15], and it has become a valuable tool to solve problems in many science branches. The wavelet on the Haar base was the first proposed in the literature and represents the simplest of the wavelet family's functions. The Haar transform is a set of mutually orthonormal functions whose support domain is '0' to '1', represented in Equation 2.
From the mathematical perspective, the wavelet on the Haar basis is discontinuous and resembles a step function, as shown in Figure 2 [7].
The methodology to calculate the DWT consists of designing low-pass (L) and high-pass (H) filters with coefficients according to the chosen wavelet mother function. The  [7] Equations 3 and 4 show how to calculate the coefficients of approximation and details at the first scale, respectively [16].
The Haar transform can also be represented by an orthogonal matrix N × N , called H N , where M = 2 N . The matrices that represent the Haar transform blocks used in this work are presented in Equations 5, 6 and 7, for one, two and three levels of decomposition, respectively.

C. SCM Operations
In DSP operations, the multiplication operations usually dominate the complexity of the project. This operation is the arithmetic core with the most significant impact on the circuit area, critical path delay, and power dissipation in the hardware design. In circuits with constant values multiplied (such as filters with finite impulse response and fast Fourier transform), using a complex general purpose multiplier is unnecessary if the constants were previously known. Instead, sum and shift operations replace the general-purpose multiplier in an SCM.
The sharing of common partial products, using shifts and sums/subtractions, allows a significant reduction in the number of operations and, consequently, in the circuit area and power dissipation in the SCM operations' design. Thus, the SCM problem consists of finding the minimum number of sums/subtraction operations that implement constant multiplications. The shifts in hardware use only wires, without additional costs in the area.
An example of representing the multiplication by constants using additions and shifts, in a method known as digitbased recoding [17], is shown in Equation 8. Figure 3 shows that the multiplication by a constant can be reduced to a set of shift-adders with less circuit area and reduced critical path, directly impacting power dissipation reduction.

D. Related Work
The Wavelet transform is a mathematical tool with particular characteristics, which has become popular in digital signal processing applications. Mainly, when it comes to reducing power dissipation, the wavelet transforms, in Haar basis, stand out due to its simplicity and low complexity for its implementation. These attributes make it possible to find various works in the most diverse application areas, which use the wavelet transform in the Haar base. The work in [18] treats a new algorithm for fast calculation of the Haar wavelet transform and the possibility of its application in the timefrequency analysis of the waveform. An FPGA-based solution of a de-noising using Haar level 5 wavelet transform was presented in [19].
Other studies propose using the Haar transform as a form of reducing power dissipation, such as in [20] and [21] that present algorithms using the Haar transform to process ECG signals, with a focus on portable devices and remote monitoring of cardiovascular diseases. Still, within the scope of biomedical engineering, the work proposed in [22] uses the Haar wavelet transform for analyzing electroencephalogram (EEG) signals in the detection of drowsiness. Another area of application where the Haar wavelet transform concentrates a significant amount of work is image processing and compression. An example is a work presented in [23] that offers an implementation of hardware for image compression, designed to meet the power restrictions of image communication in Wireless Sensor Networks. The work of [24] shows a hardware-oriented image encoding processing scheme based on the Haar wavelet transform.
The majority of the wavelet transform implementations, focusing on energy reduction, seek architectures with lower resolution levels to reduce complexity, and consequently, power dissipation. That is why it is challenging to find works in this area (low power), which implement architectures that reach nine resolution levels. However, it is still possible to see works, such as [25], using the Haar level 9 transform in a project of a sample of analog wavelet processor architecture for cochlear implant application. The work in [26] applies to level 11 of the Haar transform to implement an algorithm to extract important characteristics from fingerprints. Finally, in [27], a new scheme is proposed to identify the flow regime and measure the quality in gas-liquid two-phase using differential pressure signal. The flow regime is determined based on the analysis of a wavelet function in the Haar basis with nine resolution levels.
The solution of [28] proposed a Haar-9 architecture, based on three M=3 blocks, but with no power results. Furthermore, the SCM part uses only Carry Save adders (CSA). This solution was further improved in [29] using efficient adder compressors architectures in both the Processing Module (PM) and the SCM part, for an energy-efficient Haar-9 transform. However, none of both mentioned works explored decomposing in lower resolution blocks than M=3 for the Haar-9 solution, as we are proposing. Furthermore, our work explores more solutions for the SCM part than proposed in [29]. As will be discussed in the Results Section, our best-proposed architecture is more time processing and power-efficient than the best solution of [29]. Table I summarizes the solutions from the literature and puts into perspective the contributions of this work.

III. HAAR WAVELET TRANSFORM HARDWARE ARCHITECTURES
Among all DWTs, the Haar discrete wavelet transform (Haar DWT) is the simplest and most orthogonal. However, a traditional 2D DWT is applied by sequentially performing two 1D operations along the lines and the columns. In this case, there is performance degradation due to memory read and write operations involving intermediate results between row and column operations. For this reason, we propose sequential data entry for a hierarchical algorithm for Haar DWT. Thus, there is no implementation of the Haar matrix using a grid memory. We use adders and multipliers to estimate the levels of decomposition resulting from a convolution process with the Haar coefficients matrix. With this technique, we can implement a 2D Haar DWT by rearranging data, achieving the low memory needed to implement being from O(N).
The proposed Haar architecture uses as bases the solution proposed in [28] for 9-levels of decomposition that used three M=3 blocks. However, we extended the solution to Haar-9 using other architectures with fewer resolution levels to find combinations with fewer arithmetic operations. The architectures use as bases three different M=1 (Figure 4 Table II shows the number of additions and multiplications and the critical path for the M=1, M=2, and M=3 PM modules. To calculate the approximation coefficients and details coefficients of the Haar transform, the internal PM architectures, shown in Figures 4-a,-b,-c, include shifts registers, buffers, adders, subtractors, multipliers, and shift operators. Its operation consists of loading the input signal x(n) samples in the shifts registers and storing them in the buffers. A control block, composed of counters and comparators, will be responsible for determining when these values will be available for the operative part to carry out the calculations, thus guaranteeing the down-sampling process present in the filtering. Therefore, the first decomposition needs to be downsampling by a factor of two. Then, the architecture calculates every two samples that enter the buffer (every two clock cycles). In this way, each resolution level of the Haar transform has a different latency, i.e., each resolution level must wait a certain number of clock cycles to perform its calculation. Table III shows how many clock cycles are needed to calculate each resolution level. The values in Table III show the large number of clock cycles required to implement an entire Haar-9. On the other hand, using lower resolution levels to construct a Haar-9 can be advantageous due to the more reduced clock cycles. This work explores, mainly, the 1, 2, and 3 resolutions levels to design a Haar-9 transform.  Table II show that these blocks present fewer additions and multiplications and less critical path than the M=3 level. On the other hand, Table II shows that implementing an entire Haar with M=9 is prohibitive, mainly due to a large number of additions and multiplications required. From these three PM modules (M=1, M=2, and M=3), we offer the architectures in Table IV.  The Haar architecture's critical path is determined by multipliers, adders, and the circuit's latency. Table IV describes the critical path, the number of multipliers (Mult) and total adders (Add) for the proposed Haar architectures. The Haar-III (Figure 4-f) uses three M=3 PM modules as in [28] and [29], with a total of 45 arithmetic operators (45 additions and nine multiplications), and a critical path equal to 12. Note that we consider adders and subtractors as equal since the difference between them is minimal in terms of hardware (the subtractor is easily implemented by inverting the input and adding '1' value to realizing the operation in 2's complement. The multiplier circuit undoubtedly has the most significant influence on this requirement (critical path) from these elements. Figures 4-a,-b,-c show that, in the Haar architectures, one of the multipliers' inputs is the H coefficient. This coefficient is represented by 1 √ 2 . For simplifying the implementation of this coefficient, we approximate its calculation according to Equation 9. This equation enables substituting a complicated multiplication by simpler shift-addition operations in an SCM approach.
The SCM problem consists of finding the minimum number of addition/subtraction operations that implement constant multiplications. The shifts can be performed on hardware using only wires, without additional costs in the area. This work explores several solutions for implementing SCM strategies for the H coefficient calculation in the Haar transform. One solution uses the strategy of [28] and [29]. Some solutions use the algorithms of the Spiral environment [12]. Our solutions use

Haar -V h)
Haar -V I i) Legend: calculate √ 2 and shift the results one position right to obtain the division by 2. We explored the following SCM strategies to approximate the H coefficient for the 0.70703125 value: • SCM-I ( Figure 5-a): Solution proposed by [28,29]. The solution involves four arithmetic operators (four additions), with a critical path equal to 3.
• SCM-II ( Figure 5-b): Solution generated by HCub algorithm [30] from Spiral environment. For this solution, the H coefficient was implemented through the formulation of 181X * 2 −8 . The solution involves three arithmetic operators (three additions) and presents a critical path equal to 3.
• SCM-III ( Figure 5-c): Solution generated by BHM algorithm [31] from Spiral environment. For this solution, the H coefficient was also implemented by using 181X * 2 −8 . It represents three arithmetic operators (one addition and two subtractions), with a critical path equal to 3 (one addition and two subtractions).
• SCM-IV ( Figure 5-d): Solution generated by RAG-n algorithm [31] from Spiral environment. For this solution, the H coefficient was also implemented from the formulation of 181X * 2 −8 . The solution involves three arithmetic operators (two subtractions and one addition), and presents a critical path equal to 3 (two subtractions and one addition). This solution uses a different formulation for implementing the H coefficient. We used the formulation of 45X * 2 −6 that involves two arithmetic operators (one addition and one subtraction), and presents a critical path equal to 2 (one addition and one subtraction).
• SCM-VII (Figure 5-g): Solution proposed in this work This solution also used the formulation of the SCM-VI for the H coefficient implementation, i.e., 45X * 2 −6 . This solution involves two arithmetic operators (two subtractions) and presents a critical path equal to 2.
Regarding SCM-VI and VII architectures, there is a reduction of at least one adder about architectures I to V, which drastically reduces power dissipation, energy consumption and increases the architecture's operating frequency, enabling the calculation of a more significant amount of samples per second. There is an error of around 0.56% for the Haar coefficient, i.e., equal to 1 √ 2 in the SCM-VI and VII proposed architectures. This small error rate has no impact on the efficiency of Haar-9, as at decomposition level 9, we have a frequency range from 3.90 Hz to 2000 Hz. An error in this magnitude would reduce the frequency range by 11.20 Hz, generating an amplitude ranging from 3.90 Hz to 1988.20 Hz.  [28,29], b) Solution from Hcub algorithm [30], c) Solution from BHM algorithm [31], d) Solution from RAG-n algorithm [31], e-g) Solutions from this work.

IV. RESULTS
This section presents the main results. Initially, we present the methodology for the power results. After, we offer the synthesis results in terms of area, power dissipation, energy per operation (EPO), and fanout. The fanout represents the number of logic gates in the critical path provided by the synthesis tool.

A. Methodology for Synthesis Results
The hardware architectures used industrial EDA tools for standard-cell CMOS hardware design for the syntheses. The architectures descriptions were in VHDL, with the adder inferred by the logic synthesis tool ('+' operator in VHDL). Cadence Genus TM tool performed the RTL to gatelevel netlist synthesis and the STA. The architectures were mapped to 65nm standard cells at 1.25V voltage, aiming for their maximum frequency of 1.62GHz (with zero slack value). Figure 6 shows the methodology for power dissipation extraction. For the simulations of all network lists, we used the Cadence Incisive, considering the SDF file for precise signal propagation delays and temporal glitches. The simulation generates a toggle count format (TCF) file, loaded into the synthesis tools for the power extraction. The power estimation methodology employs the Genus synthesis tool in PLE mode to generate the Verilog gate-level network list and the SDF Format. To perform the power dissipation results with real-world input stimuli, we stimulated the postsynthesis netlists using a discretized audio signal containing 100,000 samples. Table V shows that the Haar-II architecture presents the best results in terms of total area, for all SCM combinations. It occurs because the Haar-II architecture gives the fewest number of arithmetic operators (28) among all the arrangements. However, the architecture with the best results in terms of power dissipation is the Haar-VI. This lower power dissipation is associated with the lowest fanout values presented by this architecture, as shown in Table V. Notably, this lower fanout in the Haar-VI is due to the large amount of five M=1 blocks used in this architecture, which is favorable for its optimization in the synthesis tool. It is also noticeable the advantages of the Haar-VI proposed in this work regarding energy per operation. The combination of the Haar-VI with six SCM strategies (from SCM-II to SCM-VII) presents the best EPO results among all the architectures. However, when using SCM-I, the Haar-IV shows the best EPO result. It occurs because although both Haar-IV and Haar-VI present the same fanout value (303), the synthesis tool found an advantage in optimizing the architecture with the less critical path (Haar-IV).

B. Synthesis Results
The results in Table V indicate that using our SCM-VI solution is favorable for almost all the Haar architectures, with the best circuit area, total power dissipation, and EPO results. It occurs because this architecture presents only two arithmetic operators, i.e., one adder and one subtractor. The SCM-VI does not offer gains only when used in Haar-III and Haar-IV architectures, where the SCM-I gives the best circuit area, total power dissipation, and EPO results. However, observe that, in terms of the Haar-III, the SCM-VI solution provides almost the same total power dissipation and EPO, with less circuit area than using the SCM-I solution.
Although the SCM-VI and SCM-VII architectures present the same amount of two arithmetic operators and the same critical path, the SCM-VII involves two subtractions that impose slight more logic operations than the additions. It explains the SCM-VII presents almost the same results but with fewer gains than the SCM-VI approach for nearly all Total is the Total power dissipation in (µW ), Area is the Circuit area in (µm 2 ), EPO is the Energy per operation (fJ/op). Red-colored highlighted cells represents the worst results. Green-colored highlighted cells represents the best results.
the Haar architectures. However, it is possible to claim that both proposed SCM-VI and SCM-VII strategies are favorable for use in the Haar architectures. It proves the efficiency of implementing the H coefficient by using a new 45X * 2 −6 form.
From the results, we can identify the Haar-VI and SCM-VI with the best combination for designing an energyefficient Haar w ith nine resolution l evels. It shows t he importance of using lower resolution M=1 and M=2 levels for implementing Haar-9. This result improves the literature, whose Haar-III proposed in [29] (with only M=3 blocks) presents the worst results among the Haar architectures.
While the solution of [29] operates at the maximum frequency of 300 MHz, Our solutions provide the maximum of 1.62 GHz at the same conditions of [29], i.e., considering as input the same audio signal with 100,000 samples. There-fore, the time processing of [29] is 333.33s while our solu-tions enable a processing time of 61.72s, which proves the efficiency of our proposed solutions. Although we are ex-ploring different solutions for the SCM at the maximum fre-quency operation, we can adjust the frequency operation of our solutions accordingly depending on the target applica-tion. It is noticeable the impact on power reduction of our proposed solutions. While the best architecture of [29] offers 248.2µW of total power dissipation, our best Haar-VI (SCM-VI) solution provides a significant power reduction with only 70.29µW of power dissipation. It proves the efficiency of the proposed strategies used in this work to optimize the Haar-9 architecture.

V. CONCLUSIONS
This work presented an architectural exploration for Haar Transform, combining multi-level resolutions and SCM strategies. We explored six Haar architectures with decomposition level 9. The different schemes used blocks by Haar transform with lower resolution M=1, M=2, and M=3 levels for composing the other architectures. We also explored various forms of implementing the H coefficient by using the SCM approach. The synthesis results consolidated the Haar-II with the lower cell area. This architecture comprises M=1 and M=2 blocks with fewer amount of arithmetic operations. However, the best combination for the Haar-9 transform design, regarding power dissipation and energy per operation, comprises the Haar-VI architecture (with two M=2 and five M=1 blocks) and the SCM-VI approach (with only one addition and one subtraction and a critical path equal to 2). This combination offers the lowest fanout among the architectures investigated.