Open access peer-reviewed chapter

A Comparative Performance of Discrete Wavelet Transform Implementations Using Multiplierless

By Husam Alzaq and Burak Berk Üstündağ

Submitted: October 3rd 2017Reviewed: March 15th 2018Published: November 5th 2018

DOI: 10.5772/intechopen.76522

Downloaded: 284

Abstract

Using discrete wavelet transform (DWT) in high-speed signal-processing applications imposes a high degree of care to hardware resource availability, latency, and power consumption. In this chapter, the design aspects and performance of multiplierless DWT is analyzed. We presented the two key multiplierless approaches, namely the distributed arithmetic algorithm (DAA) and the residue number system (RNS). We aim to estimate the performance requirements and hardware resources for each approach, allowing for the selection of proper algorithm and implementation of multi-level DAA- and RNS-based DWT. The design has been implemented and synthesized in Xilinx Virtex 6 ML605, taking advantage of Virtex 6’s embedded block RAMs (BRAMs).

Keywords

  • discrete wavelet transform (DWT)
  • distributed arithmetic algorithm (DAA)
  • field programmable gate array (FPGA)
  • residue number system (RNS)
  • multiplierless implementation

1. Introduction

The architecture of the embedded platform plays a significant role in ensuring that real-time systems meet the performance requirements. Moreover, software development suffers from increased implementation complexity and a lack of standard methodology for partitioning the implementation of signal-processing functionalities to heterogeneous hardware platforms. For instance, digital signal processor (DSP) is cheaper, consumes less power, and is easy to develop software applications, but it has a considerable latency and less throughput compared with field programmable gate arrays (FPGAs) [1]. For high-speed signal-processing (HSP) communication systems, such as cognitive radio (CR) [2, 3] and software-defined radio (SDR) [4], DSP may fail to capture and process the received data due to data loss. In addition, implementing applications such as finite impulse response (FIR) filtering, discrete wavelet transform (DWT), or fast Fourier transform (FFT) by software application limits the throughput, which is not sufficient to meet the requirements of high-bandwidth and high-performance applications. As a result, HSP systems are enhanced by off-loading complex signal-processing operations to hardware platforms.

Although FPGAs exhibit an increased development time and design complexity, they are preferred to meet high-performance requirements for two reasons. First, they efficiently address signal-processing tasks that can be pipelined. Second, they have the capacity to develop a programmable circuit architecture with the flexibility of computational, memory, speed, and power requirements. However, FPGA has its own resources such as memory, configurable logic blocks (CLBs), and multipliers that influence on the performance and selected algorithm. As a consequence, the choice of algorithm is determined by the hardware resource availability and performance requirements. These factors have an impact on each other and create many challenges that need to be optimized.

As an example, the discrete wavelet transform (DWT) [5, 6, 7, 8, 9], a linear signal-processing technique that transforms a signal from the time domain to the wavelet domain [10], employs various techniques for signal decomposing into an orthonormal time series with different frequency bands. The signal decomposition is performed using a pyramid algorithm (PA) [10, 11] or a recursive pyramid transform (RPT) [12]. While the PA algorithm is based on convolutions with quadrature mirror filters, which is infeasible for HW implementation, RPT decomposes the signal x[n] into two parts using high- and low-pass filters, which can be implemented using FIR filter [13]. Figure 1 shows a four-tap FIR filter with four multipliers, named as multiplier accumulator (MAC). By using the MAC structure, multipliers are involved in multiplying an input with filter coefficients, bi. It is clear that the direct implementation of the N-tap filter requires N multipliers.

Figure 1.

Four-tap finite impulse response filter.

This work focuses exclusively on implementing a one-level multiplierless DWT for a pattern-based cognitive communication system receiver (PBCCS) [8] by means of FPGA. The DWT is required to extract the received signal’s features. Then, the extracted features are fed into a multilayer perceptron (MLP) neural network (NN) to identify the received symbol. The most challenging part is that the NN could consume most of the available multipliers inside the FPGA. As an example, Ntoune et al. [14] have implemented a real-valued time-delay neural network (RVTDNN) and real-valued recurrent neural network (RVRNN) architecture with 600 and 720 multipliers, respectively, while ML605 [15], ZC706 [16], and VC707 [17] have 768, 900, and 2800 multipliers (DSP48Es), respectively.

