XCORE SDK
XCORE Software Development Kit
Functions
XS3 FFT-Related Functions

Functions

void xs3_fft_index_bit_reversal (complex_s32_t x[], const unsigned length)
 Applies the index bit-reversal required for FFTs. More...
 
headroom_t xs3_fft_spectra_split (complex_s32_t x[], const unsigned length)
 Splits the merged spectrum that results from DFTing a pair of real signals together. More...
 
headroom_t xs3_fft_spectra_merge (complex_s32_t x[], const unsigned length)
 Merges the spectra of two real signals so they can be IDFTed simultaneously. More...
 
void xs3_fft_mono_adjust (complex_s32_t x[], const unsigned length, const unsigned inverse)
 Makes the adjustments required when performing a mono DFT or IDFT. More...
 
void xs3_fft_dit_forward (complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)
 Compute a forward DFT using the decimation-in-time FFT algorithm. More...
 
void xs3_fft_dit_inverse (complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)
 Compute an inverse DFT using the decimation-in-time IFFT algorithm. More...
 
void xs3_fft_dif_forward (complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)
 Compute a forward DFT using the decimation-in-frequency FFT algorithm. More...
 
void xs3_fft_dif_inverse (complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)
 Compute an inverse DFT using the decimation-in-frequency IFFT algorithm. More...
 

Detailed Description

Function Documentation

◆ xs3_fft_dif_forward()

void xs3_fft_dif_forward ( complex_s32_t  x[],
const unsigned  N,
headroom_t hr,
exponent_t exp 
)

Compute a forward DFT using the decimation-in-frequency FFT algorithm.

This function computes the N-point forward DFT of a complex input signal using the decimation-in-frequency FFT algorithm. The result is computed in-place.

Conceptually, the operation performed is the following:

\[ X[f] = \frac{1}{2^{\alpha}} \sum_{n=0}^{N-1} \left( x[n]\cdot e^{-j2\pi fn/N} \right) \text{ for } 0 \le f \lt N \]

x[] is interpreted to be a block floating-point vector with shared exponent *exp and with *hr bits of headroom initially in x[]. During computation, this function monitors the headroom of the data and compensates to avoid overflows and underflows by bit-shifting the data up or down as appropriate. In the equation above, \(\alpha\)
represents the (net) number of bits that the data was right-shifted by.

Upon completion, *hr is updated with the final headroom in x[], 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
[in,out]xThe N-element complex input vector to be transformed.
[in]NThe size of the DFT to be performed.
[in,out]hrPointer to the initial headroom in x[].
[in,out]expPointer to the initial exponent associated with x[].
Exceptions
ET_LOAD_STORERaised if x is not word-aligned (See Note: Vector Alignment)

◆ xs3_fft_dif_inverse()

void xs3_fft_dif_inverse ( complex_s32_t  x[],
const unsigned  N,
headroom_t hr,
exponent_t exp 
)

Compute an inverse DFT using the decimation-in-frequency IFFT algorithm.

This function computes the N-point inverse DFT of a complex spectrum using the decimation-in-frequency IFFT algorithm. The result is computed in-place.

Conceptually, the operation performed is the following:

\[ x[n] = \frac{1}{2^{\alpha}} \sum_{f=0}^{N-1} \left( X[f]\cdot e^{j2\pi fn/N} \right) \text{ for } 0 \le n \lt N \]

x[] is interpreted to be a block floating-point vector with shared exponent *exp and with *hr bits of headroom initially in x[]. During computation, this function monitors the headroom of the data and compensates to avoid overflows and underflows by bit-shifting the data up or down as appropriate. In the equation above, \(\alpha\)
represents the (net) number of bits that the data was right-shifted by.

Upon completion, *hr is updated with the final headroom in x[], 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
[in,out]xThe N-element complex input vector to be transformed.
[in]NThe size of the inverse DFT to be performed.
[in,out]hrPointer to the initial headroom in x[].
[in,out]expPointer to the initial exponent associated with x[].
Exceptions
ET_LOAD_STORERaised if x is not word-aligned (See Note: Vector Alignment)

◆ xs3_fft_dit_forward()

void xs3_fft_dit_forward ( complex_s32_t  x[],
const unsigned  N,
headroom_t hr,
exponent_t exp 
)

Compute a forward DFT using the decimation-in-time FFT algorithm.

This function computes the N-point forward DFT of a complex input signal using the decimation-in-time FFT algorithm. The result is computed in-place.

Conceptually, the operation performed is the following:

\[ X[f] = \frac{1}{2^{\alpha}} \sum_{n=0}^{N-1} \left( x[n]\cdot e^{-j2\pi fn/N} \right) \text{ for } 0 \le f \lt N \]

