Not a member?

DSP Blogs > Rick Lyons > Computing an FFT of Complex-Valued Data Using a Real-Only FFT Algorithm

Rick Lyons
Richard (Rick) Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is the author of "Understanding Digital Signal Processing 2/E" (Prentice-Hall, 2004), and Editor of, and contributor to, "Streamlining Digital Signal Processing, A Tricks of the Trade Guidebook" (IEEE Press/Wiley, 2007). He is also an Associate Editor for the IEEE Signal Processing Magazine.

Would you like to be notified by email when Rick Lyons publishes a new blog?

Pageviews: 216

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

Posted by Rick Lyons on Feb 9 2010 under Tips and Tricks

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 xc(n) having N samples, and the desired FFT of that complex xc(n) sequence is the complex-valued sequence Xc(m), where the time and frequency indices are 0≤nN–1 and 0≤mN–1 respectively. The input xc(n) can be represented by:

xc(0) = xr(0) + jxi(0),
xc(1) = xr(1) + jxi(1),
xc(2) = xr(2) + jxi(2),
...
...
xc(N-1) = xr(N-1) + jxi(N-1).    (1)

If the result of a real FFT of the real part of xc(n), xr(n), is Xr(m), and the result of a real FFT of the imaginary part of xc(n), xi(n), is Xi(m), then the desired complex FFT of xc(n) is:

Xc(m) = real[Xr(m)] - imag[Xi(m)] + j{imag[Xr(m)] + real[Xi(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 xr(n) and xi(n), they'll have FFTs represented by Xr(m) and Xi(m). If we treat the xr(n) sequence as the real part of a complex FFT input and the xi(n) sequence as the imaginary part of the complex FFT input, then the constructed complex xc(n) input sequence to a complex FFT is:

xc(0) = xr(0) + jxi(0),
xc(1) = xr(1) + jxi(1),
xc(2) = xr(2) + jxi(2),
...
...
xc(N-1) = xr(N-1) + jxi(N-1).    (A-1)

If the N-point FFT of xc(n) is Xc(m), then the desired Xr(m) and Xi(m) results are:

Xr(m) = [Xc(N–m)* + Xc(m)]/2    (A-2)

and

Xi(m) = j[Xc(N–m)* – Xc(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 Xc(m), when m = 0, Xc(N-m)* = Xc(0)*.)

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

2Xr(m) - Xc(m) = Xc(Nm)*    (A-4)

and

2Xi(m)/j + Xc(m) = Xc(Nm)*.    (A-5)

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

Xc(m) = Xr(m) - Xi(m)/j .    (A-6)

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

Xc(m) = real[Xr(m)] +j•imag[Xr(m)] -{real[Xi(m)] +j•imag[Xi(m)]}/j    (A-7)

or

Xc(m) = real[Xr(m)] +j•imag[Xr(m)] -{imag[Xi(m)] - j•imag[Xi(m)]}    (A-8)

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

Xc(m) = real[Xr(m)] - imag[Xi(m)] + j{imag[Xr(m)] + real[Xi(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.

5

posted by Rick Lyons
Richard (Rick) Lyons is a consulting Systems Engineer and lecturer with Besser Associates in Mountain View, California. He is the author of "Understanding Digital Signal Processing 2/E" (Prentice-Hall, 2004), and Editor of, and contributor to, "Streamlining Digital Signal Processing, A Tricks of the Trade Guidebook" (IEEE Press/Wiley, 2007). He is also an Associate Editor for the IEEE Signal Processing Magazine.

Previous post by Rick Lyons: Some Thoughts on a German Mathematician
Next post by Rick Lyons: Computing FFT Twiddle Factors
all articles by Rick Lyons

Would you like to be notified by email when Rick Lyons publishes a new blog?

unconed
Said:
Am I missing something or did you just use a very complicated way to describe the linearity of the Fourier transform? xc = xr + j*xi <=> Xc = Xr + j*Xi <=> Xc = real(Xr) + j*imag(Xr) + j*(real(Xi) + j*imag(Xi)) <=> Xc = real(Xr) - imag(Xi) + j*(real(Xi) + image(Xr))
3 years ago
0
Sorry, you need javascript enabled to post any comments.
Rick Lyons
Replied:
Hello unconed, As it turns out, yes, you are correct. Although I didn't arrive at my Eq. (2), in the way I did, in order to make the problem appear complicated. I merely did not, for some reason, see the simple linearity property that you did unconed. You've given me another example of: how we view a problem, how we understand a problem, profoundly affects how we try to solve a problem. I knew my Eqs. (A-2) and (A-3) and thought, "How do I find xc(m)?" This isn't the first time I've solved a problem "the hard way." I wonder if it'll be the last time. Thanks unconed. [-Rick-]
3 years ago
0
squreshi
Said:
Along similar lines, there is also a neat trick to compute the FFT of a real-valued signal given an FFT that accepts only complex-valued input. This situation is actually encountered quite frequently on DSP platforms.
3 years ago
0