Examples of Discrete Transforms (Mertins - Signal Analysis (Revised Edition))

Signal Analysk: Wavelets, Filter Banks, Time-Frequency Transforms andApplications. Alfred MertinsCopyright 0 1999 John Wiley & Sons LtdPrint ISBN 0-471-98626-7 ElectronicISBN 0-470-84183-4Chapter 4Examples ofDiscrete TransformsIn this chapter we discuss the most important fixed discrete transforms. Westart with the z-transform, whichis a fundamental tool for describing theinput/output relationships in linear time-invariant (LTI) systems. Then wediscuss several variants of Fourier series expansions, namely the discrete-timeFourier transform, thediscrete Fourier transform (DFT), and thefast Fouriertransform (FFT). Theremainder of this chapter is dedicated to other discretetransforms that are of importance in digital signal processing, such as thediscrete cosine transform, the discrete sine transform, the discrete Hartleytransform, and the discrete Hadamard and Walsh-Hadamard transform.4.1The ,+TransformThe z-transform of a discrete-time signal z ( n ) is defined asn=-CQNote that the time index n is discrete, whereas z is a continuous parameter.Moreover, z is complex, even if z ( n ) is real.

Further note that for z = ejw thez-transform (4.1) is equal to the discrete-time Fourier transform.7576Chapter 4. Examples o f Discrete TransformsIn general, convergence of the sum in (4.1) depends on the sequence z ( n )and the value z. For most sequences we only have convergence in a certainregion of the z-plane, called the region of Convergence (ROC). The ROC canbe determined by finding the values r for whichcccIz(n)< m.n=-ccProof. With z = r ej4 we haveIn=-ccMn=-ccThus, IX(z)I is finite if z(n)r-" is absolutely summable. 0The inverse z-transform is given byz(n) =1f X(z)z"-'dz.32n c(4.4)The integration has to be carried out counter-clockwise on a closed contourC in the complex plane, which encloses the origin and lies in the region ofconvergence of X (2).Proof of (4.4). We multiply both sides of (4.1) with zk-' and integrateover a closed contour in a counter-clockwise manner:774.1. The z-TransformInvoking the Cauchy integral theoremfinally yields (4.4).

0Reconstruction formulaesimpler than (4.4) can be foundfor rational X ( z ) ,that is forbo b1z-lbzz-’ . . .X ( z )=a0a l z - l + azz-’ . . .‘+++Methods based on the residue theorem, on partial fraction expansion, and ona direct expansion of X ( z ) into a power series in z-l are known. For moredetail, see e.g. [80, 1131.The simplest example is the z-transform of the discrete impulse:1, n = O0, otherwise.S(n) =We havecccS(n) t)S(n)z-n = 1.n=-ccFor a delayed discrete impulse it follows thatIn the following, the most important properties of the z-transform will bebriefly recalled.

Proofs which follow directly from the definition equation ofthe z-transform are omitted.Linearity).(W= az(n)+py(n)V ( z )= a X ( z )+ P Y ( z ) .t)(4.9)Convolution).(W= z ( n ) * y ( n ) t)V ( z )= X ( z ) Y ( 2 ) .(4.10)78Chapter 4.

Examples o f Discrete TransformsPro0f.00-00k=-m=m=--00X ( z )Y ( z ) .Shifting.(n-no)c n oX(z).= z(n)*S(n-no)and usingThis result is obtained by expressing w(n)as ).(Wthe convolution property above.Scaling/Modulation. For any real or complex aan .(n)Xt)(4.11)# 0, we have(3.(4.12)This includes a = eJwsuch that(4.13)Time InversionXX(.)t)(;).(4.14)Derivatives(4.15)Pro0f.c00=n z ( n )2-"n=-cc3:nx(n).794.1. The z-TransformConjugation. Given the correspondence z ( n ) t)X ( z ) ,we have.*(n) H X * ( z * ) .=(g(4.16).(n) [ P ] *n=-ccccX ( z ) , we haveParaconjugation.

Given the correspondence ).(XX*(+)X(z),t)t)X ( z ) = [ X ( z ) ] *I l a l = l .where(4.17)That is, X ( z ) is derived from X ( z ) by complex conjugation on the unit circle.Proof.X(z) =[- p ( i r ) z - ~ ]*114=1= C.*(ir)zkk=Cn.*(4.18)(-n)z-"$X*(-n).For real signals z(n), it follows that.(-n)X ( z )= X(z-1).t)(4.19)Multiplication with cos o n and sin on. If z ( n ) t)X ( z ) ,thencoswn ).(X1[X(ejwz) x(e-jWz)]2+(4.20)j [ X ( e j w z )- x ( e - j W z ) ].(4.21)t)-andsinwn ).(Xt)-280Chapter 4. Examples o f Discrete TransformsThis follows directly from (4.13) by expressing coswn and sinwn via Euler'sformulae cos a = +[ej" + e-j"] and sin a = i [ e j a- e-j"].Multiplication in the Time Domain.

