Discrete Fourier transform (general)

In mathematics, the discrete Fourier transform over an arbitrary ring generalizes the discrete Fourier transform of a function whose values are complex numbers.

## Contents

* 1 Definition
* 2 Inverse
* 3 Matrix formulation
* 4 Polynomial formulation
* 5 Special cases
* 5.1 Complex numbers
* 5.2 Finite fields
* 5.3 Number-theoretic transform
* 5.4 Discrete weighted transform
* 6 Properties
* 7 Fast algorithms
* 8 See also
* 9 References
* 10 External links

## Definition

Let R be any ring, let n≥1 be an integer, and let α∈R be a principal nth root of unity, defined by:[1]

αn=1∑j=0n−1αjk=0 for 1≤k<n(1)

The discrete Fourier transform maps an n-tuple (v0,…,vn−1) of elements of R to another n-tuple (f0,…,fn−1) of elements of R according to the following formula:

fk=∑j=0n−1vjαjk.(2)

By convention, the tuple (v0,…,vn−1) is said to be in the time domain and the index j is called time. The tuple (f0,…,fn−1) is said to be in the frequency domain and the index k is called frequency. The tuple (f0,…,fn−1) is also called the spectrum of (v0,…,vn−1). This terminology derives from the applications of Fourier transforms in signal processing.

If R is an integral domain (which includes fields), it is sufficient to choose α as a primitive nth root of unity, which replaces the condition (1) by:[1]

αk≠1 for 1≤k<n

Proof: take β=αk with 1≤k<n. Since αn=1, βn=(αn)k=1, giving:

βn−1=(β−1)(∑j=0n−1βj)=0

where the sum matches (1). Since α is a primitive root of unity, β−1≠0. Since R is an integral domain, the sum must be zero. ∎

Another simple condition applies in the case where n is a power of two: (1) may be replaced by αn/2=−1.[1]

## Inverse

The inverse of the discrete Fourier transform is given as:

vj=1n∑k=0n−1fkα−jk.(3)

where 1/n is the multiplicative inverse of n in R (if this inverse does not exist, the DFT cannot be inverted).

Proof: Substituting (2) into the right-hand-side of (3), we get

1n∑k=0n−1fkα−jk=1n∑k=0n−1∑j′=0n−1vj′αj′kα−jk=1n∑j′=0n−1vj′∑k=0n−1α(j′−j)k.

This is exactly equal to vj, because ∑k=0n−1α(j′−j)k=0 when j′≠j (by (1) with k=j′−j), and ∑k=0n−1α(j′−j)k=n when j′=j. ∎

## Matrix formulation

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:

[f0f1⋮fn−1]=[111⋯11αα2⋯αn−11α2α4⋯α2(n−1)⋮⋮⋮⋱⋮1αn−1α2(n−1)⋯α(n−1)(n−1)][v0v1⋮vn−1].

The matrix for this transformation is called the DFT matrix.

Similarly, the matrix notation for the inverse Fourier transform is

[v0v1⋮vn−1]=1n[111⋯11α−1α−2⋯α−(n−1)1α−2α−4⋯α−2(n−1)⋮⋮⋮⋱⋮1α−(n−1)α−2(n−1)⋯α−(n−1)(n−1)][f0f1⋮fn−1].

## Polynomial formulation

Sometimes it is convenient to identify an n-tuple (v0,…,vn−1) with a formal polynomial

pv(x)=v0+v1x+v2x2+⋯+vn−1xn−1.

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

fk=v0+v1αk+v2α2k+⋯+vn−1α(n−1)k.

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

fk=pv(α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 (3) can be written:

vj=1n(f0+f1α−j+f2α−2j+⋯+fn−1α−(n−1)j).(5)

With

pf(x)=f0+f1x+f2x2+⋯+fn−1xn−1,

this means that

vj=1npf(α−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.[2]

## Special cases

### Complex numbers

If F=ℂ 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. In this case, one usually takes

α=e−2πin,

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

fk=∑j=0n−1vje−2πinjk.

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

### 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=1+1+⋯+1⏟n times is invertible, so that the notation 1n in (3) 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. Such transform can be carried out efficiently with proper fast algorithms, for example, cyclotomic fast Fourier transform.

### Number-theoretic transform

The number-theoretic transform (NTT)[3] is obtained by specializing the discrete Fourier transform to F=ℤ/p, the integers modulo a prime p. This is a finite field, and primitive nth roots of unity exist whenever n divides p−1, so we have p=ξn+1 for a positive integer ξ. Specifically, let ω be a primitive (p−1)th root of unity, then an nth root of unity α can be found by letting α=ωξ.

e.g. for p=5, α=2

21=2(mod5)22=4(mod5)23=3(mod5)24=1(mod5)

when N=4

[F(0)F(1)F(2)F(3)]=[1111124314141342][f(0)f(1)f(2)f(3)]

The number theoretic transform may be meaningful in the ring ℤ/m, even when the modulus m is not prime, provided a principal root of order n exists. Special cases of the number theoretic transform such as the Fermat Number Transform (m = 2k+1), used by the Schönhage–Strassen algorithm, or Mersenne Number Transform[4] (m = 2k − 1) use a composite modulus.

### Discrete weighted transform

The discrete weighted transform (DWT) is a variation on the discrete Fourier transform over arbitrary rings involving weighting the input before transforming it by multiplying elementwise by a weight vector, then weighting the result by another vector.[5] The Irrational base discrete weighted transform is a special case of this.

## 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 principal root of unity. These properties also hold, with identical proofs, over arbitrary rings. In the case of 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 𝐅1n.[clarification needed]

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.

## Fast algorithms

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,[6] that are efficient regardless of whether the transform length factors.

## See also

* Discrete Fourier transform (complex)
* Gauss sum
* Convolution
* Least-squares spectral analysis
* Multiplication algorithm

## References

1. ↑ 1.0 1.1 1.2 Martin Fürer, "Faster Integer Multiplication", STOC 2007 Proceedings, pp. 57-66\. Section 2: The Discrete Fourier Transform.
2. ↑ R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999, pp. 217–219.
3. ↑ Agarwal, R.; Burrus, C. (April 1974). "Fast Convolution using fermat number transforms with applications to digital filtering" (in en). IEEE Transactions on Acoustics, Speech, and Signal Processing 22 (2): 87–97. doi:10.1109/TASSP.1974.1162555. ISSN 0096-3518. http://ieeexplore.ieee.org/document/1162555/.
4. ↑ Rader, C.M. (December 1972). "Discrete Convolutions via Mersenne Transrorms". IEEE Transactions on Computers C-21 (12): 1269–1273. doi:10.1109/T-C.1972.223497. ISSN 0018-9340. http://ieeexplore.ieee.org/document/1672090/.
5. ↑ Crandall, Richard; Fagin, Barry (1994), "Discrete weighted transforms and large-integer arithmetic", Mathematics of Computation 62 (205): 305-324, doi:10.2307/2153411, http://www.faginfamily.net/barry/Papers/Discrete Weighted Transforms.pdf
6. ↑ 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

## External links

* http://www.apfloat.org/ntt.html

0.00

(0 votes)

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Discrete_Fourier_transform_(general)&oldid=175706"