Sign in

Not a member? | Forgot your Password?

Search Online Books



Search tips

Free Online Books

Chapters

IIR Filter Design Software

See Also

Embedded SystemsFPGA
Chapter Contents:

Search Mathematics of the DFT

  

Book Index | Global Index


Would you like to be notified by email when Julius Orion Smith III publishes a new entry into his blog?

  

Number Theoretic Transform

The number theoretic transform is based on generalizing the $ N$th primitive root of unity (see §3.12) to a ``quotient ring'' instead of the usual field of complex numbers. Let $ W_N$ denote a primitive $ N$th root of unity. We have been using $ W_N
= \exp(-j2\pi/N)$ in the field of complex numbers, and it of course satisfies $ W_N^N=1$, making it a root of unity; it also has the property that $ W_N^k$ visits all of the ``DFT frequency points'' on the unit circle in the $ z$ plane, as $ k$ goes from 0 to $ N-1$.

In a number theory transform, $ W_N$ is an integer which satisfies

$\displaystyle W_N^N = 1\left(\mbox{mod}\;p\right)
$

where $ p$ is a prime integer. From number theory, for each prime number $ p$ there exists at least one primitive root $ r$ such that $ r^n$ (modulo $ p$) visits all of the numbers $ 1$ through $ p-1$ in some order, as $ n$ goes from $ 1$ to $ p-1$. Since $ m^{p-1}=1\left(\mbox{mod}\;p\right)$ for all integers $ m$ (another result from number theory), $ r$ is also an $ N$th root of unity, where $ N=p-1$ is the transform size. (More generally, $ N$ can be any integer divisor $ L$ of $ p-1$, in which case we use $ W_N=r^L$ as the generator of the numbers participating in the transform.)

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

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 various FFT algorithms.

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 $ \pi $ to millions of digits of precision.


Previous: The Discrete Cosine Transform (DCT)
Next: FFT Software

Order a Hardcopy of Mathematics of the DFT


About the Author: Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.


Comments


No comments yet for this page


Add a Comment
You need to login before you can post a comment (best way to prevent spam). ( Not a member? )