XS3 FFT-Related Functions¶

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

x – [in] The vector to have its elements reordered.
length – [in] The length of x (element count).

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

x – [in] The spectrum \(X[f]\) to be split into \(A[f]\) and \(B[f]\).
length – [in] The length of x in elements (i.e. FFT length \(N\)).

Throws

ET_LOAD_STORE – Raised if x is not word-aligned (See Note: Vector Alignment)

Returns

The headroom of the result x

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

x – [in] The spectra \(A[f]\) and \(B[f]\), packed as specified.
length – [in] The length of x in elements (i.e. FFT length \(N\)).

Throws

ET_LOAD_STORE – Raised if x is not word-aligned (See Note: Vector Alignment)

Returns

The headroom of the result x

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] = { ... };
complex_s32_t* X = (complex_s32_t*)x;
exponent_t x_exp = ...;
headroom_t hr = xs3_vect_s32_headroom(x, N);
xs3_fft_index_bit_reversal(X, N);
xs3_fft_dit_forward(X, N/2, &hr, &x_exp);
xs3_fft_mono_adjust(X, N, 0);

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 = ...;
headroom_t hr = xs3_vect_s32_headroom(x, N);
xs3_fft_mono_adjust(X, N, 1);
xs3_fft_index_bit_reversal(X, N);
xs3_fft_dit_inverse(X, N/2, &hr, &X_exp);

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.

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.

Parameters

x – [in] The spectrum \(X[f]\) to be modified.
length – [in] The size of the DFT to be computed. Twice the length of x (in elements).
inverse – [in] Flag indicating whether the inverse DFT is being computed.

Throws

ET_LOAD_STORE – Raised if x is not word-aligned (See Note: Vector Alignment)

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

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 word-aligned (See Note: Vector Alignment)

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 \]

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

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 word-aligned (See Note: Vector Alignment)

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 \]

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

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 word-aligned (See Note: Vector Alignment)

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 \]

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

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 word-aligned (See Note: Vector Alignment)