Fourier Transform and Signal Spectrum - Digital Signal Processing: A Practitioner's Approach - page 83

4.3.1 Sliding DFT
The transfer function of the kth row filter can also be written as an IIR filter

1 z N
1 W N z 1

H k ð z Þ¼ for k ¼ 0 ; 1 ; ...; N 1 : ð 4 : 12 Þ

The pole z ¼ W k
N

of H k ð z Þ is cancelled by one of its zeros, resulting in an FIR filter.

For N ¼ 8 we get

ð 1 W 8 z 1 Þð 1 W 8 z 1 Þð 1 W 8 z 1 Þð 1 W 8 z 1 Þð 1 W 8 z 1 Þð 1 W 8 z 1 Þð 1 W 8 z 1 Þð 1 W 8 z 1

Þ

;

1 W 8 z 1

ð 4 : 13 Þ

where W 8 ¼ e j = 4 . This example shows the pole-zero cancellation. Each kth row k
can also be written in the form of a difference equation:

s n ¼ W N s n 1 þ x ; ð 4 : 14 Þ

where x ¼ð x n x n N þ 1 Þ can be treated as an input to the filter.

4.4 Fast Fourier Transform
Matrix multiplication in (4.11) can be done very efficiently. Since coefficients in the
matrix W N are periodic, we can arrive at a much more efficient method of
computing. The given sequence can be transformed to the frequency domain by
multiplying with an N N matrix. Direct computing involves sizeable computa-
tions and is 2 OO(N 2 ) Consider a 16-point sequence of numbers for which the DFT
equation is

X k ¼ X

15

x n W nk : ð 4 : 15 Þ

16

n ¼ 0

We illustrate decimation in time and frequency with a numerical example. Note that
the value of N is such that N ¼ 2 p where p is an integer.

4.4.1 Windowing Effect
A finite observation period is limited for many physical reasons and usually
produces an aberration in the computed spectrum. Consider x k ¼ cos ð 2 fk Þ ;

2 OO is to be read as order of.