4575 DTFT, DFT, ZT, and FFT
Those who give up liberty for the sake of security deserve neither liberty nor security.
Benjamin Franklin5.1 Introduction ...............................................................................................................
Recall that a discrete-time system can be defi ned as a process in which an input sequence(s)
f(n) referred as the excitation is transformed into an output sequence(s) g(n) referred to as
the response, using a set of predefi ned rules, algorithms, or in most practical cases a set
of difference equations. The discussion in this chapter will be restricted to single input–
single output (SISO) systems since they constitute the vast majority of the practical digital
systems and the best model to introduce the tools of analysis and synthesis due to its sim-
plicity. The transition from a SISO to a multiple input or output system is a simple process
since almost all the systems considered in this chapter are LTI systems and the general
principles of superposition hold.
The block diagram of Figure 5.1 is a simple representation of a single-input {f(n)}
sequence- and single-output {g(n)} sequence system, defi ned by the system transfer
function H, where g(n) = H[f(n)].
Some aspects of discrete-time sequences were fi rst introduced, explored, and discussed
in Chapter 7 of the book titled Practical MATLAB® Basics for Engineers and in Chapter 1 of
this book. In this chapter, arbitrary time signals once sampled and converted into discrete-
time sequences are studied by using different frequency domain transformations such as
discrete-time Fourier transform (DTFT), discrete Fourier transform (DFT), Z-transform
(ZT), and fast Fourier transform (FFT).
Recall that the input sequence f(n) can be viewed as a collection of samples of the con-
tinuous signal f(t) in which only at the sampling instances the values of f(t) are known,
whereas the signal f(t) is not defi ned for the rest of the time. Consequently, discrete-time
signals can be viewed as a sequence of numbers, representing samples where the indepen-
dent time variable is denoted by the integer n.
The fi rst studies of converting a discrete-time sequence into the frequency domain dates
back to the late 1940s and early 1950s. The pioneering research was done at the Bell Tele-
phone Laboratories (New Jersey) and Columbia University (New York) by defi ning the
DTFT, from the analog FT, and then by limiting the discrete-time sequence. The sequence
truncation led to the DFT and subsequently to the basis of digital-fi lter theory design.
Pioneering work in the area of digital fi lters was done at the Bell Telephone Laboratories in
the early 1960s, in particular, by J. K. Kaiser.
The DFT became a practical discrete tool with the publication of the research paper by
J. W. Cooley and J. K. Tukey (April 1965) titled Algorithm for Machine Calculations of Complex
Fourier Series.