An implementation of the fast Fourier transform FFT in C

Question

Where can I find a free  very quick  and reliable implementation of FFT in C    That can be used in a product  Or are there any restrictions

User · Answer

Math NET s Iridium library provides a fast  regularly updated collection of math-related functions  including the FFT  It s licensed under the LGPL so you are free to use it in commercial products

User · Answer

Here s another  a C  port of the Ooura FFT   It s reasonably fast   The package also includes overlap add convolution and some other DSP stuff  under the MIT license   https   github com hughpyle inguz-DSPUtil blob master Fourier cs

User · Answer

I see this is an old thread  but for what it s worth  here s a free  MIT License  1-D power-of-2-length-only C  FFT implementation I wrote in 2010  I haven t compared its performance to other C  FFT implementations  I wrote it mainly to compare the performance of Flash ActionScript and Silverlight C   The latter is much faster  at least for number crunching         Performs an in-place complex FFT        Released under the MIT License       Copyright  c  2010 Gerald T  Beauregard       Permission is hereby granted  free of charge  to any person obtaining a copy    of this software and associated documentation files  the  quot Software quot    to    deal in the Software without restriction  including without limitation the    rights to use  copy  modify  merge  publish  distribute  sublicense  and or    sell copies of the Software  and to permit persons to whom the Software is    furnished to do so  subject to the following conditions        The above copyright notice and this permission notice shall be included in    all copies or substantial portions of the Software        THE SOFTWARE IS PROVIDED  quot AS IS quot   WITHOUT WARRANTY OF ANY KIND  EXPRESS OR    IMPLIED  INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY     FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT  IN NO EVENT SHALL THE    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM  DAMAGES OR OTHER    LIABILITY  WHETHER IN AN ACTION OF CONTRACT  TORT OR OTHERWISE  ARISING    FROM  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS    IN THE SOFTWARE      public class FFT2          Element for linked list in which we store the        input output data  We use a linked list because        for sequential access it s faster than array index      class FFTElement               public double re   0 0         Real component         public double im   0 0         Imaginary component         public FFTElement next         Next element in linked list         public uint revTgt             Target position post bit-reversal            private uint m logN   0            log2 of FFT size     private uint m N   0               FFT size     private FFTElement   m X           Vector of linked list elements                             public FFT2                               Initialize class to perform FFT of specified size                 param   logN    Log2 of FFT length  e g  for 512 pt FFT  logN   9              public void init          uint logN                 m logN   logN          m N    uint  1  lt  lt   int m logN               Allocate elements for linked list of complex numbers          m X   new FFTElement m N           for  uint k   0  k  lt  m N  k                m X k    new FFTElement                Set up  quot next quot  pointers          for  uint k   0  k  lt  m N-1  k                m X k  next   m X k 1               Specify target for bit reversal re-ordering          for  uint k   0  k  lt  m N  k                 m X k  revTgt   BitReverse k logN                         Performs in-place complex FFT                 param   xRe     Real part of input output         param   xIm     Imaginary part of input output         param   inverse If true  do an inverse FFT             public void run          double   xRe          double   xIm          bool inverse   false                 uint numFlies   m N  gt  gt  1       Number of butterflies per sub-FFT         uint span   m N  gt  gt  1           Width of the butterfly         uint spacing   m N             Distance between start of sub-FFTs         uint wIndexStep   1            Increment for twiddle table index             Copy data into linked complex number objects            If it s an IFFT  we divide by N while we re at it         FFTElement x   m X 0           uint k   0          double scale   inverse   1 0 m N   1 0          while  x    null                        x re   scale xRe k               x im   scale xIm k               x   x next              k                          For each stage of the FFT         for  uint stage   0  stage  lt  m logN  stage                             Compute a multiplier factor for the  quot twiddle factors quot                  The twiddle factors are complex unit vectors spaced at                regular angular intervals  The angle by which the twiddle                factor advances depends on the FFT stage  In many FFT                implementations the twiddle factors are cached  but because                array lookup is relatively slow in C   it s just                as fast to compute them on the fly              double wAngleInc   wIndexStep   2 0 Math PI m N              if  inverse    false                  wAngleInc    -1              double wMulRe   Math Cos wAngleInc               double wMulIm   Math Sin wAngleInc                for  uint start   0  start  lt  m N  start    spacing                                FFTElement xTop   m X start                   FFTElement xBot   m X start span                    double wRe   1 0                  double wIm   0 0                      For each butterfly in this stage                 for  uint flyCount   0  flyCount  lt  numFlies    flyCount                                           Get the top  amp  bottom values                     double xTopRe   xTop re                      double xTopIm   xTop im                      double xBotRe   xBot re                      double xBotIm   xBot im                          Top branch of butterfly has addition                     xTop re   xTopRe   xBotRe                      xTop im   xTopIm   xBotIm                          Bottom branch of butterly has subtraction                         followed by multiplication by twiddle factor                     xBotRe   xTopRe - xBotRe                      xBotIm   xTopIm - xBotIm                      xBot re   xBotRe wRe - xBotIm wIm                      xBot im   xBotRe wIm   xBotIm wRe                          Advance butterfly to next top  amp  bottom positions                     xTop   xTop next                      xBot   xBot next                          Update the twiddle factor  via complex multiply                        by unit vector with the appropriate angle                         wRe   j wIm     wRe   j wIm  x  wMulRe   j wMulIm                      double tRe   wRe                      wRe   wRe wMulRe - wIm wMulIm                      wIm   tRe wMulIm   wIm wMulRe                                               numFlies  gt  gt   1         Divide by 2 by right shift             span  gt  gt   1              spacing  gt  gt   1              wIndexStep  lt  lt   1       Multiply by 2 by left shift                       The algorithm leaves the result in a scrambled order             Unscramble while copying values from the complex            linked list elements back to the input output vectors          x   m X 0           while  x    null                        uint target   x revTgt              xRe target    x re              xIm target    x im              x   x next                                  Do bit reversal of specified number of places of an int        For example  1101 bit-reversed is 1011                param   x       Number to be bit-reverse          param   numBits Number of bits in the number              private uint BitReverse          uint x          uint numBits                uint y   0          for  uint i   0  i  lt  numBits  i                          y  lt  lt   1              y    x  amp  0x0001              x  gt  gt   1                    return y

