2-D Discrete Wavelet Transform

2-D Discrete Wavelet Transform

2-D DISCRETE WAVELET TRANSFORM

SUBHASHRAHUL S* AND PRADEEP S KUMAR

A 2-D 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 2-D 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 2-D discrete wavelet transform is increased. It has 100% hardware utilization efficiency.

Keywords- 2-D Discrete wavelet transform (DWT), One, Two, Three Level, 2s complement design scheme, Xilinx simulation.

1. Wavelets, based on the time-scaling representations provide an alternative to the time-frequency 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, 2-D 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 bit-level multiplication of two number can be performed by shift and add operation. It has been observed that the complexity of a shift-add 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 2-D DWT with the 1-D DWT, we find that the difference is that in the 1-D 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 1-D 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 2-D discrete wavelet transform is analyzed in the section II. The low complexity design for 2-D DWT in the section III. 2s complement design for 2-D DWT in the section IV. Proposed architecture for 2s complement design for 2-D DWT in the section V. Simulation result and conclusion in the section VI and VII

2. The model used in [5] to implement the tree structure of 2-D discrete wavelet packet transform (DWT) is based on the filtering process. Figure1 depicted a complete 3-level 2-DWT. 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 j-level 2-D DWT. The period of the 3-level 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 low-pass 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 high-pass 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 2-D 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 low-pass and high-pass 2-D DWT coefficients, h[n] and g[n] are respectively, the low-pass and high-pass filter coefficients. We have assumed the Daubechies four tap (Daub-4) 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 Daub-4 low-pass filter coefficients are taken from [7]. The corresponding high-pass 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 high-pass Daub-4 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 high-pass filter coefficients. N is the filter order. The 8 bit 2complement representation of the low and high-pass filter coefficient is given in table1. Equation can be rewritten four-tap FIR filter as:

   Figure1. 3- Levels for DWPT

   The 2-D 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.

3. DWPT computation is nothing but two-channel FIR filter computation. Low-pass and high-pass down sampled filter computations are performed on the input to calculate the DWPT coefficients. Low-pass down sampled filter is the average between two samples and high-pass 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 Z-domain.

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(n-1) >> 1 + x(n-1) >> 2 + x(n-1)

>> 4 + x(n-1) >> 6 + x(n-1) >> 7] + [x(n-2)>>3 +

x(n-2)>>4 + x(n-2)>>5 + x(n-2)>>8] + [x(n-3)>>1

[] = [2 ]

[] = [2 ]

(1)

(2)

+ x(n-3)>>2 + x(n-3)>>4 + x(n-3)>>5 + x(n-3)>>6

+ x(n-3)>>7 + x(n-3)>>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(n-1) >> 1 + x(n-1) >> 2 + x(n-1)

>> 6 + x(n-1) >> 7 + x(n-1) >> 8] + [x(n-2)>>1 +

x(n-2)>>2 + x(n-2)>>4 + x(n-2)>>6 + x(n-2)>>7] +

Figure2 depicted a complete 3-level 2s complement design based 2-DWT 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 low-pass filter, same process with high-pass filter. Now we get N/2 sample at the first decomposition level output of 2s complement design based low-pass ( ) and high-pass filter ( ). At the second

decomposition level, the output of 2s complement design

based low-pass and high-pass 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 low-pass filter output and when the select line 1, we get 2s complement design based high-pass 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 high-pass 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 low-pass and high-pass 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 low-pass 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 Table-2 and Table-3. Table-2 shows the multiplier based DWPT and Table-3 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 flip-flops reduced significantly and time is little bit increased. This is the main advantage of proposed architecture.

Table2: Multiplied based technique

G

1×

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.

Figure2. 3-Level 2s complement design based 2-D DWT, 2s com. G and 2s com. H means the 2s complement design

based low & high-pass filter.

The main objective of this work was to design a processor specialized for 2-D 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 10-15% reduces the power and 10-20 % reduces the area in Multiplier less based design technique (2s complement design based).

Reference

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

2. O.Rioul, and M. Vetterli, Wavelets and Signal Processing. IEEE Signal Processing Magazine, October 1991, pp. 14-38.

3. Z. Xiong, K. Ramchandran, and M.T. Orchad, wavelet packet image Coding using space-frequency quantization, IEEE Trans. Image Processing, vol. 7,pp. 160-174, 1998.

4. O. Farooq and S. Datta, Mel filter-like admissible wavelet packet structure for speech recognition, IEEE Signal Process. Lett. vol. 8, no.7, pp. 196-198, jul.2001.

5. G. Strang and T. Nguyen. Wavelets and Filters. Wellesley-Cambridge Press. 1977.

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

7. I. Daubechies, and W. Sweldens, Factoring wavelet transform into lifiting schemes, Journal of Fourier Analysis and Application, vol.4 pp-247-269, 1998.

8. M.M.Peiro, E.I.Boemo and L.Wahnammar, Design of high-speed multiplier less filters using a non-recursive signed common sub expression algorithm, IEEE Trans. Circuit and Syst.II, vol.49 no.3 pp. 196-2003, 2002.

9. R. Mukesh and A,P. Vinod, A new common sub-expression algorithm for implementing low-complexity FIR filter in software defined radio receivers , in processing of IEEE International Symposium on Circuit and System, vol.4, pp.4515-4518, May 21-24 , 2006, Greece.