Signals and Systems - Electrical Engineering

712 CHAPTER 12: Applications of Discrete-Time Signals and Systems

Decimation-in-Time Algorithm

Applying the divide-and-conquer principle, we expressX[k] as

X[k]=

N∑− 1

n= 0

x[n]WNkn k=0,...,N− 1

=

N∑/ 2 − 1

n= 0

[

x[2n]WNk(^2 n)+x[2n+1]WNk(^2 n+^1 )

]

That is, we gather the samples with even arguments separately from those with odd arguments.

From the definition ofWnkNwe have that

WkN(^2 n)=e−j^2 π(^2 kn)/N=e−j^2 πkn/(N/^2 )=WNkn/ 2

WkN(^2 n+^1 )=WNkWknN/ 2

which allows us to write

X[k]=

N∑/ 2 − 1

n= 0

x[2n]WNkn/ 2 +WkN

N∑/ 2 − 1

n= 0

x[2n+1]WNkn/ 2

=Y[k]+WkNZ[k] k=0,...,N− 1 (12.3)

whereY[k] andZ[k] are DFTs of lengthN/2 of the even-numbered sequence{x[2n]}and of the

odd-numbered sequence{x[2n+1]}, respectively.

Although it is clear how to compute the values ofX[k] fork=0,...,(N/ 2 )−1 as

X[k]=Y[k]+WNkZ[k] k=0,...,(N/ 2 )− 1 (12.4)

it is not clear how to proceed fork≥N/2. TheN/2 periodicity ofY[k] andZ[k] allows us to find

those values:

X[k+N/2]=Y[k+N/2]+W

k+N/ 2

N Z[k+N/2]

=Y[k]−WNkZ[k] k=0,...,N/ 2 − 1 (12.5)

where besides the periodicity ofY[k] andZ[k], we used

WNk+N/^2 =e−j^2 π[k+N/2]/N=e−j^2 πk/Ne−jπ=−WkN

Writing Equations (12.4) and (12.5) in a matrix form we have

XN=

[

IN/ 2 N/ 2

IN/ 2 −N/ 2

][

YN/ 2

ZN/ 2

]

=A 1

[

YN/ 2

ZN/ 2

]

(12.6)