[16060] in cryptography@c2.net mail archive
Re: Compression theory reference?
daemon@ATHENA.MIT.EDU (Victor Duchovni)
Wed Sep 1 08:44:46 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Tue, 31 Aug 2004 18:31:49 -0400
From: Victor Duchovni <Victor.Duchovni@MorganStanley.com>
To: cryptography@metzdowd.com
Mail-Followup-To: cryptography@metzdowd.com
In-Reply-To: <4134E5F9.8040200@av8n.com>
On Tue, Aug 31, 2004 at 04:56:25PM -0400, John Denker wrote:
> 4) Don't forget the _recursion_ argument. Take their favorite
> algorithm (call it XX). If their claims are correct, XX should
> be able to compress _anything_. That is, the output of XX
> should _always_ be at least one bit shorter than the input.
> Then the compound operation XX(XX(...)) should produce something
> two bits shorter than the original input. If you start with a
> N-bit message and apply the XX function N-1 times, you should be
> able to compress each and every message down to a single bit.
>
This proof as written (the theorem is still true of course) relies on
the algorithm always compressing, rather than never expanding. It is
much simpler as a result, is there an equally simple argument to prove
that all non-expanding codes never compress?
Note that it is possible to turn any compressor into one whose expansion
is at most one 1 extra bit:
If F(x) is shorter than x by at least one bit output 0|F(x) if F(x)
is the same length as x or longer output 1|x. So we can lose 1 bit of
efficiency in compressed strings to gain at most 1 bit of overhead in
uncompressed strings.
--
/"\ ASCII RIBBON NOTICE: If received in error,
\ / CAMPAIGN Victor Duchovni please destroy and notify
X AGAINST IT Security, sender. Sender does not waive
/ \ HTML MAIL Morgan Stanley confidentiality or privilege,
and use is prohibited.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
