basic utility functions for native FFTs More...

#include <MHO_FastFourierTransformUtilities.hh>

Public Member Functions
	MHO_FastFourierTransformUtilities ()

virtual	~MHO_FastFourierTransformUtilities ()

void	ComputeBluesteinScaleFactors (unsigned int N, std::complex< double > *scale)
	Function MHO_FastFourierTransformUtilities<double>::ComputeBluesteinScaleFactors. More...

void	ComputeBluesteinScaleFactors (unsigned int N, std::complex< float > *scale)
	Function MHO_FastFourierTransformUtilities<float>::ComputeBluesteinScaleFactors. More...

void	ComputeBluesteinScaleFactors (unsigned int N, std::complex< long double > *scale)
	Function MHO_FastFourierTransformUtilities<long double>::ComputeBluesteinScaleFactors. More...

void	ComputeTwiddleFactorBasis (unsigned int log2N, std::complex< double > *twiddle)
	Function MHO_FastFourierTransformUtilities<double>::ComputeTwiddleFactorBasis. More...

void	ComputeTwiddleFactorBasis (unsigned int log2N, std::complex< float > *twiddle)
	Function MHO_FastFourierTransformUtilities<float>::ComputeTwiddleFactorBasis. More...

void	ComputeTwiddleFactorBasis (unsigned int log2N, std::complex< long double > *twiddle)
	Function MHO_FastFourierTransformUtilities<long double>::ComputeTwiddleFactorBasis. More...

void	ComputeTwiddleFactors (unsigned int N, std::complex< double > *twiddle)
	Function MHO_FastFourierTransformUtilities<double>::ComputeTwiddleFactors. More...

void	ComputeTwiddleFactors (unsigned int N, std::complex< float > *twiddle)
	Function MHO_FastFourierTransformUtilities<float>::ComputeTwiddleFactors. More...

void	ComputeTwiddleFactors (unsigned int N, std::complex< long double > *twiddle)
	Function MHO_FastFourierTransformUtilities<long double>::ComputeTwiddleFactors. More...

Static Public Member Functions
static void	ButterflyRadixTwo_CooleyTukey (XFloatType H0, XFloatType H1, XFloatType *W)
	Function ButterflyRadixTwo_CooleyTukey See page 23 of "Inside the FFT Black Box", E. Chu and A. George, Ch. 13, CRC Press, 2000. More...

static void	ButterflyRadixTwo_GentlemanSande (XFloatType H0, XFloatType H1, XFloatType *W)
	Function ButterflyRadixTwo_GentlemanSande See page 25 of "Inside the FFT Black Box", E. Chu and A. George, Ch. 13, CRC Press, 2000. More...

static unsigned int	ComputeBluesteinArraySize (unsigned int N)
	Function ComputeBluesteinArraySize Computes the array size needed to perform a Bluestein/Chirp-Z FFT for arbitrary N. More...

static void	ComputeBluesteinCirculantVector (unsigned int N, unsigned int M, std::complex< XFloatType > twiddle, std::complex< XFloatType > scale, std::complex< XFloatType > *circulant)
	Function ComputeBluesteinCirculantVector twiddle and circulant array must be length M = 2^p >= (2N - 2), where N is the data length. More...

static void	ComputeBluesteinScaleFactors (unsigned int N, std::complex< XFloatType > *scale)
	Function ComputeBluesteinScaleFactors. More...

static void	ComputeConjugateTwiddleFactorBasis (unsigned int log2N, std::complex< XFloatType > *conj_twiddle)
	Computes conjugate twiddle factor basis for given log2N and stores result in conj_twiddle. More...

static void	ComputeConjugateTwiddleFactors (unsigned int N, std::complex< XFloatType > *conj_twiddle)
	Computes the conjugate twiddle factors for given size N and stores them in provided array. More...

static void	ComputeTwiddleFactorBasis (unsigned int log2N, std::complex< XFloatType > *twiddle)
	Computes twiddle factors for Fast Fourier Transform up to log2N. computes only the twiddle factors we need in order to easily compute them on the fly e.g e^{ix}, e^{2ix}, e^{4ix}, e^{8ix}, etc up to e^{Nix} ), that way we only need log2N storage. More...

static void	ComputeTwiddleFactors (unsigned int N, std::complex< XFloatType > *twiddle)
	Compute twiddle factors for a Fast Fourier Transform. computes all the twiddle factors e^{i2pi/N} for 0 to N-1 using std::cos and std::sin which is more accurate than the recursive method. More...

static void	Conjugate (unsigned int N, std::complex< XFloatType > *array)
	Conjugates each element in a complex array. More...

static void	Conjugate (unsigned int N, std::complex< XFloatType > *array, unsigned int stride)
	Conjugates each element in a complex (strided) array. More...

static void	FFTBluestein (unsigned int N, unsigned int M, std::complex< XFloatType > data, std::complex< XFloatType > twiddle, std::complex< XFloatType > conj_twiddle, std::complex< XFloatType > scale, std::complex< XFloatType > circulant, std::complex< XFloatType > workspace, unsigned int stride=1)
	Function Bluestein algorithm for arbitrary length, N is length of the data, (supports strided data access) More...

static void	FFTRadixTwo_DIF (unsigned int N, std::complex< XFloatType > data, std::complex< XFloatType > twiddle, unsigned int stride=1)
	Radix-2 DIF FFT wrapper for a std::complex array. More...

static void	FFTRadixTwo_DIF (unsigned int N, XFloatType data, XFloatType twiddle, unsigned int stride=1)
	Performs Radix-2 Decimation In Frequency (DIF) FFT using conjugate array and twiddle factors. input: data array in normal order output: fft of data in bit-address permutated order. More...

static void	FFTRadixTwo_DIT (unsigned int N, std::complex< XFloatType > data, std::complex< XFloatType > twiddle, unsigned int stride=1)
	Radix-2 DIT FFT wrapper for a std::complex array. More...

static void	FFTRadixTwo_DIT (unsigned int N, XFloatType data, XFloatType twiddle, unsigned int stride=1)
	Computes a Radix-2 decimation in time (DIT) FFT. input: data array in bit-address permutated order output: fft of data in normal order. More...

Detailed Description

template<typename XFloatType>
class hops::MHO_FastFourierTransformUtilities< XFloatType >

basic utility functions for native FFTs

Date: Fri Oct 23 12:02:01 2020 -0400

Author: J. Barrett - barre.nosp@m.ttj@.nosp@m.mit.e.nosp@m.du

Constructor & Destructor Documentation

◆ MHO_FastFourierTransformUtilities()

template<typename XFloatType >

hops::MHO_FastFourierTransformUtilities< XFloatType >::MHO_FastFourierTransformUtilities ( )

inline

◆ ~MHO_FastFourierTransformUtilities()

template<typename XFloatType >

virtual hops::MHO_FastFourierTransformUtilities< XFloatType >::~MHO_FastFourierTransformUtilities ( )

inlinevirtual

Member Function Documentation

◆ ButterflyRadixTwo_CooleyTukey()

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::ButterflyRadixTwo_CooleyTukey	(	XFloatType *	H0,
		XFloatType *	H1,
		XFloatType *	W
	)

inlinestatic

Function ButterflyRadixTwo_CooleyTukey See page 23 of "Inside the FFT Black Box", E. Chu and A. George, Ch. 13, CRC Press, 2000.

Parameters

H0	(XFloatType*)
H1	(XFloatType*)
W	(XFloatType*)

Note: This is a static function.

◆ ButterflyRadixTwo_GentlemanSande()

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::ButterflyRadixTwo_GentlemanSande	(	XFloatType *	H0,
		XFloatType *	H1,
		XFloatType *	W
	)

inlinestatic

Function ButterflyRadixTwo_GentlemanSande See page 25 of "Inside the FFT Black Box", E. Chu and A. George, Ch. 13, CRC Press, 2000.

Parameters

H0	(XFloatType*)
H1	(XFloatType*)
W	(XFloatType*)

Note: This is a static function.

◆ ComputeBluesteinArraySize()

template<typename XFloatType >

static unsigned int hops::MHO_FastFourierTransformUtilities< XFloatType >::ComputeBluesteinArraySize ( unsigned int N )

inlinestatic

Function ComputeBluesteinArraySize Computes the array size needed to perform a Bluestein/Chirp-Z FFT for arbitrary N.

Parameters

N	(unsigned int)

Returns: Return value (unsigned int)

Note: This is a static function.

◆ ComputeBluesteinCirculantVector()

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::ComputeBluesteinCirculantVector	(	unsigned int	N,
		unsigned int	M,
		std::complex< XFloatType > *	twiddle,
		std::complex< XFloatType > *	scale,
		std::complex< XFloatType > *	circulant
	)

inlinestatic

Function ComputeBluesteinCirculantVector twiddle and circulant array must be length M = 2^p >= (2N - 2), where N is the data length.

Parameters

N	(unsigned int)
M	(unsigned int)
twiddle	(std::complex< XFloatType >*)
scale	(std::complex< XFloatType >*)
circulant	(std::complex< XFloatType >*)

Note: This is a static function.

◆ ComputeBluesteinScaleFactors() [1/4]

void hops::MHO_FastFourierTransformUtilities< double >::ComputeBluesteinScaleFactors	(	unsigned int	N,
		std::complex< double > *	scale
	)

inline

Function MHO_FastFourierTransformUtilities<double>::ComputeBluesteinScaleFactors.

Parameters

N	(unsigned int)
scale	(std::complex< double >*)

Returns: Return value (void MHO_FastFourierTransformUtilities< double)

Note: IMPORTANT NOTE! This function computes the CONJUGATE of the scale factors as defined by equation 13.22, page 127 of "Inside the FFT Black Box", E. Chu and A. George, Ch. 13, CRC Press, 2000 we do this so we can avoid having to take a complex conjugate of the scale factors when performing the actual FFT

◆ ComputeBluesteinScaleFactors() [2/4]

void hops::MHO_FastFourierTransformUtilities< float >::ComputeBluesteinScaleFactors	(	unsigned int	N,
		std::complex< float > *	scale
	)

inline

Function MHO_FastFourierTransformUtilities<float>::ComputeBluesteinScaleFactors.

Parameters

N	(unsigned int)
scale	(std::complex< float >*)

Returns: Return value (void MHO_FastFourierTransformUtilities< float)

Note: IMPORTANT NOTE! This function computes the CONJUGATE of the scale factors as defined by equation 13.22, page 127 of "Inside the FFT Black Box", E. Chu and A. George, Ch. 13, CRC Press, 2000 we do this so we can avoid having to take a complex conjugate of the scale factors when performing the actual FFT

◆ ComputeBluesteinScaleFactors() [3/4]

void hops::MHO_FastFourierTransformUtilities< long double >::ComputeBluesteinScaleFactors	(	unsigned int	N,
		std::complex< long double > *	scale
	)

inline

Function MHO_FastFourierTransformUtilities<long double>::ComputeBluesteinScaleFactors.

Parameters

N	(unsigned int)
scale	(std::complex< long double >*)

Returns: Return value (void MHO_FastFourierTransformUtilities< long double)

Note: IMPORTANT NOTE! This function computes the CONJUGATE of the scale factors as defined by equation 13.22, page 127 of "Inside the FFT Black Box", E. Chu and A. George, Ch. 13, CRC Press, 2000 we do this so we can avoid having to take a complex conjugate of the scale factors when performing the actual FFT

◆ ComputeBluesteinScaleFactors() [4/4]

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::ComputeBluesteinScaleFactors	(	unsigned int	N,
		std::complex< XFloatType > *	scale
	)

static

Function ComputeBluesteinScaleFactors.

Parameters

N	(unsigned int)
scale	(std::complex< XFloatType >*) scale factor array must be length N

Note: This is a static function.

◆ ComputeConjugateTwiddleFactorBasis()

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::ComputeConjugateTwiddleFactorBasis	(	unsigned int	log2N,
		std::complex< XFloatType > *	conj_twiddle
	)

inlinestatic

Computes conjugate twiddle factor basis for given log2N and stores result in conj_twiddle.

Parameters

log2N	Number of bits to divide N by 2 for twiddle factors
conj_twiddle	(std::complex< XFloatType )*

Note: This is a static function.

◆ ComputeConjugateTwiddleFactors()

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::ComputeConjugateTwiddleFactors	(	unsigned int	N,
		std::complex< XFloatType > *	conj_twiddle
	)

inlinestatic

Computes the conjugate twiddle factors for given size N and stores them in provided array.

Parameters

N	Size of the transform (N must be a power of 2)
conj_twiddle	Output array to store the computed conjugate twiddle factors

Note: This is a static function.

◆ ComputeTwiddleFactorBasis() [1/4]

void hops::MHO_FastFourierTransformUtilities< double >::ComputeTwiddleFactorBasis	(	unsigned int	log2N,
		std::complex< double > *	twiddle
	)

inline

Function MHO_FastFourierTransformUtilities<double>::ComputeTwiddleFactorBasis.

Parameters

log2N	(unsigned int)
twiddle	(std::complex< double >*)

Returns: Return value (void MHO_FastFourierTransformUtilities< double)

◆ ComputeTwiddleFactorBasis() [2/4]

void hops::MHO_FastFourierTransformUtilities< float >::ComputeTwiddleFactorBasis	(	unsigned int	log2N,
		std::complex< float > *	twiddle
	)

inline

Function MHO_FastFourierTransformUtilities<float>::ComputeTwiddleFactorBasis.

