Fast Fourier Transform API#
FFT API Quick Reference#
Brief 
Forward Function 
Inverse Function 

BFP FFT on single real signal 

BFP FFT on single complex signal 

BFP FFT on pair of real signals 

BFP spectrum packing 

Lowlevel decimationintime FFT 

Lowlevel decimationinfrequency FFT 

FFT on real signal of 
 group fft_api
Functions

bfp_complex_s32_t *bfp_fft_forward_mono(bfp_s32_t *x)#
Performs a forward real Discrete Fourier Transform on a real 32bit sequence.
Performs an \(N\)point forward real DFT on the real 32bit BFP vector
x
, where \(N\) isx>length
. The operation is performed inplace, resulting in an \(N/2\)element complex 32bit BFP vector. Operation Performed
 \[\begin{split}\begin{aligned} & X[f] = \sum_{n=0}^{N1} \left( x[n]\cdot e^{j2\pi fn/N} \right) \\ & \text{ for } 0 \le f \le N/2 \end{aligned}\end{split}\]
where \(x[n]\) is the BFP vector initially represented by
x
, and \(X[f]\) is the DFT of \(x[n]\) represented by the returned pointer.The exponent, headroom, length and data contents of
x
are all updated by this function, thoughx>data
will continue to point to the same address.x>length
must be a power of 2, and must be no larger than(1<<MAX_DIT_FFT_LOG2)
.This function returns a
bfp_complex_s32_t
pointer. This points to the same address as . This is intended as a convenience for user code.Upon completion, the spectrum data is encoded in
x>data
as specified for real DFTs in Spectrum Packing. That is,x>data[f]
for1 <= f < (x>length)
represent \(X[f]\) for \(1 \le f < (N/2)\) andx>data[0]
represents \(X[0] + j X[N/2]\). Example
// Initialize time domain data with samples. int32_t buffer[N] = { ... }; bfp_s32_t samples; bfp_s32_init(&samples, buffer, 0, N, 1); // Perform the forward DFT { bfp_complex_s32_t* spectrum = bfp_fft_forward_mono(&samples); // `samples` should no longer be used. // Operate on frequency domain data using `spectrum` ... // Perform the inverse DFT to go back to time domain bfp_fft_inverse_mono(spectrum); // returns (bfp_s32_t*) which is the address of `samples` } // Use `samples` again to use new time domain data. ...
 Parameters:
x – [inout] The BFP vector \(x[n]\) to be DFTed.
 Returns:
Address of input BFP vector
x
, cast asbfp_complex_s32_t*
.

bfp_s32_t *bfp_fft_inverse_mono(bfp_complex_s32_t *x)#
Performs an inverse real Discrete Fourier Transform on a complex 32bit sequence.
Performs an \(N\)point inverse real DFT on the real 32bit BFP vector
x
, where \(N\) is2*x>length
. The operation is performed inplace, resulting in an \(N\)element real 32bit BFP vector. Operation Performed
 \[\begin{split}\begin{aligned} & x[n] = \sum_{f=0}^{N/2} \left( X[f]\cdot e^{j2\pi fn/N} \right) \\ & \text{ for } 0 \le n < N \end{aligned}\end{split}\]
where \(X[f]\) is the BFP vector initially represented by
x
, and \(x[n]\) is the IDFT of \(X[f]\) represented by the returned pointer.The exponent, headroom, length and data contents of
x
are all updated by this function, thoughx>data
will continue to point to the same address.x>length
must be a power of 2, and must be no larger than(1<<(MAX_DIT_FFT_LOG21))
.This function returns a
bfp_s32_t
pointer. This points to the same address as . This is intended as a convenience for user code.When calling, the spectrum data must be encoded in
x>data
as specified for real DFTs in Spectrum Packing. That is,x>data[f]
for1 <= f < (x>length)
represent \(X[f]\) for \(1 \le f < N/2\), andx>data[0]
represents \(X[0] + j X[N/2]\). Example
// Initialize time domain data with samples. int32_t buffer[N] = { ... }; bfp_s32_t samples; bfp_s32_init(&samples, buffer, 0, N, 1); // Perform the forward DFT { bfp_complex_s32_t* spectrum = bfp_fft_forward_mono(&samples); // `samples` should no longer be used. // Operate on frequency domain data using `spectrum` ... // Perform the inverse DFT to go back to time domain bfp_fft_inverse_mono(spectrum); // returns (bfp_s32_t*) which is the address of `samples` } // Use `samples` again to use new time domain data. ...
 Parameters:
