Re: FFT test with few kbits

From: Eric Backus (eric_backus_at_alum.mit.edu)
Date: 01/31/04 

Date: Fri, 30 Jan 2004 18:55:17 -0800

"Cristiano" <cristiano.pi@NSquipo.it> wrote in message
news:6xASb.169284$VW.6887419@news3.tin.it...
> "Eric Backus" <eric_backus@alum.mit.edu> ha scritto nel messaggio
> news:1075493567.723814@cswreg.cos.agilent.com
> > "Cristiano" <cristiano.pi@NSquipo.it> wrote in message
> > news:e2xSb.168273$VW.6834917@news3.tin.it...
> >> I think the easiest way to see what I'm doing is to transform this
> >> 20-bit sequence
> >> 01101110011110111110
> >>
> >> to see if you get (real and imaginary components):
> >> 14 0
> >> -0.554254269627734 1.08778525229247
> >> -1.19098300562505 -0.587785252292473
> >> -2.84785876296257 0.45105651629515
> >> 1.92705098312484 -2.1266270208801
> >> -2 -2
> >> -2.30901699437494 -0.951056516295152
> >> 0.229824774212685 -1.45105651629515
> >> -1.42705098312484 1.31432778029783
> >> 0.172288258377629 -0.0877852522924755
> >>
> >> Obviously I discard the second half (from n/2 to n-1) because it is
> >> identical to the first half.
> >
> > For what it's worth, I can verify that this really is the first half
> > of the FFT of the 20-bit sequence you gave.
>
> Thank you for the checking.
>
> > You'll notice that the very first component really is much bigger
> > than the rest, reflecting Ernst Lippe's observation that it should
> > average to N/2 while the rest should average to zero.
>
> Why? I agree that the first term should be about N/2 (because it is the
> numbers of 1's), but the mean of the rest (terms from 1 to N/2) is 0.5
> or -0.5 for the real components.

I don't see where you're getting that. For your example above, the mean of
the real part of the rest is -0.888888888888. If you do this many times
with different random data, the expected value of the values other than the
first is zero. If you include the first value, the expected value of
everything is 1 (basicly N/2 from the first point, plus zero for each other
point, divided by N/2 which is the number of points you're averaging).

> The mean of the imaginary part varies from about -1.14 to 1.23.
> You seem able to calculate the FFT; have you checked what you've said?

Yes.

> > When you throw away the second half of the data, you can actually
> > keep the n/2 value, so you throw away only (n/2)-1 complex values.
> > The n/2 value will be real-only, just like the first value, but this
> > value is equally useful and testable and as independent as the rest
> > of the values.
>
> I'm not sure to understand exactly what you said.

You start with 20 real values. The output of the DFT is 20 complex values.
The first of these (#0) is real-only. The following 9 (#1 through #9) are
complex. The next value (#10) is real-only. The last 9 (#11 through #19)
are complex. The last 9 complex values (#11 through #19) are an image of
(#1 through #9). So you can keep the first eleven complex values out of the
20. Of those eleven values, the first and last will be real-only.

> > For the values that have non-zero imaginary parts, you should be able
> > to test that they have the same gaussian distribution as the real
> > part.
>
> Yes both components seem to be normally distributed. Here, a mathematical
> explanation would be very useful...

I'm only going to hand-wave here, so it may not be too helpful. Each output
of the DFT is a weighted sum of N random inputs. Even though the N random
inputs are binary valued, something like the central limit theorem says that
the resulting sum will approach being Gaussian distributed. For each
complex output of the DFT, I believe the distribution is Gaussian in
Magnitude squared (sorry I'm having trouble remembering the details now). I
believe that the real and imaginary parts are not independent of each other,
but each looks roughly Gaussian. For each complex output of the DFT, the
phase should be uniform between +-pi.

> As I said in my first post, the KS test over the real part gives good
> p-values, and the same happens for the imaginary part. These p-values
should
> be uniformly distributed, but unfortunately it doesn't happen.
> The KS test over the p-values gotten from the 1st level KS test is bad for
t
> he real part, but incredibly bad for the imaginary part.
> For this reason I used the real part.

If you're including the first point, which has a much larger real part and
exactly zero imaginary part, that might cause problems? I guess I don't
really know what the problem might be here. 

-- 
Eric Backus
R&D Design Engineer
Agilent Technologies, Inc.
425-356-6010 Tel

Relevant Pages

  • Re: FFT test with few kbits
    ... > output of the DFT is a weighted sum of N random inputs. ... For each complex output of the DFT, ... > the distribution is Gaussian in Magnitude squared (sorry I'm having ...
    (sci.crypt)
  • Re: Fourier Derivation of Heisenberg Uncertainty is Nonsense
    ... by taking the Fourier transform of the Gauss distribution ... Gaussian distribution in mathematical probability-statistics is like ... optimality, Gaussian/Normal and other graph-symmetric real line ... Dimitriyev gives a second alternative derivation of the Heisenberg ...
    (sci.physics)
  • Re: Random delay as a countermeasure to timing attacks
    ... - the signal has a Gaussian distribution, ... the noise ... random queries, or queries chosen according to the cipher, or ...
    (sci.crypt)
  • Fourier Derivation of Heisenberg Uncertainty is Nonsense
    ... by taking the Fourier transform of the Gauss distribution ... Gaussian distribution in mathematical probability-statistics is like ... optimality, Gaussian/Normal and other graph-symmetric real line ... Dimitriyev gives a second alternative derivation of the Heisenberg ...
    (sci.physics)
  • Re: prior distributions of estimated parameters
    ... >> distribution here based on the width of the error bar. ... >> the error bars represent an absolute limit, ... Gaussian distribution, or rather you describe your knowledge of the data ... coupled with a prior distribution for the parameters P- which I ...
    (sci.stat.math)