Someone recently asked me if I knew of a way to compute a fast Fourier transform (FFT) of complex-valued input samples using an FFT algorithm that accepts only real-valued input data. Knowing of no way to do this, I rifled through my library of hardcopy FFT articles looking for help. I found nothing useful that could be applied to this problem.

After some thinking, I believe I have a solution to this problem. Here is my idea:

Let's say our original input data is the complex-valued sequence x_c(n) having N samples, and the desired FFT of that complex x_c(n) sequence is the complex-valued sequence X_c(m), where the time and frequency indices are 0≤n≤N–1 and 0≤m≤N–1 respectively. The input x_c(n) can be represented by:

If the result of a real FFT of the real part of x_c(n), x_r(n), is X_r(m), and the result of a real FFT of the imaginary part of x_c(n), x_i(n), is X_i(m), then the desired complex FFT of x_c(n) is:

    X_c(m) = real[X_r(m)] - imag[X_i(m)] + j{imag[X_r(m)] + real[X_i(m)]}    (2)

where j = sqrt(–1).

I don't claim that Eq. (2) is novel, or special, in any way. (There are probably 8,000 guys out there who've already solved this problem.) I merely present Eq. (2) here because I haven't seen it anywhere else. Who knows, maybe Eq. (2) will be of use to someone out there. An algebraic justification for Eq. (2) is given in the Appendix.

APPENDIX
There exists a technique where two independent N–point real input data sequences can be transformed using a single N–point complex FFT. We call this scheme the "Two N–Point Real FFTs" algorithm. The derivation of this technique is straightforward and described in the literature. [1]–[4] If two N–point real input sequences are x_r(n) and x_i(n), they'll have FFTs represented by X_r(m) and X_i(m). If we treat the x_r(n) sequence as the real part of a complex FFT input and the x_i(n) sequence as the imaginary part of the complex FFT input, then the constructed complex x_c(n) input sequence to a complex FFT is:

If the N-point FFT of x_c(n) is X_c(m), then the desired X_r(m) and X_i(m) results are:

    X_r(m) = [X_c(N–m)* + X_c(m)]/2    (A-2)

and

    X_i(m) = j[X_c(N–m)* – X_c(m)]/2    (A-3)

where 0≤m≤N-1, and the "*" symbol means complex conjugate. Equations (A-2) and (A-3) are well known.(Due to the periodicity of X_c(m), when m = 0, X_c(N-m)* = X_c(0)*.)

But our problem is the reverse of the above expressions: in this blog we know X_r(m) and X_i(m) and we desire to find X_c(m). We do that by rearranging Eqs. (A-2) and (A-3), solving them for X_c(N-m)*, and writing:

    2X_r(m) - X_c(m) = X_c(N–m)*    (A-4)

and

    2X_i(m)/j + X_c(m) = X_c(N–m)*.    (A-5)

Setting the left sides of Eqs. (A-4) and (A-5) equal to each other and solving for X_c(m), we have:

    X_c(m) = X_r(m) - X_i(m)/j .    (A-6)

We're almost finished. Converting Eq. (A-6) into the more convenient rectangular form, we write

    X_c(m) = real[X_r(m)] +j•imag[X_r(m)] -{real[X_i(m)] +j•imag[X_i(m)]}/j    (A-7)

or

    X_c(m) = real[X_r(m)] +j•imag[X_r(m)] -{imag[X_i(m)] - j•imag[X_i(m)]}    (A-8)

Combining the real and imaginary terms in Eq. (A-8), we (finally) have our desired:

    X_c(m) = real[X_r(m)] - imag[X_i(m)] + j{imag[X_r(m)] + real[X_i(m)]}    (A-9)

which is equivalent to this blog's Eq. (2).

[1] Cooley, J., Lewis, P., and Welch, P. “The Fast Fourier Transform Algorithm: Programming Considerations in the Calculation of Sine, Cosine and Laplace Transforms,” Journal Sound Vib., Vol. 12, July 1970, pp. 315-337.
[2] Brigham, E. The Fast Fourier Transform and Its Applications, Prentice Hall, Englewood Cliffs, New Jersey, 1988, pp. 166-167.
[3] Burrus, C. et al., Computer-Based Exercises for Signal Processing, Prentice Hall, Englewood Cliffs, New Jersey, 1994, pp. 56.
[4] Lyons, R. Understanding Digital Signal Processing, 2nd Ed., Prentice Hall, Englewood Cliffs, New Jersey, 2004, pp. 488-490.

unconed wrote:

Rick Lyons wrote:

squreshi wrote: