<< Chapter < Page Chapter >> Page >

Here we use three methods to facilitate the construction of prime length FFT modules. First, the matrix exchange property [link] , [link] , [link] is used so that the transpose of the reduction operator can be used rather than the morecomplicated CRT reconstruction operator. This is then combined with the numerical method [link] for obtaining the multiplication coefficients rather than the direct use of the CRT. We also deviate from the Toom-Cook algorithm,because it requires too many additions for the lengths in which we are interested. Instead we use an iterated polynomial multiplication algorithm [link] . We have incorporated these three ideas into a single structural procedure that automatesthe design of prime length FFTs.

Matrix description

It is important that each step in the Winograd FFT can be described using matrices. By expressing cyclic convolution as a bilinear form, a compact form of prime length DFTs can be obtained.

If y is the cyclic convolution of h and x , then y can be expressed as

y = C [ A x . * B h ]

where, using the Matlab convention, . * represents point by point multiplication. When A , B , and C are allowed to be complex, A and B are seen to be the DFT operator and C , the inverse DFT. When only real numbers are allowed, A , B , and C will be rectangular. This form of convolution is presented with many examples in [link] . Using the matrix exchange property explained in [link] and [link] this form can be written as

y = R B T [ C T R h . * A x ]

where R is the permutation matrix that reverses order.

When h is fixed, as it is when considering prime length DFTs, the term C T R h can be precomputed and a diagonal matrix D formed by D = d i a g { C T R h } . This is advantageous because in general, C is more complicated than B , so the ability to “hide" C saves computation. Now y = R B T D A x or y = R A T D A x since A and B can be the same; they implement a polynomial reduction. The form y = R T D A x T can also be used for the prime length DFTs, it is only necessary to permute the entries of x and to ensure that theDC term is computed correctly. The computation of the DC term is simple, for the residue of a polynomial modulo a - 1 is always the sum of the coefficients. After adding the x 0 term of the original input sequence, to the s - l residue, the DC term is obtained. Now D F T { x } = R A T D A x . In [link] Johnson observes that by permuting the elements on the diagonal of D , the output can be permuted, so that the R matrix can be hidden in D , and D F T { x } = A T D A x . From the knowledge of this form, once A is found, D can be found numerically [link] .

Programming the design procedure

Because each of the above steps can be described by matrices, the development of a prime length FFTs is made convenient with the use of a matrix oriented programminglanguage such as Matlab. After specifying the appropriate matrices that describe the desired FFT algorithm, generating code involves compiling the matrices into the desiredcode for execution.

Each matrix is a section of one stage of the flow graph that corresponds to the DFT program. The four stages are:

  1. Permutation Stage: Permutes input and output sequence.
  2. Reduction Stage: Reduces the cyclic convolution to smaller polynomial products.
  3. Polynomial Product Stage: Performs the polynomial multiplications.
  4. Multiplication Stage: Implements the point-by-point multiplication in the bilinear form.

Questions & Answers

Is there any normative that regulates the use of silver nanoparticles?
Damian Reply
what king of growth are you checking .?
What fields keep nano created devices from performing or assimulating ? Magnetic fields ? Are do they assimilate ?
Stoney Reply
why we need to study biomolecules, molecular biology in nanotechnology?
Adin Reply
yes I'm doing my masters in nanotechnology, we are being studying all these domains as well..
what school?
biomolecules are e building blocks of every organics and inorganic materials.
anyone know any internet site where one can find nanotechnology papers?
Damian Reply
sciencedirect big data base
Introduction about quantum dots in nanotechnology
Praveena Reply
what does nano mean?
Anassong Reply
nano basically means 10^(-9). nanometer is a unit to measure length.
do you think it's worthwhile in the long term to study the effects and possibilities of nanotechnology on viral treatment?
Damian Reply
absolutely yes
how to know photocatalytic properties of tio2 nanoparticles...what to do now
Akash Reply
it is a goid question and i want to know the answer as well
characteristics of micro business
for teaching engĺish at school how nano technology help us
Do somebody tell me a best nano engineering book for beginners?
s. Reply
there is no specific books for beginners but there is book called principle of nanotechnology
what is fullerene does it is used to make bukky balls
Devang Reply
are you nano engineer ?
fullerene is a bucky ball aka Carbon 60 molecule. It was name by the architect Fuller. He design the geodesic dome. it resembles a soccer ball.
what is the actual application of fullerenes nowadays?
That is a great question Damian. best way to answer that question is to Google it. there are hundreds of applications for buck minister fullerenes, from medical to aerospace. you can also find plenty of research papers that will give you great detail on the potential applications of fullerenes.
what is the Synthesis, properties,and applications of carbon nano chemistry
Abhijith Reply
Mostly, they use nano carbon for electronics and for materials to be strengthened.
is Bucky paper clear?
carbon nanotubes has various application in fuel cells membrane, current research on cancer drug,and in electronics MEMS and NEMS etc
so some one know about replacing silicon atom with phosphorous in semiconductors device?
s. Reply
Yeah, it is a pain to say the least. You basically have to heat the substarte up to around 1000 degrees celcius then pass phosphene gas over top of it, which is explosive and toxic by the way, under very low pressure.
Do you know which machine is used to that process?
how to fabricate graphene ink ?
for screen printed electrodes ?
What is lattice structure?
s. Reply
of graphene you mean?
or in general
in general
Graphene has a hexagonal structure
On having this app for quite a bit time, Haven't realised there's a chat room in it.
what is biological synthesis of nanoparticles
Sanket Reply
how did you get the value of 2000N.What calculations are needed to arrive at it
Smarajit Reply
Privacy Information Security Software Version 1.1a
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!

Source:  OpenStax, Fast fourier transforms. OpenStax CNX. Nov 18, 2012 Download for free at http://cnx.org/content/col10550/1.22
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Fast fourier transforms' conversation and receive update notifications?