Discrete Fourier transform (general)

From Wikipedia, the free encyclopedia

 It has been suggested that number-theoretic transform be merged into this article or section. (Discuss)

This article is about the discrete Fourier transform (DFT) over any field (including finite fields). For specific information on the discrete Fourier transform over the complex numbers, see discrete Fourier transform.

Contents

[edit] Definition

Let F be any field, let n\geq 1 be an integer, and let α be a primitive nth root of unity.

The discrete Fourier transform maps an n-tuple (v_0,\ldots,v_{n-1}) of elements of F to another n-tuple (f_0,\ldots,f_{n-1}) of elements of F according to the following formula:

f_k = \sum_{j=0}^{n-1} v_j\alpha^{jk}.\qquad (1)

By convention, the tuple (v_0,\ldots,v_{n-1}) is said to be in the time domain and the index j is called time. The tuple (f_0,\ldots,f_{n-1}) is said to be in the frequency domain and the index k is called frequency. The tuple (f_0,\ldots,f_{n-1}) is also called the spectrum of (v_0,\ldots,v_{n-1}). This terminology derives from the applications of Fourier transforms in signal processing.

[edit] Inverse

The inverse of the discrete Fourier transform is given as:

v_j = \frac{1}{n}\sum_{k=0}^{n-1} f_k\alpha^{-jk}.\qquad (2)

Proof: first, note that whenever β is an nth root of unity, then βn − 1 = 0. If moreover \beta\neq 1, then \beta-1\neq 0, and therefore

\frac{\beta^n-1}{\beta-1} = 1+\beta+\beta^2+\cdots+\beta^{n-1} = 0.\qquad (3)

Substituting (1) into the right-hand-side of (2), we get

\begin{align} & \frac{1}{n}\sum_{k=0}^{n-1} f_k\alpha^{-jk} \\ & {} = \frac{1}{n}\sum_{k=0}^{n-1}\sum_{j'=0}^{n-1} v_k\alpha^{j'k}\alpha^{-jk} \\ & {} = \frac{1}{n}\sum_{j'=0}^{n-1} v_{j'} \sum_{k=0}^{n-1}\alpha^{(j'-j)k}. \end{align}

This is exactly equal to vj, because \sum_{k=0}^{n-1}\alpha^{(j'-j)k}=0 when j'\neq j (by (3) with β = αj' − j), and \sum_{k=0}^{n-1}\alpha^{(j'-j)k}=n when j' = j.

[edit] Matrix formulation

Since the discrete Fourier transform is a linear operation, it can be described by matrix multiplication. In matrix notation, the discrete Fourier transform is expressed as follows:

\begin{bmatrix}f_0\\f_1\\\vdots\\f_{n-1}\end{bmatrix} = \begin{bmatrix} 1&1&1&\cdots &1 \\ 1&\alpha&\alpha^2&\cdots&\alpha^{n-1} \\ 1&\alpha^2&\alpha^4&\cdots&\alpha^{2(n-1)}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&\alpha^{n-1}&\alpha^{2(n-1)}&\cdots&\alpha^{(n-1)(n-1)}\\ \end{bmatrix} \begin{bmatrix}v_0\\v_1\\\vdots\\v_{n-1}\end{bmatrix}.

The matrix for this transformation is called the DFT matrix.

Similarly, the matrix notation for the inverse Fourier transform is

\begin{bmatrix}v_0\\v_1\\\vdots\\v_{n-1}\end{bmatrix} = \frac{1}{n}\begin{bmatrix} 1&1&1&\cdots &1 \\ 1&\alpha^{-1}&\alpha^{-2}&\cdots&\alpha^{-(n-1)} \\ 1&\alpha^{-2}&\alpha^{-4}&\cdots&\alpha^{-2(n-1)}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&\alpha^{-(n-1)}&\alpha^{-2(n-1)}&\cdots&\alpha^{-(n-1)(n-1)}\\ \end{bmatrix} \begin{bmatrix}f_0\\f_1\\\vdots\\f_{n-1}\end{bmatrix}.

[edit] Polynomial formulation[1]

Sometimes it is convenient to identify an n-tuple (v_0,\ldots,v_{n-1}) with a formal polynomial

p_v(x) = v_0 + v_1x + v_2x^2 + \cdots + v_{n-1}x^{n-1}.

By writing out the summation in the definition of the discrete Fourier transform (1), we obtain:

f_k = v_0 + v_1\alpha^{k} + v_2\alpha^{2k} + \cdots + v_{n-1}\alpha^{(n-1)k}.

This means that fk is just the value of the polynomial pv(x) for x = αk, i.e.,

f_k = p_v(\alpha^k).\,

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:

v_j = \frac{1}{n}(f_0 + f_1\alpha^{-j} + f_2\alpha^{-2j} + \cdots + f_{n-1}\alpha^{-(n-1)j}).\qquad (5)

With

p_f(x) = f_0 + f_1x + f_2x^2 + \cdots + f_{n-1}x^{n-1},

this means that

v_j = \frac{1}{n}q(\alpha^{-j}).

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.

[edit] Special cases

[edit] Complex numbers

If F={\mathbb C} is the field of complex numbers, then the nth roots of unity can be visualized as points on the unit circle of the complex plane (add a picture here!). In this case, one usually takes

\alpha=e^{\frac{-2\pi i}{n}},

which yields the usual formula for the complex discrete Fourier transform:

f_k = \sum_{j=0}^{n-1} v_j e^{\frac{-2\pi i}{n}jk}.

Over the complex numbers, it is often customary to normalize the formulas for the DFT and inverse DFT by using the scalar factor \frac{1}{\sqrt{n}} in both formulas, rather than 1 in the formula for the DFT and \frac{1}{n} in the formula for the inverse DFT. With this normalization, the DFT matrix is then unitary. Note that \sqrt{n} does not make sense in an arbitrary field.

[edit] Finite fields

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 n=\underbrace{1+1+\cdots+1}_{n\ \rm times} is invertible, so that the notation \frac{1}{n} in (2) makes sense.

An application of the discrete Fourier transform over GF(q) is the reduction of Reed-Solomon codes to BCH codes in coding theory.

[edit] Number-theoretic transform

The so-called number-theoretic transform (NNT) is obtained by further specializing to F={\mathbb Z}_p, the integers modulo a prime p.

[edit] Properties

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.

In particular, the applicability of O(nlogn) 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.

[edit] See also

[edit] References

  1. ^ R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999, pp. 217-219.
Languages