Compression theory reference?

[lists at notatla.org.uk]

From: Hadmut Danisch <hadmut at danisch.de>

> It can be easily shown that there is no lossless 
> compression method which can effectively compress every possible
> input.

> Therefore, I need a book about computer science or encoding theory,
> which explicitely says that this is impossible, in a way that a person
> unexperienced in computer science (judges at a court) can read and 
> at least see that this is not just my personal phantasy and at least
> somehow reasonable. 

Section 20.4 of
    Press, Teukolsky, Vetterling & Flannery
    Numerical Recipies in Fortran, 2nd Ed (1992)
    Cambridge University Press
    ISBN 0-521-43064-X
makes simple reading to this reader with minimal computer science
education incidental to a Physics course.  There are related
"Numerical Recipies" books using other computer languages.

The first paragraph on compression is (with *italics*):

  "A lossless data compression algorithm takes a string of symbols
   (typically ASCII characters or bytes) and translates it *reversibly*
   into another string, one that is *on the average* of shorter length.
   The words "on the average" are crucial; it is obvious that no reversible
   algorithm can make all strings shorter - there just aren't enough short
   strings to be in one-to-one correspondence with longer strings.
   Compression algorithms are possible only when, on the input side, some
   strings, or some input symbols, are more common than others.  These can
   then be encoded in fewer bits than rarer input strings or symbols,
   giving a net average gain."

There is 10.5 pages on compression and some further references I have
not read.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com