Finite Fourier Analysis and the Fast Fourier Transform — Examples

False claim: for every $N\ge 1$ and all $f,g\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ with coefficient lists $u_i:=f([i{]}_N)$ and $v_j:=g([j{]}_N)$, the cyclic convolution $f\ast g$ of The unnormalised cyclic convolution on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ has the linear convolution values $(f\ast g)([k])={\sum }_{i+j=k}{u}_i{v}_j$ for every $k=0,\dots ,N-1$; that is, no coefficient of the product ever wraps around.

The false claim fails already for $N=2$ and $f=g=(1,1)$: the coefficient $1$ of $z^2$ in the unreduced product $(1+z{)}^2=1+2z+z^2$ is wrapped into degree $0$, so $(f\ast g)([0])=2$ while the linear value listed for $k=0$ is $u_0{v}_0=1$. Sufficient zero padding restores the agreement: padded to length $4$, the same two sequences have cyclic convolution $(1,2,1,0)$, exactly the unreduced coefficient list.

• Padding threshold. For nonzero coefficient polynomials $P,Q$, choosing $N\ge \mathrm{deg}P+\mathrm{deg}Q+1$ prevents wrap: every exponent in $PQ$ is below $N$, so [L1] leaves its coefficients unchanged. Here the minimum such length is $3$; length $4$ also works and admits the radix-two algorithm. The transform law The DFT turns cyclic convolution into a scaled pointwise product always computes cyclic convolution.

• Where the wrap comes from. In the group $\mathbb{Z}\mathrm{/}2\mathbb{Z}$ the class $[2]$ is $[0]$, so the exponent $2$ of $z^2$ is the exponent $0$ of the reduced polynomial; nothing is lost or approximated — the degree-$2$ and degree-$0$ coefficients are added in the field, which is exactly what the convolution sum does.

For $N=1$ the unitary transform of The unitary discrete Fourier transform on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ is the identity: the group $\mathbb{Z}\mathrm{/}1\mathbb{Z}$ has the single class $[0{]}_1$, the only term of the defining sum is $1^{-1\mathrm{/}2}f([0{]}_1)e^0=f([0{]}_1)$, and the matrix of ${\mathcal{F}}_1$ is the $1\times 1$ matrix $[1]=I_1$, which is its own inverse.

For $N=2$, write $h=(h_0,h_1)$ for $h\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}2}$ with $h_0:=h([0{]}_2)$ and $h_1:=h([1{]}_2)$. Since $e^{-\pi ixk}=(-1{)}^{xk}$ for $x,k\in \{0,1\}$,

${\mathcal{F}}_2(h_0,h_1)=2^{-1\mathrm{/}2}(h_0+h_1,h_0-h_1),$

whose matrix relative to the classes $[0],[1]$ is $\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ \\ 1& -1\end{array}\right)$; this matrix is real and symmetric and satisfies $A^2=I_2$, so it is its own inverse. Since the reflection $x\mapsto -x$ is the identity on $\mathbb{Z}\mathrm{/}1\mathbb{Z}$ and on $\mathbb{Z}\mathrm{/}2\mathbb{Z}$, the fourth-power identity of ${\mathcal{F}}_N^2$ is reflection and ${\mathcal{F}}_N^4$ is the identity reads ${\mathcal{F}}_1^2={\mathcal{F}}_2^2=\mathrm{i}\mathrm{d}$ here, consistent with $A^2=I_2$ and with the inversion theorem Finite Fourier inversion for the unitary transform on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$; and ${\mathcal{F}}_2$ preserves the counting norm by Finite Parseval and Plancherel identity for the unitary DFT.

• The degenerate length is not an exception. $N=1$ is a genuine case of every statement on this page: the transform is the identity, the orthogonality sum has its single coincident term, and the radix-two recursion later on this page terminates at this case as its base. Nothing in the definitions excludes it, and no separate convention is introduced for it.

• At $N=2$ the transform is its own inverse. This is the smallest length at which the transform is not the identity while still being involutive; for $N\ge 3$ the reflection is not the identity, so the square of the transform is not the identity either, although the fourth power always is.