Although the modern FPGAs come with a reasonable number of multipliers, designers prefer to implement multiplier-free DWT architecture for many reasons. First, a partial number of multipliers can be preserved for tasks, such as pulse shape filter, digital-up and digital-down converter that are used at SDR front-ends. Second, in contrast to DWT, the MLP weights depend on the learning step. Third, MLP weights could be frequently changed at runtime in an adaptive manner, whereas the DWT coefficients are fixed and known. Therefore, the multiplier-free DWT architecture could simplify the design process and allow the designers to focus on the MLP design.

In this work, we present the 1-D DWT implementation on FPGA by means of memory-based approaches. The aim is to compare different implementations in terms of system performance and resource consumption. We demonstrate the implementation of Daubechies wavelets (DB2, DB4, and DB5) using DAA and RNS approaches. These approaches do not employ explicit multipliers in the design. Because the main focus of this work is on extracting the key features of a signal via DWT, the inverse DWT (IDWT) and high-pass filter coefficients are not considered in this work.

1.1. Related work

Implementations of 1-D DWT for signal de-noising, feature extraction, and pattern recognition and compression can be found in [8, 9, 18, 19]. The conventional convolution-based DWT requires massive computations and consumes much area and power, which could be overcome by using the lifting-based scheme for the DWT, which is introduced by Sweldens [20]. Although, the lifting scheme is used to compute the output of low- and high-pass using fewer components, it may not be well suited to our application, owing to the PBCCS’s nature, where the low-frequency components are much important than the higher ones. Therefore, in this study, 1-D DWT decomposition, which is implemented by means of filter banks, is considered. Another advantage of using convolution-based DWT over lifting approach is that they do not require temporary registers to store the intermediate results, and with an appropriate design strategy, they could have better area and power efficiency [21].

Rather than the simplest implementation of FIR filter via multipliers and an adder tree, a multiplier-free architecture is used because they result in low-complexity systems and for their high-throughput-processing capability [22]. Fundamentally, there are two techniques for facilitating parallel processing. They are the distributed arithmetic algorithm (DAA) and the residue number system (RNS). DAA is an algorithm that performs the inner product in a bit serial with the assist of a lookup table (LUT) scheme followed by shift accumulation operations [23, 24]. Several techniques have been proposed to improve the design, such as the partial sum technique [25], a multiple memory bank technique [26, 27], and an LUT-less adder-based [28]. The DAA approach has been adapted in many applications, such as least mean square (LMS) adaptive filter [29] and square-root-raised cosine filter [30].

On the other hand, RNS is an integer number system, in which the operations are performed based on the residue of division operation [31, 32, 33]. Eventually, the RNS-based results are converted back to the equivalent binary number format using a Chinese reminder theorem (CRT) [34]. The key advantage of RNS is gained by reducing an arithmetic operation to a set of concurrent, but simple, operations. Several applications, such as digital filters, benefit from the RNS implementation, for example, [35, 36, 37]. In addition, RNS was combined with DAA in one architecture, called RNS-DA [38, 39], which benefits from the advantages of both approaches.

In this chapter, three major 1-D DWT approaches are implemented on FPGA-based platforms and compared in terms of performance and energy requirements. The implementations are compared for different number of, multipliers, memory consumptions, number of taps (N), and levels (L) of the transform to show their advantages. To the best of our knowledge, no detailed comparisons of hardware implementations of the three major 1-D DWT designs exist in the study. This comparison will give significant insight on which implementation is the most suitable for given values of relevant algorithmic parameters. Although there are many efficient designs in the study, we did not optimize the number of memories in any approach, so that we have a fair comparison.

The remainder of this chapter is organized as follows. Section 2 presents the preliminaries information to understand DWT. It also reviews the theoretical background of DAA and RNS. Section 3 describes the implementation of discrete wavelet transform. We further show an analytical comparison between these approaches. Section 4 presents the performance results. Finally, this chapter concludes in Section 5.

2. Fundamentals and basic concepts

2.1. Discrete wavelet transform

The wavelet decomposition mainly depends on the orthonormal filter banks. Figure 2 shows a two-channel wavelet structure for decomposition, where x[n] is the input signal, g[n] is the high-pass filter, h[n] is the low-pass filter, and ↓2 is the down-sampling by a factor of two. The output of each low-pass filter is fed to the next level, so that each filter creates a series of coefficients (ai and di), which represent and compact the original signal information.

Figure 2.

Multi-resolution wavelet decomposition. The block diagram of the two-channel four-level discrete wavelet transform decomposition (J = 3) that decomposes a discrete signal into two parts. Note that ↓2 is maintaining one sample out of two, ai and di are the approximation and details at level i, respectively.

Mathematically, a signal y[n] consists of high- and low-frequency components, as shown in Eq. (1). It shows that the obtained signal can be represented by using half of the coefficients, because they are decimated by 2

yn=yhighn1+ylown1E1

The decimated low-pass-filtered output is recursively passed through identical filter banks to add the dimension of varying resolution at every stage. Eqs. (2) and (3) represent the filtering process through a digital low-pass filter h[k] and high-pass filter g[k], corresponding to a convolution with an impulse response of k-tap filters

ylown=khk.x2nkE2
ylown=kgk.x2nkE3

where 2n is the down-sampling process. The outputs ylow [n] and yhigh [n] provide an approximation signal and of the detailed signal, respectively [40].

2.2. Distributed arithmetic algorithm

The distributed arithmetic algorithm (DAA) gets rid of multipliers by performing the arithmetic operations in a bit-serial computation [13]. Because the down-sampling process follows each filter (as shown in Figure 2), Eq. (2) can be rewritten without the decimation factor as

ylown=k=0N1xk.hkE4

Obviously, Eq. (4) requires an intensive operation due to multiplication of the real input values with the filter coefficients. Eq. (3) can be simplified by representing x[k] as a fixed point arithmetic of length L:

xk=xk0+l=1L1xkl.2lE5

where x[k]l is the lthbit of x[k] and x[k]0 is the sign bit. Substituting Eq. (5) into Eq. (4), the output of the filter becomes

yn=l=1L12l.k=0N1hk.xkl+k=0N1hkxk0E6

Since x[k]l takes the value of either 0 or 1, k=0N1hk.xklmay have only 2N possible values. That is, rather than computing the summation at each iteration online, it is possible to pre-compute and store these values in a ROM, indexed by x[k]l. In other words, Eq. (6) simply realizes the sum of product computation by memory (LUT), adders, and shift register.

2.3. Residue number system

The RNS is a non-weighted number system that performs parallel carry-free addition and multiplication arithmetic. In DSP applications, which require intensive computations, the carry-free propagation allows for a concurrent computation in each residue channel. The RNS moduli set, P = {m1, m2, …, mq}, consists of q channels. Each mi represents a positive relatively prime integer; the greatest common divisor (GCD) (mi, mj) = 1 for i ≠ j.

Any number, X ZM = 0, 1, …, M - 1, is uniquely represented in RNS by its residues Xmi, which is the remainder of division X by mi and M is defined in Eq. (7) as

M=Πi=1qmi=m1m2mqE7

where M determines the range of unsigned numbers in [0, M - 1], and should be greater than the largest performed results. In addition, M uniquely represents any signed numbers. The implementation of RNS-based DWT obtained from Eq. (4) is given by Eq. (8) as follows:

ynmi=ymi=|(k=0N1hkmi.xnkmimi)miE8

for each mi P. This implies that a q-channel DWT is implemented by q FIR filters that work in parallel.

Mapping from the RNS system to integers is performed by the Chinese reminder theorem (CRT) [34, 41, 42]. The CRT states that binary/decimal representation of a number can be obtained from its RNS if all elements of the moduli set are pairwise relatively prime.

