<< Chapter < Page Chapter >> Page >
X ( k ) = 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 ) = 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 willsupport the cyclic convolution. This means that if X ( k ) , H ( k ) , and Y ( k ) are the transforms of x ( n ) , h ( n ) , and y ( n ) respectively,

Y ( k ) = X ( k ) H ( k ) .

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

Y ( k ) = n = 0 N - 1 t ( n , k ) m = 0 N - 1 x ( m ) h ( n - m )
= m = 0 N - 1 n = 0 N - 1 x ( m ) h ( n - m ) t ( n , k ) .

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

= m = 0 N - 1 l = 0 N - 1 x ( m ) h ( l ) t ( l + m , k ) .

But from [link] , this must be

Y ( k ) = n = 0 N - 1 x ( n ) t ( n , k ) m = 0 N - 1 x ( m ) t ( m , k )
= m = 0 N - 1 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 [link] and [link] 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 )

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

t ( 2 m , k ) = t ( m , k ) t ( m , k ) = t 2 ( m , k )

For l = p m we likewise have

t ( p m , k ) = t p ( m , k )

and, therefore,

t N ( m , k ) = t ( N m , k ) = t ( 0 , k ) = 1 .

But

t ( m , k ) = t m ( 1 , k ) = t k ( m , 1 ) ,

therefore,

t ( m , k ) = t m k ( 1 , 1 ) .

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

X ( k ) = n = 0 N - 1 α n k x ( n )

where α is a root of order N , which means that N is the smallest integer such that α N = 1 .

Theorem 1 The transform [link] supports cyclic convolution if and only if α 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

N | O ( M )

where

O ( M ) = g c d { p 1 - 1 , p 2 - 1 , , p l - 1 }

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 m a x = O ( M ) .

One needs to find appropriate N , M , and α 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.
  • α should allow a simple multiplication for α n k x ( n ) .

We see that if M is even, it has a factor of 2 and, therefore, O ( M ) = N m a x = 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 = p q where p is prime. Then 2 p - 1 divides 2 p q - 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 2 p exist and the corresponding α = - 2 . Mersenne number transforms are not of as much interest because 2 p 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 t 4 and are composite for all t 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 b . For these Fermat primes the integer α = 3 is of order N = 2 b allowing the largest possible transform length. The integer α = 2 is of order N = 2 b = 2 t + 1 . This is particularly attractive since α to a power is multiplied times the data values in [link] .

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

t b M = F t N 2 N 2 N m a x α for N m a x
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 2
6 64 2 64 + 1 128 256 256 2

This table gives values of N for the two most important values of α which are 2 and 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 α = 2 , the fifth is the maximum length for α = 2 , the sixth is the maximum length for any α , and the seventh is the α 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] .

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Fast fourier transforms (6x9 version). OpenStax CNX. Aug 24, 2009 Download for free at http://cnx.org/content/col10683/1.5
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Fast fourier transforms (6x9 version)' conversation and receive update notifications?

Ask