Re: Theoretically, I succeeded
- From: mdsherry@xxxxxxxxx
- Date: Thu, 18 Dec 2008 05:59:31 -0800 (PST)
On Dec 18, 5:35 am, Nimo <azeez...@xxxxxxxxx> wrote:
Argument:
16 pigeons can't be in 15 Holes
What's wrong if we dig another hole for the left_out pigeon.
Assuming that we add the restriction that the holes must all be
indexable using only up to three bits, then no. We can't fit in
sixteen holes. There are only 15 possible sequences of three or fewer
bits: one for zero bits, two for one bit, four for two bits, and eight
for three bits. You can't make a 16th pigeon hole and describe it in
three or fewer bits, unless you displace one of the other fifteen
pigeon holes. If you stack the new hole on top of one of the others
and say that they're both represented by 010, then there's no way for
the decoder to say whether you meant the bottom pigeon hole, with its
message of "All is well", or the top pigeon hole, with its message of
"Send help immediately!", and your compression algorithm is no longer
lossless.
In short: for any given length of description (and it's this
description length that compression is trying to minimize *in the
average message sent*), there are only a fixed number of pigeon holes
described by that length. You can chose to not use all of them, but
there's no way to add more, anymore than you can make the integers 2
and 3 equal.
Mark Sherry
.
- References:
- Theoretically, I succeeded
- From: Nimo
- Re: Theoretically, I succeeded
- From: George Johnson
- Re: Theoretically, I succeeded
- From: Fibonacci Code
- Re: Theoretically, I succeeded
- From: Nimo
- Re: Theoretically, I succeeded
- From: mdsherry
- Re: Theoretically, I succeeded
- From: Nimo
- Theoretically, I succeeded
- Prev by Date: Re: Please I need help with especific case of permutations algorithm (not usually)
- Next by Date: Compression Algorithm
- Previous by thread: Re: Theoretically, I succeeded
- Next by thread: APE - Sound compression
- Index(es):
Relevant Pages
|
Loading
