Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:05
Mike Rosing (eresrch@msn.fullfeed.com)
Sat, 23 Jan 1999 08:04:47 -0600 (CST)
On Sat, 23 Jan 1999, Enzo Michelangeli wrote:
> The definition of entropy of a data source (a stochastic process) was
> supplied by Shannon in 1948, as minimum number of bits necessary to describe
> its output. That's the catch: if you don't know in detail the inner workings
> of the source, you can never be sure that the output couldn't be compressed
> further by using some weird algorithm.
I do know the inner workings of the source up to some limit. That is,
I can measure the signal. Nobody can know how the signal got there
which is what makes it random. Now, I should be able to explain the
physics of the signal, which makes portions of it non random. So it's
the going from real signal to random bits that I don't have a theory for.
> Of course statistical tools help to see how bad the situation is, but they
> are fundamentally limited by the fact that they only test against SOME forms
> of data interdependency, if nothing else because they must run in a limited
> time. Generally they address issues of frequency of each symbol (first-order
> statistics) and frequency of pairs of symbols separated by a given interval
> (second-order statistics, which, under some restrictive conditions
> (linearity, stationariety, ergodicity etc.), can be reduced to power
> spectra). Incidentally, those are also the areas exploited by most
> compressors, based on a first step of identification of repeated patterns or
> spectral analysis, followed by entropy coding (e.g., Huffman) of the symbols
> produced. However, no common compressor will squeeze sequences produced by
> highly non-linear algorithms, even though they are absolutely deterministic
> (PRNG's).
Well, no compressor works on the random bits I get, and it does pass
DIEHARD, so it's as random as I know how to measure.
> Up to a point: a PRNG would pass the tests with flying colours, and would
> still be useless as source of entropy.
Which is why a hardware source is useful :-)
Patience, persistence, truth,
Dr. mike
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:05