The Discrete Cosine Transform (DCT)

Other FFT Algorithms

Number Theoretic Transform

The *number theoretic transform* is based on generalizing the
th primitive root of unity (see §3.14) to a
``quotient ring'' instead of the usual field of complex numbers. Let
denote a primitive th root of unity. We have been using
in the field of complex numbers, and it of course
satisfies , making it a root of unity; it also has the
property that visits all of the ``DFT frequency points'' on
the unit circle in the plane, as goes from 0 to .

In a number theory transform, is an *integer* which
satisfies

When the number of elements in the transform is composite, a ``fast number theoretic transform'' may be constructed in the same manner as the fast Fourier transform is constructed from the DFT, or as the prime factor algorithm (or Winograd transform) is constructed for products of small primes [36].

Unlike the DFT, the number theoretic transform does not transform to a meaningful ``frequency domain''. However, it has analogous theorems, such as the convolution theorem, enabling it to be used for fast convolutions and correlations like the FFT.

An interesting feature of the number theory transform is that all
computations are *exact* (integer multiplication and addition
modulo a prime integer). There is no round-off error. This feature
has been used to do fast convolutions to multiply extremely large
numbers, such as are needed when computing to millions of digits
of precision.

Prime Factor Algorithm (PFA)

The Discrete Cosine Transform (DCT)

Other FFT Algorithms

``Mathematics of the Discrete Fourier Transform (DFT), with Music and Audio Applications'', by Julius O. Smith III, W3K Publishing, 2003, ISBN 0-9745607-0-7.

(Browser settings for best viewing results)

(How to cite this work)

(Order a printed hardcopy)

Copyright ©

W3K Publishing,