x[] is interpreted to be a block floating-point vector with shared exponent *exp and with *hr bits of headroom initially in x[]. During computation, this function monitors the headroom of the data and compensates to avoid overflows and underflows by bit-shifting the data up or down as appropriate. In the equation above, \(\alpha\)
represents the (net) number of bits that the data was right-shifted by.

Upon completion, *hr is updated with the final headroom in x[], 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
[in,out]xThe N-element complex input vector to be transformed.
[in]NThe size of the DFT to be performed.
[in,out]hrPointer to the initial headroom in x[].
[in,out]expPointer to the initial exponent associated with x[].
Exceptions
ET_LOAD_STORERaised if x is not word-aligned (See Note: Vector Alignment)

◆ xs3_fft_dit_inverse()

void xs3_fft_dit_inverse ( complex_s32_t  x[],
const unsigned  N,
headroom_t hr,
exponent_t exp 
)

Compute an inverse DFT using the decimation-in-time IFFT algorithm.

This function computes the N-point inverse DFT of a complex spectrum using the decimation-in-time IFFT algorithm. The result is computed in-place.

Conceptually, the operation performed is the following:

\[ x[n] = \frac{1}{2^{\alpha}} \sum_{f=0}^{N-1} \left( X[f]\cdot e^{j2\pi fn/N} \right) \text{ for } 0 \le n \lt N \]

x[] is interpreted to be a block floating-point vector with shared exponent *exp and with *hr bits of headroom initially in x[]. During computation, this function monitors the headroom of the data and compensates to avoid overflows and underflows by bit-shifting the data up or down as appropriate. In the equation above, \(\alpha\)
represents the (net) number of bits that the data was right-shifted by.

Upon completion, *hr is updated with the final headroom in x[], 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
[in,out]xThe N-element complex input vector to be transformed.
[in]NThe size of the inverse DFT to be performed.
[in,out]hrPointer to the initial headroom in x[].
[in,out]expPointer to the initial exponent associated with x[].
Exceptions
ET_LOAD_STORERaised if x is not word-aligned (See Note: Vector Alignment)

◆ xs3_fft_index_bit_reversal()

void xs3_fft_index_bit_reversal ( complex_s32_t  x[],
const unsigned  length 
)

Applies the index bit-reversal required for FFTs.

Applying an FFT (xs3_fft_dit_forward() or xs3_fft_dif_forward()) or IFFT (xs3_fft_dit_inverse() or xs3_fft_dif_inverse()) requires an operation where the elements in a complex vector are rearranged such that each element ends up at a location whose index is the bit-reversal of the index at which it began. This function performs that operation.

Only the \(log2(length)\) least significant bits of each index are considered.

For example, when performing a \(32\)-point FFT:

12 = 0b01100
bit_reverse(k, log2(32)) -> 0b00110 = 6
X[12] <- X[6]
X[6] <- X[12]

x is updated in-place.

length must be a power of 2.

Parameters
[in]xThe vector to have its elements reordered.
[in]lengthThe length of x (element count).

◆ xs3_fft_mono_adjust()

void xs3_fft_mono_adjust ( complex_s32_t  x[],
const unsigned  length,
const unsigned  inverse 
)

Makes the adjustments required when performing a mono DFT or IDFT.

An \(N/2\)-point DFT can be used to compute the \(N\)-point DFT \(X[f]\) of a single real signal \(x[n]\). Similarly, an \((N/2)\)-point inverse DFT can be used to compute the real \(N\)-point inverse DFT \(x[n]\) of a spectrum \(X[f]\). This is more efficient (in terms of both memory and compute resources) than performing the operations using the full \(N\)-point complex DFT or inverse DFT.

This function performs a manipulation of the spectrum required in that process.

To perform the \(N\)-point forward DFT on such a real signal x[n]:

int32_t x[N] = { ... };
exponent_t x_exp = ...;
xs3_fft_dit_forward(X, N/2, &hr, &x_exp);
int exponent_t
An exponent.
Definition: xs3_math_types.h:76
unsigned headroom_t
Headroom of some integer or integer array.
Definition: xs3_math_types.h:86
void xs3_fft_index_bit_reversal(complex_s32_t x[], const unsigned length)
Applies the index bit-reversal required for FFTs.
void xs3_fft_mono_adjust(complex_s32_t x[], const unsigned length, const unsigned inverse)
Makes the adjustments required when performing a mono DFT or IDFT.
Definition: xs3_fft_util.c:162
void xs3_fft_dit_forward(complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)
Compute a forward DFT using the decimation-in-time FFT algorithm.
Definition: xs3_fft_dit.c:79
headroom_t xs3_vect_s32_headroom(const int32_t x[], const unsigned length)
Calculate the headroom of a 32-bit vector.
Definition: xs3_vect_headroom.c:54
A complex number with a 32-bit real part and 32-bit imaginary part.
Definition: xs3_math_types.h:49

To perform the \(N\)-point inverse DFT on the spectrum X[n] of a real signal x[n]:

