Solved

FFT 1D & 2D code with fixed point math..

Posted on 2000-05-10
10
434 Views
Last Modified: 2008-03-17
Hi there,
I'm trying to code Fast Fourier Transform here..
Yup.. I can get the code from some internet site..
But those code seems to use float data type.. Which takes longer time to be executed on non floating-point h/w processor..
I just wonder.. maybe some of you or some people has already code this?
And could you point me the code?
or share the code with me?
or any suggestion?

Regards,

-ari-
0
Comment
Question by:wayud
  • 5
  • 2
  • 2
  • +1
10 Comments
 
LVL 14

Expert Comment

by:AlexVirochovsky
ID: 2798824
You can find code of FFT in many URL.
For example http://www.dc.ee/Files/Programm.C
BUT: all codes use sin/cos and log (of course). Next depend not from code, but from translator: how translator realyze this operation? If with help
of floating point(and you computer without fp processor) will be used simulation, that slows down computation.
Of course , you can use you own cos/sin and log(but to write code, that works
faster that standart: not easy task).

 
0
 
LVL 3

Expert Comment

by:3rsrichard
ID: 2800228
You can improve the speed of most FFT algorithms by a careful adjustment of the sequence of math operations and good use of pointers.
Make sure it does the fastest math first, ie never do x = c*a + b*a make sure it does x = (c+b)*a.
Make sure it doesn't shuffle stuff between arrays for no good reason, and make sure it doesn't have to do wasteful address calculations, like don't do y[2n+1] = z[2n+1] figure out
the index first also figure out if your compiler does pointer+offset faster than array[index].
If you don't need great resolution (which you wouldn't get with integer) don't use sin and cos repeatedly, try a lookup table.
0
 
LVL 14

Expert Comment

by:AlexVirochovsky
ID: 2811744
wayud, what do you think about me and
3rsrichard comments?
0
Comprehensive Backup Solutions for Microsoft

Acronis protects the complete Microsoft technology stack: Windows Server, Windows PC, laptop and Surface data; Microsoft business applications; Microsoft Hyper-V; Azure VMs; Microsoft Windows Server 2016; Microsoft Exchange 2016 and SQL Server 2016.

 
LVL 84

Expert Comment

by:ozo
ID: 2812468
You could also do integer FFTs using roots of unity in the ring of integers modulo 2^n+1 instead of roots of unity in the complex ring
0
 

Author Comment

by:wayud
ID: 2813040
Thank you guys,
for your comment...
I've read a book about perform fixed point mathmatic on non floating-point processor..
It is by using 16-bit integer data type for all data..
then perform shift operation to adjust the result..
And also we have to use lookup table (which is also integer data type) instead of using sin& cos function in the code..
Alex, I don't understand what you mean by translator, and then simulation?
Thank 3rsrichard,.. yes.. I have done that..
ozo, I don't understand what you mean..
roots of unity in the ring of integers? it sounds too mathmatical for me..
0
 
LVL 14

Expert Comment

by:AlexVirochovsky
ID: 2813074
>>Alex, I don't understand what you mean by translator, and then simulation?

Usually,for making float computation
every translator(VC,BC,gcc,...) may use 2 ways:
1. Using floating coprocessor(and in this case it is fast)
2. Using simulation of floating computation without co-processor(and it is more slow).
Every function as cos, sin, lg,.. computes as summ of sequence by some formula with some accuraticy(depends from type of data: float,double, long double).
I means, that you can rewrite  such functions(say mycos, mysin,...), but
it is not easy task .
0
 
LVL 3

Expert Comment

by:3rsrichard
ID: 2814661
And, I recalled, there is an incremental version of FFT.  For instruments like signal analysers you don't have to do all the math at once, but get to spread it out over time.
I haven't looked at it in a looong time.
0
 
LVL 14

Expert Comment

by:AlexVirochovsky
ID: 2826754
wayud???
0
 
LVL 14

Accepted Solution

by:
AlexVirochovsky earned 150 total points
ID: 2881925
By you silence, i hope, that my and
3rsrichard comments help you.

To 3rsrichard : if I get PTS, I 'll send you same summ.
Alex
0
 

Author Comment

by:wayud
ID: 2884766
Answer accepted
0

Featured Post

Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.

839 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question