83 lines
3.1 KiB
C
83 lines
3.1 KiB
C
|
/**
|
||
|
|
* @file FFT.h
|
||
|
|
* @brief Fast Fourier Transform
|
||
|
|
* @details fft() transforms time domain to frequency domain and
|
||
|
|
* ifft() transforms frequency to time domain domain
|
||
|
|
* @version TI-RSLK MAX v1.1
|
||
|
|
* @author Daniel Valvano and Jonathan Valvano
|
||
|
|
* @copyright Copyright 2020 by Jonathan W. Valvano, valvano@mail.utexas.edu,
|
||
|
|
* @warning AS-IS
|
||
|
|
* @note For more information see http://users.ece.utexas.edu/~valvano/
|
||
|
|
* @date July 13, 2020
|
||
|
|
******************************************************************************/
|
||
|
|
|
||
|
|
/* Factored discrete Fourier transform, or FFT, and its inverse iFFT */
|
||
|
|
// Derived from
|
||
|
|
// http://www.math.wustl.edu/~victor/mfmm/index.html#mfmm-software
|
||
|
|
// Mathematics for Multimedia, ISBN 978-0-8176-4879-4, was formerly managed by Elsevier/Academic Press.
|
||
|
|
// MSP432 available RAM limits size to N=2048 points
|
||
|
|
#include <math.h>
|
||
|
|
#include <stdlib.h>
|
||
|
|
/*!
|
||
|
|
* @defgroup Math
|
||
|
|
* @brief
|
||
|
|
* @{*/
|
||
|
|
|
||
|
|
/*!
|
||
|
|
* @brief a complex number has a real and imaginary part
|
||
|
|
*/
|
||
|
|
struct complex{
|
||
|
|
float Real;
|
||
|
|
float Imag;
|
||
|
|
};
|
||
|
|
typedef struct complex complex_t;
|
||
|
|
|
||
|
|
/**
|
||
|
|
* \brief PI is ratio of circumference to diameter of a circle
|
||
|
|
*/
|
||
|
|
#ifndef PI
|
||
|
|
#define PI 3.14159265358979323846264338327950288
|
||
|
|
#endif
|
||
|
|
|
||
|
|
/**
|
||
|
|
* discrete Fast Fourier Transform,
|
||
|
|
* Converts time to frequency domain <br>
|
||
|
|
* Assume the input is real data sampled at fs <br>
|
||
|
|
* Place n measurements into the real part of array v <br>
|
||
|
|
* Set the imaginary part of array v to 0 <br>
|
||
|
|
* Call fft() and the results are returned back in array v <br>
|
||
|
|
* If the input is real only, then the transform will contain <br>
|
||
|
|
* Index 0 <= k < n/2 complex components of frequency f=k/fs <br>
|
||
|
|
* E.g., k=0 represents the DC component of the input <br>
|
||
|
|
* Index n/2 <= k < n are complex conjugates of the first half <br>
|
||
|
|
* @param v array of input data in complex form
|
||
|
|
* @param n size of the two arrays 2, 4, 8, ..., 2048
|
||
|
|
* @param tmp temporary array of data in complex form
|
||
|
|
* @return none
|
||
|
|
* @note n is a power of two from 2 to 2048
|
||
|
|
* @brief fft
|
||
|
|
*/
|
||
|
|
void fft(complex_t *v, int n, complex_t *tmp);
|
||
|
|
|
||
|
|
|
||
|
|
/**
|
||
|
|
* discrete Inverse Fast Fourier Transform,
|
||
|
|
* Converts frequency to time domain <br>
|
||
|
|
* Assume the input is complex data with components k=0 to n-1 <br>
|
||
|
|
* Index 0 <= k < n-1 complex components of frequency f=k/fs <br>
|
||
|
|
* E.g., k=0 represents the DC component of the input <br>
|
||
|
|
* Place n complex values into the array v <br>
|
||
|
|
* Typically the index n/2 <= k < n are complex conjugates of the first half<br>
|
||
|
|
* Call ifft() and the results are returned back in array v <br>
|
||
|
|
* If the input is real only, then the transform will contain <br>
|
||
|
|
* @param v array of input data in complex form
|
||
|
|
* @param n size of the two arrays 2, 4, 8, ..., 2048
|
||
|
|
* @param tmp temporary array of data in complex form
|
||
|
|
* @return none
|
||
|
|
* @note n is a power of two from 2 to 2048
|
||
|
|
* @brief Inverse fft
|
||
|
|
*/
|
||
|
|
void ifft(complex_t *v, int n, complex_t *tmp);
|
||
|
|
|
||
|
|
|