Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1131

Re: entropy of a binary file with conditions

Show all headers | View raw

Alex Mizrahi <alex.mizrahi@gmail.com> wrote:
>> Well, you need to know, as best you can, how the data was generated.
>> One possibility is that whenever a run of eight is generated, the
>> opposite bit is stuffed in after it. 1024 bits might not be quite
>> enough to get the statistics needed to detect such bit stuffing.

> I think OP meant maximum possible entropy for a set of such sequences. 
> It is achieved when all sequences in set are equiprobable, then you only 
> need to count them.

Well, all 2**1024 bit sequences are equally probable. 

But some sequences are more likely to be generated in other ways.

The sequence of 1024 zeros, for example, is more likely to be
generated as 1024 zeros than 1024 consecutive tails on a coin flip.

It seems a reasonable question, given a sequence, to ask
about the likely generators of that sequence, and the entropies
for them. (Plural to allow for multiple possibilities.)

So, what generators generate sequences of runs of lengths
from 1 to 8? One possibility generates equal probability runs,
and one can compute that entropy. 

A random independent stream of 1024 bits will tend to have runs
longer than 8, but also should be exponential in run length.
Many artificial (non-independent) bit streams should be easily
detected from the run length distribution.

> I really doubt that this problem would arise in any practical setting, 
> as it makes more sense to look at how data is generated rather than at 
> maximum possible entropy within certain limitations.

You don't always have that option, but if you do, yes, use it.

-- glen

Back to comp.compression | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

entropy of a binary file with conditions pierre <pierre@invalid.invalid> - 2012-03-03 10:04 +0100
  Re: entropy of a binary file with conditions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-03-03 09:41 +0000
    Re: entropy of a binary file with conditions pierre <pierre@invalid.invalid> - 2012-03-03 10:47 +0100
      Re: entropy of a binary file with conditions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-03-03 10:00 +0000
        Re: entropy of a binary file with conditions pierre <pierre@invalid.invalid> - 2012-03-03 11:34 +0100
          Re: entropy of a binary file with conditions Alex Mizrahi <alex.mizrahi@gmail.com> - 2012-03-04 00:08 +0200
          Re: entropy of a binary file with conditions "George Johnson" <matrix29@charter.net> - 2012-03-03 22:45 -0500
            Re: entropy of a binary file with conditions "George Johnson" <matrix29@charter.net> - 2012-03-04 01:08 -0500
  Re: entropy of a binary file with conditions biject <biject.bwts@gmail.com> - 2012-03-03 12:34 -0800
    Re: entropy of a binary file with conditions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-03-03 21:11 +0000
    Re: entropy of a binary file with conditions pierre <pierre@invalid.invalid> - 2012-03-04 20:57 +0100
  Re: entropy of a binary file with conditions "George Johnson" <matrix29@charter.net> - 2012-03-03 22:30 -0500
    Re: entropy of a binary file with conditions Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-03-20 18:49 +0200
  Re: entropy of a binary file with conditions James Dow Allen <jdallen2000@yahoo.com> - 2012-03-03 22:07 -0800
    Re: entropy of a binary file with conditions pierre <pierre@invalid.invalid> - 2012-03-04 20:59 +0100
  Re: entropy of a binary file with conditions Willem <willem@toad.stack.nl> - 2012-03-04 15:41 +0000
    Re: entropy of a binary file with conditions Alex Mizrahi <alex.mizrahi@gmail.com> - 2012-03-04 21:39 +0200
    Re: entropy of a binary file with conditions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-03-04 22:45 +0000
      Re: entropy of a binary file with conditions Alex Mizrahi <alex.mizrahi@gmail.com> - 2012-03-05 10:03 +0200
        Re: entropy of a binary file with conditions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-03-05 09:52 +0000
          Re: entropy of a binary file with conditions Alex Mizrahi <alex.mizrahi@gmail.com> - 2012-03-05 18:05 +0200
        Re: entropy of a binary file with conditions James Dow Allen <jdallen2000@yahoo.com> - 2012-03-05 06:03 -0800
          Re: entropy of a binary file with conditions James Dow Allen <jdallen2000@yahoo.com> - 2012-03-05 16:16 -0800
            Re: entropy of a binary file with conditions James Dow Allen <jdallen2000@yahoo.com> - 2012-03-05 16:27 -0800

csiph-web