Parameters

log2N	(unsigned int)
twiddle	(std::complex< float >*)

Returns: Return value (void MHO_FastFourierTransformUtilities< float)

◆ ComputeTwiddleFactorBasis() [3/4]

void hops::MHO_FastFourierTransformUtilities< long double >::ComputeTwiddleFactorBasis	(	unsigned int	log2N,
		std::complex< long double > *	twiddle
	)

inline

Function MHO_FastFourierTransformUtilities<long double>::ComputeTwiddleFactorBasis.

Parameters

log2N	(unsigned int)
twiddle	(std::complex< long double >*)

Returns: Return value (void MHO_FastFourierTransformUtilities< long double)

◆ ComputeTwiddleFactorBasis() [4/4]

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::ComputeTwiddleFactorBasis	(	unsigned int	log2N,
		std::complex< XFloatType > *	twiddle
	)

static

Computes twiddle factors for Fast Fourier Transform up to log2N. computes only the twiddle factors we need in order to easily compute them on the fly e.g e^{ix}, e^{2ix}, e^{4ix}, e^{8ix}, etc up to e^{Nix} ), that way we only need log2N storage.

Parameters

log2N	Number of bits in N (N = 2^log2N)
twiddle	Array to store computed twiddle factors

Note: This is a static function.

◆ ComputeTwiddleFactors() [1/4]

void hops::MHO_FastFourierTransformUtilities< double >::ComputeTwiddleFactors	(	unsigned int	N,
		std::complex< double > *	twiddle
	)

inline

Function MHO_FastFourierTransformUtilities<double>::ComputeTwiddleFactors.

Parameters

N	(unsigned int)
twiddle	(std::complex< double >*)

Returns: Return value (void MHO_FastFourierTransformUtilities< double)

◆ ComputeTwiddleFactors() [2/4]

void hops::MHO_FastFourierTransformUtilities< float >::ComputeTwiddleFactors	(	unsigned int	N,
		std::complex< float > *	twiddle
	)

inline

Function MHO_FastFourierTransformUtilities<float>::ComputeTwiddleFactors.

Parameters

N	(unsigned int)
twiddle	(std::complex< float >*)

Returns: Return value (void MHO_FastFourierTransformUtilities< float)

◆ ComputeTwiddleFactors() [3/4]

void hops::MHO_FastFourierTransformUtilities< long double >::ComputeTwiddleFactors	(	unsigned int	N,
		std::complex< long double > *	twiddle
	)

inline

Function MHO_FastFourierTransformUtilities<long double>::ComputeTwiddleFactors.

Parameters

N	(unsigned int)
twiddle	(std::complex< long double >*)

Returns: Return value (void MHO_FastFourierTransformUtilities< long double)

◆ ComputeTwiddleFactors() [4/4]

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::ComputeTwiddleFactors	(	unsigned int	N,
		std::complex< XFloatType > *	twiddle
	)

static

Compute twiddle factors for a Fast Fourier Transform. computes all the twiddle factors e^{i*2*pi/N} for 0 to N-1 using std::cos and std::sin which is more accurate than the recursive method.

Parameters

N	Size of the transform (N).
twiddle	Output array to store computed twiddle factors.

Note: This is a static function.

◆ Conjugate() [1/2]

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::Conjugate	(	unsigned int	N,
		std::complex< XFloatType > *	array
	)

inlinestatic

Conjugates each element in a complex array.

Parameters

N	Size of the input array
array	Input/output array of complex numbers

Note: This is a static function.

◆ Conjugate() [2/2]

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::Conjugate	(	unsigned int	N,
		std::complex< XFloatType > *	array,
		unsigned int	stride
	)

inlinestatic

Conjugates each element in a complex (strided) array.

Parameters

N	Size of the array
array	Input/output complex array to conjugate
stride	(unsigned int)

Note: This is a static function.

◆ FFTBluestein()

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::FFTBluestein	(	unsigned int	N,
		unsigned int	M,
		std::complex< XFloatType > *	data,
		std::complex< XFloatType > *	twiddle,
		std::complex< XFloatType > *	conj_twiddle,
		std::complex< XFloatType > *	scale,
		std::complex< XFloatType > *	circulant,
		std::complex< XFloatType > *	workspace,
		unsigned int	stride = `1`
	)

inlinestatic

Function Bluestein algorithm for arbitrary length, N is length of the data, (supports strided data access)

Parameters

