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.