- Discrete Fourier transform (general)
This article is about the discrete Fourier transform (DFT) over any field (including finite fields), commonly called a number-theoretic transform (NTT) in the case of finite fields. For specific information on the discrete Fourier transform over the complex numbers, see discrete Fourier transform.
The discrete Fourier transform maps an n-tuple of elements of F to another n-tuple of elements of F according to the following formula:
By convention, the tuple is said to be in the time domain and the index j is called time. The tuple is said to be in the frequency domain and the index k is called frequency. The tuple is also called the spectrum of . This terminology derives from the applications of Fourier transforms in signal processing.
The inverse of the discrete Fourier transform is given as:
Proof: first, note that whenever β is an nth root of unity, then βn − 1 = 0. If moreover , then , and therefore
Substituting (1) into the right-hand-side of (2), we get
This is exactly equal to vj, because when (by (3) with β = αj' − j), and when j' = j.
Since the discrete Fourier transform is a linear operator, it can be described by matrix multiplication. In matrix notation, the discrete Fourier transform is expressed as follows:
The matrix for this transformation is called the DFT matrix.
Similarly, the matrix notation for the inverse Fourier transform is
Sometimes it is convenient to identify an n-tuple with a formal polynomial
By writing out the summation in the definition of the discrete Fourier transform (1), we obtain:
This means that fk is just the value of the polynomial pv(x) for x = αk, i.e.,
The Fourier transform can therefore be seen to relate the coefficients and the values of a polynomial: the coefficients are in the time-domain, and the values are in the frequency domain. Here, of course, it is important that the polynomial is evaluated at the nth roots of unity, which are exactly the powers of α.
Similarly, the definition of the inverse Fourier transform (2) can be written:
this means that
We can summarize this as follows: if the values of p(x) are the coefficients of q(x), then the values of q(x) are the coefficients of p(x), up to a scalar factor and reordering.
which yields the usual formula for the complex discrete Fourier transform:
Over the complex numbers, it is often customary to normalize the formulas for the DFT and inverse DFT by using the scalar factor in both formulas, rather than 1 in the formula for the DFT and in the formula for the inverse DFT. With this normalization, the DFT matrix is then unitary. Note that does not make sense in an arbitrary field.
If F = GF(q) is a finite field, where q is a prime power, then the existence of a primitive nth root automatically implies that n divides q − 1 (because the multiplicative order of each element must divide the size of the multiplicative group of F, which is q − 1). This in particular ensures that is invertible, so that the notation in (2) makes sense.
The so-called number-theoretic transform (NTT) is obtained by specializing the discrete Fourier transform to , the integers modulo a prime p. In this case, primitive nth roots of unity exists whenever n divides p − 1, so we have p = ξn + 1 for a positive integer ξ. Specifically, let ω be a primitive (p − 1)st root of unity, then an nth root of unity α can be found by letting α = ωξ.
The number-theoretic transform can further be generalized to operate on elements of the ring , even when the modulus m is not prime. Various special cases of the number theoretic transform such as the Fermat Number Transform or Mersenne Number Transform use a composite modulus (see e.g. Schönhage–Strassen algorithm).
For the number theoretic transform to work in a useful way when the modulus is composite (for the inverse algorithm, convolution etc. to work), it suffices that the modulus is chosen so that a primitive root of order n exists (where n is the transform length), and such that the multiplicative inverse of n exists. Note that if α is a primitive root of order n, then α is automatically invertible with inverse αn − 1.
Most of the important attributes of the complex DFT, including the inverse transform, the convolution theorem, and most fast Fourier transform (FFT) algorithms, depend only on the property that the kernel of the transform is a primitive root of unity. These properties also hold, with identical proofs, over arbitrary fields. This analogy can be formalized by the field with one element, considering any field with a primitive nth root of unity as an algebra over the extension field
In particular, the applicability of O(nlog n) fast Fourier transform algorithms to compute the NTT, combined with the convolution theorem, mean that the number-theoretic transform gives an efficient way to compute exact convolutions of integer sequences. While the complex DFT can perform the same task, it is susceptible to round-off error in finite-precision floating point arithmetic; the NTT has no round-off because it deals purely with fixed-size integers that can be exactly represented.
For the implementation of a "fast" algorithm (similar to how FFT computes the DFT), it is often desirable that the transform length is also highly composite, e.g. a power of two. However, there are specialized fast Fourier transform algorithms for finite fields, such as Wang and Zhu's algorithm, which are efficient regardless of whether the transform length factors.
- ^ R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999, pp. 217-219.
- ^ Yao Wang and Xuelong Zhu, "A fast algorithm for the Fourier transform over finite fields and its VLSI implementation", IEEE Journal on Selected Areas in Communications 6(3)572-577, 1988
Wikimedia Foundation. 2010.
Look at other dictionaries:
Discrete Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms In mathematics, the discrete Fourier transform (DFT) is a specific kind of discrete transform, used in… … Wikipedia
Arithmetic complexity of the discrete Fourier transform — See Fast Fourier transform#Bounds on complexity and operation counts for a general summary of this issue.Bounds on the multiplicative complexity of FFTIn his PhD thesis in 1987  , Michael Heidman focus on the arithmetic theory of complexity… … Wikipedia
Fourier transform — Fourier transforms Continuous Fourier transform Fourier series Discrete Fourier transform Discrete time Fourier transform Related transforms The Fourier transform is a mathematical operation that decomposes a function into its constituent… … Wikipedia
Discrete cosine transform — A discrete cosine transform (DCT) expresses a sequence of finitely many data points in terms of a sum of cosine functions oscillating at different frequencies. DCTs are important to numerous applications in science and engineering, from lossy… … Wikipedia
Discrete sine transform — In mathematics, the discrete sine transform (DST) is a Fourier related transform similar to the discrete Fourier transform (DFT), but using a purely real matrix. It is equivalent to the imaginary parts of a DFT of roughly twice the length,… … Wikipedia
Discrete wavelet transform — An example of the 2D discrete wavelet transform that is used in JPEG2000. The original image is high pass filtered, yielding the three large images, each describing local changes in brightness (details) in the original image. It is then low pass… … Wikipedia
Fourier transform spectroscopy — is a measurement technique whereby spectra are collected based on measurements of the temporal coherence of a radiative source, using time domain measurements of the electromagnetic radiation or other type of radiation.It can be applied to a… … Wikipedia
Fast Fourier transform — A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and its inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex number arithmetic to group … Wikipedia
Fast Fourier Transform — Transformée de Fourier rapide La transformée de Fourier rapide (sigle anglais : FFT ou Fast Fourier Transform) est un algorithme de calcul de la transformée de Fourier discrète (TFD). Sa complexité varie en avec le nombre de points n, alors… … Wikipédia en Français
Fractional Fourier transform — In mathematics, in the area of harmonic analysis, the fractional Fourier transform (FRFT) is a linear transformation generalizing the Fourier transform. It can be thought of as the Fourier transform to the n th power where n need not be an… … Wikipedia