0.12 Convolution algorithms  (Page 7/7)

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

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

The conditions are derived by taking the transform defined in [link] of both sides of equation [link] which gives

Making the change of index variables, $l=n-m$ , gives

But from [link] , this must be

This must be true for all $x\left(n\right)$ , $h\left(n\right)$ , and $k$ , therefore from [link] and [link] we have

For $l=0$ we have

and, therefore, $t(0,k)=1$ . For $l=m$ we have

For $l=pm$ we likewise have

and, therefore,

But

therefore,

Defining $t(1,1)=\alpha$ gives the form for our general linear transform [link] as

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 [link] supports cyclic convolution if and only if $\alpha$ is a root of order $N$ and $N^{-1}$ is defined.

This is discussed in [link] , [link] .

Theorem 2 The transform [link] supports cyclic convolution if and only if

where

and

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

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\left(n\right)$ .

We see that if $M$ is even, it has a factor of 2 and, therefore, $O\left(M\right)=N_{max}=1$ which implies $M$ should be odd. If $M$ is prime the $O\left(M\right)=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 transformwill 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 [link] . 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.

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=s{2}^t$ , where $s$ is an odd integer. Then $2^{2^t}$ divides $2^{s{2}^t}+1$ and the length of the possible transform will be governed by the length possiblefor $2^{2^t}+1$ . Therefore, integers of the form $M=2^{2^t}+1$ are of interest. These numbers are known as Fermat numbers [link] . Fermat numbers are prime for $0\le t\le 4$ and are composite for all $t\ge 5$ .

Since Fermat numbers up to $F_4$ are prime, $O\left(F_t\right)=2^b$ where $b=2^t$ and we can have a Fermat number transform for any length $N=2^m$ where $m\le 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=2b=2^{t+1}$ . This is particularly attractive since $\alpha$ to a power is multiplied times the data values in [link] .

The following table gives possible parameters for various 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 columngives 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 rowshave a composite Fermat number as modulus. Note the differences.

The books, articles, and presentations that discuss NTT and related topics are [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] , [link] . A recent book discusses NT in a signal processing context [link] .