• Author / Uploaded
• Thiruselvan Manian

• Categories
• Transformada discreta de Fourier
• Procesamiento de la señal
• Álgebra abstracta
• Física teórica
• Álgebra lineal

Citation preview

Finite-Length Discrete Transforms

1

Orthogonal Transforms

 Let x[n] denote a length-N timeχ [k ]with domain sequence denoting the coefficient of its Npoint orthogonal transform. The general form of the orthogonal transform pair is of the form N−1

x [ k ]=

∑

x [ n ] ψ [ k, n ] , 0≤ k ≤ N − 1

N− 1

∑

n=0

{ }

ψ [ k, n ] ψ [ l,n ] = 1, l=k 0 l≠ k

 The above condition are said to be orthogonal to each other

n=0

1 x[ n]= N

N− 1

∑

x[n ] ψ [ k, n ], 0≤ k≤ N − 1

 The verification of this equation in book page 200

n=0

 Referred to as the analysis and synthesis equation respectively. 2

The Discrete Transform

 Definition - The simplest relation between a length-N sequence x[n], defined for 0≤n≤N-1, and its DTFT X(ejω) is obtained by uniformly sampling X(ejω) on the ω-axis between 0≤ω≤2π at ωk= 2πk/N, 0≤k≤N-1  From the definition of the DTFT we thus have

 Note: X[k] is also a length-N sequence in the frequency domain  The sequence X[k] is called the discrete Fourier transform (DFT) of the sequence x[n]  Using the notation WN= e-j2π/N the DFT is usually expressed as: N−1

N−1

X [ k ]=

X [ k ]= ∑ x[ n] e n=0

− j2πk /N

, 0≤ k≤ N− 1

∑

n=0

x [ n ] W kn N , 0≤ k ≤ N − 1

The Discrete Transform  The inverse discrete transform (IDFT) is given by 1 x [ n ]= N

N− 1

∑

Fourier

X [ k ] W −N kn , 0≤ n≤ N − 1

 Example - Consider the length-N sequence defined for 0 ≤ n ≤ N-1

x[n]= cos(2π r n N ), 0≤ n≤ N− 1

k=0

 As can be seen from the above expression, the inverse DFT x[n] can be a complex sequence even when the DFT X[k] is real sequence.

X [k ]¿

 Where is r is an integer in the range 0 ≤ n ≤ N-1

 Using a trigonometric identity, we can write as

1 j2πrn /N − j2πrn /N x [ n ]= (e +e ) 2 1 (W −Nrn +W rn N) 2 4

The Discrete Transform The N-point DFT of g[n] is thus given by N−1

X [ k ]=

∑

Matrix Relations  The DFT samples defined by

g [ n ] W kn N

n=0

1 2

N− 1

(∑

W −N( r − k ) n +

n= 0

N−1

N−1

∑

)

W (Nr+k ) n

n= 0

0≤ k ≤ N − 1

∑

W −N( k− ℓ )n=

n=0

we get

{

N,fork − ℓ=rN,ran int eger 0,otherwise

{

N /2, fork=r G[ k ]= N /2, fork=N − r 0 ，otherwis 0≤ k ≤ N − 1

∑ x[ n]W kNn , 0≤ k≤ N − 1 n=0

can be expressed in matrix form as

X=DN x

Making use of the identity N− 1

X [ k ]=

}

}

Where X is the vector composed of the N DFT samples and x is the vector of N input samples

X=[ X [ 0] X [ 1]⋯ X [ N− 1]]t x=[ x[0 ] x[1]⋯ x[ N− 1]]t 5

The Discrete Transform

and DN is the N×N DFT matrix given by 1 1

1 W 1N

1 W 2N

⋯ ⋯

W (NN − 1)

DN = 1 ⋮

W 2N ⋮

W 4N ⋮

⋯ ⋱

