Hi Magnus,
On 15.05.22 19:37, Magnus Danielson via time-nuts wrote:
This is a result of using real-only values in the complex Fourier
transform. It creates mirror images. Greenhall uses one method to
circumvent the issue.
Can't quite follow on that one. What do you mean by "mirror images"?
Do you mean that my formula for X[k] is missing the complex
conjugates for k = N/2+1 ... N-1? Used with a regular, complex IFFT
the previously posted formula for X[k] would obviously generate
complex output, which is wrong. I missed that one, because my
implementation uses a complex-to-real IFFT, which has the complex
conjugate implied. However, for a the regular, complex (I)FFT given
by my derivation, the correct formula for X[k] should be the following:
{ N^0.5 * \sigma * N(0, 1) , k = 0, N/2
X[k] = { (N/2)^0.5 * \sigma * (N(0, 1) + 1j * N(0, 1)), k = 1 ... N/2
- 1
{ conj(X[N-k]) , k = N/2 + 1
... N - 1
If you process a real-value only sample list by the complex FFT, as
you did, you will have mirror fourier frequencies of opposite sign.
This comes as e^(i*2*pi*f*t)+e^(-i*2*pi*f*t) is only real.
I'm familiar with the hermitian symmetry properties of the Fourier
transform, just wasn't entirely sure that's what you were referring to.
Rather than using the optimization to remove half unused inputs
(imaginary) and half unused outputs (negative frequencies) with N/2
size transform, you can use the N-size transform more straightforward
and accept the losses for simplicity of clarity.
I agree that deriving for the regular, complex-to-complex DFT is best
regarding generality and clarity from a theoretical point of view.
However, from a practical standpoint, the complex-to-real IDFT/IFFT is
just a minor optimization with the hermitian symmetry of the spectrum
hard wired into the transform. It's an N-point (not N/2) IFFT that is
analytically -- not numerically, due to limited precision -- identical
to a fully-complex N-point IFFT of data with hermitian symmetry.
Practically, it halves memory usage and computational complexity [2].
When using common numeric packages like Matlab or NumPy, peak memory
usage may even be cut down to one third by obviating the extra copy of
the real values implied by "dropping" the imaginary component of a
regular IFFT's complex output.
IMHO, the minor head scratching involved in using a complex-to-real IFFT
(N/2+1 vs. N input samples) is well worth the computational advantage,
because the two implementation differences are minor and actually reduce
implementation complexity slightly:
1. The complex conjugate required for hermitian symmetry of the IFFT
input does not have to be explicitly computed, but is implied by the
transform.
2. The IFFT's output is already real, so explicitly dropping the
imaginary component is not required.
This is why Greenhall only use upper half frequencies.
Could you elaborate on that? Greenhall uses all 2N frequency-domain
samples of his 2N DFT [1]:
Let Z_k = √(S_k/2) (Uk + iV_k), Z_{2N-k} = Z*_k for k = 1 to N-1
Thanks and best regards,
Carsten
[1] https://apps.dtic.mil/sti/pdfs/ADA485683.pdf#page=5
[2]
https://www.fftw.org/fftw3_doc/One_002dDimensional-DFTs-of-Real-Data.html
--
M.Sc. Carsten Andrich
Technische Universität Ilmenau
Fachgebiet Elektronische Messtechnik und Signalverarbeitung (EMS)
Helmholtzplatz 2
98693 Ilmenau
T +49 3677 69-4269
_______________________________________________
time-nuts mailing list -- time-nuts@lists.febo.com
To unsubscribe send an email to time-nuts-le...@lists.febo.com