User · Answer

AForge net is a free  open-source  library with Fast Fourier Transform support   See Sources Imaging ComplexImage cs for usage  Sources Math FourierTransform cs for implemenation

User · Answer

http   www exocortex org dsp  is an open-source C  mathematics library with FFT algorithms

User · Answer

http   www exocortex org dsp  is an open-source C  mathematics library with FFT algorithms

User · Answer

For a multi-threaded implementation tuned for Intel processors I d check out Intel s MKL library   It s not free  but it s afforable  less than  100  and blazing fast - but you d need to call it s C dll s via P Invokes   The Exocortex project stopped development 6 years ago  so I d be careful using it if this is an important project

User · Answer

An old question but it still shows up in Google results     A very un-restrictive MIT Licensed C     NET library can be found at   https   www codeproject com articles 1107480 dsplib-fft-dft-fourier-transform-library-for-net  This library is fast as it parallel threads on multiple cores and is very complete and ready to use

User · Answer

The guy that did AForge did a fairly good job but it s not commercial quality   It s great to learn from but you can tell he was learning too so he has some pretty serious mistakes like assuming the size of an image instead of using the correct bits per pixel   I m not knocking the guy  I respect the heck out of him for learning all that and show us how to do it  I think he s a Ph D now or at least he s about to be so he s really smart it s just not a commercially usable library   The Math Net library has its own weirdness when working with Fourier transforms and complex images numbers  Like  if I m not mistaken  it outputs the Fourier transform in human viewable format which is nice for humans if you want to look at a picture of the transform but it s not so good when you are expecting the data to be in a certain format  the normal format   I could be mistaken about that but I just remember there was some weirdness so I actually went to the original code they used for the Fourier stuff and it worked much better   ExocortexDSP v1 2 http   www exocortex org dsp    Math net also had some other funkyness I didn t like when dealing with the data from the FFT  I can t remember what it was I just know it was much easier to get what I wanted out of the ExoCortex DSP library  I m not a mathematician or engineer though  to those guys it might make perfect sense   So  I use the FFT code yanked from ExoCortex  which Math Net is based on  without anything else and it works great   And finally  I know it s not C   but I ve started looking at using FFTW  http   www fftw org     And this guy already made a C  wrapper so I was going to check it out but haven t actually used it yet   http   www sdss jhu edu  tamas bytes fftwcsharp html   OH  I don t know if you are doing this for school or work but either way there is a GREAT free lecture series given by a Stanford professor on iTunes University     https   podcasts apple com us podcast the-fourier-transforms-and-its-applications id384232849

User · Answer

Math NET s Iridium library provides a fast  regularly updated collection of math-related functions  including the FFT  It s licensed under the LGPL so you are free to use it in commercial products

User · Answer

The Numerical Recipes website  http   www nr com   has an FFT if you don t mind typing it in   I am working on a project converting a Labview program to C  2008   NET 3 5 to acquire data and then look at the frequency spectrum   Unfortunately the Math Net uses the latest  NET framework  so I couldn t use that FFT    I tried the Exocortex one - it worked but the results to match the Labview results and I don t know enough FFT theory to know what is causing the problem   So I tried the FFT on the numerical recipes website and it worked    I was also able to program the Labview low sidelobe window  and had to introduce a scaling factor      You can read the chapter of the Numerical Recipes book as a guest on thier site  but the book is so useful that I highly recomend purchasing it   Even if you do end up using the Math NET FFT

User · Answer

AForge net is a free  open-source  library with Fast Fourier Transform support   See Sources Imaging ComplexImage cs for usage  Sources Math FourierTransform cs for implemenation

[c#] An implementation of the fast Fourier transform (FFT) in C#

Examples related to c#

Examples related to signal-processing

Examples related to fft