 Open Access
 Total Downloads : 692
 Authors : Subhashrahul S, Pradeep S Kumar
 Paper ID : IJERTV1IS5154
 Volume & Issue : Volume 01, Issue 05 (July 2012)
 Published (First Online): 02082012
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
2D Discrete Wavelet Transform
2D DISCRETE WAVELET TRANSFORM
SUBHASHRAHUL S* AND PRADEEP S KUMAR
A 2D discrete wavelet transform hardware design based on 2s complement design based architecture is presented in this paper. We have proposed based on arithmetic for low complexity and efficient implementation of 2D discrete wavelet transform. The 2s complement design based technique has been applied to reduce the number of full adders. This architecture is suitable for high speed on line applications, the most important one being image processing. With this architecture the speed of the 2D discrete wavelet transform is increased. It has 100% hardware utilization efficiency.
Keywords 2D Discrete wavelet transform (DWT), One, Two, Three Level, 2s complement design scheme, Xilinx simulation.

Wavelets, based on the timescaling representations provide an alternative to the timefrequency representation in signal processing domain. The shifting (or translation) and the scaling (or dilation) are unique to wavelets. The wavelet is a kind of bases which are generated by dilation and translation of a function [1], [2]. The wavelet analysis method has a good ability at localizing signal in both time and frequency plane[4].Due to the characteristic of flexible TF decomposition, 2D DWT has also been widely used in many applications, especially in image and video coding, speech and audio coding, speech enhancement, speech recognition, hearing aid and digital commutation [2],[3],[4].
In this paper, in the simplest form, the bitlevel multiplication of two number can be performed by shift and add operation. It has been observed that the complexity of a shiftadd type signed multiplier is depends on the number of ones of the 2s complement representation of the multiplicand number with the shifted partial sum whereas the zeros will only shift the partial sum. It is assumed that the shifting does not required any hardware as it can be done by hardwiring. The number of ones of the 2s complement number, therefore, will determine the numbers of full adder (FA) required implementing the multiplier.
Comparing the 2D DWT with the 1D DWT, we find that the difference is that in the 1D DWT the range of operation is halved with a change in decomposition level j, while in the 2 D DWT the range of operation is always the whole frame. So as the operation range halved with the increase in decomposition level, the above structure structure can perform the 1D DWT easily.
In this paper, we have introduced a new architecture for the 2 D discrete wavelet transform using 2s complement based technique. The algorithm for the tree structure of 2D discrete wavelet transform is analyzed in the section II. The low complexity design for 2D DWT in the section III. 2s complement design for 2D DWT in the section IV. Proposed architecture for 2s complement design for 2D DWT in the section V. Simulation result and conclusion in the section VI and VII

