SPRACN4 August   2019 66AK2G12 , 66AK2H06 , 66AK2H12 , 66AK2H14 , OMAP-L132 , OMAP-L138 , TMS320C6452 , TMS320C6454 , TMS320C6455 , TMS320C6457 , TMS320C6652 , TMS320C6654 , TMS320C6655 , TMS320C6657 , TMS320C6672 , TMS320C6674 , TMS320C6678 , TMS320C6742 , TMS320C6743 , TMS320C6745 , TMS320C6746 , TMS320C6747 , TMS320C6748

 

  1.   Using DSPLIB FFT Implementation for Real Input and Without Data Scaling
    1.     Trademarks
    2. 1 Real Input Introduction
      1. 1.1 Prerequisites
      2. 1.2 Computing a Length N/2 Complex FFT From a Length N Real Input Sequence
      3. 1.3 Returning to a Length N Real Sequence Using a Length N/2 Complex IFFT
      4. 1.4 Benchmark of the Efficient Compute of FFT
    3. 2 Fixed Point FFT With No Data Scaling
      1. 2.1 Suggested Change
      2. 2.2 Example Application
    4. 3 Summary
    5. 4 References

1.2 Computing a Length N/2 Complex FFT From a Length N Real Input Sequence

Let g(n) be an N-point real sequence (N must be even). Compute the N-point complex FFT, but only use an N/2-point FFT computation. This can be accomplished by using the following steps:

  1. Form the the N/2-point complex valued sequence, x(n) = x1(n) + jx2(n), where x1(n) = g(2n) and x2(n) = g(2n + 1).
  2. Compute the N/2-point complex FFT on the complex valued sequence x(n) to obtain X(k) = FFT{x(n)}. Note that the FFT should be performed with bit reversal.
  3. Perform an additional computation to get G(k) from X(k).
    4. Gr(k) = Xr(k)Ar(k) – Xi(k)Ai(k) + Xr(N/2–k)Br(k) + Xi(N/2–k)Bi(k), for k = 0, 1, ..., N/2–1 and X(N/2) = X(0) Gi(k) = Xi(k)Ar(k) + Xr(k)Ai(k) + Xrr(N/2–k)Bi(k) – Xi(N/2–k)Br(k)

Note that only N/2 points of the N-point sequence of G(k) are computed in the above equations. Because the FFT of a real-sequence has symmetric properties, you can easily compute the remaining N/2 points of G(k) with the following equations:

Gr(N/2) = Xr(0) – Xi(0) Gi(N/2) = 0 Gr(N–k) = Gr(k), for k = 1, 2, ..., N/2–1 Gi(N–k) = –Gi(k)

As you can see, the above equations require A(k) and B(k), which are sine and cosine coefficients. These values can be precomputed with the following C code, where even indices contains the real part and odd indices contain the imaginary part.

for (i = 0; i < N/2; i++) { A[2 * i] = 0.5 * (1.0 - sin (2 * PI / (double) (2 * N) * (double) i)); A[2 * i + 1] = 0.5 * (-1.0 * cos (2 * PI / (double) (2 * N) * (double) i)); B[2 * i] = 0.5 * (1.0 + sin (2 * PI / (double) (2 * N) * (double) i)); B[2 * i + 1] = 0.5 * (1.0 * cos (2 * PI / (double) (2 * N) * (double) i)); }