Re: FFT test with few kbits
From: Cristiano (cristiano.pi_at_NSquipo.it)
Date: 01/30/04
- Next message: Cristiano: "Re: FFT test with few kbits"
- Previous message: Foo Bar: "Re: Is this simple scheme secure?"
- In reply to: Eric Backus: "Re: FFT test with few kbits"
- Next in thread: Eric Backus: "Re: FFT test with few kbits"
- Reply: Eric Backus: "Re: FFT test with few kbits"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Fri, 30 Jan 2004 22:03:46 GMT
"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...
>> "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.
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.
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?
> You'll also notice that the imaginary part of the first component is
identically
> zero, while the rest are not.
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.
> 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...
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.
Cristiano
- Next message: Cristiano: "Re: FFT test with few kbits"
- Previous message: Foo Bar: "Re: Is this simple scheme secure?"
- In reply to: Eric Backus: "Re: FFT test with few kbits"
- Next in thread: Eric Backus: "Re: FFT test with few kbits"
- Reply: Eric Backus: "Re: FFT test with few kbits"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
