# 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.

**Previous post by Rick Lyons:**

Some Thoughts on a German Mathematician

**Next post by Rick Lyons:**

Computing FFT Twiddle Factors

- 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.

Registering will allow you to participate to the forums on ALL the related sites and give you access to all pdf downloads.