complex_s32_t X[N/2] = { ... };
int32_t* x = (int32_t*)X;
exponent_t X_exp = ...;
xs3_fft_dit_inverse(X, N/2, &hr, &X_exp);
void xs3_fft_dit_inverse(complex_s32_t x[], const unsigned N, headroom_t *hr, exponent_t *exp)
Compute an inverse DFT using the decimation-in-time IFFT algorithm.
Definition: xs3_fft_dit.c:153
Note
xs3_fft_dit_forward() and xs3_fft_dit_inverse() each require a certain amount of headroom to avoid overflows. See their documentation for details.

x[] is an \(N/2\)-element complex vector representing the spectrum to be adjusted.

length is size of the real DFT to be computed, not the number of elements in x[] (or the size of the complex DFT to actually be employed).

inverse should be 1 if the inverse DFT is being computed, and 0 otherwise.

Parameters
[in]xThe spectrum \(X[f]\) to be modified.
[in]lengthThe size of the DFT to be computed. Twice the length of x (in elements).
[in]inverseFlag indicating whether the inverse DFT is being computed.
Exceptions
ET_LOAD_STORERaised if x is not word-aligned (See Note: Vector Alignment)

◆ xs3_fft_spectra_merge()

headroom_t xs3_fft_spectra_merge ( complex_s32_t  x[],
const unsigned  length 
)

Merges the spectra of two real signals so they can be IDFTed simultaneously.

This function is the inverse of xs3_fft_spectra_split().

If two spectra \(A[f]\) and \(B[f]\) meeting certain requirements are assumed to be the spectra of two real signals \(a[n]\) and \(b[n]\) respectively, then the two spectra can be combined in such a way that an inverse complex DFT will invert the spectra simultaneously, resulting in a complex signal \(x[n] = a[n] + j\cdot b[n]\). This function performs that merger.

This function requires the spectra of \(A[f]\) and \(B[f]\) to be packed into x as speciied for real stereo spectra in Spectrum Packing. Note that this is how the spectra are packed by xs3_fft_spectra_split().

length is the inverse DFT length \(N\), as well as the length of x and must be a power of 2.

This function returns the headroom of the resulting vector x.

Parameters
[in]xThe spectra \(A[f]\) and \(B[f]\), packed as specified.
[in]lengthThe length of x in elements (i.e. FFT length \(N\)).
Returns
The headroom of the result x
Exceptions
ET_LOAD_STORERaised if x is not word-aligned (See Note: Vector Alignment)

◆ xs3_fft_spectra_split()

headroom_t xs3_fft_spectra_split ( complex_s32_t  x[],
const unsigned  length 
)

Splits the merged spectrum that results from DFTing a pair of real signals together.

Two real signals \(a[n]\) and \(b[n]\) can be DFTed simultaneously by computing the DFT of a third, complex signal \(x[n] = a[n] + j\cdot b[n]\). The resulting spectrum \(X[f]\) contains the desired DFTs \(A[f]\) and \(B[f]\) mixed together in a separable way. This function separates \(X[f]\) into \(A[f]\) and \(B[f]\).

Note that the DFT \(G[f]\) of a real signal \(g[n]\) is periodic with period \(N\), and with a complex conjugate symmetry such that \(G[-f] = G^*[f]\). The \(N\)-point DFT of a real signal can therefore be represented with only \(N/2\) complex elements. As such, this function only writes \(A[f]\) and \(B[f]\) for \(0 <= f < N/2\).

All remaining elements can be calculated using the following properties of the DFT of a real signal:

\(G[-f] = G^*[f]\) and \(G[f] = G[f+N]\)

where \(G^*[f]\) is the complex conjugate of \(G[f]\).

Note that the above properties imply that both \(G[0]\) and \(G[N/2]\) must be purely real. For simplicity (i.e. so the operation can be performed in-place), the real part of \(A[N/2]\) and \(B[N/2]\) will be packed into the imaginary part of \(A[0]\) and \(B[0]\) respectively.

This function will pack the spectra \(A[f]\) and \(B[f]\) as specified for real stereo signals in Spectrum Packing. \(A[f]\) will begin at address &x[0] and \(B[f]\) will begin at address &x[length/2].

length is the DFT length \(N\), as well as the length of x and must be a power of 2.

This function returns the headroom of the resulting vector x.

Note
Either of the resulting two spectra \(A[f]\) and \(B[f]\) may actually have more headroom than the value returned. Due to an optimization in this algorithm's implementation, only the minimum of the two headrooms is computed. If an accurate headroom count is required on the resulting spectra, they should be computed following this function.
Parameters
[in]xThe spectrum \(X[f]\) to be split into \(A[f]\) and \(B[f]\).
[in]lengthThe length of x in elements (i.e. FFT length \(N\)).
Returns
The headroom of the result x
Exceptions
ET_LOAD_STORERaised if x is not word-aligned (See Note: Vector Alignment)