-1
$\begingroup$

Suppose we get $m+1$-bit signed noise samples $n_i$ with magnitude of noise as high as $m$ bits.

  • Does averaging say $m\log m$ samples suffice to get average of $n_i$ to magnitude within few LSBs?
  • How many samples do we need?

This is a purely theoretical question.

My noise samples are independent with magnitude uniformly distributed and sign equidistributed.

  1. Assume magnitude of noise is uniform in range $(2^{m−1},2^{m}−1)$.
  2. Also assume your working precision is very large say of $2^{2^{2^m}}$ bits so you never run into precision problems.
$\endgroup$
  • $\begingroup$ Unsure of "n+1-bit signed samples". You mean you have quantity n samples that are each a signed 1 bit? Or you have quantity n+1 sample that are "bit signed" (whatever that means)? $\endgroup$ – Daniel Kiracofe Jan 8 '17 at 23:54
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Peter K. Jan 9 '17 at 15:37
1
$\begingroup$

Look at the plot below. It generates noise according to the distribution you mentioned, and averages it (with different numbers of measurements). What is shown is the histogram of the obtained averaged noise values. As you can see, the more you average, the more the noise goes to the center. However, for $m \log m$ measurements, the noise has still significant contributions up to $2^{m-2}$, I dont know, if you would consider these the LSB. If you average more, you can get the gross of noise samples close to zero.

However, note that the minimum and maximum possible values of the averaged noise are still $\pm2^m-1$, which happens when all noise realizations are the maximum (which becomes more and more unlikely, when you have many measurements).

m = 16;
def getnoise(realizations, measurements):
    lowest = 2**(m-1)
    highest = 2**m - 1
    width = highest - lowest
    shape = (realizations, measurements)
    sign = (1-2*(np.random.randn(*shape)>0).astype(float))
    value = np.random.uniform(lowest, highest, size=shape)

    return sign * value

N = 10000
plt.hist(getnoise(realizations=N, measurements=1), bins=50, label='noise distribution');
plt.hist(np.mean(getnoise(realizations=N, measurements=2), axis=1), bins=50, label="2 average");
plt.hist(np.mean(getnoise(realizations=N, measurements=3), axis=1), bins=50, label="3 average");
plt.hist(np.mean(getnoise(realizations=N, measurements=int(m*np.log2(m))), axis=1), bins=50, label="mlogm average");
plt.hist(np.mean(getnoise(realizations=N, measurements=1000), axis=1), bins=50, label="1000 average");
plt.legend();

enter image description here

Some analytic result: Actually, the central limit theorem kicks in here. You have i.i.d. random variables of finite variance $\sigma^2=\frac{2}{3}(-1+2^m)^3$ (asking Mathematica):

Simplify[Integrate[x*x, {x, -(2^m - 1), 2^(m - 1)}] + 
  Integrate[x*x, {x, 2^(m - 1), 2^m - 1}]]

$=\frac{2}{3} \left(2^m-1\right)^3$

Hence, according to the central limit theorem, if you take the average of enough of those measurements, you will end up with a Gaussian distribution of variance

$$Var(\frac{1}{n}\sum_{i=0}^{n-1}X_i)\approx\frac{\sigma^2}{n},$$

So, with this result, you can calculate how much measurements you need, to get the required reduction in noise.

$\endgroup$
  • $\begingroup$ Python code and plot? Regarding ' If you average more, you can get the gross of noise samples close to zero' how much did you average to get to zero? $\endgroup$ – Turbo Jan 9 '17 at 11:14
  • $\begingroup$ @AJ.Yes, it's python code and the resulting plot. The last histogram (which appears only black) was done with 1000 measurements averaging. The cyan was done with m ld m measurements. $\endgroup$ – Maximilian Matthé Jan 9 '17 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.