1 #ifndef __FFT_H__ 2 3 /*============================================================================= 4 | 5 | NAME 6 | 7 | FFT.h 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.4 - 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 */ 59 const 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 // 69 template <typename FloatType> 70 class 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 120 class 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 144 template <typename FloatType> // Not just a class, but a template class with a parameterized type. 145 vector< complex<FloatType> > // The data type of this static variable. 146 FastFourierTransform<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. 149 template <typename FloatType> bool FastFourierTransform<FloatType>::called_already = false ; 150 template <typename FloatType> const FloatType FastFourierTransform<FloatType>::PI = static_cast<FloatType>(3.1415926535897932384626433832795028841) ; 151 #endif // __FFT_H__