1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242

==============================================================================
FFTReal
Version 2.00, 2005/10/18
Fourier transformation (FFT, IFFT) library specialised for real data
Portable ISO C++
(c) Laurent de Soras <laurent.de.soras@clubinternet.fr>
Object Pascal port (c) Frederic Vanmol <frederic@fruityloops.com>
==============================================================================
1. Legal

This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.
This library is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with this library; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 021111307 USA
Check the file license.txt to get full information about the license.
2. Content

FFTReal is a library to compute Discrete Fourier Transforms (DFT) with the
FFT algorithm (Fast Fourier Transform) on arrays of real numbers. It can
also compute the inverse transform.
You should find in this package a lot of files ; some of them are of interest:
 readme.txt: you are reading it
 FFTReal.h: FFT, length fixed at runtime
 FFTRealFixLen.h: FFT, length fixed at compiletime
 FFTReal.pas: Pascal implementation (working but not uptodate)
 stopwatch directory
3. Using FFTReal

Important  if you were using older versions of FFTReal (up to 1.03), some
things have changed. FFTReal is now a template. Therefore use FFTReal<float>
or FFTReal<double> in your code depending on the application datatype. The
flt_t typedef has been removed.
You have two ways to use FFTReal. In the first way, the FFT has its length
fixed at runtime, when the object is instanciated. It means that you have
not to know the length when you write the code. This is the usual way of
proceeding.
3.1 FFTReal  Length fixed at runtime

Just instanciate one time a FFTReal object. Specify the data type you want
as template parameter (only floating point: float, double, long double or
custom type). The constructor precompute a lot of things, so it may be a bit
long. The parameter is the number of points used for the next FFTs. It must
be a power of 2:
#include "FFTReal.h"
...
long len = 1024;
...
FFTReal <float> fft_object (len); // 1024point FFT object constructed.
Then you can use this object to compute as many FFTs and IFFTs as you want.
They will be computed very quickly because a lot of work has been done in the
object construction.
float x [1024];
float f [1024];
...
fft_object.do_fft (f, x); // x (real) FFT> f (complex)
...
fft_object.do_ifft (f, x); // f (complex) IFFT> x (real)
fft_object.rescale (x); // Postscaling should be done after FFT+IFFT
...
x [] and f [] are floating point number arrays. x [] is the real number
sequence which we want to compute the FFT. f [] is the result, in the
"frequency" domain. f has the same number of elements as x [], but f []
elements are complex numbers. The routine uses some FFT properties to
optimize memory and to reduce calculations: the transformaton of a real
number sequence is a conjugate complex number sequence: F [k] = F [k]*.
3.2 FFTRealFixLen  Length fixed at compiletime

This class is significantly faster than the previous one, giving a speed
gain between 50 and 100 %. The template parameter is the base2 logarithm of
the FFT length. The datatype is float; it can be changed by modifying the
DataType typedef in FFTRealFixLenParam.h. As FFTReal class, it supports
only floatingpoint types or equivalent.
To instanciate the object, just proceed as below:
#include "FFTRealFixLen.h"
...
FFTRealFixLen <10> fft_object; // 1024point (2^10) FFT object constructed.
Use is similar as the one of FFTReal.
3.3 Data organisation

Mathematically speaking, the formulas below show what does FFTReal:
do_fft() : f(k) = sum (p = 0, N1, x(p) * exp (+j*2*pi*k*p/N))
do_ifft(): x(k) = sum (p = 0, N1, f(p) * exp (j*2*pi*k*p/N))
Where j is the square root of 1. The formulas differ only by the sign of
the exponential. When the sign is positive, the transform is called positive.
Common formulas for Fourier transform are negative for the direct tranform and
positive for the inverse one.
However in these formulas, f is an array of complex numbers and doesn't
correspound exactly to the f[] array taken as function parameter. The
following table shows how the f[] sequence is mapped onto the usable FFT
coefficients (called bins):
FFTReal output  Positive FFT equiv.  Negative FFT equiv.
++
f [0]  Real (bin 0)  Real (bin 0)
f [...]  Real (bin ...)  Real (bin ...)
f [length/2]  Real (bin length/2)  Real (bin length/2)
f [length/2+1]  Imag (bin 1)  Imag (bin 1)
f [...]  Imag (bin ...)  Imag (bin ...)
f [length1]  Imag (bin length/21)  Imag (bin length/21)
And FFT bins are distributed in f [] as above:
  Positive FFT  Negative FFT
Bin  Real part  imaginary part  imaginary part
+++
0  f [0]  0  0
1  f [1]  f [length/2+1]  f [length/2+1]
...  f [...],  f [...]  f [...]
length/21  f [length/21]  f [length1]  f [length1]
length/2  f [length/2]  0  0
length/2+1  f [length/21]  f [length1]  f [length1]
...  f [...]  f [...]  f [...]
length1  f [1]  f [length/2+1]  f [length/2+1]
f [] coefficients have the same layout for FFT and IFFT functions. You may
notice that scaling must be done if you want to retrieve x after FFT and IFFT.
Actually, IFFT (FFT (x)) = x * length(x). This is a not a problem because
most of the applications don't care about absolute values. Thus, the operation
requires less calculation. If you want to use the FFT and IFFT to transform a
signal, you have to apply post (or pre) processing yourself. Multiplying
or dividing floating point numbers by a power of 2 doesn't generate extra
computation noise.
4. Compilation and testing

Drop the following files into your project or makefile:
Array.*
def.h
DynArray.*
FFTReal*.cpp
FFTReal*.h*
OscSinCos.*
Other files are for testing purpose only, do not include them if you just need
to use the library ; they are not needed to use FFTReal in your own programs.
FFTReal may be compiled in two versions: release and debug. Debug version
has checks that could slow down the code. Define NDEBUG to set the Release
mode. For example, the command line to compile the test bench on GCC would
look like:
Debug mode:
g++ Wall o fftreal_debug.exe *.cpp stopwatch/*.cpp
Release mode:
g++ Wall o fftreal_release.exe DNDEBUG O3 *.cpp stopwatch/*.cpp
It may be tricky to compile the test bench because the speed tests use the
stopwatch sublibrary, which is not that crossplatform. If you encounter
any problem that you cannot easily fix while compiling it, edit the file
test_settings.h and undefine the speed test macro. Remove the stopwatch
directory from your source file list, too.
If it's not done by default, you should activate the exception handling
of your compiler to get the class memoryleaksafe. Thus, when a memory
allocation fails (in the constructor), an exception is thrown and the entire
object is safely destructed. It reduces the permanent error checking overhead
in the client code. Also, the test bench requires RunTime Type Information
(RTTI) to be enabled in order to display the names of the tested classes 
sometimes mangled, depending on the compiler.
The test bench may take a long time to compile, especially in Release mode,
because a lot of recursive templates are instanciated.
5. History

v2.00 (2005.10.18)
 Turned FFTReal class into template (data type as parameter)
 Added FFTRealFixLen
 Trigonometric tables are sizelimited in order to preserve cache memory;
over a given size, sin/cos functions are computed on the fly.
 Better test bench for accuracy and speed
v1.03 (2001.06.15)
 Thanks to Frederic Vanmol for the Pascal port (works with Delphi).
 Documentation improvement
v1.02 (2001.03.25)
 sqrt() is now precomputed when the object FFTReal is constructed, resulting
in speed impovement for small size FFT.
v1.01 (2000)
 Small modifications, I don't remember what.
v1.00 (1999.08.14)
 First version released
