# Computing an FFT of Complex-Valued Data Using a Real-Only FFT Algorithm

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:

*x*

_{c}(0) =

*x*

_{r}(0) +

*jx*

_{i}(0),

*x*

_{c}(1) =

*x*

_{r}(1) +

*jx*

_{i}(1),

*x*

_{c}(2) =

*x*

_{r}(2) +

*jx*

_{i}(2),

...

...

*x*

_{c}(

*N*-1) =

*x*

_{r}(

*N*-1) +

*jx*

_{i}(

*N*-1). (1)

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:

*x*

_{c}(0) =

*x*

_{r}(0) +

*jx*

_{i}(0),

*x*

_{c}(1) =

*x*

_{r}(1) +

*jx*

_{i}(1),

*x*

_{c}(2) =

*x*

_{r}(2) +

*jx*

_{i}(2),

...

...

*x*

_{c}(

*N*-1) =

*x*

_{r}(

*N*-1) +

*jx*

_{i}(

*N*-1). (A-1)

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:

2*X*_{r}(*m*) - *X*_{c}(*m*) = *X*_{c}(*N*–*m*)* (A-4)

and

2*X*_{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.

- Comments
- Write a Comment Select to add a comment

To post reply to a comment, click on the 'reply' button attached to each comment. To post a new comment (not a reply to a comment) check out the 'Write a Comment' tab at the top of the comments.

Please login (on the right) if you already have an account on this platform.

Otherwise, please use this form to register (free) an join one of the largest online community for Electrical/Embedded/DSP/FPGA/ML engineers: