Recent thread on RFFT

I read through part of the recent thread on FFT's for FPGAs.
Interestng comments on optimization.  Is the real vs complex issue
covered in any notable texts?  I would not have thought that it would
afford any significant advantage in runtime.

I'm not so interested in FPGAs.as in whether there are methods that
are generally accepted as close to optimal for a -windowed- FFT/STFT,
assuming that input data is real, not complex.  Any examples out there
in C/C++ (preferrably with a selection of windowing methods)?  My
texts (Embree, etc) are relatively old, and probably not highly
optimized to begin with.
 

On Tue, 28 Feb 2017 17:05:00 -0500, Eric <Eric@spamspamorspam.com>
wrote:

>I read through part of the recent thread on FFT's for FPGAs.
>Interestng comments on optimization.  Is the real vs complex issue
>covered in any notable texts?  I would not have thought that it would
>afford any significant advantage in runtime.
>
>I'm not so interested in FPGAs.as in whether there are methods that
>are generally accepted as close to optimal for a -windowed- FFT/STFT,
>assuming that input data is real, not complex.  Any examples out there
>in C/C++ (preferrably with a selection of windowing methods)?  My
>texts (Embree, etc) are relatively old, and probably not highly
>optimized to begin with.
> 

One point of view is that all FFTs are windowed (with at least a
rectangular window), and the real-valued input condition just exploits
one of the symmetry conditions of the DFT.

Just searching on "real-valued FFT" gives some good resources,
including two from TI:

http://www.ti.com/lit/an/spra291/spra291.pdf

http://processors.wiki.ti.com/index.php/Efficient_FFT_Computation_of_Real_Input

and a book chapter that is decent:

http://dsp-book.narod.ru/FFTBB/0270_PDF_C14.pdf

The book chapter also has a good Notes and References section at the
end.

Also, Rick Lyon's book(s) cover real-symmetry for DFTs.



---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

Eric

A lot of discussion on comp.dsp involves fitting real data into the complex DFTs that we need to perform in many communication systems anyway (and may have optimized architectures for). In audio and image compression systems there may be only real data so there has been an emphasis on performing real data transforms directly, performing DCTs instead of DFTs to avoid the costs of packing and unpacking passes. That literature has more efficient algorithms developed bottom-up for real data.

Dale B. Dalrymple

On Tue, 28 Feb 2017 12:45:28 -0800 (PST), dbd
<d.dalrymple@sbcglobal.net> wrote:

>Eric
>
>A lot of discussion on comp.dsp involves fitting real data into the complex=
> DFTs that we need to perform in many communication systems anyway (and may=
> have optimized architectures for). In audio and image compression systems =
>there may be only real data so there has been an emphasis on performing rea=
>l data transforms directly, performing DCTs instead of DFTs to avoid the co=
>sts of packing and unpacking passes. That literature has more efficient alg=
>orithms developed bottom-up for real data.
>
>Dale B. Dalrymple

Hartley transforms are very useful there, too.



---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

On 2/28/2017 1:08 PM, eric.jacobsen@ieee.org wrote:
> On Tue, 28 Feb 2017 17:05:00 -0500, Eric <Eric@spamspamorspam.com>
> wrote:
>
>> I read through part of the recent thread on FFT's for FPGAs.
>> Interestng comments on optimization.  Is the real vs complex issue
>> covered in any notable texts?  I would not have thought that it would
>> afford any significant advantage in runtime.
>>
>> I'm not so interested in FPGAs.as in whether there are methods that
>> are generally accepted as close to optimal for a -windowed- FFT/STFT,
>> assuming that input data is real, not complex.  Any examples out there
>> in C/C++ (preferrably with a selection of windowing methods)?  My
>> texts (Embree, etc) are relatively old, and probably not highly
>> optimized to begin with.
>>
>
> One point of view is that all FFTs are windowed (with at least a
> rectangular window), and the real-valued input condition just exploits
> one of the symmetry conditions of the DFT.
>
> Just searching on "real-valued FFT" gives some good resources,
> including two from TI:
>
> http://www.ti.com/lit/an/spra291/spra291.pdf
>
> http://processors.wiki.ti.com/index.php/Efficient_FFT_Computation_of_Real_Input
>
> and a book chapter that is decent:
>
> http://dsp-book.narod.ru/FFTBB/0270_PDF_C14.pdf
>
> The book chapter also has a good Notes and References section at the
> end.

