|
From: | Maximilian Stiefel |
Subject: | Re: [Discuss-gnuradio] Floating point FFT usage - suppress half of it? |
Date: | Sun, 18 Mar 2018 16:09:48 +0100 |
User-agent: | Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.6.0 |
Hi Brad, Hi Marcus, @ Brad: The basic properties of the Fourier transform give you this symmetry.In general the Fourier transform has the following property, usually refered to as conjungation:
F{ x*(t) } = X*(-jw). For purely real input signals, this boils down to Xr(jw) = Xr(-jw) (even) and Xi(jw) = -Xi(-jw) (odd). ^ ^ real part imaginary part of the Fourier transform For purely imaginary input signals, it boils down to Xr(jw) = -Xr(-jw) (odd) and Xi(jw) = Xi(-jw) (even). ^ ^ real part imaginary part of the Fourier transformHence, you will always get a symmetric spectrum for a purely real or purely imaginary input, since purely real or purely imaginary signals need two frequencies (a positive and a negative one) to cancel out the imaginary part or the real part respectively (http://whiteboard.ping.se/SDR/IQ).
Think e.g. about a real cosine (even); it's Fourier transform will be real and even (two positive diracs at -w0 and w0). If you have a real sine (odd), the Fourier transform will be imaginary and odd (a positive dirac at w0 and a negative dirac at -w0).
If you think about a complex signal instead e.g. x(t) = A * e^{jw0t}. This will not yield a symmetric spectrum (one dirac at w0).
Thus, you can not really discard the negative frequencies if you want to be able to go back to time domain, but you can predict, what they are going to be. If you do an IFFT with the positive frequencies only, you will get rubbish at the output. You do not really waste CPU time if you calculate the full spectrum as it is just natural to obtain a result from the FFT which spans from -fs to fs (assuming you are sampling complex with fs). The negative frequencies are simply a part of a purely real signal, that you have in your case.
@ Marcus: The FFTW lib probably still needs to compute the negative bins, right?
As I understood it, correct me if I am wrong, you have to change physics to get around the negative frequencies to be calculated. Indeed, it is an interesting question, though.
Regards, Max On 2018-03-18 15:17, Müller, Marcus (CEL) wrote:
Hi Brad,Put another way, is it safe to discard the left side of the output as it appears to consist only of aliases of the true data?Well, it does not contain information that's not in the other side (it's not really an alias, though, but the conjugate mirror of the other side).best way to recover the useful information from the FFTWhat's the thing you want to achieve? Because "useful" and "best" are meaningless without knowing what you want to do! :) Regarding the numerical inefficiency of computing both sides of something symmetric: The FFTW, the library used to actually compute these DFTs, does come with an effort-reduced FFT for real-valued input data, which will also only output one side of the spectrum. The savings in CPU cycles are usually relatively modest (because the non-hermitian FFT is already very optimized, and leaving out the results stage doesn't simply go and half the effort) – the main advantage would, in practice, probably be reduced memory bandwidth. But: audio sample rates on modern CPUs with FFTs of benign length might not really be what you should worry about computationally, I'd guess. What is the computational bottleneck you need to widen? Best regards, Marcus On Sun, 2018-03-18 at 09:29 -0400, Brad Hein wrote:Frequency domain output of the FFT block seems to be mirrored when using floating point data type. I recall that when using complex numbers this mirroring doesn't occur. The input I'm working with is 48khz sound from a wav file. I understand this mirroring is a characteristic of the Fourier transform, but what I'm wondering is what is the best way to recover the useful information from the FFT I tried marshaling the data into complex data before feeding it into the FFT but I couldn't get a reliable process. If discarding half of the FFT output is the way to go then what about the wasted CPU in calculating that half of the frequency domain - is there a better way to recover the useful frequency domain information? Thanks! _______________________________________________ Discuss-gnuradio mailing list address@hidden https://lists.gnu.org/mailman/listinfo/discuss-gnuradio _______________________________________________ Discuss-gnuradio mailing list address@hidden https://lists.gnu.org/mailman/listinfo/discuss-gnuradio
[Prev in Thread] | Current Thread | [Next in Thread] |