Designing a robust RNS-based DWT requires selecting a moduli set and implementing the hardware design of residue to binary conversion. Most widely studied moduli sets are given as a power of two due to the attractive arithmetic properties of these modulo sets. For example, 2n12n2n+11[43], 2n12n2n+1[39], and 2n22n122n+1[44] have been investigated.

For the purpose of illustrating, the moduli set Pn=2n12n2n+11is used for three reasons. First, the multiplicative adder (MA) is simple and identical for m1=2n1and m3=2n+11. Second, for small (n = 7), the dynamic range of P7 is large, M = 4,145,280, which could efficiently express real numbers in the range [−2.5, 2.5] using a 16-bit fixed-point representation, provided scaling and rounding are done properly. We assume that this interval is sufficient to map the input values, which does not exceed ±2. Third, the reverse converter unit is simple and regular [42] due to using simple circuits design.

3. DWT implementation methodology

3.1. DWT implementation using DA

DAA hides the explicit multiplications with a ROM lookup table. The memory stores all possible values of the inner product of a fixed w-bit with any possible combination of the DWT filter coefficients. The input data, x[n], are signed fixed-point of a 22-bit width, with 16 binary-point bits (Q5,16). We assumed that the memory contents have the same precision as the input, which is reasonable to give high enough accuracy for the fixed-point implementation. As a consequence, 22 ROMs, each consisting of 16 words, are required. Each ROM stores any possible combination of the four DWT filter coefficients, where the final result is a 22-bit signed fixed-point (Q5,16). In order to decrease the number of memory, the width should be reduced, which will have an impact on the output precision.

Figure 3 shows the block diagram of 1-bit DAA at position l. This block contains one ROM (4 × 22) and one shift register. Because the word’s length w of the input x is 22 bits, the actual design contains 22 memory blocks and 21 adders for summing up the partial results.

Figure 3.

The block diagram of DAA-based architecture of the DB2. For simplicity, we showed one ROM and one shift register. In the actual design, there are 22 ROMs and shift registers. >> is a 16 − l shift operation, where 16 is the number of the binary point.

3.2. DWT implementation using RNS

The RNS-based DWT implementation has mainly three components. They are the forward converter, the modulo adders (MAs), and the reverse converter. The forward converter, which is also known as the binary-to-residue converter (BRC), is used to convert a binary input number to residue numbers. By contrast, the reverse converter or the residue-to-binary converter (RBC) is used to obtain the result in a binary format from the residue numbers. We refer to the RNS system, which does not include RBC, as a forward converter and modular-adders (FCMA), as illustrated in Figure 4.

Figure 4.

The block diagram of DB2 RNS-based architecture. BRC is an abbreviation for binary-to-residue converter, RBC for residue-to-binary converter, and MA for modulo adder.

3.2.1. The forward converter

The forward converter is used to convert the result of multiplying an input number by a wavelet coefficient to q residue numbers via LUT, shift, and modulo adders, where q is the number of channels.

3.2.2. RNS-system number conversion

The received samples and wavelet coefficients span the real number and might take small values. One of the main drawbacks of RNS-number representation is that it only operates with positive integer numbers from [0, M – 1]. The DWT coefficients are generally between 1 and − 1. As a possible solution, we have divided the range of RNS, [0, M – 1], to handle those numbers.

In addition, the received sample X[i] is scaled up by shifting y positions to the left (multiplying by 2y), which ensures that X[i] is a y-bit fixed point integer. In a similar manner, the wavelet coefficients are scaled by shifting its z positions to the left. In our design, we set the filter scaling factor z to 11. Table 1 presents the low-pass filter of DB2 before and after scaling.

Coefficient(hk)Real valueRNS-system value
h0−0.129409522550921−266
h10.224143868041857459
h20.8365163037374691713
h30.482962913144690989

Table 1.

The DB2 low-pass real and RNS-system number equivalent, multiplied by 211.

3.2.3. Modulo mi multiplier

The multiplication of the received sample, X[i], by the filter coefficients, which are constants, is performed by indexing the ROM. As the word length, w, of the received sample X[i] is increased, the memory size becomes 2w. In addition, q ROMs are required to perform the modulo multiplication.

