Real vs. complex FFT

Hi DSP People,

Just a quick question...  is there really much difference between the
processing of a normal, complex FFT and a real-only FFT?  I thought there
wouldn't be...  The FFT/DFT math still requires that complex and imaginary
parts of the FFT would be needed during the FFT processing, right?...  but
only the real part would be left at the end?.  This wouldn't necessarily
result in very much reduction in processing power, would it?

Thanks,

Chris

On Mon, 05 Apr 2004 07:08:59 GMT, "Chris Fogelklou"
<chris.fogelklou@comhem.se> wrote:

>Hi DSP People,
>
>Just a quick question...  is there really much difference between the
>processing of a normal, complex FFT and a real-only FFT?  I thought there
>wouldn't be...  The FFT/DFT math still requires that complex and imaginary
>parts of the FFT would be needed during the FFT processing, right?...  but
>only the real part would be left at the end?.  This wouldn't necessarily
>result in very much reduction in processing power, would it?

No, if that's all you did.  But the real advantage of a real-only FFT
is that there is a computational shortcut that makes an n point real
FFT into an n-1 point complex FFT.  You start out by packaging the 2^n
real points into the real and imaginary parts of an array of 2^(n-1)
complex numbers.  Perform the usual complex FFT on this array.  Then
there is a faily fast untangling step where that FFT is transformed
into the complete FFT of the original 2^n sequence.


-Robert Scott
 Ypsilanti, Michigan
(Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

On Mon, 05 Apr 2004 11:51:34 GMT, "Chris Fogelklou"
<chris.fogelklou@comhem.se> wrote:


>..Is there a good source on the theory regarding this?
>I did a quick google and only found implementations...

Try http://www.eptools.com/tn/T0001/PT10.HTM


-Robert Scott
 Ypsilanti, Michigan
(Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

"Robert Scott" <no-one@dont-mail-me.com> wrote in message
news:407137c5.1390772@news.provide.net...
> On Mon, 05 Apr 2004 07:08:59 GMT, "Chris Fogelklou"
> <chris.fogelklou@comhem.se> wrote:
>
> >Hi DSP People,
> >
> >Just a quick question...  is there really much difference between the
> >processing of a normal, complex FFT and a real-only FFT?  I thought there
> >wouldn't be...  The FFT/DFT math still requires that complex and
imaginary
> >parts of the FFT would be needed during the FFT processing, right?...
but
> >only the real part would be left at the end?.  This wouldn't necessarily
> >result in very much reduction in processing power, would it?
>
> No, if that's all you did.  But the real advantage of a real-only FFT
> is that there is a computational shortcut that makes an n point real
> FFT into an n-1 point complex FFT.  You start out by packaging the 2^n
> real points into the real and imaginary parts of an array of 2^(n-1)
> complex numbers.  Perform the usual complex FFT on this array.  Then
> there is a faily fast untangling step where that FFT is transformed
> into the complete FFT of the original 2^n sequence.

Hi Robert,

Thanks for the answer!  Is there a good source on the theory regarding this?
I did a quick google and only found implementations...

If you don't know, don't go out of the way... I could probably google it
myself if I gave it 15 minutes...  :)

Cheers,

Chris

Robert Scott wrote:
> On Mon, 05 Apr 2004 07:08:59 GMT, "Chris Fogelklou"
>>
>>Just a quick question...  is there really much difference between the
>>processing of a normal, complex FFT and a real-only FFT? 
> 
> No, if that's all you did.  But the real advantage of a real-only FFT
> is that there is a computational shortcut that makes an n point real
> FFT into an n-1 point complex FFT.  You start out by packaging the 2^n

I think you meant n/2, not n-1.  Otherwise, your explanation is great.

> real points into the real and imaginary parts of an array of 2^(n-1)
> complex numbers.  Perform the usual complex FFT on this array.  Then
> there is a faily fast untangling step where that FFT is transformed
> into the complete FFT of the original 2^n sequence.
> 
> -Robert Scott


There is code in KISS FFT to perform this processing.  The cost for the 
real fft is roughly half that of a complex fft of same length.

The final untangling step (BTW, I like that description) is fast and 
O(n), rather than O(n/2 log(n/2).  So it is not terribly significant at 
small n and it becomes even less significant as n gets larger.

Interestingly, FFTW can do odd-length real ffts using the discrete sine 
transform (DST).  I'm not really familiar with the method.  Perhaps 
Steven Johnson will chime in at this point.  He is one of the authors of 
fftw and is known to frequent comp.dsp.

-- Mark Borgerding

links:
www.fftw.org
-- fast, featureful, huge, GPL

sourceforge.net/projects/kissfft
-- half speed, half features, 2% size, BSD, fixed or float point

On Mon, 05 Apr 2004 13:00:31 GMT, Mark Borgerding
<mborgerding@cinci.rr.com> wrote:

>
>> No, if that's all you did.  But the real advantage of a real-only FFT
>> is that there is a computational shortcut that makes an n point real
>> FFT into an n-1 point complex FFT.  You start out by packaging the 2^n
>
>I think you meant n/2, not n-1.  Otherwise, your explanation is great.

Yes, thank you.  I was confusing the number of points and the log2 of
the number of points.  I should have said that a 2^n point real FFT
can be reduced to a 2^(n-1) point complex FFT.

-Robert Scott
 Ypsilanti, Michigan
(Reply through this forum, not by direct e-mail to me, as automatic reply address is fake.)

"Robert Scott" <no-one@dont-mail-me.com> wrote in message
news:407137c5.1390772@news.provide.net...

> No, if that's all you did.  But the real advantage of a real-only FFT
> is that there is a computational shortcut that makes an n point real
> FFT into an n-1 point complex FFT.  You start out by packaging the 2^n
> real points into the real and imaginary parts of an array of 2^(n-1)
> complex numbers.  Perform the usual complex FFT on this array.  Then
> there is a faily fast untangling step where that FFT is transformed
> into the complete FFT of the original 2^n sequence.

Yeah, but that takes more operations than computing the real-half-
complex DFT directly.  Also there is an advantage to computing
a full complex DFT by first executing separate real-half-complex
DFTs on the real and imaginary parts and then carrying out a
final step to combine these partial results to get a full-complex
DFT: 2-way SIMD is a no-brainer for this approach because you do
the same thing to the real an imaginary part except at the last
step; it's trickier for the classical complex arithmetic technique
because the complex multiplications involved are not necessarily
as well adapted to SIMD.  Doing a full-complex DFT via 2 intermediate
real-half-complex DFTs requires no more arithmetic operations than
doing a full complex DFT directly.

-- 
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end

Mark Borgerding <mborgerding@cinci.rr.com> wrote...
> The final untangling step (BTW, I like that description) is fast and 
> O(n), rather than O(n/2 log(n/2).  So it is not terribly significant at 
> small n and it becomes even less significant as n gets larger.

It depends on what you mean by "significant."  I just ran a check on
my 2.2GHz P-IV (Linux/gcc), and the untangling step in your kissfft
1.0.1 code takes from 26% (for n=16) to 5% (for 2^16) of your FFT
time.  If you compare to a more optimized code like FFTW, then your
untangling step takes longer than the whole real FFT in FFTW for small
n (<= 128) for which we have hard-coded transforms, and takes a good
30% of FFTW's time even for 2^16.

One problem is that it's an extra pass over the array, which is hard
on the registers for small sizes and on the cache for large sizes. 
Yes, eventually it becomes insignificant, because the FFT has log(n)
passes, but log(n) in practice may be only 3-4 even for quite large
sizes if a large radix is used.

Viewed another way, the standard untangling step is equivalent to a
radix-2 step, where the two sub-DFTs are performed by the
two-real-in-one-complex DFT trick, but radix-2 steps are often not
optimal on today's CPUs.  In principle, what you might want to do is
to combine the untangling step with a larger radix, but we haven't
tried implementing this yet.

> Interestingly, FFTW can do odd-length real ffts using the discrete sine 
> transform (DST).  I'm not really familiar with the method.  Perhaps 
> Steven Johnson will chime in at this point. 

Hmm, I never thought of our algorithm as using the DST; what gave you
that impression?  (We do implement DSTs and DCTs, on the other hand,
by expressing them in terms of real FFTs.)

We support real FFTs of both odd and even lengths essentially just by
implementing the ordinary Cooley-Tukey FFT algorithm, but eliminating
the redundant computations for real input and Hermitian output. 
Similar ideas were described e.g. by Bergland, Swartztrauber
(FFTPACK), and Sorensen in the past.

(In FFTW 3, we also added the option of the unscrambling trick for
even sizes, mainly so that we could take advantage of the SIMD support
in our complex FFTs, but also because with that approach it is
somewhat easier to obtain interleaved real/imaginary format output. 
The planner automatically decides which approach to use.)

Cordially,
Steven G. Johnson

PS. The original poster asked for explanatory material; you might
check out www.fftw.org/links.html for links to various explanations,
e.g. Numerical Recipes is readable online and has some introductory
discussion about real-data FFTs.

Steven G. Johnson wrote:
> Mark Borgerding <mborgerding@cinci.rr.com> wrote...
> 
>>The final untangling step (BTW, I like that description) is fast and 
>>O(n), rather than O(n/2 log(n/2).  So it is not terribly significant at 
>>small n and it becomes even less significant as n gets larger.
> 
> It depends on what you mean by "significant."  I just ran a check on
> my 2.2GHz P-IV (Linux/gcc), and the untangling step in your kissfft
> 1.0.1 code takes from 26% (for n=16) to 5% (for 2^16) of your FFT
> time.  

Significant: adj. Having importance measured by a relative difference of 
27% or more.

Steven, sometimes I think you spend more time looking at my code than I. 
  Yes, that must be it (geek rationalization functioning within nominal 
parameters).

You are certainly keeping me honest.  I was posting from memory, and I 
don't recall even testing speed at sizes that small.  I suppose it is a 
symptom of the way I have used ffts; I consider 256 a small fft.

I would not increase the complexity of KISSFFT for any speed gain so 
paltry as 26%.  Thus, FFTW's reign as the speed king of open source FFTs 
is certainly unthreatened by KISSFFT.

I doubt you and Matteo are willing to implement fixed point processing, 
change licenses, or discard ninety-some percent of fftw's code to make 
it easier to understand/modify.

So FFTW seems equally unlikely to encroach on KISSFFT's niche.

<insert Biology metaphor here>

I am quick to recommend FFTW to those who can use it, and happy to 
present an alternative to those who cannot.

BTW, if you ever find yourself in Cincinnati, I'd be honored to buy you 
dinner to thank you for your great work.

>>Interestingly, FFTW can do odd-length real ffts using the discrete sine 
>>transform (DST).  I'm not really familiar with the method.  Perhaps 
>>Steven Johnson will chime in at this point. 
> 
> Hmm, I never thought of our algorithm as using the DST; what gave you
> that impression?  (We do implement DSTs and DCTs, on the other hand,
> by expressing them in terms of real FFTs.)

I think I got the notion from the fftw docs "What FFTW Really Computes", 
section 4.7.4 "1d Real-odd DFTs (DSTs)"


-- Mark Borgerding

Mark Borgerding <mark@borgerding.net> wrote...
> I would not increase the complexity of KISSFFT for any speed gain so 
> paltry as 26%.  Thus, FFTW's reign as the speed king of open source FFTs 
> is certainly unthreatened by KISSFFT.

Hi Mark,

I wasn't suggesting that you should; we recognize and applaud the
design goals of kissfft, and don't hesitate to recommend it when it's
appropriate.

I just wanted to make the discussion of the speed penalty more
quantitative, and also to point out that the speed penalty is more
substantial for a more heavily optimized code.  Similar comments apply
to e.g. separate bit-reversal stages.

> I think I got the notion [that FFTW computes odd-size real-data DFTs using
> DSTs] from the fftw docs "What FFTW Really Computes", section 4.7.4
> "1d Real-odd DFTs (DSTs)"

Ah, I see; yes, we meant "odd-symmetry data", not "odd-size DFT"
there.  We wanted to emphasize that DCTs and DSTs are simply special
cases of the DFT; I'll see if I can make this clearer in the manual.

(Actually, the ordinary types I-IV DCTs and DSTs all correspond to
real-data DFTs whose "logical size" is even.  Odd-size DFTs of real
even/odd data correspond to types V-VIII DCTs/DSTs, which seem rarely
used.)

Steven