The model used in [5] to implement the tree structure of 2D discrete wavelet packet transform (DWT) is based on the filtering process. Figure1 depicted a complete 3level 2DWT. In this figure G and H are the high pass and low pass filter respectively.
Computation period is the number of the input cycles for one time produces output samples. In general, the computation period is M= for a jlevel 2D DWT. The period of the 3level computation is 8. Figure 1, The Sub band Coding Algorithm As an example, suppose that the original signal X[n] has N sample points, spanning a frequency band of zero to rad/s. At the first decomposition level, the signal passed through the high pass and low pass filters, followed by subsampling by 2. The output of the high pass filter has N/2 sample points (hence half the time resolution) but it only spans the frequencies /2 to rad/s (hence double the frequency resolution).
The output of the lowpass filer also has N/2 sample points, but it spans the other half of the frequency band, frequencies from 0 to /2 rad/s. Again low and highpass filter output passed through the same low pass and high pass filters for further decomposition. The output of the second low pass filter followed by sub sampling has N/4 samples spanning a
frequency band of 0 to /4 rad/s, and the output of the second high pass filter followed by sub sampling has N/4 samples spanning a frequency band of /4 to /2 rad/s. The second high pass filtered signal constitutes the second level of 2D DWT coefficients. This signal has half the time resolution, but twice the frequency resolution of the first level signal. This process continues until two samples are left. For this specific example there would be 3 levels of decomposition, each having half the number of samples of the previous level.
2
G
N/8
Where x(n) is the input and [] & [] are respectively the lowpass and highpass 2D DWT coefficients, h[n] and g[n] are respectively, the lowpass and highpass filter coefficients. We have assumed the Daubechies four tap (Daub4) filter coefficients for the low pass filter proposed design. However, similar type of design can be derived for other type of wavelet filters as well. The Daub4 lowpass filter coefficients are taken from [7]. The corresponding highpass filter coefficients are calculated using the following relation:
() = (1) ( ) (3)
G
2
G N/2
N/4
2
Filter
Coefficient
Decimal Value
2s Complement
h(0)
0.4829629131
0.01111011
h(1)
0.8365163037
0.11010110
h(2)
0.2241438680
0.00111001
h(3)
0.129409522
1.11011111
g(0)
0.129409522
1.11011111
g(1)
0.224143868
1.11000111
g(2)
0.836516303
0.11010110
g(3)
0.482962913
1.10000101
H
N/8
2
G
2
N/8
Table1: Low and highpass Daub4 filter coefficients.
N
sample
2
H
H
2
2
G
N/2
2
H
N/4
H
G
N/4
H
G
N/4
H
N/8 N/8
2
2
2
N/8
2
2
N/8 N/8
Where, h(n) and g(n) are, respectively, the low and highpass filter coefficients. N is the filter order. The 8 bit 2complement representation of the low and highpass filter coefficient is given in table1. Equation can be rewritten fourtap FIR filter as:
Figure1. 3 Levels for DWPT
The 2D DWT of the original signal is then obtained by concatenating all coefficients starting from the last level of decomposition (remaining two samples, in this case). The DWT will then have the same number of coefficients as the original signal.

DWPT computation is nothing but twochannel FIR filter computation. Lowpass and highpass down sampled filter computations are performed on the input to calculate the DWPT coefficients. Lowpass down sampled filter is the average between two samples and highpass filter is the difference b/w two samples. The DWPT algorithms for 1 level decomposition are given as;
= 0 + 1 1 + 2 3 3 () (4)
= 0 + 1 1 + 2 2 3 3 () (5) Where 1 operator represents one sample delay in Zdomain.
Each of the multiplier unit is replaced with shifters and adders/subtraction for CSD implementation of DWPT. The constant multiplication factors of [5] are replaced with shift and adder/subtraction operation and rewritten as
Low pass filter
Yh [k] = [x(n)>>2 + x(n)>>3 + x(n)>>4 + x(n)>>5 + x(n)>>7
+ x(n)>>8] + [x(n1) >> 1 + x(n1) >> 2 + x(n1)
>> 4 + x(n1) >> 6 + x(n1) >> 7] + [x(n2)>>3 +
x(n2)>>4 + x(n2)>>5 + x(n2)>>8] + [x(n3)>>1
[] = [2 ]
[] = [2 ]
(1)
(2)
+ x(n3)>>2 + x(n3)>>4 + x(n3)>>5 + x(n3)>>6
+ x(n3)>>7 + x(n3)>>8] (6)
High pass filter
Yg [k] = [x(n)>>1 + x(n)>>2 + x(n)>>4 + x(n)>>5 + x(n)>>7
+ x(n)>>8] + [x(n1) >> 1 + x(n1) >> 2 + x(n1)
>> 6 + x(n1) >> 7 + x(n1) >> 8] + [x(n2)>>1 +
x(n2)>>2 + x(n2)>>4 + x(n2)>>6 + x(n2)>>7] +
[x(n3)>>1 + x(n3)>>6 + x(n3)>>8] (7)Figure2 depicted a complete 3level 2s complement design based 2DWT In this paper, the original signal X[n] has N sample points, is passed through 1Ã—2 demultipler. When select line is 0 then we get even sample and when select line is 1 then we get odd sample. After that we have passed these samples through 2s complement design based lowpass filter, same process with highpass filter. Now we get N/2 sample at the first decomposition level output of 2s complement design based lowpass ( ) and highpass filter ( ). At the second
decomposition level, the output of 2s complement design
based lowpass and highpass filter passed through a register unit. Now the output of register unit passed through mux. When the select line 0, we get 2s complement design based lowpass filter output and when the select line 1, we get 2s complement design based highpass filter. Now we have passed mux output through 2s complement design based low pass filter then we get & output now same process applied with the 2s complement design based highpass filter
we get & .
Reg Unit
H
1Ã—
At the third decomposition level, the time period is doubled and frequency will be half, and the output of 2s complement design based lowpass and highpass filter is passed through a register unit. Now the output of register unit is passed through mux. When the select line is 00, we get 2s complement design based lowpass filter output , the select line is 01, we get , the select line is 10 we get and the select line is 11 we get . Now finally we have passed mux output through 2s complement design based low pass filter and high pass filter we get , , , and , ,
, .
We have simulated this architecture in Xilinx 8.2i. The result is shown in Table2 and Table3. Table2 shows the multiplier based DWPT and Table3 shows the 2s Complement based design. In multiplier based technique the number is slices is more than the 2s Complement based technique but time is increased. The area and power requirement is also reduced. Here the comparison shows first level decomposition to second level decomposition and second level to third level decomposition the number of slices, number of LUTs and flipflops reduced significantly and time is little bit increased. This is the main advantage of proposed architecture.
Table2: Multiplied based technique
G
1Ã—
Number of slices 
Number of slice flip flop 
Number of 4 input LUTs 
Required time() 

