BogaudioModules

BogaudioModules for VCV Rack
Log | Files | Refs | README | LICENSE

readme.txt (10918B)


      1 ==============================================================================
      2 
      3         FFTReal
      4         Version 2.11
      5 
      6         Fourier transformation (FFT, IFFT) library specialised for real data
      7         Portable ISO C++
      8 
      9         Copyright (c) 1999-2010 Laurent de Soras
     10         Object Pascal port (c) Frederic Vanmol
     11 
     12 ==============================================================================
     13 
     14 
     15 
     16 Contents:
     17 
     18 1. Legal
     19 2. Content
     20 3. Using FFTReal
     21 3.1 FFTReal - Length fixed at run-time
     22 3.2 FFTRealFixLen - Length fixed at compile-time
     23 3.3 Data organisation
     24 4. Compilation and testing
     25 5. History
     26 6. Contact
     27 
     28 
     29 
     30 1. Legal
     31 --------
     32 
     33 FFTReal is distributed under the terms of the Do What The Fuck You Want To
     34 Public License. 
     35 
     36 Check the file license.txt to get full information about the license.
     37 
     38 
     39 
     40 2. Content
     41 ----------
     42 
     43 FFTReal is a library to compute Discrete Fourier Transforms (DFT) with the
     44 FFT algorithm (Fast Fourier Transform) on arrays of real numbers. It can
     45 also compute the inverse transform.
     46 
     47 You should find in this package a lot of files ; some of them are of
     48 particular interest:
     49 - readme.txt          : you are reading it
     50 - ffft/FFTReal.h      : FFT, length fixed at run-time
     51 - ffft/FFTRealFixLen.h: FFT, length fixed at compile-time
     52 - delphi/FFTReal.pas  : Pascal implementation (working but not up-to-date)
     53 
     54 
     55 
     56 3. Using FFTReal
     57 ----------------
     58 
     59 Important - if you were using older versions of FFTReal (up to 1.03), some
     60 things have changed. FFTReal is now a template. Therefore use FFTReal<float>
     61 or FFTReal<double> in your code depending on the application datatype. The
     62 flt_t typedef has been removed. And if you were previously using FFTReal 2.0,
     63 note that all the classes have moved to the ffft namespace.
     64 
     65 You have two ways to use FFTReal. In the first way, the FFT has its length
     66 fixed at run-time, when the object is instanciated. It means that you have
     67 not to know the length when you write the code. This is the usual way of
     68 proceeding.
     69 
     70 
     71 3.1 FFTReal - Length fixed at run-time
     72 --------------------------------------
     73 
     74 Just instanciate one time a FFTReal object. Specify the data type you want
     75 as template parameter (only floating point: float, double, long double or
     76 custom type). The constructor precompute a lot of things, so it may be a bit
     77 long. The parameter is the number of points used for the next FFTs. It must
     78 be a power of 2:
     79 
     80    #include "ffft/FFTReal.h"
     81    ...
     82    long len = 1024;
     83    ...
     84    // 1024-point FFT object constructed.
     85    ffft::FFTReal <float> fft_object (len);
     86 
     87 Then you can use this object to compute as many FFTs and IFFTs as you want.
     88 They will be computed very quickly because a lot of work has been done in the
     89 object construction.
     90 
     91    float x [1024];
     92    float f [1024];
     93 
     94    ...
     95    fft_object.do_fft (f, x);     // x (real) --FFT---> f (complex)
     96    ...
     97    fft_object.do_ifft (f, x);    // f (complex) --IFFT--> x (real)
     98    fft_object.rescale (x);       // Post-scaling should be done after FFT+IFFT
     99    ...
    100 
    101 x [] and f [] are floating point number arrays. x [] is the real number
    102 sequence which we want to compute the FFT. f [] is the result, in the
    103 "frequency" domain. f has the same number of elements as x [], but f []
    104 elements are complex numbers. The routine uses some FFT properties to
    105 optimize memory and to reduce calculations: the transformaton of a real
    106 number sequence is a conjugate complex number sequence: F [k] = F [-k]*.
    107 
    108 
    109 3.2 FFTRealFixLen - Length fixed at compile-time
    110 ------------------------------------------------
    111 
    112 This class is significantly faster than the previous one, giving a speed
    113 gain between 50 and 100 %. The template parameter is the base-2 logarithm of
    114 the FFT length. The datatype is float; it can be changed by modifying the
    115 DataType typedef in FFTRealFixLenParam.h. As FFTReal class, it supports
    116 only floating-point types or equivalent.
    117 
    118 Use is similar as the one of FFTReal. To instanciate the object, just proceed
    119 as indicated below:
    120 
    121    #include "ffft/FFTRealFixLen.h"
    122    ...
    123    // 1024-point (2^10) FFT object constructed.
    124    ffft::FFTRealFixLen <10> fft_object;
    125 
    126 Warning: long FFT objects may take a very long time to compile, depending on
    127 the compiler and its optimisation options. If compilation time is too high,
    128 encapsulate the FFT object in a seprate class whose header doesn't need
    129 to include FFTRealFixLen.h, so you just have to compile the wrapper once
    130 and only link it the other times. For example (quick, dirty and incomplete):
    131 
    132 ffft/FFTWrapper.h:            | ffft/FFTWrapper.cpp:
    133                               |
    134 class FFTWrapper              | #include "ffft/FFTRealFixLen.h"
    135 {                             | #include "ffft/FFTWrapper.h"
    136 public:                       |
    137    FFTWrapper ();             | FFTWrapper::FFTWrapper ()
    138    ~FFTWrapper ();            | :  _impl_ptr ((void*) new FTRealFixLen <10>)
    139    void  do_fft (...);        | {
    140    void  do_ifft (...);       | }
    141 private:                      |
    142    void *_impl_ptr;           | ...
    143 }                             |
    144 
    145 
    146 3.3 Data organisation
    147 ---------------------
    148 
    149 Mathematically speaking, DFT formulas below show what does FFTReal:
    150 
    151 do_fft() : f(k) = sum (p = 0, N-1, x(p) * exp (+j*2*pi*k*p/N))
    152 do_ifft(): x(k) = sum (p = 0, N-1, f(p) * exp (-j*2*pi*k*p/N))
    153 
    154 Where j is the square root of -1. The formulas differ only by the sign of
    155 the exponential. When the sign is positive, the transform is called positive.
    156 Common formulas for Fourier transform are negative for the direct tranform and
    157 positive for the inverse one.
    158 
    159 However in these formulas, f is an array of complex numbers and doesn't
    160 correspound exactly to the f[] array taken as function parameter. The
    161 following table shows how the f[] sequence is mapped onto the usable FFT
    162 coefficients (called bins):
    163 
    164    FFTReal output | Positive FFT equiv.   | Negative FFT equiv.
    165    ---------------+-----------------------+-----------------------
    166    f [0]          | Real (bin 0)          | Real (bin 0)
    167    f [...]        | Real (bin ...)        | Real (bin ...)
    168    f [length/2]   | Real (bin length/2)   | Real (bin length/2)
    169    f [length/2+1] | Imag (bin 1)          | -Imag (bin 1)
    170    f [...]        | Imag (bin ...)        | -Imag (bin ...)
    171    f [length-1]   | Imag (bin length/2-1) | -Imag (bin length/2-1)
    172 
    173 And FFT bins are distributed in f [] as above:
    174 
    175                |                | Positive FFT    | Negative FFT
    176    Bin         | Real part      | imaginary part  | imaginary part
    177    ------------+----------------+-----------------+---------------
    178    0           | f [0]          | 0               | 0
    179    1           | f [1]          | f [length/2+1]  | -f [length/2+1]
    180    ...         | f [...],       | f [...]         | -f [...]
    181    length/2-1  | f [length/2-1] | f [length-1]    | -f [length-1]
    182    length/2    | f [length/2]   | 0               | 0
    183    length/2+1  | f [length/2-1] | -f [length-1]   | f [length-1]
    184    ...         | f [...]        | -f [...]        | f [...]
    185    length-1    | f [1]          | -f [length/2+1] | f [length/2+1]
    186 
    187 f [] coefficients have the same layout for FFT and IFFT functions. You may
    188 notice that scaling must be done if you want to retrieve x after FFT and IFFT.
    189 Actually, IFFT (FFT (x)) = x * length(x). This is a not a problem because
    190 most of the applications don't care about absolute values. Thus, the operation
    191 requires less calculation. If you want to use the FFT and IFFT to transform a
    192 signal, you have to apply post- (or pre-) processing yourself. Multiplying
    193 or dividing floating point numbers by a power of 2 doesn't generate extra
    194 computation noise.
    195 
    196 
    197 
    198 4. Compilation and testing
    199 --------------------------
    200 
    201 Drop the following files into your project or makefile:
    202 
    203 ffft/Array.*
    204 ffft/def.h
    205 ffft/DynArray.*
    206 ffft/FFTReal*.h*
    207 ffft/OscSinCos.*
    208 
    209 Other files are for testing purpose only, do not include them if you just need
    210 to use the library; they are not needed to use FFTReal in your own programs.
    211 
    212 FFTReal may be compiled in two versions: release and debug. Debug version
    213 has checks that could slow down the code. Define NDEBUG to set the Release
    214 mode. For example, the command line to compile the test bench on GCC would
    215 look like:
    216 
    217 Debug mode:
    218 g++ -Wall -I. -o ./fftreal_debug.exe ffft/test/*.cpp ffft/test/stopwatch/*.cpp
    219 
    220 Release mode:
    221 g++ -Wall -I. -o ./fftreal_release.exe -DNDEBUG -O3 ffft/test/*.cpp ffft/test/stopwatch/*.cpp
    222 
    223 It may be tricky to compile the test bench because the speed tests use the
    224 stopwatch sub-library, which is not that cross-platform. If you encounter
    225 any problem that you cannot easily fix while compiling it, edit the file
    226 ffft/test/conf.h and un-define the speed test macro. Remove the stopwatch
    227 directory from your source file list, too.
    228 
    229 If it's not done by default, you should activate the exception handling
    230 of your compiler to get the class memory-leak-safe. Thus, when a memory
    231 allocation fails (in the constructor), an exception is thrown and the entire
    232 object is safely destructed. It reduces the permanent error checking overhead
    233 in the client code. Also, the test bench requires Run-Time Type Information
    234 (RTTI) to be enabled in order to display the names of the tested classes -
    235 sometimes mangled, depending on the compiler.
    236 
    237 Please note: the test bench may take an insane time to compile, especially in
    238 Release mode, because a lot of recursive templates are instanciated.
    239 
    240 
    241 
    242 5. History
    243 ----------
    244 
    245 v2.11 (2010.09.12)
    246 - The LGPL was not well suited to 100% template code, therefore I changed
    247 the license again. Everything is released under the WTFPL.
    248 - Removed warnings in the testcode on MSVC++ 8.0
    249 - Fixed the multiple definition linking error with template specialisations
    250 on GCC 4.
    251 
    252 v2.10 (2008.05.28)
    253 - Classes are now in the ffft namespace
    254 - Changed directory structure
    255 - Fixed compilation information in the documentation
    256 
    257 v2.00 (2005.10.18)
    258 - Turned FFTReal class into template (data type as parameter)
    259 - Added FFTRealFixLen
    260 - Trigonometric tables are size-limited in order to preserve cache memory;
    261 over a given size, sin/cos functions are computed on the fly.
    262 - Better test bench for accuracy and speed
    263 - Changed license to LGPL
    264 
    265 v1.03 (2001.06.15)
    266 - Thanks to Frederic Vanmol for the Pascal port (works with Delphi).
    267 - Documentation improvement
    268 
    269 v1.02 (2001.03.25)
    270 - sqrt() is now precomputed when the object FFTReal is constructed, resulting
    271 in speed impovement for small size FFT.
    272 
    273 v1.01 (2000)
    274 - Small modifications, I don't remember what.
    275 
    276 v1.00 (1999.08.14)
    277 - First version released
    278 
    279 
    280 
    281 6. Contact
    282 ----------
    283 
    284 Please address any comment, bug report or flame to:
    285 
    286 Laurent de Soras
    287 laurent.de.soras@free.fr
    288 http://ldesoras.free.fr
    289 
    290 For the Pascal port:
    291 Frederic Vanmol
    292 frederic@fruityloops.com
    293