Re: FFT test with few kbits

From: Cristiano (cristiano.pi_at_NSquipo.it)
Date: 02/18/04 

Date: Wed, 18 Feb 2004 21:38:01 GMT

Ernst Lippe wrote:
> On Tue, 17 Feb 2004 22:06:25 +0000, Cristiano wrote:
>
>> Ernst Lippe wrote:
>>> On Fri, 06 Feb 2004 16:42:33 +0000, Cristiano wrote:
>>>
>>>> Ernst Lippe wrote:
>>>>> On Thu, 05 Feb 2004 17:49:29 +0000, Cristiano wrote:
>>>>>
>>>>>> Ernst Lippe wrote:
>>>>>>> On Tue, 03 Feb 2004 20:05:15 +0000, Cristiano wrote:
>>>>>>>
>>>>>>>> Ernst Lippe wrote:
>>>>>>>>> On Fri, 30 Jan 2004 18:06:02 +0000, Cristiano wrote:
>>>>>>>>>
>>>>>>>>>> "Ernst Lippe" <ernstl-at-planet-dot-nl@ignore.this> ha
>>>>>>>>>> scritto nel
>>>>>>>>> So, I am afraid that I can't see why you expect that the mean
>>>>>>>>> is different from zero.
>>>>>>>>>
>>>>>>>>> Let's take a very simple example, the real value of Fourier
>>>>>>>>> component F_1 on a sample of 4 bits, that should be equal to
>>>>>>>>> the value of x_0 - x_2. Now when you calculate the possible
>>>>>>>>> values for all 16 possible 4 bit sequences, you should find
>>>>>>>>> that in 4 cases the value
>>>>>>>>> is +1, in 4 cases the value is -1 and in the remaining 8 cases
>>>>>>>>> the value is zero. So obviously the average is also zero
>>>>>>>>> because all 16 sequences are equally probable.
>>>>>>>>
>>>>>>>> Perhaps now I know where is the misunderstanding: I've never
>>>>>>>> said that the first component is F_0. I discard it. Then I
>>>>>>>> consider N/2-1 components from F_1 to F_N/2.
>>>>>>>
>>>>>>> F_1 is the first Fourier component that you are also using,
>>>>>>> and I believe that I have shown that it has a mean of zero
>>>>>>> for 4 bit inputs.
>>>>>>> Why don't you just do the calculations and compute the
>>>>>>> mean for each Fourier component over all 16 possible 4 bit
>>>>>>> inputs. If you have a different mean, please give a concrete
>>>>>>> example,
>>>>>>> so we can discover where our differences are.
>>>>>>
>>>>>> I get exactly what you say. I also checked that the real part of
>>>>>> F_1 is equal to the value of x_0 - x_2.
>>>>>> But why do you ask me that? In other words, I don't understand
>>>>>> what that has to do with "my" mean equal to +/-0.5.
>>>>>
>>>>> Then perhaps the problem is just the definition of mean. When I
>>>>> do an FFT on n-bits, there are 2^n different possible inputs. Now
>>>>> because we assumed that these bits are unbiased each of these
>>>>> possibilities are equally likely. Now for each Fourier coefficient
>>>>> F_k, I can compute the mean expected value for F_k by simply
>>>>> taking the average value of F_k over all 2^n possible inputs.
>>>>> This is what I would call the average value of F_k. Now like I
>>>>> said for all k > 0 it expect the average value of F_k to be zero.
>>>>> So I don't understand what "mean" you are using.
>>>>
>>>> That seems a strange mean. :-)
>>>> If there are N components I think the mean is ( F_1 + ... + F_(N/2)
>>>> ) / (N/2). I needed that mean to normalize the components, but, as
>>>> I said, in the new version I normalize the components using F_i /
>>>> Expected_StdDev.
>>>
>>> As you probably might have noticed there is something strange
>>> with your "mean". You can write it as the sum for k = 1 to N-1
>>> of c_k * x_k, where c_0 = 1/2 N, and for all k > 0: c_k = -1
>>> when k is odd, and c_k = 0 when k is even.
>>> In other words your "mean" depends mostly on the value of
>>> the first input bit (x_0) and is not influenced by all
>>> other even-numbered bits.
>
> I made two errors here. First, k should go from 0 to N-1.
> Second, I forgot to divide by N/2, my formula was for the
> sum of the components, which you divide by N/2 to get your
> "mean".
>
>
>>
>> If I calculate c_k for k = 1 to N/2 (N=16384) when k is odd I can
>> get: -8192, 0 or 8192; when k is even I get anything from -8191 to
>> 8191 (always integer numbers).
>> I have a question: is not easier to calculate the mean for a
>> practical case? It seems really incredible that we don't get the
>> same mean!
>
>
> Strange. Start with some simple cases. Obviously, c_k is
> equal to the sum of the Fourier components F_1 to F_(N/2)
> with an input where x_k is equal to 1 while the other
> bits are 0.
>
> A few results:
> 10000000 Sum = 4
> 01000000 Sum = -1
> 00100000 Sum = 0

Good, I get the same results.

Now, I think it's time to do a real example:

1) generate an N-bit sequence (N=10)

1100001010

2) transform the sequence of 0's and 1's using the FFT

i real imaginary
0 4.000000000000 0.000000000000
1 1.309016994375 0.951056516295
2 0.809016994375 -1.314327780298
3 0.190983005625 -0.587785252292
4 -0.309016994375 -2.126627020880
5 2.000000000000 0.000000000000

3) discard the first value

i real imaginary
1 1.309016994375 0.951056516295
2 0.809016994375 -1.314327780298
3 0.190983005625 -0.587785252292
4 -0.309016994375 -2.126627020880
5 2.000000000000 0.000000000000

The mean of the real components from F_1 to F_(N/2) is 0.8.
The mean of the imaginary components from F_1 to F_(N/2) is -0.615536707.

If you generate many bits, for example 10000, you should get the mean of the
real components from F_1 to F_(N/2) equal to + or - 0.5.

Cristiano

Relevant Pages
Quantcast