2
$\begingroup$

Is it possible to encode two 6-bit wide positive integers a and b guaranteed to be in [0, 63] in a way that a and b are recoverable -- in fewer than 12 bits? We could obviously concatenate the binary representations (a << 6 | b). The scheme would have to allow any two arbitrary values within the given range. Can we do better than 12 bits?

$\endgroup$
1
  • 3
    $\begingroup$ There are $2^{12}$ options, and you need a different encoding for each option, so no. Of course, if you have some prior knowledge (e.g. how often each pair appears), you can improve average encoding length by using non-fixed length encodings (see e.g. Huffman codes). $\endgroup$
    – user114966
    Oct 14, 2020 at 14:55

1 Answer 1

3
$\begingroup$

Suppose that $H\colon \{0,1\}^6 \times \{0,1\}^6 \to \{0,1\}^n$ is such that $a,b \in \{0,1\}^6$ can be recovered from $H(a,b)$. In particular, $H(a,b) \neq H(c,d)$ whenever $(a,b) \neq (c,d)$. Since there are $2^{12}$ possible inputs, and the value of $H$ on each of them is different, it follows that the range of $H$ must consist of at least $2^{12}$ different points. Since $\{0,1\}^n$ has $2^n$ points, we conclude that $n \geq 12$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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