We propose few improvements to this design. First, instead of preserving a dedicated memory for each modulo mi, a ROM that contains all module results is used. Thus, each word at location j contains the q modules of hkj211. Figure 5 shows the internal BRC block design of the three-channel moduli set P7 = {127, 128, 255} with its memory map at the right top corner. It shows that, for a location j, the least significant 8 bit contains hkxm3, the next 7 bit contains hkxm2and the most significant 7 bit contains hkxm1, which is generalized by Eq. (9). The advantage of this method is that no extra hardware is required to separate each module value.

ROMj=hkj211m122n+1+hkj211m22n+1+hkj211m3,j=02wE9

Figure 5.

The block diagram of the binary-to-residue converter for the three-channel RNS-based DWT, P7 = {127, 128, 255}. Four identical memories are used for each tap. The upper corner shows the memory content at location j ∈ [0, 15].

As with DAA-based approach, if the input word length is 16 bits, the ROM should contain 216 locations. One way to reduce the size of the memory is to divide it into four ROMs of 4 × 22. Figure 4 shows the block diagram of the binary-to-residue converter with four ROMs; each is indexed by four bits of x. However, the output of each ROM should be combined, so that the final result can be corrected. It is worth noting that this division comes with a cost in terms of adders and registers.

According to the previous improvements, the RNS-based works are as follows. The input X16bit=x1x2x3x4is divided into four segments. Each of the 4-bit segment is fed into one ROM, so that three outputs, corresponding to hkxl211mi, are produced.

To obtain the final multiplications’ result, each mi output should be shifted by l positions, where l is the index of the lowest input bit (4, 8, or 12). The modular multiplication and shift for (2n – 1) and (2n + 1–1) can be achieved by a left circular shift (left rotate) for l positions, whereas the modular multiplication and shift for 2n can be achieved by a left shift for l positions [17]. Finally, the modulo adder adds the corresponding output (Figure 6).

Figure 6.

The block diagram of (2n – 1) modulo adder.

3.2.4. Modulo adder (MA)

The modulo adders are required for adding the results from a modular multiplier as well as for a reverse converter. In this work, we have two MAs—that is, one is based on 2n and the other is based on 2n1. Modulo 2n adder is just the lowest n bits of adding two integer numbers, where the carry is ignored. Figure 7 shows the block diagram of the 2n – 1 modulo adder.

Figure 7.

The block diagram of two-level RNS-based DWT design, and FCMA represents FIR-filtering process in RNS.

3.2.5. The reverse converter

The Chinese remainder theorem (CRT) [34] provides the theoretical basis for converting a residue number into a natural integer. The moduli set Pn=2n12n2n+11can be efficiently implemented by four modulo adders and two multiplexers [42]. The output of the RBC is unsigned (3 * n + 1)-bits integer number. The actual signed number can be found by shifting the result y + z positions to the left, which is equivalent to dividing by 2(y + z). y and z are the scaled values of the input and wavelet coefficients, respectively. Generally, the word length of one-level DWT is bounded by Eq. (10) and should not exceed (3 * n – 2) bits

3n+1y+z+3E10

As a consequence, the range of the moduli set should be greater than the maximum output, tho, which can be computed as follows:

tho=khk2maxxn2z22yM1E11

where hk is the kth filter coefficient, x[n] is the input, y and z are the input and filter scaling factors, respectively, and M is the maximum range.

3.3. Two-level DWT implementation

The two-level discrete wavelet transform compromises two one-level DWTs, where the output of the first level is fed into the second level (as shown in Figure 7). The one-level DWT at each level is identical, but the output of each level is halved. For example, if a signal of 1800 samples is applied to the input, then 900 and 450 samples are produced by the first and second levels, respectively.

Figure 7 shows the design of two-level RNS-based DWT, which involves two FCMA blocks and two RBC blocks. Each FCMA requires converting the result of the first stage to binary, shifting the number by 11 and converting it to residue number again.

3.4. Hardware complexity

3.4.1. Memory usage

