# Entropy Shmear

Consider the 1 MB of concatenated raw JPEG samples from the Photonic Instrument.

Naive application of Shannon’s $H = -K\sum_{i} {p_i \log p_i}, \enspace i \in \{0, 1\}^n$ entropy equation suggests a Shannon entropy rate of = 7.67 bits/byte for the JPEGs if $n=8$ (as is typical). A cmix compression estimate is only 5.17 bits/byte. What has happened to the missing 2.5 bits of Shannon entropy estimated to be in each byte? Our/an alternative way of thinking about auto correlation is that the missing 2.5 bits of entropy supposedly within each 8 bit window are elsewhere; outside of that narrow 8 bit window of consideration. The missing shmeared bits break the IID criterion, overlapping with many other bytes. We could say with enthusiasm and a grin that:-

• Each byte does contain 5.17 bits of true entropy based on scan windows for $n \gg 8$.
• The missing 2.5 bits are shmeared out across adjoining bytes and words due to auto correlation.
• They live outside of the enumeration of $i$, due to it’s 8 bit window (a probability distribution $P(\text{JPEG})$ based on $n = 8$).
• Thus the common means of applying Shannon cannot see nor account for them.

Our novel Entropy Shmear ($ES$) metric can be calculate as:-

1. Let $\pi$ be the concatenated file of JPEG frames (1,077,644 bytes).
2. Compute the entropy $H_{compression}(\pi)$ measured via cmix compression as $\frac{|Cmix(\pi)| - k}{|\pi|} \times 8$. $|Cmix(\pi)| = 697,126$ bytes in this case.
3. And $k$ is a constant representing the compressor’s file overhead, found from $|Cmix(u)| - |u|$. 67 bytes in this case for cmix.
4. $u$ is a good pseudo random file such as that from /dev/urandom, of length equivalent to $|\pi|$.
5. Hint: use ent to measure $H_{Shannon}(\pi)$. 7.67 bits/byte in this case.
6. The entropy shmear due to auto correlation $ES = \frac{H_{Shannon} - H_{compression}}{H_{Shannon}}$. That is $\frac{7.67 - 5.17}{7.67}$ or 33% for our $\pi$ sample.

Clearly in an IID situation, $H_{Shannon} - H_{compression} - k \approx 0$ [1]. Obviously an approximation, but might $ES$ be an alternative way of viewing auto correlation? We could say that $\pi$ has an auto correlation coefficient of >0.01. Or we can imagine 33% of $\pi$'s bits that would have made an IID sequence, being shmeared out to adjacent bytes. 33% of any byte in $\pi$ is strongly dependant on others.

Anyway, it’s a thought isn’t it ¯\_(ツ)_/¯

Notes:

[1] An ent test of 1.2 MB of /dev/urandom samples showing that auto correlation is never exactly zero, even for cryptographically strong pseudo random sequences :-

$ent /tmp/u Entropy = 7.999855 bits per byte. Optimum compression would reduce the size of this 1200000 byte file by 0 percent. Chi square distribution for 1200000 samples is 242.00, and randomly would exceed this value 71.10 percent of the times. Arithmetic mean value of data bytes is 127.5589 (127.5 = random). Monte Carlo value for Pi is 3.144180000 (error 0.08 percent). Serial correlation coefficient is 0.000989 (totally uncorrelated = 0.0).  [2] And the correlation coefficient is inversely proportional to the length of an IID test sequence. This is a problem for DIY TRNG builders as the entropy sources we have resources to build cannot easily produce Gigabytes of test data. The Arduino-Entropy-Library produces “approximately two 32-bit integer values every second”. It would take over 41 hours to generate a similar 1.2 MB sample! Even the venerable HotBits only produces entropy at$\approx\$ 800 bps.