We will mostly consider one-dimensional signals-functions of one variable, such as monophonic audio recordings, or a single row of an image. Everything can be easily generalized to two-dimensional signals, such as images.
The Fourier transform of a function x(t) is defined as:
For a given a frequency , the Fourier transform is a complex number c. The magnitude of cindicates how much of the frequency is present, and the indicates the phase of that frequency component relative to the origin.
The inverse Fourier transform recovers the original signal from its Fourier transform, and is defined as:
Note that the forward and inverse FTs are almost the same operation. This will be quite convenient when analyzing sampling and filtering.
The Fourier transforms of the following simple signals will be useful for understanding sampling, shifting and resizing.
A constant function k consists of only one frequency-zero. Therefore its Fourier transform must be zero everywhere except at .
The value at zero frequency should be selected such that the inverse Fourier transform yields k:
To satisfy these two conditions simulteously we need to introduce an unconventional function, the -function, which is defined as:
Despite its name, it is not a function at all; it is a more general object called distribution. The -function can be thought of as an operator that cancels integration: when multiplied by a function appearing inside an integral, it causes the value of the integral to be equal to the value of the function evaluated at a point.
So the Fourier transform of a constant function k is a delta-function at the origin:
The box function is defined by:
Its Fourier transform, known as the sinc, is given by:
The definition of sinc is
The definition of the comb function is:
Since this function is periodic, it may be expressed as a Fourier series, and all its frequency content are in a series of harmonics. In fact, its transform is another comb function. Since the period of the original comb was T, the fundamental frequency of its transform will be .
The derivation of this fact is relatively complicated and we omit it here. Section 2.3 describes a generalization of the comb function known as the impulse train.
Figure 3 summarizes a number of identities involving the Fourier transforms of special types of signals.
Name of the property | signals | Fourier transforms |
Linearity | ax(t)+by(t) | |
Time shifting (Section 3) | x(t-t0) | |
Zooming (Section 4.1) | x(t/a) | |
Differentiation | dx(t)/dt | |
Convolution (Section 2.2) | x(t)*y(t) |
Later in this handout we will describe circumstances in which we want to remove high or low frequencies from images. The frequency domain is a natural place to think of doing this; ideally, we could multiply all the desired frequencies by one and all the unwanted ones by zero. Although strictly speaking such an operation is not possible, we will use it as an idealization throughout this handout.
Operations on signals are referred to as filters. A simplified type of filter-linear, shift invariant-turns out to be adequate for our antialiasing purposes. A filter of this class (operating on a signal s) has the following properties:
i.e. the result of application of a filter to a shifted signal is the shifted version of the result that we get if we apply the same filter to the original signal.
For the rest of this handout we will use ``filter'' only to refer to linear and shift-invariant filters.
For an example of filtering, consider the analog telephone, which is supposed to transmit audio frequencies in the range of 300 to 3000 Hz. We could represent the sound of a voice on the telephone as:
Where V is the Fourier transform of the original voice, T is the Fourier transform of the voice on the telephone, and His the following frequency response:
A filter, like a signal, may be represented either in the frequency domain, in terms of its frequency response, or in the time domain, by its impulse response. As with a signal, the forward and inverse Fourier transforms convert between representations.
We can express filtering in the time domain rather than the frequency domain as an operation known as convolution. The expression for the convolution on two signals x(t) and y(t) is
It is usually written u = x*y.
In the frequency domain, filtering is simply multiplication by a function. In the time domain, it becomes convolution. Conversely, multiplication by a function in the time domain becomes convolution in the frequency domain.
So far we were discussing only continuous signals. If we are going to process our signal digitally, we will have to deal with discrete signals, that is, signals defined only at isolated points. We will consider signals defined at uniformly spaced points of the real line nT, where n is an integer, T is the sampling period. We will use the notation x[n] for such signals.
An important question is how to represent the sampled signal in such a way that we can use the machinery of the Fourier transform. In order to use the continuous Fourier Transform, we need a signal defined on the real line, not on a set of discrete points. The naive approach doesn't work: if we define the signal xsampled(t)=x[n] at points nT and zero elsewhere, the Fourier integral of this signal will be zero.
It turns out that we can obtain a convenient representation of a discrete signal if we use the comb function. We represent the discrete signal x[n] with
Then sampling a continuous function x(t) is equivalent to multiplying x(t)by the comb function x[n] = x(nT) is represented by
We will call a signal represented in this manner an impulse train.
Intuitively, the impulse train representation can be interpreted as follows: an approximation to a -function is a spike of a small width aand the height , with area 1; the area under the plot of a spike can be interpreted as the energy of the spike. If we multiply the spike by a number c, the energy becomes c. Thus, we can think of the impulse trains as idealizations of uniform sequences of spikes with varying energy.
A reason for using the impulse train representation of discrete signals is that now we can apply the CFT to the signal:
Alternatively, we could define the FT of a discrete signal to be the sum above. The impulse train allows us to establish a connection between these two types of Fourier transforms.
Note that the FT in Equation 1 is periodic in with period , because . That means that we have to consider FT of discrete signals only on the interval . The number is called sampling frequency.
We can derive a number of properties of the FT of discrete signals from the properties of the CFT. A list of such properties is shown in the table below.
An interesting question is when the FT of a continuous signal x(t) coincides with the FT of the discrete signal on . FT has all the information about the signal, and if we can recover the FT of the continuous signal from the FT of the sampled version, we can recover the continuous signal from the samples exactly.
We can answer this question using the convolution theorem. The sampled signal xsampled(t) is just the product of the comb function with the continuous function x(t); therefore,
As the convolution with is just a shift by , we can see that the Fourier transform of the sampled signal is just a sum of shifted copies of Fourier transforms of the continuous signals:
Equation 1 gives a different representation:
It is quite remarkable that an infinite sum of shifted copies of the FT of a continuous function turns out to be just a sum of exponents multiplied by discrete samples of the signal.
This fact has some important consequences:
We can immediately see when the FT of the sampled signal coincides with FT of the original signal on : this happens only when there is no overlap between the shifted copies of . In particular, there is no overlap if the continuous signal x(t) is band-limited, that is, the Fourier transform of the signal is 0 for all frequencies above some frequency . Figure 5 shows that there is no overlap if , that is, if . The frequency is called the Nyquist frequency.
If a signal x(t) is band-limited below the Nyquist frequency, then the Fourier transform of the sampled signal consists of copies of centered at ; we can use a low-pass filter with cutoff frequency to get rid of extra copies. If we use the ideal low pass filter sinc, we will recover the original signal exactly. This result is called Shannon theorem or Nyquist theorem:
We can derive an explicit formula for reconstructing the signal by convolving appropriate sinc function with the sampled function xs(t) = x(t) comb(t). The signal x(t) can be reconstructed from samples x[n]using
If we convolve an impulse train with another impulse train , the result will be
We get a new impulse train which corresponds to a discrete signal
which is called the discrete convolution of x and y Given that the signals x[n] and y[n] have finite length, this is an operation that we can perform on a computer. As it is just the regular convolution applied to impulse trains, the Convolution Theorem holds:
Now we have all tools in place for the applications that we are interested in: resampling of a discrete signal at a different set of points and filtering the signal in order to modify its properties.
The following pipeline summarizes the process of sampling. Given a sampling rate, Shannon's theorem gives the cutoff frequency of the prefilter h.
As described above, if the original signal has been passed through an ideal low-pass filter during sampling, then an identical filter h may be used to reconstruct the signal.