# The Fourier Family

Treated as a linear operator, the Discrete Fourier Transform (DFT) is fairly simple to understand and to use: it's just a representation of an arbitrary vector in terms of an orthogonal basis with particularly useful properties. For nearly everything that we'll be doing in this course, we can leave it at that.

However, the DFT is connected, both historically and mathematically, to a family of four closely-related decompositions of signals/sequences. If only to avoid confusion in reading the literature, you should be aware of what these are. In addition, a quick survey may help you to understand and to remember a key property of the DFT: both its input and its output are periodic.

In the table below, I've arranged the four members of the Fourier Family according to whether they are discrete or continuous in frequency and time. The DFT is discrete in both frequency and time

 Discrete in Frequency Continuous in Frequency (periodic in time) Discrete in Time Discrete-time Fourier Series (= DFT) Discrete-time Fourier Transform (DTFT) (periodic in frequency) Continuous in Time Fourier Series Fourier Transform

In each of the sections below, there is an equation for creating the (time-domain) signal/sequence x out of a sum or integral of frequency-domain components X -- sometimes called a synthesis equation -- and also a corresponding analysis equation, for going from the time domain to the frequency domain.

Notational conventions:

• time-domain signals/sequences are indicated with lower-case letters (here x), while frequency-domain signals/sequences are indicated with upper-case letters (here X);
• functions of integers (i.e. discretely indexed sequences) are written with square brackets -- x[n], X[k];
• continuous functions are written with parentheses -- x(t), X(omega).
• n is used for discrete indices of time; t for continuous values of time; k for discrete indices of frequency; omega for continuous values of frequency.

To emphasize the similarities, I've written the series coefficients as X[k] rather than the more usual a_k.

In the context of this course, there is no reason for you to memorize these equations. You should understand that there are four cases, depending on whether time and frequency are treated as continuous or discrete; and that making one side of the relationship discrete makes the other side periodic.

### Discrete-time Fourier Series

A periodic sequence x[n], with period N, is expressed as a sum of sinusoidal sequences at N integer frequencies. The series can be viewed as being defined for all k, but only N values are used (and any N values of k that are distinct mod N will do). The coefficients of the Discrete Fourier Transform are exactly the N terms of this series from 0 to N-1 (ignoring a scale factor -- the DFT puts the 1/N factor on the "inverse" side -- and allowing for the question of whether indices start from 0 or from 1):

 Discrete Fourier Transform (Matlab-style indices) Inverse Discrete Fourier Transform (Matlab-style indices)

The N complex exponentials obviously form an orthogonal basis for an n-dimensional vector space. If they were normalized to unit length, they would be an orthonormal basis, and the DFT would just be a rigid rotation (and we would not have to worry about which direction the 1/N factor belongs on)..

Both the time-domain sequence and the frequency-domain sequence are treated as periodic. This is not completely obvious in the linear algebra perspective -- it seems that one N-element vector is just being transformed into another N-element vector -- but it remains true in this context as well.

### Fourier Series

A continuous, periodic signal x(t) with period T is expressed as a sum of infinitely-many sinusoidal signals at integer multiples of the fundamental frequency corresponding to T. The set of frequencies is discrete (1, 2, 3 etc. times the fundamental) but at each frequency, the sinusoid is a continuous function of time.

### Discrete-time Fourier Transform

In the time domain, x is sampled at discrete points. X is a continuous function of frequency, and is periodic (so that we integrate over 2pi).

### Fourier Transform

x is a continuous function of time, and need not be periodic. X is a continuous function of frequency, and also need not be periodic.

## Sampling and Periodicity

The relationship between sampling (discrete values) on one side of the Fourier relationship and periodicity on the other side is important. The easiest way to understand it is by means of the concept of aliasing. Suppose that x is a vector containing 64 samples of the interval from 0 to 2*pi -- in Matlab terms

x = (0:63)*2*pi/64


Then if we plot sin(2*x) we see a sine wave of frequency 2 (taking one period in the original sampled interval as frequency 1), if we plot sin(3*x) we see a sine wave of frequency 3, and so on up to sin(32*x). However, if we try to look at sin(n*x) for values of n above 32, we don't really get what we (seem to) ask for. From 33 to 63, we see negative-frequency versions of sine waves we've already seen: 33 -> -31, 34 -> -30, ... 63 -> -1. Then the frequencies cross zero and start counting through the positive integers below 32 again. Try it and see.

If we plot these relationships for a wider range of values of n, we'll see that sin(n*x) produces functions that are equivalent modulo 64. That is, if n equals m mod 64, then sin(n*x) = sin(m*x). This remains true for non-integer frequencies -- if we ask for sin(5.6789*x), or sin((64+5.6789)*x), we get the same thing.

There is nothing magical about the number 64 -- it is just the size of our original vector. If our original vector had 128 values in it, then the periodicity would be 128 rather than 64.

Since we are always working with samples of the fixed interval 0 to 2*pi, the size of the vector simply defines the density of our sampling. As the sampling gets more dense, the periodicity in the frequency domain gets larger -- we are able to see a larger and larger number of distinct frequencies. If we sampled infinitely densely, then we could see all frequencies.

To put it another way, if x covered continuously many points between 0 and 2pi -- continuously many samples of the interval -- then we could represent all frequencies. Given that x is discretely sampled, with finitely many points between 0 and 2pi, we are limited in what frequencies we can see. When we try to look at other frequencies beyond the range that our density of sampling permits, we just see copies of other modularly-related frequencies. In other words, when the time dimension is discretely sampled, the frequency dimension becomes periodic.

Analogous arguments go the other way. Suppose we have N sinusoids (whether sampled or continuous), at frequencies that are integer multiples of some basic frequency f. The lowest-frequency sinusoid will of course have the longest period (1/f). Now consider any linear combination of these N sinusoids. The frequency f contribution will obviously be periodic, with period 1/f. The frequency 2*f contribution will also be periodic, with period 1/(2*f); but it will also be period at double its period, 1/f. Likewise, all the N sinusoids will be periodic at period 1/f; and therefore their sum will also have this property. Increasing N doesn't change anything -- no matter how high the multiple of f becomes, a sinusoid at frequency N*f is still periodic at 1/f. We can sum infinitely many sinusoids (at integer multiples of the fundamental), and the result is still periodic at 1/f. Likewise, lowering the fundamental frequency f doesn't change the argument -- the period 1/f gets longer, but the sum is still periodic.

Any evenly-sampled frequency dimension thus produces a sum that is periodic in the time dimension. The only way to make the sum not be periodic is to permit frequencies whose ratio is irrational. Of course this is guaranteed if we use all real-valued frequencies.