DAA and RNS techniques employ the memory as a key resource to avoid multiplying two input variables. In each approach, as the number of filter taps increases, both the size and the number of memories change. Assuming that the length of the received word is w-bit and there are N filter taps, the size of a memory element can be considered as a × b, where a and b are the word length in bits of the input and output, respectively. The value of a determines the size of the memory, 2a.

The total number of memory elements that are occupied by the DAA-based filter is w * (N × 22). The output is a fixed 16-bit fixed point and the word length is 22 bits. The number of memory elements remains constant as the filter taps increase, whereas the size of the memory exponentially increases to 2N.

On the other hand, the total number of memory elements occupied by an RNS-based filter is Nlog2w4×22. This equation shows that the number of memory elements increases linearly with the number of filter taps, while the memory size remains constant (4 × 22). Table 2 shows a comparison of the memory usage with w = 16 for different DWT families.

DB2DB4DB5
Number of filter taps4810
DA memory usage22*(4 × 22)22*(8 × 22)22*(10 × 22)
RNS memory usage16*(4 × 22)32*(4 × 22)40*(4 × 22)

Table 2.

Occupied memories when DA- and RNS-based approaches are used. The word length, w, is 22 and 16 bits for DA- and RNS-based, respectively.

3.4.2. Shift register and adder counts

DAA-based implementation employs shift registers and adders to sum the result at each bit level (Figure 3). For a word length w with m magnitude bits, we need (w – 1) shift registers and (w – 1) 2-input adders (data combined by a tree adder architecture). To handle the negative numbers, the two’s complement operation requires additional (m – 1) shift registers and (m – 1) adders. Thus, for l-level DA-based implementation, a total of l * (w – m – 2) shift registers and two-input adders is required.

On the other hand, for a word length w and N-tap filter, the q-channel FCMA implementation requires N BRC blocks and (q*(N – 1)) MA blocks to compute the final result. Each BRC block has log2w1,log2n1, and log2w1MA blocks for 2n – 1, 2n, and 2n + 1–1 modulo, respectively. The modulo 2n requires log2(n) because shifting operations is not circular and shifting n-bit numbers to the left by n positions or more is always zero. Likewise, the RBC has four MA blocks (for 2n + 1–1), two multiplexers, and two subtractors. Thus, the total number of MA blocks at one-level RNS-based is

MAt=2Nlog2w12n1+log2n12n+qN1+4E12

For instance, three-channel DB2 implementation requires nine MA blocks to sum the result, and P7 RNS-based implementation has a total of 45 MA blocks when w = 16.

Meanwhile, the number of RNS-based adders depends on the design of the MA block. For example, each MA block of (2n – 1) and (2n + 1–1) requires two adders, while each MA block of 2n requires one adder. Thus, at=12N+Nlog2n1+5N1+10adders are required, which can be simplified as follows (summarized in Table 3):

at=17N+Nlog2n1+10E13

Table 3.

Memory usage and adders for 1-L N-tap DA and RNS-based approaches DWT.

4. Performance analysis and validation

Hardware analysis was carried out by using a Xilinx System Generator for DSP (SysGen) [45], which is a high-level software tool that enables the use of MATLAB/Simulink environment to create and verify hardware designs for Xilinx FPGAs. It enables the use of the MathWorks model-based Simulink design environment for FPGA design. Furthermore, the hardware-software co-simulation design was synthesized and implemented on ML605 Xilinx Vertex 6 [15].

The implementation of RNS and DA is compared with the multiplier-accumulate-based DWT structure (MAC), as shown in Figure 8. We also consider the direct DWT implementation using an IP FIR Compiler 6.3 (FIR6.3) block [46], which provides a common interface to generate highly area-efficient and high-performance FIR filters (Figure 9).

Figure 8.

The Simulink model of MAC-based one-level DB2 discrete wavelet transform. Filter coefficients are stored as constants.

Figure 9.

The Simulink model of FIR-based one-level DB2 discrete wavelet transform. The IP FIR compiler 6.3 of the system generator is used.

For RNS implementation, the moduli sets of P7 = {127, 128, 255} and P10 = {1023, 1024, 2047} were used. The dynamic ranges of these sets are M = 4,161,536 and 2,144,338,944, respectively. The moduli set of P10 is selected because its dynamic range is greater than tho (Eq. (11) with y = 6, z = 11 and ∑(hi) = 1.5436). In all RNS-based implementations, the word length was set to 16 bits.

