Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. The DFT can be computed efficiently in practice using a fast Fourier transform (FFT) algorithm.

The sequence of n complex numbers x₀, ..., x_n−1 are transformed into the sequence of n complex numbers f₀, ..., f_n−1 by the DFT according to the formula:

$f_{j}=\sum _{k=0}^{n-1}x_{k}e^{-{\frac {2\pi i}{n}}jk}\quad \quad j=0,\dots ,n-1$

where e is the base of the natural logarithm, i is the imaginary unit ($i^{2}=-1$), and π is Pi. The transform is sometimes denoted by the symbol ${\mathcal {F}}$, as in $\mathbf {f} ={\mathcal {F}}(\mathbf {x} )$ or ${\mathcal {F}}\mathbf {x}$.

The inverse discrete Fourier transform (IDFT) is given by

$x_{k}={\frac {1}{n}}\sum _{j=0}^{n-1}f_{j}e^{{\frac {2\pi i}{n}}jk}\quad \quad k=0,\dots ,n-1.$

Note that the normalization factor multiplying the DFT and IDFT (here 1 and 1/n) and the signs of the exponents are merely conventions, and differ in some treatments. The only requirements of these conventions are that the DFT and IDFT have opposite-sign exponents and that the product of their normalization factors be 1/n. A normalization of $1/{\sqrt {n}}$ for both the DFT and IDFT makes the transforms unitary, which has some theoretical advantages, but it is often more practical in numerical computation to perform the scaling all at once as above (and a unit scaling can be convenient in other ways).

(The convention of a negative sign in the exponent is often convenient because it means that $f_{j}$ is the amplitude of a "positive frequency" $2\pi j/n$. Equivalently, the DFT is often thought of as a matched filter: when looking for a frequency of +1, one correlates the incoming signal with a frequency of −1.)

In the following discussion the terms "sequence" and "vector" will be considered interchangeable.

Properties

Completeness

The discrete Fourier transform is an invertible, linear transformation

${\mathcal {F}}:\mathbf {C} ^{n}\to \mathbf {C} ^{n}$

with C denoting the set of complex numbers. In other words, for any n ≥ 0, any n-dimensional complex vector has a DFT and an IDFT which are in turn n-dimensional complex vectors.

Orthogonality

The vectors exp(2πi jk/n) form an orthogonal basis over the set of n-dimensional complex vectors:

