# 12.5: Number Theoretic Transforms for Convolution

- Page ID
- 2039

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)\]

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)\]

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)\]

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)\]

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

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)\]

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)\]

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

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)\]

For \(l=0\) we have

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

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

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

For \(l=pm\) we likewise have

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

Therefore,

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

But

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

Therefore,

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

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)\]

where \(\alpha\) is a root of order \(N\), which means that \(N\) is the smallest integer such that \(\alpha ^N=1\).

**Theorem 1** The transform equation supports cyclic convolution if and only if \(\alpha\) 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)\]

where

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

and

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

This theorem is a more useful form of Theorem 1. Notice that \(N_{max}=O(M)\).

One needs to find appropriate \(N\), \(M\) and \(\alpha\) 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 \(\alpha ^{nk}x(n)\).

We see that if \(M\) is even, it has a factor of 2 and, therefore \(O(M)=N_{max}=1\) which implies \(M\) should be odd. If \(M\) is prime the \(O(M)=M-1\) which is as large as could be expected in a field of \(M\) integers. For \(M=2^k-1\), let \(k\) be a composite \(k=pq\) where \(p\) is prime. Then \(2^p-1\) divides \(2^{pq}-1\) and the maximum possible length of the transform will be governed by the length possible for \(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 \(2p\) exist and the corresponding \(\alpha =-2\). Mersenne number transforms are not of as much interest because \(2p\) is not highly composite and, therefore, we do not have FFT-type algorithms.

\(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 \(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=2^{2^t}+1\) are of interest. These numbers are known as Fermat numbers. Fermat numbers are prime for \(0\leq t\leq 4\) and are composite for all \(t\geq 5\).

Since Fermat numbers up to \(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 \(\alpha =3\) is of order \(N=2^b\) allowing the largest possible transform length. The integer \(\alpha =2\) is of order \(N=2^b=2^{t+1}\). This is particularly attractive since \(\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 \(N\) for the two most important values of \(\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 \(\alpha =2\), the fifth is the maximum length for \(\alpha =\sqrt{2}\), the sixth is the maximum length for any \(\alpha\), and the seventh is the \(\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