First 
123 
18 
232 
11.069 
Up to Second 
321 
77 
599 
17.422 
Up to Third 
592 
172 
1084 
24.930 
Reg unit
Mux unit
Mux unit
2s com.
2s com.
Reg unit
Reg unit
Table3: Proposed architecture (2s complement based design)
Mux unit
Mux unit
2s com.
2s com.
Number of slices 
Number of slice flip flop 
Number of 4 input LUTs 
Required time() 

First 
106 
21 
189 
11.563 
Up to Second 
229 
63 
414 
18.757 
Up to Third 
389 
127 
684 
25.035 
Figure2. 3Level 2s complement design based 2D DWT, 2s com. G and 2s com. H means the 2s complement design
based low & highpass filter.
The main objective of this work was to design a processor specialized for 2D discrete wavelet transforms that could be used for image processing, such as image compression. In this paper we have used 2s complement design based number system to represent the filter coefficient of the wavelet filter
with minimum number of ones consequently; Then we applied the 2s complement design based technique to further reduce the power and area. In this architecture the used of the low and high pass filter. Low pass filter is the average between two sample and high pass filter is the difference between two samples. So minimum 1015% reduces the power and 1020 % reduces the area in Multiplier less based design technique (2s complement design based).
Reference

S.G. Mallat, A Theory for Multiresolution Signal Decomposition: The Wavelet Representation, IEEE Trans. on Pattern Analysis on Machine Intelligence, 110. July1989, pp. 674693.

O.Rioul, and M. Vetterli, Wavelets and Signal Processing. IEEE Signal Processing Magazine, October 1991, pp. 1438.

Z. Xiong, K. Ramchandran, and M.T. Orchad, wavelet packet image Coding using spacefrequency quantization, IEEE Trans. Image Processing, vol. 7,pp. 160174, 1998.

O. Farooq and S. Datta, Mel filterlike admissible wavelet packet structure for speech recognition, IEEE Signal Process. Lett. vol. 8, no.7, pp. 196198, jul.2001.

G. Strang and T. Nguyen. Wavelets and Filters. WellesleyCambridge Press. 1977.

K.K.Parhi, VLSI Digital Signal Processing. New York: Wiley, 1998.

I. Daubechies, and W. Sweldens, Factoring wavelet transform into lifiting schemes, Journal of Fourier Analysis and Application, vol.4 pp247269, 1998.

M.M.Peiro, E.I.Boemo and L.Wahnammar, Design of highspeed multiplier less filters using a nonrecursive signed common sub expression algorithm, IEEE Trans. Circuit and Syst.II, vol.49 no.3 pp. 1962003, 2002.

R. Mukesh and A,P. Vinod, A new common subexpression algorithm for implementing lowcomplexity FIR filter in software defined radio receivers , in processing of IEEE International Symposium on Circuit and System, vol.4, pp.45154518, May 2124 , 2006, Greece.