4.1. Resource utilization and system performance

Table 4 summarizes the resource use by RNS-based components—that is, FCMA and reverse converter (RBC). The RBC consumes fewer resources and less power. However, the operating frequency is equal in all models and greater than the entire RNS-based filter.

ResourcesRNS-based (n = 7)RNS-based (n = 10)
FCMARBCFCMARBC
Number of slice registers656157883190
Number of slice LUTs591138854180
Number of RAMB18E1160160
Max. operating freq. (MHz)291.2311.62283.85298.67
Min. period (ns)3.4343.213.5233.348
Estimated total power (mW)40.56.5943.087.33
Latency (clock cycle (CC))6666

Table 4.

The resource use and system performance of the RNS components—that is, FCMA.

Table 5 summarizes the resource consumption of each filter implementation. It shows that the MAC and IP FIR-based implementations have four multiplier units (DSP48E1s) with maximum frequencies of 296 and 472 MHz, respectively. By contrast, the proposed approaches are more complex than MAC. However; DAA- and RNS-based implementations has 22 and 16 memory blocks (BRAMs) used to store the pre-calculated wavelet coefficients. It also shows that the number of slice registers, slice LUTs, and occupied slices of P10 RNS-based is greater than one of P7 because the former has 31 output signals, while the latter has 22 output signals. As a result, the number of flip-flops is increased and the number of resources is approximately increased by one-third, while the maximum frequency in both designs is greater than 235 MHz.

ResourcesMACDAFIRRNS (n = 7)RNS (n = 10)
Number of slice registers2826611677671089
Number of slice LUTs128520717211055
Number of occupied slices5818860240358
Number of DSP48E1s40400
Number of RAMB18E102201616
Max. operating freq. (MHz)296.38229.83472.59258.86261.028
Min. period (ns)3.3744.3512.0303.8633.831
Estimated total power (mW)8.4466.549.0556.2253.05

Table 5.

The resource use and system performance of the DWT implementation for one-level DB2 implementation.

Table 6 shows a comparison between the DA- and RNS-based one-level DWT implementations when using larger filter banks—that is, DB4 and DB5. It shows that DAA-based implementation occupies a fixed number of RAMB18E1. The number of memory elements of DAA-based implementation is fixed and depends on the word length (Table 2).

ResourcesDA-basedRNS (n = 7)
DB2DB4DB5DB2DB4DB5
Number of slice registers65073778076714411898
Number of slice LUTs5215395687211321677
Number of RAMB18E1222222163240
Max. operating freq. (MHz)232.72205.55223.31258.87265.32258.80

Table 6.

Resource use for the DWT implementation of DB2, DB4, and DB5.

However, as the number of filter taps increases, the memory size is exponentially increased to 2N. By contrast, the number of memory elements that are used in RNS-based implementation is linearly increased as the number of filter taps is increased. Similarly, the number of memories that are used at multilevel DAA-based and RNS-based implementations with the l-level would be an aggregate of levels 1 through l.

4.2. Functionality verification

The discrete wavelet transform was simulated by means of ModelSim simulator. Figure 10 shows that the MAC and DAA have lower latency than other approaches. It depicts that the FIR- and RNS-based of P7 and P10 implementations lag behind MAC and DAA by four clock cycles.

Figure 10.

The output and latency of one-level DWT using a ModelSim simulator when a sin wave is applied. Each clock cycle is 10 ns.

4.3. Precision analysis

We carried out the precision analysis for the first and DWT levels, and the result is presented in Table 7. The output bit precision is set to Q5,16 for all implementations. Table 7 shows the maximum performance based on the signal-to-noise-ratio (SNR) and peak-signal-to-noise-ratio (PSNR). For P7, we could not achieve a better accuracy with the specified scaling factors because y + z = 19 < (3 ∗ 7) + 1 = 22. However, both DAA- and RNS-based approaches offer high-signal quality with a peak signal-to-noise ratio (PSNR) of 73.5 and 56.5 dB, respectively. Figure 11 shows the effect of changing the scaling factors of P10 for DB2 RNS-based approach. The input scaling factor is increased from 8 to 13 bit and the filter scaling factor is increased from 11 to 18. As expected, lower scaler factors produce PSNR equal to 56 dB, whereas the maximum PSNR equal to 84 is obtained when y = 12 and z = 16.

