The unnormalised engineering DFT and its conversion to the unitary transform

Let $N\ge 1$ and $f\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$. The unnormalised (engineering) discrete Fourier transform of $f$ is the function $X(f):\mathbb{Z}\to \mathbb{C}$ defined by

$X_k(f):={\sum }_{x=0}^{N-1}f([x{]}_N)e^{-2\pi ikx\mathrm{/}N},k\in \mathbb{Z},$

the sum being the finite sum of A finite sum in a commutative monoid indexed by an arbitrary finite set over the representatives $[0{]}_N,\dots ,[N-1{]}_N$ of the classes of $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (The congruence class $[a{]}_n$ and the quotient set $\mathbb{Z}\mathrm{/}n$), with $e^z$ the complex exponential of The complex exponential by its power series. Comparing with The unitary discrete Fourier transform on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$,

$X_k(f)=\sqrt{N}({\mathcal{F}}_{N}f)(k),({\mathcal{F}}_{N}f)(k)=N^{-1\mathrm{/}2}{X}_k(f),k\in \mathbb{Z},$

where $\sqrt{N}=N^{1\mathrm{/}2}$ is the rational power of Rational powers $a^r$ of a positive base and the two conversions are inverse to each other by $N^{1\mathrm{/}2}{N}^{-1\mathrm{/}2}=1$ (Laws of rational exponents). So the two transforms determine each other, and the only difference between them is the constant $\sqrt{N}$.

The transform is defined on classes and is $N$-periodic. If $[x{]}_N=[x^{\mathrm{\prime }}{]}_N$ then $x^{\mathrm{\prime }}=x+mN$ for some integer $m$ and $e^{-2\pi ik{x}^{\mathrm{\prime }}\mathrm{/}N}=e^{-2\pi ikx\mathrm{/}N}{e}^{-2\pi ikm}=e^{-2\pi ikx\mathrm{/}N}$, so the summands depend only on classes; and $e^{-2\pi i(k+N)x\mathrm{/}N}=e^{-2\pi ikx\mathrm{/}N}{e}^{-2\pi ix}=e^{-2\pi ikx\mathrm{/}N}$ for every integer $x$, both identities following from the addition law and $\exp (2\pi i\cdot )=1$ ($\exp (z+w)=\exp z\exp w$, and the complex exponential extends the real exponential, $\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$). Hence $X(f)$ factors through $\mathbb{Z}\to \mathbb{Z}\mathrm{/}N\mathbb{Z}$ and $X_k(f)$ depends on $k$ only through its class.

Inverse formulas. The inversion theorem in its unitary form is the identity $f(x)=N^{-1\mathrm{/}2}{\sum }_{k=0}^{N-1}({\mathcal{F}}_{N}f)(k)e^{2\pi ikx\mathrm{/}N}$ of Finite Fourier inversion for the unitary transform on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$; substituting $({\mathcal{F}}_{N}f)(k)=N^{-1\mathrm{/}2}{X}_k(f)$ and collecting $N^{-1\mathrm{/}2}{N}^{-1\mathrm{/}2}=N^{-1}$ (Laws of rational exponents) gives the engineering form

$f(x)=\frac{1}{N}{\sum }_{k=0}^{N-1}{X}_k(f)e^{2\pi ikx\mathrm{/}N},x\in \mathbb{Z}\mathrm{/}N\mathbb{Z}\mathrm{.}$

This is the convention in which the radix-two algorithm computes its output. The unitary transform is recovered by the single rescaling $N^{-1\mathrm{/}2}=2^{-m\mathrm{/}2}$ at length $N=2^m$. The correctness and complexity theorems refer to this unnormalised output; the convolution lemma is stated in the unitary convention.

• No factor $1\mathrm{/}N$ in the forward direction. The normalisation sits in the inverse formula. MIT's heading 3 uses the positive-sign unnormalised forward transform; replacing its primitive root by its inverse gives the sign here. Taylor's negative-sign finite sum (12.1), multiplied by $N$ and identified by ${\omega }^j\leftrightarrow [j{]}_N$, agrees with $X$. His printed recursive twiddle has a sign inconsistency, explained in the radix-two factorisation lemma; no printed recursion identity is needed for the conversion above.

• What is not asserted. Nothing here claims that $X$ is an isometry for the counting inner product — with this normalisation $X$ rescales norms by $N^{1\mathrm{/}2}$ — and nothing here claims an $O(N\log N)$ evaluation of $X$ for arbitrary $N$; the algorithmic statements are proved later on this page and are restricted to the lengths stated there.