On Wednesday, March 1, 2017 at 12:32:42 AM UTC-8, Christian Gollwitzer wrot=
e:
> Am 28.02.17 um 21:45 schrieb dbd:
> > performing DCTs
> > instead of DFTs to avoid the costs of packing and unpacking passes.
>=20
> I think the DCT vs DFT issue is not about the cost of packing/unpacking.=
=20
> DCT assumes a different boundary condition...
That is one one the differences between some applications with real data fr=
om some applications with complex data. My point was that users with DCT ap=
plications should look to DCT specific literature for efficient implementat=
ions rather that to literature on how to pack DCTs into architectures optim=
ized for complex data to avoid the costs of unnecessary packing and unpacki=
ng. and achieve higher efficiency.
Dale B. Dalrymple
Reply by ●March 1, 20172017-03-01
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
Reply by rickman●March 1, 20172017-03-01
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
Reply by Christian Gollwitzer●March 1, 20172017-03-01
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
Reply by Eric●March 1, 20172017-03-01
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)
Reply by Eric●March 1, 20172017-03-01
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?
Reply by rickman●February 28, 20172017-02-28
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
Reply by ●February 28, 20172017-02-28
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
Reply by dbd●February 28, 20172017-02-28
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
Reply by ●February 28, 20172017-02-28
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.
>