Let z ( n ) and y(n) be real-valuedsequences. Then~ ( n=)~ ( ny(n))V ( Z )=(4.22)t)where C is a closed contour that lies within the region of convergence of bothX ( z ) and Y ( k ) .Proof. We insert (4.4) intoc00V ( z )=.(n) y(n) . K n .(4.23)n=-mThis yieldsUsing the same arguments, we may write for complex-valued sequences).(W4.2=).(Xy*(n)1f X ( v ) Y *(5)v-' dv.V ( 2 )= -t)2Tl c(4.25)The Discrete-Time FourierTransformThe discrete-time Fourier transform of a sequence ).(Xis defined as00X(ej') =Ce-jwn.(4.26)n=-mDue to the 2~-periodicity of the complex exponential, X(ej") is periodic:X ( e j w ) = X ( e j ( , + 2.rr)). If ).(Xis obtained by regularsampling of a814.2. The Discrete-Time Fourier Transformcontinuous-time signal z c t ( t ) such that z ( n ) = z,t(nT), where T is thesampling period,W can be understood as the normalized frequencyW = 27r f T .(4.27)Convolution(4.28)Multiplication in the Time Domain27rz(n)y(n) w1X ( e j w )* Y ( e j w ) = 27r-S"X ( e j ( w - V ) ) Y ( e j V ) d v(4.29).Reconstruction.

If the sequence z(n) is absolutely summablem)), it can be reconstructed from X ( e j w ) via(X El 1 (-m,S"z(n) = 27rX ( e j w ) ejwn dw.(4.30)-rThe expression (4.30) is nothing but the inverse z-transform, evaluated on theunit circle.Parseval's Theorem. As in the case of continuous-time signals, the signalenergy can be calculated in the time and frequency domains. If a signal z ( n )is absolutely and square summable ( X E l 1 (-m, m) n &(-m, m)),then(4.31)Note that the expression (4.26) may be understood as a series expansionof the 27r-periodic spectrum X ( e j " ) , where the values z(n) are thecoefficientsof the series expansion.82Chapter 4.

Examples o f Discrete Transforms4.3TheDiscrete FourierTransform (DFT)The transform pair of the discrete Fourier transform (DFT) is defined ascN-lX(k) =.(n)w;kn=O5.(n)=(4.32)c1 N-lx(k)wink)k=O(4.33)Due to the periodicity of the basis functions, the DFT can be seen as thediscrete-time Fourier transform of a periodic signal with period N .(4.35)the above relationships can also be expressed asx=wxt)x1=-WHX.N(4.36)We see that W is orthogonal, but not orthonormal.The DFT can be normalized as follows:a = +H x t ) x = 9 a ,where19 = -WH.aThe columns of 9,(4.37)(4.38)834.3. The Discrete Fourier Transform (DFT)then form an orthonormal basis as usual.We now briefly recall the most important properties of the DFT. For anelaborate discussion of applications of the DFT in digital signal processingthe reader is referred to [113].Shifting. A circular time shift by p yields+x p ( n ) = ~ ( ( np ) mod N)tX,(m)=cN-lx((n+ p ) mod N)WGm(4.39)n=ON-li=O=W,""X(m).Accordingly,Wp).(XcN-lt)+x ( ~ ) W $ ~=+X~( )( m Ic) mod N ) .(4.40)n=OMultiplicationandCircularConvolution.Fourier transform (IDFT) ofFor the inverse discretewe have(4.41)That is,a multiplication in the frequency domain meansa circular convolution84Chapter 4.

Examples o f Discrete Transformsin the time domain. Accordingly,cN-l~ ( nm(n))t)X l ( n )X z ( ( m - n )modN).(4.42)n=OComplex Conjugation. Conjugation in thetimeyields2*(n)X * ( N - n)or frequencydomains(4.43)and2* ( N-n)X * (n).(4.44)Relationship between the DFT and the KLT. The DFT is related tothe KLT due to the fact that it diagonalizes any circulant matrix(4.45)In order to show the diagonalization effect of the DFT, we consider a lineartime-invariant system (FIR filter) with impulse responseh ( n ) ,0 5 n 5 N - 1which is excited by the periodic signal WN"/fl.The output signal y(n) isgiven by(4.46)4.4.

The Fast Fourier Transform85Comparing (4.47) with (4.45) and (4.37) yields the relationshipH(k)p, =Hp,,k=O, 1,.. . , N - l .(4.48)Thus, the eigenvalues X k = H ( k ) of H are derived from the DFT of the firstcolumn of H . The vectors p,, k = 0,1, . .

. , N - 1 are the eigenvectors of H .We haveaHHa= diag{H(O), H(1),. . . ,H ( N4.4-l)}.(4.49)The Fast Fourier TransformFor a complex-valued input signal ~ ( nof) length N the implementation ofthe DFT matrix W requires N 2 complex multiplications. The idea behindthe fast Fourier transform (FFT) is to factorize W into a product of sparsematrices that altogether require a lower implementation cost than the directDFT.

Thus, the FFT is a fast implementation of the DFT rather thanadifferent transform with different properties.Several concepts for the factorization of W have been proposed in theliterature. We will mainly focus on the case where the DFT lengthis a powerof two. In particular, we will discuss the radix-2 FFTs, the radix-4 FFT, andthe split-radix FFT.

Section 4.4.5 gives a brief overview of FFT algorithmsfor cases where N is not a power of two.Wewill only discuss the forward DFT. For the inverse DFT a similaralgorithm can be found.4.4.1Radix-2Decimation-in-TimeFFTLet us consider an N-point DFT where N is a power of two, i.e. N = 2K forsome K E N. The first step towards a fast implementation is to decomposethe time signal ).(Xinto its even and odd numbered components86Chapter 4 .

Examples of Discrete TransformsThe DFT can be written asN-ln=Oc%-l=ZL(n)W?k+8-1c.(.)W,(2n+l)kn=On=O%-l=c~(n)W$,+W; ~ u ( ~ ) W $k ~= 0,1,,..., N-1.n=On=O(4.51)In the last step the properties W z k = W,!$2 and W (,2 n + l ) k = W;were used. The next step is to write (4.51) for k = 0,1, . . . , $ - 1 as+X ( S ) = U ( S ) WiV(Ic), 5 = O , l , . . .,2-1(4.52)withc--T 1V(k) =N25 = 0 , 1 , . . ., - - 1u(n)W$,,n=O(4.53)--T 1V(k) =N25 = 0 , 1 , .