ResourcesFIRMACDAA-basedRNS-based
P7P7
Input precisionQ5,16Q5,16Q5,16y = 8y = 8
Coefficients precisionQ0,12Q1,15Q0,15z = 11z = 11
Internal word length22 bit22 bitNA22 bit31 bit
SNR (dB)83.278.770.453.4154.78
PSNR (dB)86.381.873.556.557.9

Table 7.

The SNR and PSNR values of different DWT implementations.

Figure 11.

The impact of input and wavelet filter scaling factors of one-level RNS-based implementation with respect to P10 and P13 moduli sets on PSNR.

4.4. Discussion

Hardware availability and system performance requirements are critical for selecting the appropriate architecture of the embedded platform. The number of DWT levels, filter taps, and word length has a substantial influence on the performance of the design and complexity.

Increasing the number of DWT levels has roughly the same effect on the operating frequency. Because the only change between the RNS-based with P7 or P10 implementations is the output signal width, and the maximum operating frequencies slightly change. Furthermore, the one-level DB2 filter bank was designed with maximum operating frequencies of 232 and 258 MHz for DAA- and RNS-based approaches, respectively. However, all high-frequency implementations introduce a latency of at least 10 clock cycles for one-level DA-based DWT.

Another critical parameter that affects the DWT performance is the filter order. DAA-based implementation outperforms the RNS-based with at most 10 taps. When the number of taps increases, the number of memory units and binary adders within the RNS-based implementation constantly increases, and the size is not affected as shown in Table 2. The memory requirement for DAA-based implementation is exponentially increased as the number of filter taps increases.

In addition, the two approaches have different memory content. Whereas the memory content of DAA-based implementation is consistent and identical, the memory content of RNS-based varies from tap to tap. This is obvious because each memory 590 stores the multiplication values of each filter coefficient by the moduli set.

The word length determines the number of occupied memory in both implementations. As the word length increases, the number of memory within the DAA- and RNS-based approaches increases linearly by w and w∗log2(w), respectively. Furthermore, we could not neglect the effect of output word length on the accuracy and the internal structure. The DAA-based approach requires large memories to have high precision. By contrast, RNS-based approach could achieve high precision with adopting the scaling factors, which do not require any change to the design, except updating memory contents.

5. Conclusion

In this chapter, we addressed the effect of multiplierless DWT implementations, which have a substantial impact on the overall performance of the design and resource availability. We presented DAA- and RNS-based implementations of DWT and compared them with the MAC-based approach. The former approaches are multiplierless architectures that intensively use memory to speed up the entire processing time.

Given implementation examples for experimental verifications and analysis, the approaches were simulated using Simulink and validated on a Xilinx Virtex 6 FPGA platform. The co-simulation results have also been verified and compared with the simulation environment. The complexity and optimization of multi-level DWT with respect to hardware structure provides a foundation for employing an appropriate algorithm for high-performance applications, such as in cognitive communication when combining the DWT analysis with machine-learning algorithms.

© 2018 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Husam Alzaq and Burak Berk Üstündağ (November 5th 2018). A Comparative Performance of Discrete Wavelet Transform Implementations Using Multiplierless, Wavelet Theory and Its Applications, Sudhakar Radhakrishnan, IntechOpen, DOI: 10.5772/intechopen.76522. Available from:

chapter statistics

284total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Application of Wavelet Decomposition and Phase Space Reconstruction in Urban Water Consumption Forecasting: Chaotic Approach (Case Study)

By Peyman Yousefi, Gholamreza Naser and Hadi Mohammadi

Related Book

First chapter

Scalable Video Coding

By Z. Shahid, M. Chaumont and W. Puech

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us