[16074] in cryptography@c2.net mail archive
Re: Compression theory reference?
daemon@ATHENA.MIT.EDU (bear)
Wed Sep 1 15:48:48 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 1 Sep 2004 11:30:04 -0700 (PDT)
From: bear <bear@sonic.net>
To: John Denker <jsd@av8n.com>
Cc: Matt Crawford <crawdad@fnal.gov>,
Hadmut Danisch <hadmut@danisch.de>, cryptography@metzdowd.com
In-Reply-To: <413523BE.10809@av8n.com>
On Tue, 31 Aug 2004, John Denker wrote:
> I emphasize that I am only discussing messages of length N,
> where N is some pre-chosen number. For concreteness, let's
> choose N=10.
> I repeat my assertion that _if_ XX can compress any string,
> shortening it by one bit, and _if_ you know that the original
> messages each have exactly 10 bits, _then_ any 10-bit message
> can be compressed down to a single bit.
Actually you don't need to take it all the way to the
reductio ad absurdum here. There are 1024 10-bit
messages. There are 512 9-bit messages. You need
to point out that since a one-to-one mapping between
sets of different ordinality cannot exist, it is not
possible to create something that will compress every
ten-bit message by one bit.
Or, slightly more formally, assume that a function C
can reversibly compress any ten-bit message by one bit.
Since there are 1024 distinct ten-bit messages, there
must be at least 1024 distinct nine-bit messages which,
when the reversal is applied, result in these 1024
messages. There are exactly 512 distinct nine-bit
messages. Therefore 512 >= 1024.
Bear
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