N− 1) W 2( N ⋮

W (NN − 1 )

N − 1) W 2( N

⋯

W (NN − 1)

[

1

1

2

 Likewise, the IDFT relation given by

1 x [ n ]= N

N− 1

∑

k=0

X [ K ]W −Nkn , 0≤ n≤ N − 1

]

can be expressed in matrix form as

x=D−N1 X where D−N1 is the N×N DFT matrix Where 1 1

1 W −N1

1 W −N2

⋯ ⋯

DN = 1 ⋮

W −N 2 ⋮

W −N4 ⋮

⋯ ⋱

−1

[

1 W −N( N − 1) W −N2( N − 1) ⋯

1 W −N( N − 1 ) W −N2( N − 1) ⋮ 2

W −N( N − 1)

]

Note

D−N1 =

1 D N N

6

Relation Between the DTFT and the DFT and Their Inverses Relation with DTFT The FT e

jωn

of length-N sequence x[n] ∞

jω

X (e )=

∑

Numerical Computation of the DTFT using the DFT  A practical approach to the numerical computation of the DTFT of a finite-length sequence.

− jωn

x[ n]e

n=− ∞ N− 1

= ∑ x[ n]e− jωn

 Let X(ejω) be the DTFT of a length-N sequence x[n]

n=0

 limit the extent of the summation to N points and evaluate the continuous function of frequency at N equally spaced points

 We wish to evaluate X(ejω) at a dense grid of frequencies ωk=2πk/M, 0≤k≤M-1,where M >> N:

N− 1

X (e

jω

)∣

2π =X ω= k N

( k ) =X k =

∑

x [ n ]e−

j2πkn/ N

n=0

7

Relation Between the DTFT and the DFT and Their Inverses

X (e

jω k

N−1

)=

∑ x[ n]e n=0

− jωk n

N−1

=

∑ x[ n]e− j2πkn/ M

jω k

X (e )



Thus is essentially an Mpoint DFT Xe[k] of the length-M sequence xe[n]



The DFT Xe[k] can be computed very efficiently using the FFT algorithm if M is an integer power of 2



The function freqz employs this approach to evaluate the frequency response at a prescribed set of frequencies of a DTFT expressed as a rational function in e-jω

n=0

Define a new sequence

{

x e [n]= x[n] ,0≤ n≤ N− 1 0, N≤ n≤ M− 1 Then

X (e

jω k

}

M−1

)=

∑

n=0

x e [ n]e− j2πkn/ M

Relation Between the DTFT and the DFT and Their Inverses

DTFT from DFT by Interpolation  The N-point DFT X[k] of a length-N sequence x[n] is simply the frequency samples of its DTFT X(ejω) evaluated at N uniformly spaced frequency points

ω=ωk = 2πk /N , 0≤ k≤ N − 1  Given the N-point DFT X[k] of a length-N sequence x[n], its DTFT X(ejω) can be uniquely determined from X[k]

 Thus

X ( e jω )= N− 1

∑

[

1 N

n=0 N− 1

1 N

∑

k= 0

N− 1

∑

x [n ]e− jωn

n=0 N− 1

∑

X [ k ]W −N kn ]e− jωn

k=0 N− 1

X [k] ∑ e

− j( ω− 2πk /N )n

n=0 ⏟ S

5.3 Relation Between the DTFT and the DFT and Their Inverses  To develop a compact expression for the sum S, let

− j(ω− 2πk /N )

r=e  Then

1− r N 1− e− j (ωN − 2πk ) S= = 1− r 1− e− j [ ω− ( 2πk / N ) ] ωN − 2πk sin 2 ⋅ e− j [ω− 2πk / N )][( N − 1)/ 2] ωN − 2πk sin 2N

( (

S= ∑ r n

 From the above

rS= ∑ r n = 1+ ∑ r n +r N − 1 ∑ rn +r N − 1 =S+r N − 1 Or, equivalently,

S− rS=(1− r) S=1− r

Hence

N

) )

Therefore

X (e jω ) 1 N

sin

N− 1

∑

k= 0

X [k] sin

ωN − 2πk 2

( (

ωN − 2πk 2N

) )

⋅ e− j [ω− 2πk/ N ) ][( N − 1)/2 ]

