Hi I am looking for pure ANSI-C DIF FFT code for implementing on hardware. my implementation platform do not support sin(), cos() or trigonometric functions so I need a code with twiddle factor table or Trigonometric function tables. I have read Alan V. Oppenhum text book in Discrete Time signal processing, in this book there is a dedicated chapter for computation of FFT. are there any where that I could see implementation of these algorithms ? Regards Alireza Haghdoost
Pure ANSI-C DIF FFT code
Started by ●July 6, 2008
Reply by ●July 6, 20082008-07-06
On 6 Jul, 06:33, ARH <haghdo...@gmail.com> wrote:> Hi > > I am looking for pure ANSI-C DIF FFT code for implementing on > hardware. my implementation platform do not support sin(), cos() or > trigonometric functionsI thought those functions were part of the ANSI C standard?> so I need a code with twiddle factor table or > Trigonometric function tables.Check out the classic book by Abramowitz & Stegun. Rune
Reply by ●July 6, 20082008-07-06
ARH wrote:> Hi > > I am looking for pure ANSI-C DIF FFT code for implementing on > hardware. my implementation platform do not support sin(), cos() or > trigonometric functions so I need a code with twiddle factor table or > Trigonometric function tables. > I have read Alan V. Oppenhum text book in Discrete Time signal > processing, in this book there is a dedicated chapter for computation > of FFT. are there any where that I could see implementation of these > algorithms ? > > Regards > Alireza HaghdoostIf you know the size of the FFT (how would you write the code if you didn't?) you can compute the twiddle factors at of before compile time. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 7, 20082008-07-07
> If you know the size of the FFT (how would you write the code if you > didn't?) you can compute the twiddle factors at of before compile time.Hi Jerry Thanks for your reply, Ofcourse my FFT size is fixed, So do you think that all the thing hat I need is just a twiddle factor table ? Regards ARH
Reply by ●July 7, 20082008-07-07
> Hi Jerry > > Thanks for your reply, Ofcourse my FFT size is fixed, So do you think > that all the thing hat I need is just a twiddle factor table ? > > Regards > ARHTwiddle factor table have N^2 element and if I use it for computing X[k], the computation grows from O(NlogN) into O(N^2), are there any other methods ? ARH
Reply by ●July 7, 20082008-07-07
ARH wrote:>> If you know the size of the FFT (how would you write the code if you >> didn't?) you can compute the twiddle factors at of before compile time. > > Hi Jerry > > Thanks for your reply, Ofcourse my FFT size is fixed, So do you think > that all the thing hat I need is just a twiddle factor table ?It could be a large table, but yes. Basically, you need to *have* the twiddle factors. You don't need to *compute* them. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 7, 20082008-07-07
ARH wrote:>> Hi Jerry >> >> Thanks for your reply, Ofcourse my FFT size is fixed, So do you think >> that all the thing hat I need is just a twiddle factor table ? >> >> Regards >> ARH > > Twiddle factor table have N^2 element and if I use it for computing > X[k], the computation grows from O(NlogN) into O(N^2), are there any > other methods ?What makes a table lookup slower than a trig computation? Where does N^2 come in? Computing the table entries is done when the code is written, not when it's executed. There is a lot of redundancy in that table. If you work out the pattern, you may be able to collapse it substantially. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 8, 20082008-07-08
On Jul 7, 8:08�am, Jerry Avins <j...@ieee.org> wrote:> ARH wrote: > >> Hi Jerry > > >> Thanks for your reply, Ofcourse my FFT size is fixed, So do you think > >> that all the thing hat I need is just a twiddle factor table ? > > >> Regards > >> ARH > > > Twiddle factor table have N^2 element and if I use it for computing > > X[k], the computation grows from O(NlogN) into O(N^2), are there any > > other methods ? > > What makes a table lookup slower than a trig computation? Where does N^2 > come in? Computing the table entries is done when the code is written, > not when it's executed. > > There is a lot of redundancy in that table. If you work out the pattern, > you may be able to collapse it substantially. > > Jerry > -- > Engineering is the art of making what you want from things you can get. > �����������������������������������������������������������������������Hi for designing an FFT processor the number of sampleling points has been determined, so we could easily compute twiddle factors and store them in a table. then we could compute each X[k] from multiplication of proper x[n]s with pre defined twiddle factors in the table. the idea is so simple but I didn't found any one use it, are there any problem behind this idea ? ARH
Reply by ●July 8, 20082008-07-08
ARH wrote:> On Jul 7, 8:08 am, Jerry Avins <j...@ieee.org> wrote: >> ARH wrote: >>>> Hi Jerry >>>> Thanks for your reply, Ofcourse my FFT size is fixed, So do you think >>>> that all the thing hat I need is just a twiddle factor table ? >>>> Regards >>>> ARH >>> Twiddle factor table have N^2 element and if I use it for computing >>> X[k], the computation grows from O(NlogN) into O(N^2), are there any >>> other methods ? >> What makes a table lookup slower than a trig computation? Where does N^2 >> come in? Computing the table entries is done when the code is written, >> not when it's executed. >> >> There is a lot of redundancy in that table. If you work out the pattern, >> you may be able to collapse it substantially. >> >> Jerry >> -- >> Engineering is the art of making what you want from things you can get. >> ����������������������������������������������������������������������� > > Hi > > for designing an FFT processor the number of sampleling points has > been determined, so we could easily compute twiddle factors and store > them in a table. then we could compute each X[k] from multiplication > of proper x[n]s with pre defined twiddle factors in the table. > the idea is so simple but I didn't found any one use it, are there > any problem behind this idea ?Size of table. Speed of access. It is used where appropriate. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 8, 20082008-07-08
for designing an FFT processor the number of sampleling points have been determined, so we could easily compute twiddle factors and store them in a table. then we could compute each X[k] from multiplication of proper x[n]s with pre defined twiddle factors in the table. the idea is so simple but I didn't found any one use it, are there any problem behind this idea ? ARH> Jerry
