722 CHAPTER 12: Applications of Discrete-Time Signals and Systems
M = 2∗NN-1;
t0 = cputime;
y = conv(x,x); % convolution using conv
time1(i) = cputime-t0;
t1 = cputime;
X = fft(x,M); X = fft(x,M); Y = X.∗X; y1 = ifft(Y); % convolution using fft
time2(i) = cputime-t1
sum(y-y1) % check conv and fft results coincide
pause % check for small difference
end nGauss and the FFT
Going back to the sources used by the FFT researchers it was discovered that many well-known mathematicians had
developed similar algorithms for different values ofN. But that an algorithm similar to the modern FFT had been developed
and used by Carl Gauss, the German mathematician, probably in 1805, predating even Fourier’s work on harmonic analysis
in 1807, was an interesting discovery—although not surprising [31]. Gauss has been called the “prince of mathematicians”
for his prodigious work in so many areas of mathematics, and for the dedication to his work. His motto wasPauca sed matura
(few, but ripe); he would not disclose any of his work until he was very satisfied with it. Moreover, as it was customary in
his time, his treatises were written in Latin using a difficult mathematical notation, which made his results not known or
understood by modern researchers. Gauss’s treatise describing the algorithm was not published in his lifetime, but appeared
later in his collected works. He, however, deserves the paternity of the FFT algorithm.
The developments leading to the FFT, as indicated by Cooley [14], point out two important concepts in numerical analysis
(the first of which applies to research in other areas): (1) thedivide-and-conquer approach—that is, it pays to break a
problem into smaller pieces of the same structure; and (2) theasymptotic behavior of the number of operations. Cooley’s
final recommendations in his paper are worth serious consideration by researchers in technical areas:
n Prompt publication of significant achievements is essential.
n Review of old literature can be rewarding.
n Communication among mathematicians, numerical analysts, and workers in a wide range of applications can be
fruitful.
n Do not publish papers in neoclassic Latin.12.3 Application to Sampled-Data and Digital Control Systems
Most control systems being used today use computers and ADCs and DACs. Control systems where
continuous- and discrete-time signals appear are calledsample-data systems. The analysis of these
systems is more complicated than that of either continuous- or discrete-time systems, given the mixed
signals in the system. In the following analysis we will ignore the effect of the quantizer and the coder,
so that we are not considering digital control systems, but rather sampled-data or discrete control
systems. Understanding the effects of sampling and the conversion of signals from continuous to