Encoding two 6-bit positive integers compactly
-
20-10-2020 - |
Domanda
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?
Soluzione
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$.