12.5: Number Theoretic Transforms for Convolution

Here we look at the conditions placed on a general linear transform in order for it to support cyclic convolution. The form of a linear transformation of a length-N sequence of number is given by

\[X(k)=\sum_{n=0}^{N-1}t(n,k)x(n) \nonumber \]

for \(k=0,1,...,(N-1)\). The definition of cyclic convolution of two sequences is given by

\[y(n)=\sum_{m=0}^{N-1}x(m)h(n-m) \nonumber \]

for \(n=0,1,...,(N-1)\) and all indices evaluated modulo \(N\). We would like to find the properties of the transformation such that it will support the cyclic convolution. This means that if \(X(k),\; H(k),\; Y(k)\) are the transforms of \(x(n),\; h(n),\; y(n)\) respectively,

\[Y(k)=X(k)H(k) \nonumber \]

The conditions are derived by taking the transform defined in the above equations of both sides of the equation which gives

\[Y(k)=\sum_{n=0}^{N-1}t(n,k)\sum_{m=0}^{N-1}x(m)h(n-m) \nonumber \]

\[Y(k)=\sum_{m=0}^{N-1}\sum_{n=0}^{N-1}x(m)h(n-m)t(n,k) \nonumber \]

Making the change of index variables, \(l=n-m\) gives

\[Y(k)=\sum_{m=0}^{N-1}\sum_{l=0}^{N-1}x(m)h(l)t(l+m,k) \nonumber \]

But from the equation, this must be

\[Y(k)=\sum_{n=0}^{N-1}x(n)t(n,k)\sum_{m=0}^{N-1}x(m)t(m,k) \nonumber \]

\[Y(k)=\sum_{m=0}^{N-1}\sum_{l=0}^{N-1}x(m)h(l)t(n,k)t(l,k) \nonumber \]

This must be true for all \(\(x(n),\; h(n)\) and \(k\), therefore from the above equations we have

\[t(m+l,k)=t(m,k)t(l,k) \nonumber \]

For \(l=0\) we have

\[t(m,k)=t(m,k)t(0,k) \nonumber \]

Therefore, \(t(0,k)=1\). For \(l=m\) we have

\[t(2m,k)=t(m,k)t(m,k)=t^2(m,k) \nonumber \]

For \(l=pm\) we likewise have

\[t(pm,k)=t^p(m,k) \nonumber \]

Therefore,

\[t^N(m,k)=t(Nm,k)=t(0,k)=1 \nonumber \]

But

\[t(m,k)=t^m(1,k)=t^k(m,1) \nonumber \]

Therefore,

\[t(m,k)=t^{mk}(1,1) \nonumber \]

Defining \(t(1,1)=\alpha\) gives the form for our general linear transform equation as

\[X(k)=\sum_{n=0}^{N-1}\alpha ^{nk}x(n) \nonumber \]

where \(\alpha\) is a root of order \(N\)NN" role="presentation" style="position:relative;" tabindex="0">, which means that \(N\)NN" role="presentation" style="position:relative;" tabindex="0"> is the smallest integer such that αN=1αN=1" role="presentation" style="position:relative;" tabindex="0">\(\alpha ^N=1\).

Theorem 1 The transform equation supports cyclic convolution if and only if \(\alpha\)αα" role="presentation" style="position:relative;" tabindex="0"> is a root of order \(N\) and \(N^{-1}\) is defined.

Theorem 2 The transform equation supports cyclic convolution if and only if

\[N\mid O(M) \nonumber \]

where

\[O(M)=\text{gcd}\; \left \{ p_1-1,p_2-1,...,p_l-1 \right \} \nonumber \]

and

\[M=p_{1}^{r_1}p_{2}^{r_2}...p_{l}^{r_l} \nonumber \]

This theorem is a more useful form of Theorem 1. Notice that Nmax=O(M)Nmax=O(M)" role="presentation" style="position:relative;" tabindex="0">\(N_{max}=O(M)\).

One needs to find appropriate \(N\), \(M\) and \(\alpha\)NN" role="presentation" style="position:relative;" tabindex="0"> such that

• \(N\) should be appropriate for a fast algorithm and handle the desired sequence lengths.
• \(M\) should allow the desired dynamic range of the signals and should allow simple modular arithmetic.
• \(\alpha\) should allow a simple multiplication for αnkx(n)αnkx(n)" role="presentation" style="position:relative;" tabindex="0">\(\alpha ^{nk}x(n)\).

We see that if MM" role="presentation" style="position:relative;" tabindex="0">\(M\) is even, it has a factor of 2 and, therefore \(O(M)=N_{max}=1\) which implies MM" role="presentation" style="position:relative;" tabindex="0">\(M\) should be odd. If MM" role="presentation" style="position:relative;" tabindex="0">\(M\) is prime the O(M)=M-1O(M)=M-1" role="presentation" style="position:relative;" tabindex="0">\(O(M)=M-1\) which is as large as could be expected in a field of MM" role="presentation" style="position:relative;" tabindex="0">\(M\) integers. For \(M=2^k-1\), let \(k\) be a composite k=pqk=pq" role="presentation" style="position:relative;" tabindex="0">\(k=pq\) where \(p\) is prime. Then 2p-12p-1" role="presentation" style="position:relative;" tabindex="0">\(2^p-1\) divides 2pq-12pq-1" role="presentation" style="position:relative;" tabindex="0">\(2^{pq}-1\) and the maximum possible length of the transform will be governed by the length possible for 2p-12p-1" role="presentation" style="position:relative;" tabindex="0">\(2^p-1\). Therefore, only the prime \(k\) need be considered interesting. Numbers of this form are know as Mersenne numbers and have been used by Rader. For Mersenne number transforms, it can be shown that transforms of length at least MM" role="presentation" style="position:relative;" tabindex="0">\(2p\)2p2p" role="presentation" style="position:relative;" tabindex="0">kk" role="presentation" style="position:relative;" tabindex="0">2p-12p-1" role="presentation" style="position:relative;" tabindex="0"> exist and the corresponding α=-2α=-2" role="presentation" style="position:relative;" tabindex="0">\(\alpha =-2\). Mersenne number transforms are not of as much interest because MM" role="presentation" style="position:relative;" tabindex="0">\(2p\) is not highly composite and, therefore, we do not have FFT-type algorithms.

2p2p" role="presentation" style="position:relative;" tabindex="0">For \(M=2^k+1\) and \(k\) odd, 3 divides \(2^k+1\) and the maximum possible transform length is 2. Thus we consider only even \(k\). Let \(k=s2^t\), where \(s\) is an odd integer. Then 22t22t" role="presentation" style="position:relative;" tabindex="0">\(2^{2^t}\) divides \(2^{s2^t}+1\) and the length of the possible transform will be governed by the length possible for \(2^{s2^t}+1\). Therefore, integers of the form M=22t+1M=22t+1" role="presentation" style="position:relative;" tabindex="0">\(M=2^{2^t}+1\) are of interest. These numbers are known as Fermat numbers. Fermat numbers are prime for 0≤t≤40≤t≤4" role="presentation" style="position:relative;" tabindex="0">\(0\leq t\leq 4\) and are composite for all \(t\geq 5\).

Since Fermat numbers up to F4F4" role="presentation" style="position:relative;" tabindex="0">\(F_4\) are prime, \(O(F_t)=2^b\) where \(b=2^t\) and we can have a Fermat number transform for any length \(N=2^m\) where \(m\leq b\). For these Fermat primes the integer α=3α=3" role="presentation" style="position:relative;" tabindex="0">\(\alpha =3\) is of order \(N=2^b\) allowing the largest possible transform length. The integer α=2α=2" role="presentation" style="position:relative;" tabindex="0">\(\alpha =2\) is of order N=2b=2t+1N=2b=2t+1" role="presentation" style="position:relative;" tabindex="0">\(N=2^b=2^{t+1}\). This is particularly attractive since αα" role="presentation" style="position:relative;" tabindex="0">\(\alpha\) to a power is multiplied times the data values in the equation.

The following table gives possible parameters for various Fermat number moduli.

t	b	\(M=F_t\)	\(N_2\)	\(N_{\sqrt{2}}\)	\(N_{max}\)	\(\alpha \: \text{for}\: N_{max}\)
3	8	\(2^8+1\)	16	32	256	3
4	16	\(2^{16}+1\)	32	64	65536	3
5	32	\(2^{32}+1\)	64	128	128	\(\sqrt{2}\)
6	64	\(2^{64}+1\)	128	256	256	\(\sqrt{2}\)

Table 12.5.1 Fermat number moduli

This table gives values of NN" role="presentation" style="position:relative;" tabindex="0">\(N\) for the two most important values of αα" role="presentation" style="position:relative;" tabindex="0">\(\alpha\) which are 2 and \(\sqrt{2}\). The second column give the approximate number of bits in the number representation. The third column gives the Fermat number modulus, the fourth is the maximum convolution length for α=2α=2" role="presentation" style="position:relative;" tabindex="0">\(\alpha =2\), the fifth is the maximum length for α=2α=2" role="presentation" style="position:relative;" tabindex="0">\(\alpha =\sqrt{2}\), the sixth is the maximum length for any αα" role="presentation" style="position:relative;" tabindex="0">\(\alpha\), and the seventh is the αα" role="presentation" style="position:relative;" tabindex="0">αα" role="presentation" style="position:relative;" tabindex="0">αα" role="presentation" style="position:relative;" tabindex="0">\(\alpha\) for that maximum length. Remember that the first two rows have a Fermat number modulus which is prime and second two rows have a composite Fermat number as modulus. Note the differences.

Contributor

• ContribEEBurrus