N	(unsigned int) length of data
M	(unsigned int) Bluestein array size
data	(std::complex< XFloatType >*) data array
twiddle	(std::complex< XFloatType >*) twiddle factors
conj_twiddle	(std::complex< XFloatType >*) conjugate twiddle factors
scale	(std::complex< XFloatType >*) scale factors
circulant	(std::complex< XFloatType >*) circulant array
workspace	(std::complex< XFloatType >*) scratch space
stride	(unsigned int) (default is 1, unstrided)

Note: This is a static function.

◆ FFTRadixTwo_DIF() [1/2]

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::FFTRadixTwo_DIF	(	unsigned int	N,
		std::complex< XFloatType > *	data,
		std::complex< XFloatType > *	twiddle,
		unsigned int	stride = `1`
	)

inlinestatic

Radix-2 DIF FFT wrapper for a std::complex array.

Parameters

N	Size of the data array
data	Input/output complex data array
twiddle	Output twiddle factors array
stride	Stride for accessing data elements

Note: This is a static function.

◆ FFTRadixTwo_DIF() [2/2]

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::FFTRadixTwo_DIF	(	unsigned int	N,
		XFloatType *	data,
		XFloatType *	twiddle,
		unsigned int	stride = `1`
	)

inlinestatic

Performs Radix-2 Decimation In Frequency (DIF) FFT using conjugate array and twiddle factors. input: data array in normal order output: fft of data in bit-address permutated order.

Parameters

N	Size of the data array (must be power of 2)
data	Input/output complex data array
twiddle	Twiddle factor array
stride	Stride for accessing data elements

Note: This is a static function.

◆ FFTRadixTwo_DIT() [1/2]

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::FFTRadixTwo_DIT	(	unsigned int	N,
		std::complex< XFloatType > *	data,
		std::complex< XFloatType > *	twiddle,
		unsigned int	stride = `1`
	)

inlinestatic

Radix-2 DIT FFT wrapper for a std::complex array.

Parameters

N	Size of the data array
data	Input/output complex data array with given stride
twiddle	Precomputed twiddle factors array
stride	Stride for accessing data elements

Note: This is a static function.

◆ FFTRadixTwo_DIT() [2/2]

template<typename XFloatType >

static void hops::MHO_FastFourierTransformUtilities< XFloatType >::FFTRadixTwo_DIT	(	unsigned int	N,
		XFloatType *	data,
		XFloatType *	twiddle,
		unsigned int	stride = `1`
	)

inlinestatic

Computes a Radix-2 decimation in time (DIT) FFT. input: data array in bit-address permutated order output: fft of data in normal order.

Parameters

N	Size of the data array (must be power of 2)
data	Input/output array of complex numbers to conjugate
twiddle	Array of precomputed twiddle factors
stride	Stride between elements in the input array

Note: This is a static function.

The documentation for this class was generated from the following file:

MHO_FastFourierTransformUtilities.hh

Public Member Functions

Static Public Member Functions

Detailed Description

template<typename XFloatType> class hops::MHO_FastFourierTransformUtilities< XFloatType >

Constructor & Destructor Documentation

◆ MHO_FastFourierTransformUtilities()

◆ ~MHO_FastFourierTransformUtilities()

Member Function Documentation

◆ ButterflyRadixTwo_CooleyTukey()

◆ ButterflyRadixTwo_GentlemanSande()

◆ ComputeBluesteinArraySize()

◆ ComputeBluesteinCirculantVector()

◆ ComputeBluesteinScaleFactors() [1/4]

◆ ComputeBluesteinScaleFactors() [2/4]

◆ ComputeBluesteinScaleFactors() [3/4]

◆ ComputeBluesteinScaleFactors() [4/4]

◆ ComputeConjugateTwiddleFactorBasis()

◆ ComputeConjugateTwiddleFactors()

◆ ComputeTwiddleFactorBasis() [1/4]

◆ ComputeTwiddleFactorBasis() [2/4]

◆ ComputeTwiddleFactorBasis() [3/4]

◆ ComputeTwiddleFactorBasis() [4/4]

◆ ComputeTwiddleFactors() [1/4]

◆ ComputeTwiddleFactors() [2/4]

◆ ComputeTwiddleFactors() [3/4]

◆ ComputeTwiddleFactors() [4/4]

◆ Conjugate() [1/2]

◆ Conjugate() [2/2]

◆ FFTBluestein()

◆ FFTRadixTwo_DIF() [1/2]

◆ FFTRadixTwo_DIF() [2/2]

◆ FFTRadixTwo_DIT() [1/2]

◆ FFTRadixTwo_DIT() [2/2]

template<typename XFloatType>
class hops::MHO_FastFourierTransformUtilities< XFloatType >