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

3. Add corresponding halves to get two half-sequences.
4. Compute the DFT of these two half-sequences.

4.4.5 Computing Effort Estimate
Consider a real sequence of length N. Computing the DFT is equivalent to
multiplying an N N complex matrix with an N-vector. Each row-by-column
multiplication needs 2N multiplications and 2N additions. Assuming there is not
much difference between multiplication and addition (true in the case of floating
point), the total number of operations per row is 4N. For the entire matrix we need
4N 2 operations. Generally it is written as OO(N 2 ) in an engineering sense, without
much detail on the minutiae of the computations.
By performing either decimation in time or frequency once, as illustrated above, we
have reduced the computations from OO(N 2 ) to OO(2 ð N = 2 Þ

2 ). The computational
effort has been reduced by 50%. By repeating this till we get a two-point DFT,
generating a DFT becomes generating an FFT and the effort will be OO(N log 2 N).

4.5 Fourier Series Coefficients
Fourier series are defined for periodic functions in time and also we assume that the
integral of the function is finite. In this section we show the evaluation of Fourier
series coefficients using a DFT. We take a pulse signal as an example.

4.5.1 Fourier Coefficients
Let x ð t Þ be a continuous and periodic function of t with periodicity T, defined as

x ( t )

T

A

τ t

A ; 0 t ;

x ð t Þ¼ ð 4 : 26 Þ

0 ;< t T ;

t t

x ð t Þ¼ 1
k ¼1

þ 1
k ¼1

2 k 2 k

a k cos b k sin ; ð 4 : 27 Þ

T T

where the values of a k and b k are defined as

ð T = 2 dt

2
T

k
T t

a k ¼ x ð t Þ cos 2 ;

T = 2

dt :

ð T = 2

2
T

k
T t

b k ¼ x ð t Þ sin 2 ð 4 : 28 Þ

T = 2