Aliasing

Encyclopedia : A : AL : ALI : Aliasing

---

This article applies to signal processing, including computer graphics. For uses in computer programming, please refer to aliasing (computing).

In statistics, signal processing, and related disciplines, aliasing is an effect that causes different continuous signals to become indistinguishable (or aliases of one another) when sampled. When this happens, the original signal cannot be uniquely reconstructed from the sampled signal. 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 be incorrectly reconstructed as such during the subsequent digital-to-analog conversion. To prevent this problem, the signals must be appropriately filtered before sampling.

It is also a major concern in digital imaging and computer graphics, where it may give rise to moiré patterns (when the original image is finely textured) or jagged outlines (when the original has sharp contrasting edges, e.g. screen fonts). 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 one measures a sinusoidal signal at regular intervals, one may obtain the same sequence of samples that one would get from a sinusoid with a different, possibly lower frequency. Specifically, if a sinusoid of frequency [f\,] (in cycles per second for a time-varying signal, or in cycles per centimeter for space-varying signal) is sampled [f_s\,] samples per second or per centimeter, the resulting samples will also be compatible with a sinusoid of frequency [Nf_s - f\,] and one of frequency [Nf_s + f\,], for any integer [N\,]. In the area's jargon, each sinusoid gets aliased to (becomes an alias for) the others. If [f_s > 2f\,], the lowest of these alias frequencies will be the original signal frequency, but otherwise it will not.

Therefore, if we sample at frequency [f_s\,] a continuous signal that may contain several such sinusoids with identical samples, we will not be able to reconstruct the original signal from the samples, because it is mathematically impossible to tell how much of each component we should take.

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 [f_s/2\,]. 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 (according to the formulas above, for any and all values of [N\,]) are present in the signal.

This condition is sometimes called the Nyquist criterion, and is equivalent to saying that the sampling frequency [f_s\,] 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 [f_1\,] and [f_2\,], the criterion was spelled out by Harold Stephen Black in his 1953 book Modulation Theory. The criterion in that case is that the sampling rate must exceed [2f_2/m\,], where [m\,] is the largest integer not exceeding [f_2/B\,]. See the plot to the right, where the segments correspond to integer values of [m\,] starting with 1.

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 (A4), the second two having fundamental frequency of 880 Hz (A5), and the final two at 1760 Hz (A6). The sawtooths alternate between bandlimited (non-aliased) 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.

• [Sawtooth aliasing demo]

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 (and, in particular, to measure the difference between two signals), we will use the root mean square norm (see L_p spaces for some details), namely

[||f||^2 := \int_0^1|f(t)|^2\,dt.]

Accordingly, we will consider only signals that have finite norm, i.e. the square-integrable functions

[L^2=L^2([0,1]):=\left\.\,]

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 (see the S₀ sampling method, below.) For details, see Lp spaces.

Point sampling

The conversion of a continuous signal f to an n-dimensional vector of equally spaced samples (a sampled signal) can be modeled as a point sampling operator [S_0], defined by [S_0 f := (f(t_1), f(t_2), \dots, f(t_n))], where [t_i = i/n]. That is, the function is sampled at the points [1/n, 2/n, \dots, 1.\,]

Note that [S_0] is a linear map: for any two signals f and g, and any scalar a, then [S_0(af+g)=aS_0(f)+S_0(g).\,]

Unfortunately, while [S_0(f)] is well-defined if f is continuous (say), it is not well defined on the space [L^2] defined above. A symptom of this is, even if we restrict our attention to functions f that are continuous, function [S_0] of f is not continuous in the [L^2] norm.

In many physically significant settings, the [L^2] 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 [S_0f] and [S_0g] which are very dissimilar.

A better sampling method (filtering)

In order to preserve closeness of signals after sampling (in other words, to get a sampling method which varies smoothly as a function of the signal f) we need to modify our sampling strategy [S_0]. An improved method is as follows:

[S_1f(k)=n \int_^ f(t)dt, k=1,...,n]

This is a better filtering method, as [S_1\,] is now a continuous linear map from [L^2\,] to [\Bbb C^n].

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 frequecy of one cycle per sample, which is twice the Nyquist frequency. This zero removes all the signal energy that would alias to DC (zero frquency), and greatly attentuates all frequencies that would alias to very low frequencies. The filter does not have a sharp cutoff at the Nyquist frequency, however, so doe little 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 [f(k)\in \Bbb C^n] one would like to reconstruct the original signal [f(x)\in L^2]. This is obviously impossible in general, as [L^2] is an infinite dimensional vector space, while [\Bbb C^n] is a finite dimensional vector space (of dimension n.)

In practice, one picks a subspace [H \subset L^2] of dimension n and a reconstruction linear map R from [\Bbb C^n] 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

[R_1s=\sum_^n s(k) 1_]

where [1_E(x)] is 1 if [x\in E] and 0 otherwise.

Ideally, we would have [S(R(s))=s] for all [s\in \Bbb C^n]. If this occurs, then R and S both have the same picture of how signals in [L^2] and in [\Bbb C^n] behave, we might say that S and R are coherent. Here, [R_1] and [S_1] are in fact coherent, but [R_1] and [S_0] aren't.

Another way of saying that R and S are coherent is that R is a right-inverse for S (or S is a left-inverse for R.)

Aliasing

For any sampled signal [v\in \Bbb C^n] the set of continuous signals [f\in L^2] which sample to the same [v] 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 [L^2] being infinite dimensional while [\Bbb C^n] 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:

[H=\left\^n \alpha_k \exp 2\pi ikx\,;\, \alpha_k \in \Bbb C \right\}.\,]

Further restrictions are that, for instance, S should coincide with [S_0 \ ] on H. If sufficiently many of these demands are put forward, we eventually conclude that the sampling algorithm must take a very special shape:

[S_\mathrmf=S_0(\mathrm*f) \ ]

where [\mathrm*f \ ] 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 (we chose [L^2]) 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

• Anti-aliasing
• Wagon-wheel effect
• Sinc filter
• Sinc function
• Temporal aliasing
• Nyquist–Shannon sampling theorem
• Whittaker–Shannon interpolation formula
• Nyquist rate
• Nyquist frequency

External link

• [Sampling Theory white paper] by Dan Lavry; opens wiht an incorrect statement about Nyquist; mostly a diatribe about audio.
• [Aliasing animated gif] a graph of signals sampled at different rates, showing how the character of some signals changes dramatically when the rate is too low.

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?