Filter
Top Products
DSP_fft
4-98
Complex Forward FFT With Digital Reversal
DSP_fft
Function void DSP_fft (const short * restrict w, int nx, short * restrict x, short * restrict y)
Arguments w[2*nx] Pointer to vector of Q.15 FFT coefficients of size 2 * nx
elements. Must be double-word aligned.
nx Number of complex elements in vector x. Must be a power of
4 and 4 ≤ nx ≤ 65536.
x[2*nx] Pointer to input sequence of size 2 * nx elements. Must be
double-word aligned.
y[2*nx] Pointer to output sequence of size 2 * nx elements. Must be
double-word aligned.
Description This routine is used to compute an FFT of a complex sequence of size nx, a
power of 4, with “decimation-in-frequency decomposition” method. The output
is returned in a separate array y in normal order. This routine also performs
digit reversal as a special last step. Each complex value is stored as
interleaved 16-bit real and imaginary parts. The code uses a special ordering
of FFT factors and memory accesses to improve performance in the presence
of cache.
Algorithm This is the C equivalent of the assembly code without restrictions. Note that
the assembly code is hand optimized and restrictions may apply.
/*−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−*/
/* The following macro is used to obtain a digit reversed index, of a given */
/* number i, into j where the number of bits in ”i” is ”m”. For the natural */
/* form of C code, this is done by first interchanging every set of ”2 bit” */
/* pairs, followed by exchanging nibbles, followed by exchanging bytes, and */
/* finally halfwords. To give an example, consider the following number: */
/* */
/* N = FEDCBA9876543210, where each digit represents a bit, the following */
/* steps illustrate the changes as the exchanges are performed: */
/* M = DCFE98BA54761032 is the number after every ”2 bits” are exchanged. */
/* O = 98BADCFE10325476 is the number after every nibble is exchanged. */
/* P = 1032547698BADCFE is the number after every byte is exchanged. */
/* Since only 16 digits were considered this represents the digit reversed */
/* index. Since the numbers are represented as 32 bits, there is one more */
/* step typically of exchanging the half words as well. */
/*−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−*/