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__