Fast cosine transform

From Wikipedia, the free encyclopedia

In mathematics, a fast cosine transform (FCT) is an efficient algorithm to compute the discrete cosine transform (DCT) and its inverse. Cosine transforms are of great importance to a wide variety of applications, from digital signal processing to solving partial differential equations to algorithms for quickly multiplying large integers. This article describes the algorithms, of which there are many; see discrete cosine transform and discrete Fourier transform for properties and applications of the transform.

Contents

[edit] Variants of FCT algorithm

Exist wide range of FCT algorithms. Some of them exploits similarity to FFT, some calculates discrete cosine transform directly. Since FCT is a variant of fast Fourier transform, we can easily find implementable variants of FCT by reviewing variants of FFT. Therefore, instead of listing them here you can see wider overview on FFT page of Wikipedia.

Lets look closely on one of most practical implementations of Fast Cosine Transform, based directly on Cooley-Tukey FFT algorithm.

[edit] Implementation

Recall the formula of discrete cosine transform, or rather one of its variants:

f(m) = \frac{F(0)}{2} + \sum_{n=1}^{N-1} F(n) \cos \left[2 \pi \frac{n m}{N}\right]

and the corresponding reverse transform:

F(m) = \frac{2}{N} \sum_{n=0}^{N-1} f(n) \cos \left[2 \pi \frac{n m}{N}\right]

One can try and compute DCT directly by this formula. The result will always be valid. In advance, since this formula is very simple, it is much less error prone than any other possible algorithm to compute DCT. However, computation time needed to compute DCT directly is O(N2), that is hardly acceptable in most cases except educational purposes.

It is impossible to describe this variant of Fast Cosine Transform without description of closely related Fast Sine Transform. Here is a mirrored variant of Discrete Sine Transform:

f(m) = \sum_{n=1}^{N-1} F(n) \sin \left[2 \pi \frac{n m}{N}\right]

and the corresponding reverse transform:

F(m) = \frac{2}{N} \sum_{n=0}^{N-1} f(n) \sin \left[2 \pi \frac{n m}{N}\right]

There exist two main approaches to calculate DCT fast:

[edit] 1. Decimation in time (DIT)

The central point of DIT fast cosine/sine transform is to follow this rule:

  • Split the summation in the original formula to odd and even summators.

This way we have two sums - sum with even elements and sum with odd elements of the original.

  • Compute each sum separately.

By refactoring the given sums with well known trigonometric formulas, we can easily get the follow main loop of DIT FCT algorithm:

for k = 0 to \frac{N}{2}-1

F[k]=F_e[k] + \cos \left[ 2 \pi \frac{k}{N} \right] F_{o1}[k] - \sin \left[ 2 \pi \frac{k}{N} \right] F_{o2}[k]
F\left[k+\frac{N}{2}\right]=F_e[k] - \cos \left[ 2 \pi \frac{k}{N} \right] F_{o1}[k] + \sin \left[ 2 \pi \frac{k}{N} \right] F_{o2}[k]

Where we use the follow notation:

F[k] - is DCT coefficient number k
Fe[k] - is DCT coefficient particle number k, computed from the even subsum
Fo1[k] - is DCT coefficient particle number k, computed from the cosine part of the odd subsum
Fo2[k] - is DCT coefficient particle number k, computed from the sine part of the odd subsum

From here on the only thing we have to do is to recursively supply particles to this main loop: DIT-COS(N, f)

if N is equal 1
then return f
for n = to \frac{N}{2}-1
fe[n] = f[2n]
fo[n] = f[2n + 1]
Fe = DIT-COS({\frac{N}{2}}, f_e)
Fo1 = DIT-COS({\frac{N}{2}}, f_o)
Fo2 = DIT-SIN({\frac{N}{2}}, f_o)
for k=0 to \frac{N}{2}-1
F[k]=F_e[k] + \cos \left[ 2 \pi \frac{k}{N} \right] F_{o1}[k] - \sin \left[ 2 \pi \frac{k}{N} \right] F_{o2}[k]
F[k+\frac{N}{2}]=F_e[k] - \cos \left[ 2 \pi \frac{k}{N} \right] F_{o1}[k] + \sin \left[ 2 \pi \frac{k}{N} \right] F_{o2}[k]

DIT-SIN(N, f)

if N is equal 1
then return {0}
for n = 0 to \frac{N}{2}-1
fe[n] = f[2n]
fo[n] = f[2n + 1]
Fe = DIT-SIN({\frac{N}{2}}, f_e)
Fo1 = DIT-SIN({\frac{N}{2}}, f_o)
Fo2 = DIT-COS({\frac{N}{2}}, f_o)
for k=0 to \frac{N}{2}-1
F[k]=F_e[k] + cos \left[ 2 \pi \frac{k}{N} \right] F_{o1}[k] + \sin \left[ 2 \pi \frac{k}{N} \right] F_{o2}[k]
F[k+\frac{N}{2}]=F_e[k] - \cos \left[ 2 \pi \frac{k}{N} \right] F_{o1}[k] - \sin \left[ 2 \pi \frac{k}{N} \right] F_{o2}[k]

Finally

[edit] Forward cosine transform

is calculated by

FCT-DIT-COS(N, f)

F = DIT-COS(N, f)
for n = 0 to N-1
F[n] = \frac{2}{N}F[n]
return F


[edit] Reverse cosine transform

is calculated by

IFCT-DIT-COS(N, F)

f = DIT-COS(N, F)
for n = 0 to N-1
f[n] = f[n] - \frac{F[0]}{2}
return f

[edit] Forward sine transform

is calculated by

FCT-DIT-SIN(N, f)

F = DIT-SIN(N, f)
for n = 0 to N-1
F[n] = \frac{2}{N}F[n]
return F

[edit] Reverse sine transform

is exactly DIT-SIN(N, F)

[edit] 2. Decimation in frequency

The central point of DIF Fast Cosine/Sine Transform is to follow this rule:

  • Split the summation in the original formula to \sum_{n=0}^{\frac{N}{2}-1} and \sum_{n=\frac{N}{2}}^{N-1}.

This way we have two sums.

  • Compute each sum separately

[edit] Related topics

[edit] External links