Encyclopedia
In
statistics, signal processing, and related disciplines,
aliasing is an effect that causes different continuous signals to become indistinguishable when sampled.
Aliasing also refers to the distortion or artifact that is caused by a signal being sampled and reconstructed as an alias of the original signal.
By either meaning, aliasing can take place either in time, temporal aliasing, or in space, spatial aliasing.
Aliasing is a major concern in the analog-to-digital conversion of
video and
audio signals: improper sampling of the analog signal will cause high-
frequency components to be aliased with genuine low-frequency ones, and to be incorrectly reconstructed as such during the subsequent
digital-to-analog conversion. To prevent this problem, the sampling frequency must be sufficiently large and the signals must be appropriately filtered before sampling.
Aliasing is also a major concern in digital imaging and computer graphics, where it may give rise to
moiré patterns or jagged outlines .
Anti-aliasing techniques are used to reduce such artifacts.
Overview
Aliasing in periodic phenomena
The
sun moves east to west in the sky, with 24 hours between sunrises. If one were to take a picture of the sky every 23 hours, the sun would appear to move west to east, with 24 × 23 = 552 hours between sunrises. Note that both motions would result in the same pictures. The same phenomenon causes spoked wheels to apparently turn at the wrong speed or in the wrong direction when filmed, or illuminated with a flashing light source — such as
fluorescent lamp, a
CRT, or a
strobe light. These are examples of temporal aliasing.
If someone wearing a tweed jacket with a pronounced
herringbone pattern was videoed, and the video played on a TV screen with a smaller number of lines than the image of the pattern or on a computer monitor with pixels larger than the elements of the pattern, then one would see large areas of darkness and lightness over the image of the jacket and not the herringbone pattern. This is an example of spatial aliasing, also known as a
moiré pattern; how it is produced is illustrated next.
Sampling a periodic signal
In the same way, when a sinusoidal signal measured or
sampled at regular but not sufficiently close intervals, one will obtain the same sequence of samples that would be obtained from a sinusoid of a lower
frequency. Specifically, if a sinusoid of frequency is sampled samples per second or per centimeter, the resulting samples will also be compatible with a sinusoid of frequency and one of frequency , for any integer . If , the lowest of these image frequencies will be the original signal frequency, but otherwise it will not. In the case that , the lowest image frequencies will be at , the lowest image frequency in a sense
masquarades as the sinusoid that was sampled and is called an
alias of the sinusoid that was actually sampled, albeit inadequately sampled.
If a sample sequence is used to reconstruct a continuous-time waveform via the
Whittaker–Shannon interpolation formula or other
lowpass technique, then the lowest-frequency alias will be the one that appears in the reconstruction. In these typical cases, sampling at a rate greater that twice the highest frequency expected of any sinusoidal component in the input will generally prevent the distortion known as aliasing. In other reconstruction methods, under suitable restrictive conditions, aliasing in reconstruction can be prevented under more general conditions discussed below, even when is
not greater than twice the signal frequencies.
The Nyquist criterion
One way to avoid such
aliasing is to make sure that the signal does not contain any sinusoidal component with a frequency equal to or greater than . More generally, this condition can be generalized to allow energy in some band or set of bands such that no frequencies that are aliases of each other with respect to the sample rate are present in the signal.
This condition is sometimes called the
Nyquist criterion, and is equivalent to saying that the sampling frequency must be high enough; either greater than twice the highest frequency or some other more complicated criterion.
In the case of a single band of width
B with lower and upper frequency limits and , the criterion was incompletely spelled out by Harold Stephen Black in his 1953 book
Modulation Theory. The criterion he states is that the minimum sampling rate is , where is the largest integer not exceeding . See the plot to the right, where the segments correspond to integer values of starting with 1. He does point out, however, that this lower bound is not a sufficient condition, since higher sampling frequencies will lead to aliasing in some cases, saying simply, "Obviously, not all higher rates are necessarily usable." The more complete criterion is spelled out in
Nyquist–Shannon sampling theorem#Undersampling.
Origin of the term
The term "aliasing" derives from the usage in radio engineering, where a radio signal could be picked up at two different positions on the radio dial in a
superheterodyne radio: one where the local oscillator was above the radio frequency, and one where it was below. This is analogous to the frequency-space "wrapround" that is one way of understanding aliasing.
An audio example
The qualitative effects of aliasing can be heard in the following audio demonstration. Six
sawtooth waves are played in succession, with the first two sawtooths having a fundamental frequency of 440 Hz , the second two having fundamental frequency of 880 Hz , and the final two at 1760 Hz . The sawtooths alternate between
bandlimited sawtooths and aliased sawtooths and the sampling rate is 22.05 kHz. The bandlimited sawtooths are synthesized from the sawtooth waveform's
Fourier series such that no harmonics above the Nyquist frequency are present.
The aliasing distortion in the lower frequencies is increasingly obvious with higher fundamental frequencies, and while the bandlimited sawtooth is still clear at 1760 Hz, the aliased sawtooth is degraded and harsh with a buzzing audible at frequencies lower than the fundamental. Note that the audio file has been coded using
Ogg's Vorbis codec, and as such the audio is somewhat degraded.
Mathematical explanation of aliasing
The preceding explanation and the Nyquist criterion are somewhat idealised, because they assume instantaneous sampling and other slightly unrealistic hypotheses, although useful approximations to these things do exist. The following is a more detailed explanation of the phenomenon in terms of function approximation theory.
Continuous signals
For the purposes of this analysis, we define a continuous-time signal as a real or
complex valued function whose domain is the interval [0,1]. To quantify the "magnitude" of a signal , we will use the root mean square norm , namely
Accordingly, we will consider only signals that have finite norm, i.e. the
square-integrable functions
Note that these signals need not be continuous as functions; the adjective "continuous" refers only to the domain.
To be precise, we do not distinguish between functions that differ only on sets of zero measure. This technicality turns || || into a norm, and explains some of the difficulties For details, see Lp spaces.
Point sampling
The conversion of a continuous signal
f to an
n-dimensional vector of equally spaced samples can be modeled as a
point sampling operator , defined by , where . That is, the function is sampled at the points
Note that is a linear map: for any two signals
f and
g, and any scalar
a, then
Unfortunately, while is well-defined if
f is continuous , it is not well defined on the space defined above. A symptom of this is, even if we restrict our attention to functions
f that are continuous, function of
f is not continuous in the norm.
In many physically significant settings, the norm, or a similar norm, is an appropriate measure of similarity between signals. What will then happen is that two signals
f and
g that are deemed very similar to begin with will sample to two signals and which are very dissimilar.
A better sampling method
In order to preserve closeness of signals after sampling we need to modify our sampling strategy . An improved method is as follows:
This is a better filtering method, as is now a continuous linear map from to .
This sampling method is also a better model of how an actual machine might sample a signal. For instance, telescopes sample light signals by accumulating photons on a film or CCD receptor. The resulting image is therefore approximately the integral of all the electrons received over a period of time and over a rectangular region of the image plane.
This
rectangle function filter is just one of many possible filters for sampling. In the frequency domain, it is a lowpass sinc-shaped filter, with the first zero at a frequency of one cycle per sample, which is twice the Nyquist frequency. This zero removes all the signal energy that would alias to DC , and greatly attenuates all frequencies that would alias to very low frequencies. The filter does not have a sharp cutoff at the Nyquist frequency, however, so does little to prevent energy just above the Nyquist frequency aliasing to just below it. The rectangle function filter is popular in computer-generated image
anti-aliasing, where it is "good enough".
Reconstruction
Given a sampled signal one would like to reconstruct the original signal . This is obviously impossible in general, as is an infinite dimensional vector space, while is a finite dimensional vector space
In practice, one picks a subspace of dimension
n and a reconstruction linear map
R from to
H. The purpose of
R is to turn a sampled signal into a continuous one in a way that makes sense to us.
An example reconstruction map would be
where is
1 if and
0 otherwise.
Ideally, we would have for all . If this occurs, then
R and
S both have the same picture of how signals in and in behave, we might say that
S and
R are coherent. Here, and are in fact coherent, but and aren't.
Another way of saying that
R and
S are coherent is that
R is a right-inverse for
SAliasing
For any sampled signal the set of continuous signals which sample to the same are called
aliases of one another. The fact that there are many aliases for any one given sampled signal is called aliasing. As previously mentioned, the large quantity of aliasing is caused by being infinite dimensional while is finite dimensional.
Optimal filtering
In certain physical situations, the choice of
R,
H or
S are somehow constrained. For instance, it is usual to choose
H to be the linear span of low-degree trigonometric polynomials:
Further restrictions are that, for instance,
S should coincide with on
H. If sufficiently many of these demands are put forward, we eventually conclude that the sampling
algorithm must take a very special shape:
where is some sort of sinc filter or
sinc function.
The reconstruction formula
R is chosen so that
R and
S are coherent.
Caveats
It is important to keep in mind what is much repeated in the above discussion: the Nyquist theorem, the optimality of the sinc filter, the choice of the error norm and so on
are all assumptions we are making about the underlying physical problem.In many problems, these assumptions are unsuitable, and in these cases, the Nyquist theorem might need to be modified to be more relevant to the situation at hand.
See also
External links
- by Dan Lavry; opens with an incorrect statement about Nyquist; mostly a diatribe about audio.
- a graph of signals sampled at different rates, showing how the character of some signals changes dramatically when the rate is too low.
- by Burton MacKenZie using stop frame animation and a clock.
.gif)