x – [inout] The BFP vector \(X[f]\) to be IDFTed.
 Returns:
Address of input BFP vector
x
, cast asbfp_s32_t*
.

void bfp_fft_forward_complex(bfp_complex_s32_t *x)#
Performs a forward complex Discrete Fourier Transform on a complex 32bit sequence.
Performs an \(N\)point forward complex DFT on the complex 32bit BFP vector
x
, where \(N\) isx>length
. The operation is performed inplace. Operation Performed
 \[\begin{split}\begin{aligned} & X[f] = \sum_{n=0}^{N1} \left( x[n]\cdot e^{j2\pi fn/N} \right) \\ & \text{ for } 0 \le f < N \end{aligned}\end{split}\]
where \(x[n]\) is the BFP vector initially represented by
x
, and \(X[f]\) is the DFT of \(x[n]\), also represented byx
upon completion.The exponent, headroom and data contents of
x
are updated by this function.x>data
will continue to point to the same address.x>length
( \(N\)) must be a power of 2, and must be no larger than(1<<MAX_DIT_FFT_LOG2)
.Upon completion, the spectrum data is encoded in
x
as specified in Spectrum Packing. That is,x>data[f]
for0 <= f < (x>length)
represent \(X[f]\) for \(0 \le f < N\). Example
// Initialize complex time domain data with samples. complex_s32_t buffer[N] = { ... }; bfp_complex_s32_t vector; bfp_complex_s32_init(&vector, buffer, 0, N, 1); // Perform the forward DFT bfp_fft_forward_mono(&vector); // Operate on frequency domain data ... // Perform the inverse DFT to go back to time domain bfp_fft_inverse_mono(&vector); // `vector` contains (complex) timedomain data again ...
 Parameters:
x – [inout] The BFP vector \(x[n]\) to be DFTed.

void bfp_fft_inverse_complex(bfp_complex_s32_t *x)#
Performs an inverse complex Discrete Fourier Transform on a complex 32bit sequence.
Performs an \(N\)point inverse complex DFT on the complex 32bit BFP vector
x
, where \(N\) isx>length
. The operation is performed inplace. Operation Performed
 \[\begin{split}\begin{aligned} & x[n] = \sum_{f=0}^{N1} \left( X[f]\cdot e^{j2\pi fn/N} \right) \\ & \text{ for } 0 \le f < N \end{aligned}\end{split}\]
where \(X[f]\) is the BFP vector initially represented by
x
, and \(x[n]\) is the DFT of \(X[f]\), also represented byx
upon completion.The exponent, headroom and data contents of
x
are updated by this function.x>data
will continue to point to the same address.x>length
must be a power of 2, and must be no larger than(1<<MAX_DIT_FFT_LOG2)
.The data initially encoded in
x
are interpreted as specified in Spectrum Packing. That is,x>data[f]
for0 <= f < (x>length)
represent \(X[f]\) for \(0 \le f < N\). Example
// Initialize complex time domain data with samples. complex_s32_t buffer[N] = { ... }; bfp_complex_s32_t vector; bfp_complex_s32_init(&vector, buffer, 0, N, 1); // Perform the forward DFT bfp_fft_forward_mono(&vector); // Operate on frequency domain data ... // Perform the inverse DFT to go back to time domain bfp_fft_inverse_mono(&vector); // `vector` contains (complex) timedomain data again ...
 Parameters:
x – [inout] The BFP vector \(x[n]\) to be IDFTed.

void bfp_fft_forward_stereo(bfp_s32_t *a, bfp_s32_t *b, complex_s32_t scratch[])#
Performs a forward real Discrete Fourier Transform on a pair of real 32bit sequences.
Performs an \(N\)point forward real DFT on the real 32bit BFP vectors \(\bar a\) and \(\bar b\), where \(N\) is
a>length
(which must equalb>length
). The resulting spectra, \(\bar A\) and \(\bar B\), are placed ina
andb
. Each spectrum is a \(N/2\)element complex 32bit BFP vectors. To access the spectrum, the pointersa
andb
should be cast tobfp_complex_s32_t*
following a call to this function. Operation Performed
 \[\begin{split}\begin{aligned} & A[f] = \sum_{n=0}^{N1} \left( a[n]\cdot e^{j2\pi fn/N} \right) \text{ for } 0 \le f \le N/2 \\ & B[f] = \sum_{n=0}^{N1} \left( b[n]\cdot e^{j2\pi fn/N} \right) \text{ for } 0 \le f \le N/2 \end{aligned}\end{split}\]
where \(a[n]\) and \(b[n]\) are the two timedomain sequences represented by input BFP vectors
a
andb
, and \(A[f]\) and \(B[f]\) are the DFT of \(a[n]\) and \(b[n]\) respectively.a>length
( \(N\)) must be equal tob>length, must be a power of 2, and must be no larger than
(1<<MAX_DIT_FFT_LOG2)`.The parameters and are used as both inputs and outputs. To access the result of the FFT,
a
andb
should be cast tobfp_complex_s32_t
*. The structs’ metadata (e.g.exp
,hr
,length
) are updated by this function to reflect this change of interpretation. Thebfp_s32_t
references should be considered corrupted after this call (at least until bfp_fft_inverse_stereo() is called).The spectrum data is encoded in
a>data
andb>data
as specified for real DFTs in Spectrum Packing. That is,a>data[f]
for1 <= f < (a>length)
represent \(A[f]\) for \(1 \le f < (N/2)\) anda>data[0]
represents \(A[0] + j A[N/2]\). Likewise for the encoding ofb>data
.This function requires a scratch buffer large enough to contain \(N\)
complex_s32_t
elements. Deprecated:
 Example
// Initialize time domain data with samples. int32_t bufferA[N] = { ... }; int32_t bufferB[N] = { ... }; complex_s32_t scratch[N]; // scratch buffer  contents don't matter bfp_s32_t channel_A, channel_B; bfp_s32_init(&channel_A, buffer, 0, N, 1); bfp_s32_init(&channel_B, buffer, 0, N, 1); // Perform the forward DFT bfp_fft_forward_stereo(&channel_A, &channel_B, scratch); // channel_A and channel_B should now be considered clobbered as the structs are now // effectively bfp_complex_s32_t bfp_complex_s32_t* chanA = (bfp_complex_s32_t*) &channel_A; bfp_complex_s32_t* chanB = (bfp_complex_s32_t*) &channel_B; // Operate on frequency domain data using `chanA` and `chanB` ... // Perform the inverse DFT to go back to time domain bfp_fft_inverse_stereo(&chanA, &chanB, scratch); // Use channel_A and channel_B again to use new time domain data. ...
// Suppress this from generated documentation for the time being //
Note
Use of this function is not currently recommended. It functions correctly, but a recent change in this library’s API (namely, dropping support for channelpair vectors) means this function is no more computationally efficient than calling
bfp_fft_forward_mono()
on each input vector separately. Additionally, this function currently requires a scratch buffer, whereas the mono FFT does not. Parameters:
a – [inout] [Input] Timedomain BFP vector \(\bar a\). [Output] Frequency domain BFP vector \(\bar A\)
b – [inout] [Input] Timedomain BFP vector \(\bar b\). [Output] Frequency domain BFP vector \(\bar B\)
scratch – Scratch buffer of at least
a>length
complex_s32_t
elements

void bfp_fft_inverse_stereo(bfp_complex_s32_t *A_fft, bfp_complex_s32_t *B_fft, complex_s32_t scratch[])#
Performs an inverse real Discrete Fourier Transform on a pair of complex 32bit sequences.
Performs an \(N\)point inverse real DFT on the 32bit complex BFP vectors \(\bar A\) and \(\bar B\) (
A_fft
andB_fft
respectively), where \(N\) isA_fft>length
. The resulting real signals, \(\bar a\) and \(\bar b\), are placed inA_fft
andB_fft
. Each timedomain result is a \(N/2\)element real 32bit BFP vectors. To access the spectrum, the pointersA_fft
andB_fft
should be cast tobfp_s32_t*
following a call to this function. Operation Performed
 \[\begin{split}\begin{aligned} & a[n] = \sum_{f=0}^{N/21} \left( A[f]\cdot e^{j2\pi fn/N} \right) \text{ for } 0 \le n < N \\ & b[n] = \sum_{f=0}^{N/21} \left( B[f]\cdot e^{j2\pi fn/N} \right) \text{ for } 0 \le n < N \end{aligned}\end{split}\]
where \(A[f]\) and \(B[f]\) are the frequency spectra represented by BFP vectors
A_fft
andB_fft
, and \(a[n]\) and \(b[n]\) are the IDFT of \(A[f]\) and \(B[f]\).A_fft>length
( \(N\)) must be a power of 2, and must be no larger than(1<<(MAX_DIT_FFT_LOG21))
.The parameters and are used as both inputs and outputs. To access the result of the IFFT,
A_fft
andB_fft
should be cast tobfp_s32_t
*. The structs’ metadata (e.g.exp
,hr
,length
) are updated by this function to reflect this change of interpretation. Thebfp_complex_s32_t
references should be considered corrupted after this call.The spectrum data encoded in
A_fft>data
andA_fft>data
are interpreted as specified for real DFTs in Spectrum Packing. That is,A_fft>data[f]
for1 <= f < (a>length)
represent \(A[f]\) for \(1 \le f < (N/2)\) andA_fft>data[0]
represents \(A[0] + j A[N/2]\). Likewise for the encoding ofB_fft>data
.This function requires a scratch buffer large enough to contain \(2N\)
complex_s32_t
elements. Deprecated:
 Example
// Initialize time domain data with samples. int32_t bufferA[N] = { ... }; int32_t bufferB[N] = { ... }; complex_s32_t scratch[N]; // scratch buffer  contents don't matter bfp_s32_t channel_A, channel_B; bfp_s32_init(&channel_A, buffer, 0, N, 1); bfp_s32_init(&channel_B, buffer, 0, N, 1); // Perform the forward DFT bfp_fft_forward_stereo(&channel_A, &channel_B, scratch); // channel_A and channel_B should now be considered clobbered as the structs are now // effectively bfp_complex_s32_t bfp_complex_s32_t* chanA = (bfp_complex_s32_t*) &channel_A; bfp_complex_s32_t* chanB = (bfp_complex_s32_t*) &channel_B; // Operate on frequency domain data using `chanA` and `chanB` ... // Perform the inverse DFT to go back to time domain bfp_fft_inverse_stereo(&chanA, &chanB, scratch); // Use channel_A and channel_B again to use new time domain data. ...
// Suppress this from generated documentation for the time being //
Note
Use of this function is not currently recommended. It functions correctly, but a recent change in this library’s API (namely, dropping support for channelpair vectors) means this function is no more computationally efficient than calling
bfp_fft_forward_mono()
on each input vector separately. Additionally, this function currently requires a scratch buffer, whereas the mono FFT does not. Parameters:
A_fft – [inout] [Input] Freqdomain BFP vector \(\bar A\). [Output] Time domain BFP vector \(\bar b\)
B_fft – [inout] [Input] Freqdomain BFP vector \(\bar b\). [Output] Time domain BFP vector \(\bar b\)
scratch – Scratch buffer of at least
2*A_fft>length
complex_s32_t
elements

void bfp_fft_unpack_mono(bfp_complex_s32_t *x)#
Unpack the spectrum resulting from bfp_fft_forward_mono().
The DFT of a real signal is periodic with period FFT_N (the FFT length) and has a complex conjugate symmetry about index 0. These two properties guarantee that the imaginary part of both the DC component (index 0) and the Nyquist component (index FFT_N/2) of the spectrum are zero. To compute the forward FFT inplace, bfp_fft_forward_mono() packs the real part of the Nyquist rate component of the output spectrum into the imaginary part of the DC component.
This may be undesirable when operating on the signal’s complex spectrum. Use this function to unpack the Nyquist component. This function will also adjust the BFP vector’s length to reflect this unpacking.
NOTE: If you intend to unpack the spectrum using this function, the buffer for the timedomain BFP vector must have length
FFT_N+2
, rather thanFFT_N
(int32_t
elements), but these should NOT be reflected in the timedomain BFP vector’slength
field. Operation Performed
 \[\begin{split}\begin{aligned} & Re{x_{N/2}} && \leftarrow Im{x_0} \\ & Im{x_0} && \leftarrow 0 \\ & Im{x_{N/2}} && \leftarrow 0 \\ & x.length && \leftarrow x.length + 1 \end{aligned}\end{split}\]
NOTE: Before bfp_fft_inverse_mono() may be applied, bfp_fft_pack_mono() must be called, as the inverse FFT expects the data to be packed.
See also
 Parameters:
x – [inout] The spectrum to be unpacked

void bfp_fft_pack_mono(bfp_complex_s32_t *x)#
Pack the spectrum resulting from bfp_fft_unpack_mono().
This function applies the reverse process of bfp_fft_unpack_mono(), to prepare it for an inverse FFT using bfp_fft_inverse_mono().
See also
 Parameters:
x – [inout] The spectrum to be packed

void fft_dit_forward(complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)#
Compute a forward DFT using the decimationintime FFT algorithm.
This function computes the
N
point forward DFT of a complex input signal using the decimationintime FFT algorithm. The result is computed inplace. Operation Performed
 \[\begin{split}\begin{aligned} & X[f] = \frac{1}{2^{\alpha}} \sum_{n=0}^{N1} \left( x[n]\cdot e^{j2\pi fn/N} \right) \\ & \text{ for } 0 \le f < N \end{aligned}\end{split}\]
x[]
is interpreted to be a block floatingpoint vector with shared exponent*exp
and with*hr
bits of headroom initially inx[]
. During computation, this function monitors the headroom of the data and compensates to avoid overflows and underflows by bitshifting the data up or down as appropriate. In the equation above, \(\alpha\) represents the (net) number of bits that the data was rightshifted by.Upon completion,
*hr
is updated with the final headroom inx[]
, and the exponent*exp
is incremented by \(\alpha\).Note
In order to guarantee that saturation will not occur,
x[]
must have an initial headroom of at least 2 bits. Parameters:
x – [inout] The
N
element complex input vector to be transformed.N – [in] The size of the DFT to be performed.
hr – [inout] Pointer to the initial headroom in
x[]
.exp – [inout] Pointer to the initial exponent associated with
x[]
.
 Throws ET_LOAD_STORE:
Raised if
x
is not wordaligned (See Note: Vector Alignment)

void fft_dit_inverse(complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)#
Compute an inverse DFT using the decimationintime IFFT algorithm.
This function computes the
N
point inverse DFT of a complex spectrum using the decimationintime IFFT algorithm. The result is computed inplace. Operation Performed
 \[\begin{split}\begin{aligned} & x[n] = \frac{1}{2^{\alpha}} \sum_{f=0}^{N1} \left( X[f]\cdot e^{j2\pi fn/N} \right) \\ & \text{ for } 0 \le n < N \end{aligned}\end{split}\]
x[]
is interpreted to be a block floatingpoint vector with shared exponent*exp
and with*hr
bits of headroom initially inx[]
. During computation, this function monitors the headroom of the data and compensates to avoid overflows and underflows by bitshifting the data up or down as appropriate. In the equation above, \(\alpha\) represents the (net) number of bits that the data was rightshifted by.Upon completion,
*hr
is updated with the final headroom inx[]
, and the exponent*exp
is incremented by \(\alpha\).Note
In order to guarantee that saturation will not occur,
x[]
must have an initial headroom of at least 2 bits. Parameters:
x – [inout] The
N
element complex input vector to be transformed.N – [in] The size of the inverse DFT to be performed.
hr – [inout] Pointer to the initial headroom in
x[]
.exp – [inout] Pointer to the initial exponent associated with
x[]
.
 Throws ET_LOAD_STORE:
Raised if
x
is not wordaligned (See Note: Vector Alignment)

void fft_dif_forward(complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)#
Compute a forward DFT using the decimationinfrequency FFT algorithm.
This function computes the
N
point forward DFT of a complex input signal using the decimationinfrequency FFT algorithm. The result is computed inplace. Operation Performed
 \[\begin{split}\begin{aligned} & X[f] = \frac{1}{2^{\alpha}} \sum_{n=0}^{N1} \left( x[n]\cdot e^{j2\pi fn/N} \right) \\ & \text{ for } 0 \le f < N \end{aligned}\end{split}\]
x[]
is interpreted to be a block floatingpoint vector with shared exponent*exp
and with*hr
bits of headroom initially inx[]
. During computation, this function monitors the headroom of the data and compensates to avoid overflows and underflows by bitshifting the data up or down as appropriate. In the equation above, \(\alpha\) represents the (net) number of bits that the data was rightshifted by.Upon completion,
*hr
is updated with the final headroom inx[]
, and the exponent*exp
is incremented by \(\alpha\).Note
In order to guarantee that saturation will not occur,
x[]
must have an initial headroom of at least 2 bits. Parameters:
x – [inout] The
N
element complex input vector to be transformed.N – [in] The size of the DFT to be performed.
hr – [inout] Pointer to the initial headroom in
x[]
.exp – [inout] Pointer to the initial exponent associated with
x[]
.
 Throws ET_LOAD_STORE:
Raised if
x
is not wordaligned (See Note: Vector Alignment)

void fft_dif_inverse(complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)#
Compute an inverse DFT using the decimationinfrequency IFFT algorithm.
This function computes the
N
point inverse DFT of a complex spectrum using the decimationinfrequency IFFT algorithm. The result is computed inplace. Operation Performed
 \[\begin{split}\begin{aligned} & x[n] = \frac{1}{2^{\alpha}} \sum_{f=0}^{N1} \left( X[f]\cdot e^{j2\pi fn/N} \right) \\ & \text{ for } 0 \le n < N \end{aligned}\end{split}\]
x[]
is interpreted to be a block floatingpoint vector with shared exponent*exp
and with*hr
bits of headroom initially inx[]
. During computation, this function monitors the headroom of the data and compensates to avoid overflows and underflows by bitshifting the data up or down as appropriate. In the equation above, \(\alpha\) represents the (net) number of bits that the data was rightshifted by.Upon completion,
*hr
is updated with the final headroom inx[]
, and the exponent*exp
is incremented by \(\alpha\).Note
In order to guarantee that saturation will not occur,
x[]
must have an initial headroom of at least 2 bits. Parameters:
x – [inout] The
N
element complex input vector to be transformed.N – [in] The size of the inverse DFT to be performed.
hr – [inout] Pointer to the initial headroom in
x[]
.exp – [inout] Pointer to the initial exponent associated with
x[]
.
 Throws ET_LOAD_STORE:
Raised if
x
is not wordaligned (See Note: Vector Alignment)

bfp_complex_s32_t *bfp_fft_forward_mono(bfp_s32_t *x)#