Signals and Systems - Electrical Engineering

12.2 Application to Digital Signal Processing 719

G[k]=

∑^1

n 1 = 0

y[1,n 1 ]Wn 21 k=

∑^1

n 1 = 0

y[2n 1 +1]W 2 n^1 k=

∑^1

n 1 = 0

x[4n 1 +2]W 2 n^1 k

Likewise,

H[k]=

∑^1

n 1 = 0

z[0,n 1 ]W 2 n^1 k=

∑^1

n 1 = 0

z[2n 1 ]Wn 21 k=

∑^1

n 1 = 0

x[4n 1 +1]Wn 21 k

F[k]=

∑^1

n 1 = 0

z[1,n 1 ]W 2 n^1 k=

∑^1

n 1 = 0

z[2n 1 +1]Wn 21 k=

∑^1

n 1 = 0

x[4n 1 +3]W 2 n^1 k

n

nExample 12.3

In this example we wish to compare the efficiency of the FFT algorithm with that of our algorithm

dft.mthat computes the DFT using its definition. Consider the computation of the FFT and the DFT

of a signal consisting of ones of increasing lengthsN= 2 r,r=8,..., 11, or 256 to 2048.

Solution

To compare the algorithms we use the following script. The MATLAB functioncputimemeasures

the time it takes for each of the algorithms to compute the DFT of the sequence of ones.

%%%%%%%%%%%%%%

% example 12.3

% fft vs dft

%%%%%%%%%%%%%%

clf; clear all

time = zeros(1,4); time1 = time;

for r = 8:11,$$

N(r) = 2 ˆ r;

i = r - 7;

t = cputime;

fft(ones(1,N(r)),N(r));

time(i) = cputime - t;

t = cputime;

dft(ones(N(r),1),N(r));

time1(i) = cputime - t;

end

%%%%%%%%%%%

% function dft

%%%%%%%%%%%

function X = dft(x,N)

n = 0:N - 1;