Fast Fourier Transform Application

The N-point discrete Fourier transform (DFT) is a block operation which takes N complex-valued (time-domain) input coefficients and transforms them into N complex-valued (frequency-domain) output coefficients. The N-point DFT is defined by: X[k] = ∑N-1n=0 x[n] · ej·2πknN, 0 ≤ k ≤ N.

An efficient implementation of the DFT is the decimation-in-time radix2 FFT. In this implementation, the computation is split up into N / 2 · log2(N). 2point FFTs:

Using the 2-point FFT, higher-order FFTs can be computed by arranging N / 2 · log2(N). 2-point FFTs and connecting them using a butterfly network:

The complexity of the FFT is O(N log N) compared to O(N2) of the DFT.

To model the FFT, we proceed as follows:

• The input coefficients are ordered in bit-reversed order, that is, the index of the coefficient at channel k can be computed by writing down the binary representation of k using log2(N) bits and reversing the order of bits. For instance: 3 ⟶ 011 ⟶ 110 ⟶ 6. This function is defined in a <function> element in the process network.
• The butterfly network is generated by properly connecting the ports of the 2-point FFTs. The index of the channel connected to port inA of a 2-point FFT with process index p and layer index l is given by: indexinA = 2(p mod 2l-1) + [p –— 2l-1] + [p — 2l] · (2l+1 - 2). The index of the channel connected to port inB is given by indexinB = indexinA + 2l. This function is defined in a <function> element in the process network.
• Each 2-point FFT in the last layer of the network yields two output coefficients. In particular, the indices of the output coefficients are as follows, where p stands for the process index: outA = X[p] and outB = X[p + N / 2] . This function is directly defined in a corresponding <append> element.
• The coefficient WkN for a process with index p and located in layer l is Wp mod 2l2(l+1) . This function is computed in the init() function of the 2-point FFT process.