1
$\begingroup$

Is the following scenario theoretically possible, or provably impossible?

Alice generates a 1 GiB file with random bits and sends it to Bob. This file is a shared dictionary they call Q. Now, Alice and Bob starts sending each other new files with arbitrary entropy, each of them < 1 MiB, but they compress them with a clever algorithm that exploits information in Q, typically breaking the Shannon limit.

$\endgroup$
1
$\begingroup$

This is provably impossible. The proof of Shannon's theorem goes through as usual.

As a simple example, suppose that are looking for an algorithm that compresses all $n$-bit strings to smaller strings. This is impossible since there are $2^n$ possible inputs, but only $2^n-1$ possible outputs. The proof of Shannon's theorem is very similar. Note how $Q$ makes absolutely no difference.

What happens if you choose a random 1 MiB window of $Q$ as your file? This can easily be compressed to 30 bits, by sending the location of the window. However, in this case the entropy of $Q$ is indeed at most 30 bits, since there are at most $2^{30}$ different windows.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.