Re: FFT test with few kbits
From: Eric Backus (eric_backus_at_alum.mit.edu)
Date: 01/30/04
- Next message: NYC: "Is this simple scheme secure?"
- Previous message: lcs Mixmaster Remailer: "Re: LEN SASSAMAN: WHERE DID YOU LEARN HOW TO LIE WITH SUCH A BALD FACE"
- In reply to: Cristiano: "Re: FFT test with few kbits"
- Next in thread: Cristiano: "Re: FFT test with few kbits"
- Reply: Cristiano: "Re: FFT test with few kbits"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Fri, 30 Jan 2004 12:09:48 -0800
"Cristiano" <cristiano.pi@NSquipo.it> wrote in message
news:e2xSb.168273$VW.6834917@news3.tin.it...
> "Ernst Lippe" <ernstl-at-planet-dot-nl@ignore.this> ha scritto nel
> messaggio news:401a7015$0$13793$ba620dc5@nova.planet.nl
> > On Thu, 29 Jan 2004 20:42:53 +0000, Cristiano wrote:
> >
> >> Ernst Lippe wrote:
> >>> On Thu, 29 Jan 2004 10:21:25 +0000, Cristiano wrote:
> >>>
> >>>> My test uses the real part and the phase of the tranformed bits.
> >>>> If the sequence is good, the real part follows a normal
> >>>> distribution with |mean| = 0.5 and standard deviation =
> >>>> 0.3535158*sqrt(n);
> >>>
> >>> How did you get these results?
> >>> I would expect that the mean of the first component is N/2,
> >>> while the mean of the other components is equal to zero.
> > As I wrote, the first Fourier component has a different mean.
> >
> > Some notation: we have N differents bits x_0,x_1,...,x_N-1, that
> > are independently and uniformly distributed.
> > After the transformation we have N Fourier components F_k.
> > The Fourier components are computed by the following formula:
> > F_k = sum_m=0^N-1 x_m * exp(- 2 pi i m k / N)
> >
> > Now if we want to compute the mean (or the expected value) of F_k
> > it is easy to see that in 50% of the cases x_m will be zero, and
> > in 50% of the cases it will be equal to one. So the expected value
> > for F_k is
> > 1/2 * sum_m=0^N-1 exp(- 2 pi i m k / N)
> >
> > When k = 0 the expected value is N/2, for the values of k in the
> > range [1,N-1] the expected value is zero.
>
> 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.
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. You'll also notice that the
imaginary part of the first component is identically zero, while the rest
are not.
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.
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.
-- Eric Backus R&D Design Engineer Agilent Technologies, Inc. 425-356-6010 Tel
- Next message: NYC: "Is this simple scheme secure?"
- Previous message: lcs Mixmaster Remailer: "Re: LEN SASSAMAN: WHERE DID YOU LEARN HOW TO LIE WITH SUCH A BALD FACE"
- In reply to: Cristiano: "Re: FFT test with few kbits"
- Next in thread: Cristiano: "Re: FFT test with few kbits"
- Reply: Cristiano: "Re: FFT test with few kbits"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
