3
$\begingroup$

I really don't know how to word this better, sorry if that title is confusing.

Basically, I'm wanting to use the noise from an AM radio audio signal to generate random numbers. To do this effectively, I need to know how many bits of entropy I can expect from some number of bits of signal data.

If every sample were independent, I could easily calculate the entropy using probabilities. The problem is that the samples are dependent on the samples that came before it and the samples that come after. I don't know how to account for this.

How can I calculate the entropy (in bits) of a section of my signal?

$\endgroup$
  • $\begingroup$ I think the term you want to research in "mutual information" :) $\endgroup$ – Marcus Müller Jun 27 '17 at 8:31
  • $\begingroup$ This may help $\endgroup$ – oxuf Jun 27 '17 at 14:05
  • $\begingroup$ What if you tune your radio to an empty station (that is, pure noise)? Also, if you wait long enough, the noise samples should become uncorrelated. Lastly, if you can determine the distribution of the noise samples, you may be able to use a whitening filter. $\endgroup$ – MBaz Jun 27 '17 at 14:40
  • $\begingroup$ @oxuf No it doesn't unfortunately. ent is only for fully independent samples that are not auto correlated. $\endgroup$ – Paul Uszak Jul 28 '18 at 14:44
  • $\begingroup$ @PaulUszak What do you mean? as I understand it, ent is just a set of tests. without assuming any property from the signal under study. $\endgroup$ – oxuf Jul 28 '18 at 17:55
1
$\begingroup$

I think that the answer is that there is no correct answer. Whilst this is a simple question, the answer is kinda open.

You're asking about the entropy of correlated data with respect to random number generation. The key reference for this is NIST Special Publication 800-90B, Recommendation for the Entropy Sources Used for Random Bit Generation. Look to sections 5 and 6. You be faced with two questions; Is my data correlated (non IID) and if so, what is it's entropy rate? You have already realised that the standard $ -K\sum_{i=1}^n {p_i \log p_i} $ isn't appropriate.

Is your data correlated?

This is the first step, and NIST suggests permutation testing, as below:-

permutations

There are 11 tests NIST recommends, all of which are somewhat complex. To help (not) they have release some code on GitHub that implement these tests. I'm unsure of how official this is, but see the well received How to interpret the entropy results for a NIST test file as to their soundness. An immediately apparent problem for implementation is that as $ T, T_i \in \mathbb{R} $, the equality test in Fig.4, section 2.2.2 becomes difficult without bounds. In a nutshell, the code doesn't work well enough for field use.

What is the entropy?

If you manage to satisfy yourself that the data is non IID, NIST recommends taking the lowest value of another 10 complex statistical tests as the min. entropy value. Similarly, the Python and C++ code has problems outputting a coherent and credible entropy estimate. Perhaps you can implement the tests yourself in another fashion.

What I do.

I too build random number generators and I use similar permutation tests, but focused solely on a compression test. Compression exploits correlation and eliminates redundancy. Compression is also used in both the NIST non IID confirmation and entropy estimation tests above.

One can calculate what I have termed a correlation factor, $ c_f $, explored in What exactly does compression say about correlation of data? If $ c_f \simeq 1 $ then the data is IID, and non IID if $ c_f > 1 $. I then use the non permuted compressed file size and divide twice by two to get a conservative entropy rate. This method seems to be as good as any, and more robust that most. I estimate about 1.6 bits / byte from a 24V Zener diode at 10kSa/s. That's 16kbps of cryptographic strength entropy.


Notes.

  1. I now use fp8 and paq8px compressors as they are about the best I can find that will compile for me. They'll compress IID data to within 1% of the theoretical Shannon limit.
  2. Divide by two as a security precaution to allow for improvements in compression algorithms, whilst realising that these improvements are asymptotic with diminishing returns.
  3. Divide by two again just because.
$\endgroup$

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.