[time-nuts] Re: Simple simulation model for an OCXO?

[Carsten Andrich]

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