Systems, Sampling and Quantization
9
Fourier matrix
Inverse Discrete Fourier
Transform
Fast Fourier Transform
FFT
discrete-time system
linear and time-invariant
systems
time invariance
decimator
LTI
where F is the Fourier matrix, whose generic element of indices k, n is
F
k,n
= e
-j
2
N
kn
.
(21)
It is clear that the sequence y can be recovered by premultiplication of the
sequence Y by the matrix F
-1
, which is the inverse Fourier matrix. This can
be expressed as
y(n) =
1
N
N -1
k=0
Y (k)e
j
2
N
kn
, n = [0 . . . N - 1] ,
(22)
which is called the Inverse Discrete Fourier Transform.
The Fast Fourier Transform (FFT) [65, 67], is a fast algorithm for computing
the sum (19). Namely, the FFT has computational complexity [24] of the order
of N log N , while the trivial procedure for computing the sum (19) would take an
order of N
2
steps, thus being intractable in many practical cases. The FFT can
be found as a predefined component in most systems for digital signal processing
and sound processing languages. For instance, there is an fft builtin function
in Octave, CSound, CLM (see the appendix B).
1.4
Discrete-Time Systems
A discrete-time system is any processing block that takes an input sequence
of samples and produces an output sequence of samples. The actual processing
can be performed sample by sample or as a sequence of transformations of data
blocks.
The linear and time-invariant systems are particularly interesting because a
theory is available that describes them completely. Since we have already seen
in sec. 1.1 what we mean by linearity, here we restate the concept with formulas.
If y
1
(n) and y
2
(n) are the system responses to the inputs x
1
(n) and x
2
(n) then,
feeding the system with the input
x(n) = a
1
x
1
(n) + a
2
x
2
(n)
(23)
we get, at each discrete instant n
y(n) = a
1
y
1
(n) + a
2
y
2
(n) .
(24)
In words, the superposition principle does hold.
The time invariance is defined by considering an input sequence x(n), which
gives an output sequence y(n), and a version of x(n) shifted by D samples:
x(n - D). If the system is time invariant, the response to x(n - D) is equal to
y(n) shifted by D samples, i.e. y(n - D). In other words, the time shift can be
indifferently put before or after a time-invariant system. Cases where the time
invariance does not hold are found in systems that change their functionality
over time or that produce an output sequence at a rate different from that of
the input sequence (e.g., a decimator that undersamples the input sequence).
An important property of linear and time-invariant (LTI) systems is that,
in a cascade of LTI blocks the order of such blocks is irrelevant for the global
input-output relation.