1#ifndef __FFT_HPP__
2
3/*=============================================================================
4|
5| NAME
6|
7| FFT.hpp
8|
9| DESCRIPTION
10|
11| This program does an in-place one dimensional complex discrete
12| Fourier transform. It uses an FFT algorithm for a number of
13| input points which is a power of two. It works on both single
14| precision and double precision floating point numbers.
15|
16| AUTHOR
17|
18| Created: Sean O'Connor 19 November 2005
19|
20| LEGAL
21|
22| FFT Version 1.6 - An FFT utility library in C++.
23| Copyright (C) 2005-2024 by Sean Erik O'Connor. All Rights Reserved.
24|
25| This program is free software: you can redistribute it and/or modify
26| it under the terms of the GNU General Public License as published by
27| the Free Software Foundation, either version 3 of the License, or
28| (at your option) any later version.
29|
30| This program is distributed in the hope that it will be useful,
31| but WITHOUT ANY WARRANTY; without even the implied warranty of
32| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
33| GNU General Public License for more details.
34|
35| You should have received a copy of the GNU General Public License
36| along with this program. If not, see <http://www.gnu.org/licenses/>.
37|
38| The author's address is seanerikoconnor!AT!gmail!DOT!com
39| with !DOT! replaced by . and the !AT! replaced by @
40|
41+============================================================================*/
42
43/*
44 * We must set the size of the sine and cosine table used in the FFT.
45 * The table is called starting_multiplier.
46 *
47 * Suppose MAX is the largest number of points we would ever transform. We set
48 *
49 * MAX_TABLE_SIZE = LOG ( MAX ) - 1
50 * 2
51 *
52 * to be the size of the table. This table can now be used by the FFT for
53 * any number of points from 2 up to MAX.
54 *
55 * For example, if MAX_TABLE_SIZE = 14, then we can transform anywhere from
56 * 2 to 2 ^ 15 = 32,768 points, using the same sine and cosine table.
57 *
58 */
59const int MAX_TABLE_SIZE = 13 ;
60
61
62
63// Derive the FFT class from an STL vector with a floating point type to be specified.
64// Thus we get the vector's data manipulation attributes and
65// we can substitute FFT objects into an existing software
66// framework which uses vector objects in containers.
67// But extend the class by adding a Fourier Transform capability.
68//
69template <typename FloatType>
70class FastFourierTransform
71 : public vector< complex<FloatType> > // Need spaces between angle brackets to satisfy compiler.
72{
73 public:
74 // Default constructor.
75 FastFourierTransform() ;
76
77 // Destructor.
78 ~FastFourierTransform() ;
79
80 // Copy constructor ;
81 FastFourierTransform( const FastFourierTransform & transform ) ;
82
83 // Assignment operator.
84 FastFourierTransform & operator=( const FastFourierTransform & transform ) ;
85
86 // Fast Fourier transform capability.
87 void fft( bool direction = true ) ;
88
89 // Maybe these should be private to be safe!
90 protected:
91 bool direction ;
92
93 private:
94 // Table of sines and cosines whose values are created the first
95 // time any object calls the fft() member function and which are
96 // shared among all subsequent objects.
97 static vector< complex<FloatType> > starting_multiplier ;
98 static bool called_already ;
99 static const FloatType PI ;
100
101 // Helper function used by FFT member function only.
102 static int reverse_bits( int n, int num_bits ) ;
103} ;
104
105
106/*=============================================================================
107|
108| NAME
109|
110| FastFourierTransformException
111|
112| DESCRIPTION
113|
114| Helper class for recording data thrown by FastFourierTransform.
115|
116| BUGS
117|
118+============================================================================*/
119
120class FastFourierTransformException : public runtime_error
121{
122 public:
123 // This form will be used most often in a throw.
124 FastFourierTransformException( const string & description )
125 : runtime_error( description )
126 {
127 } ;
128
129 // Throw with no error message.
130 FastFourierTransformException()
131 : runtime_error( "FFT exception: " )
132 {
133 } ;
134
135} ; // end class FastFourierTransformException
136
137
138/*==============================================================================
139| Static Class Variables Initialization |
140==============================================================================*/
141
142// Static class variables must be initialized outside the class.
143
144template <typename FloatType> // Not just a class, but a template class with a parameterized type.
145vector< complex<FloatType> > // The data type of this static variable.
146FastFourierTransform<FloatType>::starting_multiplier(MAX_TABLE_SIZE) ; // Declare the variable as a member of class having a
147 // parameterized type.
148 // Initialize the size to the maximum, and default to zeros.
149template <typename FloatType> bool FastFourierTransform<FloatType>::called_already = false ;
150template <typename FloatType> const FloatType FastFourierTransform<FloatType>::PI = static_cast<FloatType>(3.14159265358979323846264338327950288419716939) ;
151#endif // __FFT_HPP__
