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