Editing Discrete cosine transform (section)

==Informal overview==

Like any Fourier-related transform, DCTs express a function or a signal in terms of a sum of [[sinusoid]]s with different [[frequencies]] and [[amplitude]]s. Like the DFT, a DCT operates on a function at a finite number of [[Discrete signal|discrete data points]]. The obvious distinction between a DCT and a DFT is that the former uses only cosine functions, while the latter uses both cosines and sines (in the form of [[complex exponential]]s). However, this visible difference is merely a consequence of a deeper distinction: a DCT implies different [[boundary condition]]s from the DFT or other related transforms.

The Fourier-related transforms that operate on a function over a finite [[domain of a function|domain]], such as the DFT or DCT or a [[Fourier series]], can be thought of as implicitly defining an ''extension'' of that function outside the domain. That is, once you write a function <math>f(x)</math> as a sum of sinusoids, you can evaluate that sum at any <math>x</math>, even for <math>x</math> where the original <math>f(x)</math> was not specified. The DFT, like the Fourier series, implies a [[periodic function|periodic]] extension of the original function. A DCT, like a [[cosine transform]], implies an [[even and odd functions|even]] extension of the original function.

[[Image:DCT-symmetries.svg|thumb|right|350px|Illustration of the implicit even/odd extensions of DCT input data, for ''N''=11 data points (red dots), for the four most common types of DCT (types I-IV). Note the subtle differences at the interfaces between the data and the extensions: in DCT-II and DCT-IV both the end points are replicated in the extensions but not in DCT-I or DCT-III (and a zero point is inserted at the sign reversal extension in DCT-III).]]

However, because DCTs operate on ''finite'', ''discrete'' sequences, two issues arise that do not apply for the continuous cosine transform. First, one has to specify whether the function is even or odd at ''both'' the left and right boundaries of the domain (i.e. the min-''n'' and max-''n'' boundaries in the definitions below, respectively). Second, one has to specify around ''what point'' the function is even or odd. In particular, consider a sequence ''abcd'' of four equally spaced data points, and say that we specify an even ''left'' boundary. There are two sensible possibilities: either the data are even about the sample ''a'', in which case the even extension is ''dcbabcd'', or the data are even about the point ''halfway'' between ''a'' and the previous point, in which case the even extension is ''dcbaabcd'' (''a'' is repeated).

Each boundary can be either even or odd (2 choices per boundary) and can be symmetric about a data point or the point halfway between two data points (2 choices per boundary), for a total of 2 × 2 × 2 × 2 = 16 possibilities. These choices lead to all the standard variations of DCTs and also [[discrete sine transform]]s (DSTs). Half of these possibilities, those where the ''left'' boundary is even, correspond to the 8 types of DCT; the other half are the 8 types of DST.

These different boundary conditions strongly affect the applications of the transform and lead to uniquely useful properties for the various DCT types. Most directly, when using Fourier-related transforms to solve [[partial differential equation]]s by [[spectral method]]s, the boundary conditions are directly specified as a part of the problem being solved. Or, for the MDCT (based on the type-IV DCT), the boundary conditions are intimately involved in the MDCT's critical property of time-domain aliasing cancellation. In a more subtle fashion, the boundary conditions are responsible for the ''energy compactification'' properties that make DCTs useful for image and audio compression, because the boundaries affect the rate of convergence of any Fourier-like series.

In particular, it is well known that any [[Classification of discontinuities|discontinuities]] in a function reduce the [[rate of convergence]] of the Fourier series so that more sinusoids are needed to represent the function with a given accuracy. The same principle governs the usefulness of the DFT and other transforms for signal compression; the smoother a function is, the fewer terms in its DFT or DCT are required to represent it accurately, and the more it can be compressed.{{efn|Here, we think of the DFT or DCT as approximations for the [[Fourier series]] or [[cosine series]] of a function, respectively, in order to talk about its smoothness.}} However, the implicit periodicity of the DFT means that discontinuities usually occur at the boundaries: any random segment of a signal is unlikely to have the same value at both the left and right boundaries.{{efn|A similar problem arises for the DST, in which the odd left boundary condition implies a discontinuity for any function that does not happen to be zero at that boundary.}} In contrast, a DCT where ''both'' boundaries are even ''always'' yields a continuous extension at the boundaries (although the [[slope]] is generally discontinuous). This is why DCTs, and in particular DCTs of types I, II, V, and VI (the types that have two even boundaries) generally perform better for signal compression than DFTs and DSTs. In practice, a type-II DCT is usually preferred for such applications, in part for reasons of computational convenience.