On $\mathbb{Z}\mathrm{/}4\mathbb{Z}$ let $f=g=(1,1,0,0)$, that is $f([0])=f([1])=1$ and $f([2])=f([3])=0$, and similarly for $g$. Their unnormalised transforms of The unnormalised engineering DFT and its conversion to the unitary transform are $X(f)=X(g)=(2,1-i,0,1+i)$; the convolution law in engineering form gives $X(f\ast g)=X(f)X(g)$ componentwise, that is $X(f\ast g)=(4,-2i,0,2i)$, and inverse transforming by $(f\ast g)(x)=\frac{1}{4}{\sum }_{k=0}^3{X}_k(f\ast g)e^{2\pi ikx\mathrm{/}4}$ returns $(1,2,1,0)$. Direct evaluation of the cyclic convolution $(f\ast g)(x)={\sum }_{y\in \mathbb{Z}\mathrm{/}4}f(y)g(x-y)$ of The unnormalised cyclic convolution on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ gives the same tuple $1,2,1,0$. In this instance the length is large enough that no coefficient wraps, so the cyclic convolution equals the linear convolution $(1,2,1,0)$ of the coefficient sequences.

• What the computation shows and what it does not. It shows the transform law of [F2] producing a genuine cyclic convolution and agreeing with direct summation for one four-point pair. It does not claim that a length-$4$ transform is efficient — the point of the example is the normalisation bookkeeping: with $X$ unnormalised the product law has no extra factor, while with ${\mathcal{F}}_4$ the same computation carries the factor $\sqrt{4}=2$.

• The wrap-free regime. Because the coefficient lists have length $2$ each and the product has $3$ coefficients, the four-point cyclic convolution sees no wrap. The companion counterexample shows what changes at length $2$, where the product's third coefficient wraps back into degree $0$.

False claim: for every integer $N\ge 2$, the even/odd split of the classes of $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ into the images of $r\mapsto 2r$ and $r\mapsto 2r+1$ partitions the group into two disjoint sets of size $N\mathrm{/}2$, so that the radix-two factorisation of The radix-two even/odd factorisation of the DFT reduces the $N$-point transform to two transforms of length $N\mathrm{/}2$; equivalently, that reduction applies to every length $N\ge 2$.

The claim fails for $N=3$: doubling permutes the three classes of $\mathbb{Z}\mathrm{/}3\mathbb{Z}$, so the "even" classes are all of $\mathbb{Z}\mathrm{/}3\mathbb{Z}$ and the "odd" classes are all of $\mathbb{Z}\mathrm{/}3\mathbb{Z}$ as well; the two attempted index sets are not disjoint and have no length $M=N\mathrm{/}2=3\mathrm{/}2$ behind them. This says nothing against direct evaluation of the three-point transform, which is a finite sum like any other.

• Scope of the witness. It shows that the radix-two reduction needs $N$ even: for odd $N$, the attempted even and odd images do not form a partition. Other algorithms for odd lengths are outside this counterexample.

• Domains of doubling. For $N=2M$, doubling from $\mathbb{Z}\mathrm{/}M\mathbb{Z}$ into $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ is injective, as the factorisation lemma proves. For odd $N=2q+1$, $2(q+1)=N+1$, so $[q+1{]}_N$ is the multiplicative inverse of $[2{]}_N$. Thus doubling on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ is a permutation of the whole group; it cannot give one half of a partition.

For $N=4=2^2$ and $f=(f_0,f_1,f_2,f_3)\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}4}$, the recursion of The recursive radix-two fast Fourier transform takes the even part $e=(f_0,f_2)$ and the odd part $o=(f_1,f_3)$. The two length-two unnormalised transforms are $E=(f_0+f_2,f_0-f_2)$ and $O=(f_1+f_3,f_1-f_3)$, extended $2$-periodically, and the combine with twiddle factors $e^{-2\pi ik\mathrm{/}4}=(-i{)}^k$ gives

$X_0=f_0+f_1+f_2+f_3,X_2=f_0-f_1+f_2-f_3,$

$X_1=f_0-i{f}_1-f_2+i{f}_3,X_3=f_0+i{f}_1-f_2-i{f}_3\mathrm{.}$

These agree with direct evaluation of $X_k={\sum }_{x=0}^3{f}_x{e}^{-2\pi ikx\mathrm{/}4}$, as Correctness of the recursive radix-two FFT requires, and the operation count for this length is $16=2\cdot 2\cdot 4$ complex additions and multiplications in the model of The radix-two FFT uses $O(N{\log }_{2}N)$ complex arithmetic operations, which is the bound $2N{\log }_{2}N$ of that theorem at $N=4$ (here ${\log }_{2}4=2$ because $4=2^2$).