$\sum _{k=0}^{n-1}\left(e^{{\frac {2\pi i}{n}}jk}\right)\left(e^{-{\frac {2\pi i}{n}}j'k}\right)=n~\delta _{jj'}$

where δ_jk is the Kronecker delta.

The Plancherel theorem and Parseval's theorem

If X_j and Y_j are the DFTs of x_k and y_k respectively then we have the Plancherel theorem:

$\sum _{k=0}^{n-1}x_{k}y_{k}^{*}={\frac {1}{n}}\sum _{j=0}^{n-1}X_{j}Y_{j}^{*}$

where the star denotes complex conjugation. Parseval's theorem is a special case of the Plancherel theorem and states:

$\sum _{k=0}^{n-1}|x_{k}|^{2}={\frac {1}{n}}\sum _{j=0}^{n-1}|X_{j}|^{2}.$

The shift theorem

Multiplying $x_{k}$ by a linear phase $\exp(2\pi ikm/n)$ for some integer $m$ corresponds to a circular shift of the output $f_{j}$: $f_{j}$ is replaced by $f_{j-m}$, where the subscript is interpreted modulo $n$ (i.e. periodically). Similarly, a circular shift of the input $x_{k}$ corresponds to multiplying the output $f_{j}$ by a linear phase. Mathematically, if $\{x_{k}\}$ represents the vector x then

if ${\mathcal {F}}(\{x_{k}\})_{j}=f_{j}$

then ${\mathcal {F}}(\{x_{k}e^{{\frac {2\pi i}{n}}km}\})_{j}=f_{j-m}$

and ${\mathcal {F}}(\{x_{k-m}\})_{j}=f_{j}e^{-{\frac {2\pi i}{n}}jm}$

Periodicity and aliasing

Although the DFT transforms n numbers to n numbers, in many ways it can be thought of as implicitly operating on infinite periodic sequences of both inputs and outputs. (Indeed, the DFT can be derived as the continuous Fourier transform of infinite periodic sequences of impulses.)

If one simply evaluates the DFT formula at $j+n$ then one finds that $f_{j+n}=f_{j}$, because $\exp[-2\pi i(j+n)k/n]$ is equal to $\exp[-2\pi ijk/n]\exp[-2\pi ink/n]$ which equals $\exp[-2\pi ijk/n]$. This phenomenon is called aliasing, and it means that in a discrete signal one cannot distinguish between frequencies $j$ that differ by $n$.

For the same reason, if one evaluates the inverse DFT formula at $k+n$ then one finds that $x_{k+n}=x_{k}$. Thus, the inputs also have implicitly periodic boundaries.

The shift theorem, above, is also an expression of this implicit periodicity, because it shows that the DFT amplitudes $|f_{j}|$ are unaffected by a circular (periodic) shift of the inputs, which is simply a choice of origin and therefore only affects the phase.

These periodic boundary conditions play an important role in many applications of the DFT. When solving differential equations they allow periodic boundary conditions to be automatically satisfied, and thus can be a useful property. For digital signal processing on the other hand, the periodicity is usually an obstacle—not only does it alias high frequencies with low frequencies, as noted above, but it also tends to introduce artifacts because natural signals are often non-periodic (resulting in implied discontinuities between the ends of the input). See also the applications section below.

See also

Derivation of the discrete Fourier transform

Circular convolution theorem and cross-correlation theorem

The cyclic convolution x*y of the two vectors x = x_j  and y = y_k  is the vector x*y with components

$(\mathbf {x*y} )_{k}=\sum _{j=0}^{n-1}x_{j}y_{k-j}\quad \quad k=0,\dots ,n-1$

where we continue y cyclically so that

$y_{-j}=y_{n-j}\quad \quad ~~~~~~~~~~j=0,...,n-1$

The discrete Fourier transform turns cyclic convolutions into component-wise multiplication. That is, if $z_{k}=(\mathbf {x*y} )_{k}$ then

$Z_{j}=X_{j}Y_{j}\quad \quad ~~~~~~~~~~j=0,\dots ,n-1$

where capital letters (X, Y, Z) represent the DFTs of sequences represented by small letters (x, y, z). Note that if a different normalization convention is adopted for the DFT (e.g., the unitary normalization), then there will in general be a constant factor multiplying the above relation.

The direct evaluation of the convolution summation, above, would require $O(n^{2})$ operations, but the DFT (via an FFT) provides an $O(n\log n)$ method to compute the same thing. Conversely, convolutions can be used to efficiently compute DFTs via Rader's FFT algorithm and Bluestein's FFT algorithm.

See also: Convolution theorem

In an analogous manner, it can be shown that if $z_{k}$ is the cross-correlation of $x_{j}$ and $y_{j}$:

$z_{k}=(\mathbf {x\star y} )_{k}=\sum _{j=0}^{n-1}x_{j}^{*}\,y_{j+k}$

where the sum is again cyclic in j, then the discrete Fourier transform of $z_{k}$ is:

$Z_{k}=X_{k}^{*}\,Y_{k}$

where capital letters are again used to signify the discrete Fourier transform.

Relationship to trigonometric interpolation polynomials

The function

$p(t)={\frac {f_{0}}{n}}+{\frac {f_{1}}{n}}e^{it}+{\frac {f_{2}}{n}}e^{2it}+\cdots +{\frac {f_{n-1}}{n}}e^{(n-1)it}$

whose coefficients f_j /n are given by the DFT of x_k, above, is called the trigonometric interpolation polynomial of degree n − 1. It is the unique function of this form that satisfies the property: p(2πk/n) = x_k for k = 0, ..., n − 1.

Because of aliasing, however, the form of the trigonometric interpolation polynomial is not unique, in that any of the frequencies can be shifted by any multiple of n while maintaining the property p(2πk/n) = x_k . In particular, the following form is often preferred:

$p(t)={\frac {f_{0}}{n}}+{\frac {f_{1}}{n}}e^{it}+\cdots +{\frac {f_{n/2}}{n}}\cos(nt/2)+{\frac {f_{n/2+1}}{n}}e^{(-n/2+1)it}+\cdots +{\frac {f_{n-1}}{n}}e^{-it}$

for even $n$ (where the Nyquist amplitude $f_{n/2}$ should be handled specially) or, for odd $n$:

$p(t)={\frac {f_{0}}{n}}+{\frac {f_{1}}{n}}e^{it}+\cdots +{\frac {f_{\lfloor n/2\rfloor }}{n}}e^{\lfloor n/2\rfloor it}+{\frac {f_{\lfloor n/2\rfloor +1}}{n}}e^{(-\lceil n/2\rceil +1)it}+\cdots +{\frac {f_{n-1}}{n}}e^{-it}$

These latter two forms have the useful property that, if the $x_{k}$ are all real numbers, then $p(t)$ will be real for all $t$ as well. They also use the smallest possible frequencies of the interpolating sinusoids (a balance of positive and negative frequencies instead of all positive frequencies), and consequently minimize the mean-square slope $\int |p'(t)|^{2}dt$ of the interpolated function.

The unitary DFT

Another way of looking at the DFT is to note that in the above discussion, the DFT can be expressed as a Vandermonde matrix:

$\mathbf {F} ={\begin{bmatrix}\omega _{n}^{0\cdot 0}&\omega _{n}^{0\cdot 1}&\ldots &\omega _{n}^{0\cdot (n-1)}\\\omega _{n}^{1\cdot 0}&\omega _{n}^{1\cdot 1}&\ldots &\omega _{n}^{1\cdot (n-1)}\\\vdots &\vdots &\ddots &\vdots \\\omega _{n}^{(n-1)\cdot 0}&\omega _{n}^{(n-1)\cdot 1}&\ldots &\omega _{n}^{(n-1)\cdot (n-1)}\\\end{bmatrix}}$

where

$\omega _{n}=e^{-2\pi i/n}\,$

is a primitive nth root of unity. The inverse transform is then given by the inverse of the above matrix:

$\mathbf {F} ^{-1}={\frac {1}{n}}\mathbf {F} ^{*}$

With unitary normalization constants $1/{\sqrt {n}}$, the DFT becomes a unitary transformation, defined by a unitary matrix:

$\mathbf {U} =\mathbf {F} /{\sqrt {n}}$

$\mathbf {U} ^{-1}=\mathbf {U} ^{*}$

$\det(\mathbf {U} )=1$

where det()  is the determinant function. In a real vector space, a unitary transformation can be thought of as simply a rigid rotation of the coordinate system, and all of the properties of a rigid rotation can be found in the unitary DFT.

The orthogonality of the DFT is now expressed as an orthonormality condition (which arises in many areas of mathematics as described in root of unity):

$\sum _{m=0}^{n-1}U_{jm}U_{mk}^{*}=\delta _{jk}$

If $\mathbf {X}$ is defined as the unitary DFT of the vector $\mathbf {x}$ then

$X_{j}=\sum _{k=0}^{n-1}U_{jk}x_{k}$

and the Plancherel theorem is expressed as:

$\sum _{k=0}^{n-1}x_{k}y_{k}^{*}=\sum _{j=0}^{n-1}X_{j}Y_{j}^{*}$

If we view the DFT as just a coordinate transformation which simply specifies the components of a vector in a new coordinate system, then the above is just the statement that the dot product of two vectors is preserved under a unitary DFT transformation. For the special case $\mathbf {x} =\mathbf {y}$, this implies that the length of a vector is preserved as well—this is just Parseval's theorem:

$\sum _{k=0}^{n-1}|x_{k}|^{2}=\sum _{j=0}^{n-1}|X_{j}|^{2}$

Expressing the inverse DFT in terms of the DFT

A useful property of the DFT is that the inverse DFT can be easily expressed in terms of the (forward) DFT, via several well-known "tricks". (For example, in computations, it is often convenient to only implement a fast Fourier transform corresponding to one transform direction and then to get the other transform direction from the first.)

First, we can compute the inverse DFT by reversing the inputs:

${\mathcal {F}}^{-1}(\{x_{k}\})={\mathcal {F}}(\{x_{n-k}\})/n$

(As usual, the subscripts are interpreted modulo $n$; thus, for $k=0$, we have $x_{n-0}=x_{0}$.)

Second, one can also conjugate the inputs and outputs:

${\mathcal {F}}^{-1}(\mathbf {x} )={\mathcal {F}}(\mathbf {x} ^{*})^{*}/n$

Third, a variant of this conjugation trick, which is sometimes preferable because it requires no modification of the data values, involves swapping real and imaginary parts (which can be done on a computer simply by modifying pointers). Define swap($x_{k}$) as $x_{k}$ with its real and imaginary parts swapped—that is, if $x_{k}=a+bi$ then swap($x_{k}$) is $b+ai$. Equivalently, swap($x_{k}$) equals $ix_{k}^{*}$. Then

${\mathcal {F}}^{-1}(\mathbf {x} )={\textrm {swap}}({\mathcal {F}}({\textrm {swap}}(\mathbf {x} )))/n$

That is, the inverse transform is the same as the forward transform with the real and imaginary parts swapped for both input and output, up to a normalization

The conjugation trick can also be used to define a new transform, closely related to the DFT, that is involutary—that is, which is its own inverse. In particular, $T(\mathbf {x} )={\mathcal {F}}(\mathbf {x} ^{*})/{\sqrt {n}}$ is clearly its own inverse: $T(T(\mathbf {x} ))=\mathbf {x}$. A closely related involutary transformation (by a factor of (1+i)/√2) is $H(\mathbf {x} )={\mathcal {F}}((1+i)\mathbf {x} ^{*})/{\sqrt {2n}}$, since the $(1+i)$ factors in $H(H(\mathbf {x} ))$ cancel the 2. For real inputs $\mathbf {x}$, the real part of $H(\mathbf {x} )$ is none other than the discrete Hartley transform, which is also involutary.

The real DFT

If $x_{0},\ldots ,x_{n-1}$ are real numbers, as they often are in practical applications, then the DFT obeys the symmetry:

$f_{j}=f_{n-j}^{*},$

where the star denotes complex conjugation and the subscripts are interpreted modulo n.

Therefore, the DFT output for real inputs is half redundant, and one obtains the complete information by only looking at roughly half of the outputs $f_{0},\ldots ,f_{n-1}$. In this case, the "DC" element $f_{0}$ is purely real, and for even n the "Nyquist" element $f_{n/2}$ is also real, so there are exactly n non-redundant real numbers in the first half + Nyquist element of the complex output f.

Using Euler's formula, the interpolating trigonometric polynomial can then be interpreted as a sum of sine and cosine functions.

Generalized DFT

It is possible to shift the transform sampling in time and/or frequency domain by some real shifts a and b, respectively. This is sometimes known as a generalized DFT (or GDFT) and has analogous properties to the ordinary DFT:

$f_{j}=\sum _{k=0}^{n-1}x_{k}e^{-{\frac {2\pi i}{n}}(j+b)(k+a)}\quad \quad j=0,\dots ,n-1$

Most often, shifts of $1/2$ (half a sample) are used. While the ordinary DFT corresponds to a periodic signal in both time and frequency domains, $a=1/2$ produces a signal that is anti-periodic in frequency domain ($f_{j+n}=-f_{j}$) and vice-versa for $b=1/2$. Thus, the specific case of $a=b=1/2$ is known as an odd-time odd-frequency discrete Fourier transform (or O² DFT). Such shifted transforms are most often used for symmetric data, to represent different boundary symmetries, and for real-symmetric data they correspond to different forms of the discrete cosine and sine transforms.

The discrete Fourier transform can be viewed as a special case of the z-transform, evaluated on the unit circle in the complex plane.

Multidimensional DFT

The ordinary DFT computes the transform of a "one-dimensional" dataset: an sequence (or array) $x_{k}$ that is a function of one discrete variable $k$. More generally, one can define the multidimensional DFT of a multidimensional array $x_{k_{1},k_{2},\cdots ,k_{d}}$ that is a function of $d$ discrete variables $k_{\ell }=0,1,\cdots ,n_{\ell }-1$ for $\ell$ in $1,2,\cdots ,d$:

$f_{j_{1},j_{2},\cdots ,j_{d}}=\sum _{k_{1}=0}^{n_{1}-1}\omega _{n_{1}}^{~j_{1}k_{1}}\cdots \sum _{k_{d}=0}^{n_{d}-1}\omega _{n_{d}}^{~j_{d}k_{d}}x_{k_{1},k_{2},\cdots ,k_{d}}\,,$

where $\omega _{n_{\ell }}=\exp(-2\pi i/n_{\ell })$ as above and the $d$ output indices run from $j_{\ell }=0,1,\cdots ,n_{\ell }-1$. This is more compactly expressed in vector notation, where $\mathbf {k} \equiv (k_{1},k_{2},\cdots ,k_{d})$ and $\mathbf {j} \equiv (j_{1},j_{2},\cdots ,j_{d})$ are $d$-dimensional vectors of indices from 0 to $\mathbf {n} -1\equiv (n_{1}-1,n_{2}-1,\cdots ,n_{d}-1)$:

$f_{\mathbf {j} }=\sum _{\mathbf {k} =0}^{\mathbf {n} -1}e^{-2\pi i\mathbf {j} \cdot (\mathbf {k} /\mathbf {n} )}x_{\mathbf {k} }\,,$

where the division $\mathbf {k} /\mathbf {n} \equiv (k_{1}/n_{1},\cdots ,k_{d}/n_{d})$ is performed element-wise, and the sum denotes the set of nested summations above.

The inverse of the multi-dimensional DFT is, analogous to the one-dimensional case, given by:

$x_{\mathbf {k} }={\frac {1}{\prod _{\ell =1}^{d}n_{\ell }}}\sum _{\mathbf {j} =0}^{\mathbf {n} -1}e^{2\pi i\mathbf {k} \cdot (\mathbf {j} /\mathbf {n} )}f_{\mathbf {j} }\,.$

The multidimensional DFT has a simple interpretation. Just as the one-dimensional DFT expresses the input $x_{k}$ as a superposition of sinusoids, the multidimensional DFT expresses the input as a superposition of plane waves, or sinusoids oscillating along the direction $\mathbf {j} /\mathbf {n}$ in space and having amplitude $f_{\mathbf {j} }$. Such a decomposition is of great importance for everything from digital image processing ($d$=2) to solving partial differential equations in three dimensions ($d$=3) by breaking the solution up into plane waves.

Computationally, the multidimensional DFT is simply the composition of a sequence of one-dimensional DFTs along each dimension. For example, in the two-dimensional case $x_{k_{1},k_{2}}$ one can first compute the $n_{1}$ independent DFTs of the rows (i.e., along $k_{2}$) to form a new array $y_{k_{1},j_{2}}$, and then compute the $n_{2}$ independent DFTs of $y$ along the columns (along $k_{1}$) to form the final result $f_{j_{1},j_{2}}$. Or, one can transform the columns and then the rows—the order is immaterial because the nested summations above commute.

Because of this, given a way to compute a one-dimensional DFT (e.g. an ordinary one-dimensional FFT algorithm), one immediately has a way to efficiently compute the multidimensional DFT. This is known as a row-column algorithm, although there are also intrinsically multi-dimensional FFT algorithms.

Applications

The DFT has seen wide usage across a large number of fields; we only sketch a few examples below (see also the references at the end). All applications of the DFT depend crucially on the availability of a fast algorithm to compute discrete Fourier transforms and their inverses, a fast Fourier transform.

Spectral analysis

Suppose a signal x(t) is to be analyzed. Here, t stands for time, which varies over the interval [0,T], and, in the case of a sound signal, x(t) is the air pressure at time t.

The signal is sampled at n equidistant points to get the n real numbers x₀ = x(0), x₁ = x(h), x₂ = x(2h), ..., x_n−1 = x((n−1)h), where h = T/n and n is even.

Then the discrete Fourier transform f₀, ..., f_n−1 is computed and the numbers f_{n/2 + 1}, ..., f_n−1 are discarded (they are redundant for real signals).

Then f₀/n approximates the average value of the signal over the interval, and for every j = 1, ..., n/2, the argument (see complex number) arg(f_j) represents the phase and the modulus |f_j|/n represents one half of the amplitude of the component of the signal having frequency j/T (see wave).

The reason behind this interpretation is that the f_j are approximations to the coefficients occurring in the Fourier series expansion of x(t). Or, more commonly, T is a small section of an infinite signal x(t), and the DFT is an approximation for the discrete-time Fourier transform of the sampled signal, which in turn is an approximation for the continuous Fourier transform if x(t) is band-limited (see the Nyquist frequency). In general, the problem of using the DFT of discrete samples to approximate the Fourier transform of an infinite, continuous signal is called spectral estimation, and involves many more details than are described here.

For an example see frequency spectrum.

Data compression

The field of digital signal processing relies heavily on operations in the frequency domain (i.e. on the Fourier transform). For example, several lossy image and sound compression methods employ the discrete Fourier transform: the signal is cut into short segments, each is transformed, and then the Fourier coefficients of high frequencies, which are assumed to be unnoticeable, are discarded. The decompressor computes the inverse transform based on this reduced number of Fourier coefficients. (Compression applications often use a specialized form of the DFT, the discrete cosine transform or sometimes the modified discrete cosine transform).

Partial differential equations

Discrete Fourier transforms, especially in more than one dimension, are often used to solve partial differential equations, where again the DFT is used as an approximation for the Fourier series (which is recovered in the limit of infinite n). The reason is that it expands the signal in complex exponentials e^ikx, which are eigenfunctions of differentiation: d/dx e^ikx = ik e^ikx. Thus, in the Fourier representation, a linear differential equation with constant coefficients is transformed into an easily solvable algebraic equation. One then uses the inverse DFT to transform the result back into the ordinary spatial representation. Such an approach is called a spectral method.

Multiplication of large integers

The fastest known algorithms for the multiplication of large integers or polynomials are based on the discrete Fourier transform: the sequences of digits or coefficients are interpreted as vectors whose convolution needs to be computed; in order to do this, they are first Fourier-transformed, then multiplied component-wise, then transformed back.

Outline of DFT polynomial multiplication algorithm

Suppose we wish to compute the polynomial product c(x) = a(x) · b(x). The ordinary product expression for the coefficients of c involves a linear (acyclic) convolution, where indices do not "wrap around." This can be rewritten as a cyclic convolution by taking the coefficient vectors for a(x) and b(x) with constant term first, then appending zeros so that the resultant coefficient vectors a and b have dimension d > deg(a(x)) + deg(b(x)). Then,

$\mathbf {c} =\mathbf {a} \star \mathbf {b}$

Where c is the vector of coefficients for c(x), and the convolution operator $\star$ is defined so

$c_{i}=\sum _{j=0}^{d-1}a_{j}b_{i-j\ \mathrm {mod} \ d}\qquad \qquad \qquad i=0,1,...,d-1$

But convolution becomes multiplication under the DFT:

${\mathcal {F}}(\mathbf {c} )={\mathcal {F}}(\mathbf {a} ){\mathcal {F}}(\mathbf {b} )$

Here the vector product is taken elementwise. Thus the coefficients of the product polynomial c(x) are just the terms 0, ..., deg(a(x)) + deg(b(x)) of the coefficient vector

$\mathbf {c} ={\mathcal {F}}^{-1}({\mathcal {F}}(\mathbf {a} ){\mathcal {F}}(\mathbf {b} ))$

With a Fast Fourier transform, the resulting algorithm takes O(n log n) arithmetic operations. Due to its simplicity and speed, the Cooley-Tukey FFT algorithm, which is limited to composite sizes, is often chosen for the transform operation. In this case, d should be chosen as the smallest integer greater than the sum of the input polynomial degrees that is factorizable into small prime factors (e.g. 2, 3, and 5, depending upon the FFT implementation).

Some discrete Fourier transform pairs

In the following table $\omega _{n}$ stands for $\exp(-2\pi i/n)$, a primitive n-th root of unity.

Some DFT pairs

$x_{k}\equiv {\frac {1}{n}}\sum _{j=0}^{n-1}f_{j}\omega _{n}^{-jk}$	$f_{j}\equiv \sum _{k=0}^{n-1}x_{k}\omega _{n}^{jk}$	Note
$x_{k}\omega _{n}^{-km}$	$f_{j-m}\,$	Shift theorem
$x_{k-m}\,$	$f_{j}\omega _{n}^{jm}$
$x_{k}\in \mathbf {R}$	$f_{j}=f_{n-j}^{*}\,$	Real DFT
$a^{k}\,$	${\frac {1-a^{n}}{1-a\omega _{n}^{j}}}$
${n-1 \choose k}\,$	$(1+\omega _{n}^{j})^{n-1}\,$

References

• . ISBN 0133075052. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help)
• . ISBN 0137549202. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help)
• . ISBN 0966017633. {{cite book}}: External link in |Title= (help); Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 30: Polynomials and the FFT, pp.822–848, esp. section 30.2: The DFT and FFT, pp.830–838.