Relation Between the DTFT and the DFT and Their Inverses

Sampling the Fourier Transform   Consider a sequence x[n] with a DTFT X(ejω)

Thus

Y [ k ]=X (e ∞

∑

jω k

)=X (e j2πk / N )

− j2πkℓ / N

x [ ℓ ]e

∞

=

ℓ ＝－ ∞

ℓ ＝－∞

 We sample X(ejω) at N equally spaced points ωk=2πk/N, 0≤k≤N-1 developing the N frequency samples

{X (e jω )} k

 These N frequency samples can be considered as an N-point DFT Y[k] whose N- point IDFT is a length-N sequence y[n]  now jω

X (e )=

∞

∑

ℓ＝－∞

x[ ℓ]e

x [ ℓ ]W kℓN

An IDFT of Y[k] yields

y[ n]=

1 N

1 y [ n ]= N ∞

∑

x[ ℓ ]

ℓ=− ∞

− jωℓ

∑

1 N

N− 1

N−1

∑ Y [k ]W −Nkn

k＝ 0 N−1

∞

∑ ∑

k＝ 0 ℓ=− ∞ N− 1

[

1 N

− kn x[ ℓ ]W kℓ N WN

∑ W −Nk ( n− ℓ) k= 0

]

forr=n+mN ∑ W −Nk ( n− r )= ( 1, 0, otherwise

n＝ 0

Relation Between the DTFT and the DFT and Their Inverses  we arrive at the desired relation ∞

y[ n]=

∑

x[ n+mN ],0≤ n≤ N− 1

 Thus if x[n] is a length-M sequence with M≤N, then y[n]= x[n] , for 0≤n≤N-1

m=− ∞

 Thus y[n] is obtained from x[n] by adding an infinite number of shifted replicas of x[n], with each replica shifted by an integer multiple of N sampling instants, and observing the sum only for the interval 0≤n≤N-1  To apply ∞

y[ n]=

∑

x[ n+mN ], 0≤ n≤ N − 1

m=− ∞

 To finite-length sequences, we assume that the samples outside the specified range are zeros

Example 5.6 – Let {x[n]}={0 1 2 3 4 5} ↑

By

sampling its DTFT X(ejω) at ωk=2πk/4, 0≤k≤3 and then applying a 4-point IDFT to these samples, we arrive at the sequence y[n] given by

y[n]= x[n]+ x[n+4]+x[n-4]

0≤n≤3

i.e. {y[n]}={4 6 2 3} ↑ {x[n]} cannot be recovered from {y[n]}

Circular Convolution

 This operation is analogous to linear  In computing yL[n] we have assumed that both length-N sequence have convolution, but with a subtle been zero-padded to extend their difference lengths to 2N-1  Consider two length-N sequences,  The longer form of y [n] results from L g[n] and h[n], respectively the time-reversal of the sequence h[n] and its linear shift to the right

 Their linear convolution results in a length-(2N-1) sequence yL[n] given  The first nonzero value of yL[n] is by yL[0]= g[0]h[0] ,and the last nonzero value is N−1

y L [n ]=

∑

m=0

g [ m ] h[ n− m] , 0≤ n≤ 2N− 2

yL[2N-2]= g[N-1]h[N-1]

Circular Convolution

Definition:  To develop a convolution-like operation resulting in a length-N sequence yC[n] , we need to define a circular time-reversal, and then apply a circular time-shift

 Since the operation defined involves two length-N sequences, it is often referred to as an N-point circular convolution, denoted as

y[n] = g[n] h[n]  Resulting operation, called a circular convolution, is defined by N−1

y C [ n ]=

∑

g [ m ] h [〈n− m〉N ],

m=0

0≤ n≤ N − 1

 The circular commutative, i.e.

convolution

g[n] h[n] = h[n] g[n]

is

5.4 Circular Convolution

 The N-point circular convolution can be written in matrix form as

[ ][

yC [0] h[ 0] h[ N − 1] h[ N − 2] y C [1] h[ 1] h[ 0] h[ N − 1] h[ 1] h[ 0] yC [2] = h[ 2] ⋮ ⋮ ⋮ ⋮ y C [ N − 1] h[ N − 1] h[ N − 2] h[ N − 3]

⋮ ⋮ ⋮ ⋱ ⋮

][ ]

h[1] g[ 0] h[ 2] g [1] h[3] g[ 2] ⋮ ⋮ h[ 0] g [ N − 1]

 Note: The elements of each diagonal of the N×N matrix are equal  Such a matrix is called a circulant matrix

Tabular Method Consider the evaluation of y[n]= h[n] g[n]  where {g[n]} and {h[n]} are length-4 sequences First, the samples of the two sequences are multiplied using the conventional multiplication method as shown on the next slide

Circular Convolution

The partial products generated in the 2nd, 3rd, and 4th rows are circularly shifted to the left as indicated above

Circular Convolution  The modified table after circular shifting is shown below

Thus yc[0]=g[0]h[0]+ g[3]h[1]+ g[2]h[2]+ g[1]h[3] yc[1]=g[1]h[0]+ g[0]h[1]+ g[3]h[2]+ g[2]h[3] yc[2]=g[2]h[0]+ g[1]h[1]+ g[0]h[2]+ g[3]h[3] yc[3]=g[3]h[0]+ g[2]h[1]+ g[1]h[2]+ g[0]h[3]  The definition of circular conjugatesymmetric sequence and circular conjugate-antisymmetric sequence.

 The samples of the sequence { yc[n]} are obtained by adding the 4 partial products in the column above of each sample

 Circular conjugate-symmetry

 Circular conjugate-antisymmetry

Classifications of Finite-Length Sequences Classifications Based on Conjugate Symmetry  Any complex length-N sequence x[n] can be expressed as:

 Where, Xcs[n] is its circular conjugate-symmetric part and Xca[n] is its circular conjugate-antisymmetric part, defined by:

 For a real sequence x[n], it can be expressed as:

 Where, Xev[n] is its circular even part and Xca[n] is its circular odd part, defined by:

Classifications of Finite-Length Sequences Classifications Based on Geometric Symmetry  Two types of geometric symmetries are usually defined:For a real

(1) Symmetric sequence

(2) Antisymmetric sequence  Type1: Symmetric impulse response with odd length.  Type2: Symmetric impulse response  Since the length N of a sequence with even length can be either even or odd, four types  Type1: Anti-symmetric impulse of geometric symmetry are defined: response with odd length.  Type1: Anti-symmetric response with even length.

impulse

Classifications of Finite-Length Sequences Type 1 Symmetry with Odd Length Type 1 symmetric sequence, with N=9, is

Taking e-j4ω as a common factor in each group of.

x[n]= x[0]+ x[1]+ x[2]+ x[3]+ x[4]+ x[5]+ x[6]+ x[7]+ x[8] • The Fourier transform is Factoring out e-j4ω in the right hand side

Classifications of Finite-Length Sequences Notice that the quantity inside the braces, { }, is a real function of ω and can assume positive or negative values in the range 0≤ω≤π The of the sequence is given by θ (ω) = −4ω + β where β is either 0 or π, and hence the phase is a linear function of ω

In general, for Type 1 linear-phase sequence of length-N

Type 2 Symmetry with Even Length Similarly, the Fourier transform of Type 2 symmetric sequence, with N=8, can be written.

where the phase is given by

In general, for Type 2 linear-phase sequence of length-N

Classifications of Finite-Length Sequences Type 3 Antisymmetry with Odd Length The Fourier transform of Type 3 antisymmetric sequence, with N=9, is (notice that x[4]=0)

Multiplying by j=ejπ/2 and 2, we obtain

which results in

Now, x[0]=-x[8], x[1]=-x[7], x[2]=-x[6], x[3]=-x[5] and x[4]=0 The phase is now The antisymmetry introduces a phase shift of π/2

Classifications of Finite-Length Sequences Type 4 Antisymmetry with Even Length In general, the Fourier transform of Type 3 linear phase antisymmetric sequence of odd length-N is

Multiplying by j=ejπ/2 and 2, we obtain

which results in

Similarly, the Fourier transform of Type 4 linear phase antisymmetric sequence of even length-N is

The phase is now The antisymmetry introduces a phase shift of π/2

In both cases, phase shift of π/2

j=ejπ/2 introduces a

DFT Symmetry Relations

In general, the DFT X[k] of a finite sequence x[n] is a sequence of complex numbers and can be expressed as

X [ k ]= X re [ k ] + j

its DFT can be found as:

X im [ k ]

Real and imaginary parts of the DFT sequence can be found as:

Assuming that the original time-domain signal is complex

Therefore, real and imaginary parts of the DFT sequence are:

DFT Symmetry Relations Symmetry Properties of the DFT of a complex sequence

Symmetry Properties of the DFT of a real sequence

Discrete Fourier Transform Theorems The DFT satisfies a number of properties that are useful in signal processing. All time domain sequences are assumed to be of length-N with N-point DFT.

Linearity Theorem Consider a sequence x[n] obtained by a linear combination of g[n] and h[n]

Circular Time Shifting Theorem The DFT of the circularly time shifting sequence x[n] is given by

Circular Frequency Shifting Theorem The inverse DFT of the circularly frequency shifting DFT is given by

Duality Theorem If the N-point DFT of the length-N sequence g[n] is G[k], then

Circular Convolution Theorem The N-point DFT Y[k] of the length Nsequence is given by

Computation of the DFT of Real Sequence Modulation Theorem The N-point DFT Y[k] of the length-N product sequence is given by a circulation of their DFT’s

Parseval’s Theorem The total energy of a length-N sequence g[n] can be computed by summing the square of the absolute values of the DFT.

N-point DFT’s of two Real Sequences using a single N-point DFT Let g[n] and h[n] be two length-N real sequences with G[k] and H[k] denoting their respective N-point DFTs • These two N-point DFTs can be computed efficiently using a single Npoint DFT • Define a complex length-N sequence The inverse DFT of the circularly frequency shifting DFT is given by

Let X[k] denote the N-point DFT of x[n]

Note that for 0 ≤ k ≤ N −1,

Computation of the DFT of Real Sequence 2N-point DFT of a Real Sequence using a single N-point DFT Let v[n] be a length-N real sequence with a 2N-point DFT V[k] • Define two length-N real sequences g[n] and h[n] as follows:

Let G[k] and H[k] denote their espective N-point DFTs • Define a length-N complex sequence

with an N-point DFT X[k]

Thus

Linear Convolution using the DFT Since a DFT can be efficiently implemented using FFT algorithms, it is of interest to develop methods for the implementation of linear convolution using the DFT • Let g[n] and h[n] be two finite-length sequences of length N and M, respectively • Define two length-L (L = N + M −1) sequences

Thus

Linear Convolution using the DFT The corresponding implementation scheme is illustrated below

We next consider implementation of

the

DFT-based

Linear Convolution of a Finite-Length Sequence with an infinite Length Sequence Overlap-Add Method We first segment x[n], assumed to be a causal sequence here without any loss of generality, into a set of contiguous finite-length subsequences of length N each:

Where where h[n] is a finite-length sequence of length M and x[n] is an infinite length (or a finite length sequence of length much greater than M)

Thus

where

Linear Convolution using the DFT The desired linear convolution y[n] = h[n] x[n] is broken up into a sum of infinite number of short-length linear convolutions of length N + M −1 each: ym[n] = h[n] xm[n]

• Consider implementing the following convolutions using the DFT-based method, where now the DFTs (and the IDFT) are computed on the basis of (N + M −1) points

In general, there will be an overlap of M −1 samples between the samples of the short convolutions h[n] xr-1[n] and h[n] xm[n] for (r −1)N ≤ n ≤ rN + M − 2

Linear Convolution using the DFT Therefore, y[n] obtained by a linear convolution of x[n] and h[n] is given by

The above procedure is called the overlap-add method since the results of the short linear convolutions overlap and the overlapped portions are added to get the correct final result

Overlap-Save Method In implementing the overlap-add method using the DFT, we need to compute two (N + M −1)-point DFTs and one (N + M −1)-point IDFT for each short linear convolution • It is possible to implement the overall linear convolution by performing instead circular convolution of length shorter than (N + M −1) • To this end, it is necessary to segment x[n] into overlapping blocks xm[n], keep the terms of the circular convolution of h[n] with that corresponds to the terms obtained by a linear convolution of h[n] and xm[n], and throw away the other parts of the circular convolution

Linear Convolution using the DFT To understand the correspondence between the linear and circular convolutions, consider a length-4 sequence x[n] and a length-3 sequence h[n] • Let yL[n] denote the result of a linear convolution of x[n] with h[n] • The six samples of yL[n] are given by

If we append h[n] with a single zerovalued sample and convert it into a length-4 sequence he[n], the 4-point circular convolution yC[n] of he[n] and x[n] is given by

Next form

Linear Convolution using the DFT Or equivalently

Computing the above for m = 0, 1, 2, 3, . . . , and substituting the values of xm[n] we arrive at Then, we reject the first M − 1 samples of wm[n] and “abut” the remaining M − M + 1 samples of wm[n] to form yL[n], the linear convolution of h[n] and x[n] If ym[n] denotes the saved portion of wm[n], i.e.,

Linear Convolution using the DFT The approach is called overlap-save method since the input is segmented into overlapping sections and parts of the results of the circular convolutions are saved and abutted to determine the linear convolution result

Discrete Cosine Transform

In general, the N-point DFT X[k] of length-N real sequence is a complex sequence satisfying the symmetry condition * X[k] = X kN

For N even, the DFT samples X[0] and X[N-2]/2 are real and distinct. The remaining N-2 DFT samples are complex and only half of these samples are distinct For N odd, the DFT samples x[0] is real and the remaining N-1 DFT samples are complex, of which only half of these samples are distinct

The DFT of a real symmetric and antisymmetric finite sequence is a product of a linear phase term and a real amplitude function.

Orthogonal transform is based on converting an arbitrary sequence into either a symmetric or an anti-symmetric sequence and then extracting the real orthogonal transform coefficients from the DFT, the transform develop via this approach is called discrete cosine transform (DCT)

Discrete Cosine Transform

To develop the expression for the DCT for symmetric periodic sequence, consider type 1 DCT.

{ x[n] } = { abc d } then the extracted periodic is given by

{ y[n] } = { a b cdcb }

let x[n] be a length-N sequence defined for 0≤n≤N-1. First, x[n] is extended to a length-2N sequence by zero padding.

x [ n ],0 nN 1 x [ n ] e xe [n] 0 , N n 2 N 1 Next, type-2 symmetric sequence y[n] of length 2N is formed from xe[n] according to

To develop the Type-2 DCT, extract y[n] of the symmetric periodic sequence

y [ n ]x [ n ]x [ 2 N 1 n ] e e

{ y[n] } = { a b c d d cb a }

x [ n ], 0 n N 1 x [ 2 N 1 n ], N n 2 N 1

0 n 2 N 1

Discrete Cosine Transform

The generated sequence satisfies the symmetry property.

y[n]

By making a change of variables, the DFT Y[k] can be expressed as N1

y [ n ]y [ 2 N 1 n ] the 2N-point DFT Y[k] of the length2N sequence y[n] is thus kn Y [ k ] y [ n ] W , 0 n 2 N 1 2 N n 0

rewrite N1

Y [k]

2 N1

kn y [n ] W 2 N

kn y [n ] W 2 N,

n0

n0

N1

2 N1

kn x [n ] W , 2 N n0

Y[k]

kn x [2 N1 n ] W , 2 N n0

0k 2 N1

kn k(2N 1) x[n]W , 2N W 2N

x[n]W n0

n0

N1 kn 2N n0

W

kn k/2 kn k/2 x[n]W W W W 2N 2N 2N 2N

N1 k/2 2N n0

W

2 N 1

N1 kn 2N

2x[n]cos

k(2n 1) , 2N

0 k 2N 1 The Type-2 N point DCT, N− 1

X DCT [ k ]=

∑

n= 0

π k (2n + 1) , 2N

(

2x[n] cos

)

0≤ k≤ 2N− 1 The samples of XDCT[k] are real for real sequence x[n]

Discrete Cosine Transform The inverse discrete cosine transform (IDCT) of an N-point DCT XDCT[k] is given by

In other words, the basis sequence

N 1 1 k ( 2 n 1 ) x [ n ] [ k ] X [ k ] cos , DCT N 2 N n 0 0 k2 N 1

where 1 / 2 [ k ] 1

k0 1 kN 1

a DCT pair may often be denoted as DCT

x[ k ] ↔ X DCT [ k ] it can be shown that 1N1 k(2 n1 ) m (2 n1 ) cos cos Nn0 2 N 2 N 1 , k m0 , 1 /2 , k m0 , 0 ,

k m ,

k(2 n1 ) cos 2 N are orthogonal to each other. To verify that x[n] is indeed the IDCT of XDCT[k]

N 1N 1 2 l ( 2 n 1 ) k ( 2 n 1 ) X [ k ] [ l ] X [ l ]cos cos DCT DCT N 2 N 2 N n 0l0 N 1

N 1 1 l ( 2 n 1 ) k ( 2 n 1 ) 2 [ l ] X [ l ] cos cos DCT N 2 N 2 N l0 l0

0k N 1

The IDCT of an N-point DCT XDCT[k] can also be computed using the DFT k / 2 W [ k ] 2 NX DCT

Y [ k ]0 ,

0 kN 1 kN ,

k / 2 W [ 2 N k ],N 1 k2 N 1 , 2 NX DCT

Discrete Cosine Transform The 2N-point IDFT y[n] of Y[k] is given by

DCT Properties The DCT satisfies a number of

2 N 1 1 kn y [ n ] y [ k ] W , 0 n 2 N 1 properties that are useful in certain 2 N 2 N k 0 application. Assume all time domain

sequences to be length N with an Npoint DCT. DCT

We get

1 1 N 1 2 N 1 ( n ) k1 ( n ) k 1 2 2 y [ n ] X [ k ] W X [ 2 N k ] W DCT 2 N DCT 2 N 2 N 2 N k 0 k N 1 1 1 N 1 ( n ) k ( n )( 2 N k ) 2 2 DCT 2 N DCT 2 N k 0 k 1

N 1

1 1 X [ k ] W X [ k ] W 2 N 2 N 1 2 N 1 ( n ) k 2 DCT 2 N k 0

1 N 1 ( n ) 2 DCT 2 N k 1

1 1 X [ k ] W X [ k ] W 2 N 2 N N 1 X [ 0 ]1 k ( 2 n 1 ) DCT X [ k ] cos DCT 2 NN 2 N k 1 0 n 2 N 1

The length-N IDCT x[n] of the N-point DCT

x [ n ]y [ n ]0 n N 1

g [n ] G [k ] DCT DCT

h [n ] H [k ] DCT Linearity Property The DCT XDCT[k] of a sequence obtained by a linear combination of two sequences, g[n] and h[n]. Where α and β arbitrary constants. DCT

g [ n ]h [ n ] G [ k ]H [ k ] DCT DCT

The Haar Transform Symmetry Properties The DCT of the conjugate sequence is given by *

DCT * DCT

The Haar Transform The discrete-time Haar transform is derived by sampling the continousetime Haar function.

g [ n ] G[ k ]

Energy Preservation Property The energy preservation property of the DCT is similar to the perseval’s relation for the DFT.

N 1 1 2 |g [ n ] | [ k ] |G [ k ] | DCT 2 N n 0 k 0

The set of Haar function hl(t) contains N numbers, with N a power-of-2 positive integer: that is N=2v+1, where v ≥ 0. In defining the Haar function, the integer subscript l is uniquely represented as a function of two non negative integer variable, r and s.

N 1

2

r l 2 s1

Where variables r and s have ranges 0 ≤ r ≤ v; 0 ≤ s ≤ 2r

The Haar Transform

h ( t )h ( t )1 , 0 t1 0 0 , 0 s1 s 0.5 2 , t , r r 2 2 s 0.5 s 2r/2 t 2r 2r 0 otherwise for 0 t 1 r/2

hl(t) hr,s(t)

To derive transform

H v 2 1

the

high

order

Haar

H 1 1 v 2

, v 1 . 2 I 11 v / 2 v 2

Where denotes the kronecker product and IK is the K×K identity. The N-point transform XHaar of length N sequence x[n] is given by

Definition The N×N discrete-time Haar transform matrix HN is obtained by discretizing the Haar functions at discrete values of t, given by t = n/N, 0 ≤ n ≤ N-1

h H .x , Haar N where

l= 2r +s− 1 T

h X [ 0 ] X [ 1 ]... X [ N 1 ] Haar Haar Haar Haar T

xx [ 0 ] x [ 1 ]... x [ N1 ]

The Haar Transform Haar Transform Properties

The inverse Haar transform is give by 1 x H NX Haar 2 × 2 normalized Haar ransform matrix is given by

1 1 2 2 x 1 1 2 2 Higher order normalized transform is given by

H v 2 ,n H v1 2 I2v

1 2 1 2

1 2 1 2

,v 0 .

Orthogonality Property The Haar transform orthogonal and hence 1 H N

matrix

is

1 t H N N

Haar transform expression reduced to

x Haar

1t H NX Haar N

If denote the (k, l)-th element of HN as hN(k,l) then

1N1 x [ n ] h ( k ,l)X [ k ] N Haar N k0 0 n N1

The Haar Transform Energy conservation property The expression is similar to the Parseval’s relation for the DFT also exists for the Haar transform N 1

N 1

|x [ n ] |2 n 0

1 |H [ k ] |2 Haar N k0

Consider the energy compaction proper of the DFT, the DCT and the Haar transform. The Discrete Fourier Transform

N-point DFT, the high frequency indices around

Energy Compaction Properties

N1 L

If L samples of the transform with X [k], 0 k DFT 2 indices in the range R are set to zero N1 L N1 L with L < < N and if x(m) [n] denotes the (m ) X [ k ] 0 , k inverse of the modified transform, then DFT 2 2 a measure of the energy compaction N1 L X [ k ], k N1 property DFT

2

N 1 1 ( m ) 2 ( L ) |x [ n ]x [ n ] | N k 0

The Energy Compaction Properties The original time domain sequence x[n] is obtained by computing the IDFT N 1

1 (m ) kn X[ n ] X [ k ] W DFT N k0 ( m ) DFT

The original time domain sequence x[n] is obtained by computing the IDCT N 1 L ( m ) DCT k 0

1 k ( 2 n 1 ) ( m ) X [ n ] [ k ] X [ k ] cos DCT N 2 N Hence the approximation error is

The corresponding error is given by

approximation

N 1 1 ( m ) 2 ( L ) |x [ n ]X [ n ] | DFT N k 0

The Discrete Cosine Transform The high frequency samples have high indices and thus the modified DCT obtained

X [ k ]0 k N 1 L

DCT ( m ) DCT

X [ k ]

0

N L k N 1

N 1 1 ( m ) 2 ( L ) |x [ n ]x [ n ] | DCT N k 0

The Haar Transform The modified Haar transform obtained

X [ k ]0 k N 1 L

Haar ( m ) Haar

X [ k ]

0

N L k N 1

The x[n] is obtained by computing the IDCT N 1 L

1 ( m ) x [ n ] h [ k , n ] X [ k ] Haar Haar N k 0 N 1 1 ( m ) 2 ( L ) |x [ n ]x [ n ] | Haar N k 0