Codificación compacta de dos enteros positivos de 6 bits

Question

¿Es posible codificar dos enteros de 6 bits de ancho positivos ay bgarantizado para estar en [0, 63]una forma que ay bson recuperables - en menos de 12 bits? Obviamente, podríamos concatenar las representaciones binarias (a << 6 | b). El esquema debería permitir dos valores arbitrarios cualesquiera dentro del rango dado. ¿Podemos hacerlo mejor que 12 bits?

Answer 1

Suponer que $H\colon \{0,1\}^6 \times \{0,1\}^6 \to \{0,1\}^n$ es tal que $a,b \in \{0,1\}^6$ se puede recuperar de $H(a,b)$. En particular,$H(a,b) \neq H(c,d)$ cuando $(a,b) \neq (c,d)$. Puesto que hay$2^{12}$ posibles entradas, y el valor de $H$ en cada uno de ellos es diferente, se deduce que el rango de $H$ debe constar de al menos $2^{12}$diferentes puntos. Ya que$\{0,1\}^n$ tiene $2^n$ puntos, concluimos que $n \geq 12$.