Is this file available elsewhere?  My anit-virus program doesn't allow 
access.

Access has been blocked as the threat Mal/HTMLGen-A has been found on 
this website.

-- 

Rick C

On Tue, 28 Feb 2017 18:08:10 GMT, eric.jacobsen@ieee.org wrote:

>On Tue, 28 Feb 2017 17:05:00 -0500, Eric <Eric@spamspamorspam.com>
>wrote:

>>I'm not so interested in FPGAs.as in whether there are methods that
>>are generally accepted as close to optimal for a -windowed- FFT/STFT,

>One point of view is that all FFTs are windowed (with at least a
>rectangular window), and the real-valued input condition just exploits
>one of the symmetry conditions of the DFT.

So it's best not to take that negative and positive infinity bounds
literally then?  No wonder my memory allocation was blowing up! :-)
Seriously, that was one of those minor WTFs when I started reading
books on DSP. 

>Just searching on "real-valued FFT" gives some good resources,
>including two from TI:
...
>Also, Rick Lyon's book(s) cover real-symmetry for DFTs.

Thanks for the links (including a surprisingly long paper from TI)

So there is a quantifiable advantage in RFFTs then...hmmm.
I thought that all the real values would end up complex on their first
encounter with e^j, so I was skeptical about the runtime advantage.

Is most of the standard 'book code' close to optimal these days, or
are there repositories with more optimized C/C++ code?

On Tue, 28 Feb 2017 12:45:28 -0800 (PST), dbd
<d.dalrymple@sbcglobal.net> wrote:

>Eric
>
> In audio and image compression systems there may be only real data 

I was trying to think of where that would -not- be the case.  Perhaps
when data is coming from another algorithm whose output is complex.
But where would complex data be encountered outside that?

And given that, why are real-only FFTs not encountered more often?
(Inquiring minds, and all that)

Am 28.02.17 um 21:45 schrieb dbd:
> performing DCTs
> instead of DFTs to avoid the costs of packing and unpacking passes.

I think the DCT vs DFT issue is not about the cost of packing/unpacking. 
DCT assumes a different boundary condition, whereas DFT assumes that the 
same packet repeats - which gives discontinuities if the leftmost and 
rightmost sample are different - the DCT assumes a mirrored symmetry. 
This results in a continuous function and much less ringing artifacts.

	Christian

On 3/1/2017 7:13 AM, Eric wrote:
> On Tue, 28 Feb 2017 12:45:28 -0800 (PST), dbd
> <d.dalrymple@sbcglobal.net> wrote:
>
>> Eric
>>
>> In audio and image compression systems there may be only real data
>
> I was trying to think of where that would -not- be the case.  Perhaps
> when data is coming from another algorithm whose output is complex.
> But where would complex data be encountered outside that?
>
> And given that, why are real-only FFTs not encountered more often?
> (Inquiring minds, and all that)

In communications it is common to mix signals to baseband with 
quadrature mixers.  Dual ADCs provide real and imaginary digital inputs 
for complex plane computations.

-- 

Rick C

On Wed, 01 Mar 2017 07:13:43 -0500, Eric <Eric@spamspamorspam.com>
wrote:

>On Tue, 28 Feb 2017 12:45:28 -0800 (PST), dbd
><d.dalrymple@sbcglobal.net> wrote:
>
>>Eric
>>
>> In audio and image compression systems there may be only real data 
>
>I was trying to think of where that would -not- be the case.  Perhaps
>when data is coming from another algorithm whose output is complex.
>But where would complex data be encountered outside that?

Many, many applications mix the signal of interest to baseband so that
it is complex-valued at the time of sampling.   This includes
communications, radar, sonar, and many medical imaging applications
like ultrasound, MRI, etc.

Mixing the signal to baseband allows the use of complex-valued
processing and algorithms that are net more efficient in computational
complexity.

>And given that, why are real-only FFTs not encountered more often?
>(Inquiring minds, and all that)

They're around plenty.   They just don't need to be re-invented very
often, and implementation is cheap enough these days that many times
people just use a complex-valued FFT input with the imaginary part set
to zero and it gets the job done.



---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus