Codificando dois inteiros positivos de 6 bits de forma compacta

Question

É possível codificar dois inteiros positivos largos de 6 bits ae bgarantidamente estar de [0, 63]uma forma que ae bsão recuperáveis ​​- em menos de 12 bits? Obviamente, poderíamos concatenar as representações binárias (a << 6 | b). O esquema teria que permitir quaisquer dois valores arbitrários dentro do intervalo fornecido. Podemos fazer melhor do que 12 bits?

Answer 1

Suponha que $H\colon \{0,1\}^6 \times \{0,1\}^6 \to \{0,1\}^n$ é tal que $a,b \in \{0,1\}^6$ pode ser recuperado de $H(a,b)$. Em particular,$H(a,b) \neq H(c,d)$ sempre que $(a,b) \neq (c,d)$. Uma vez que existem$2^{12}$ possíveis entradas, e o valor de $H$ em cada um deles é diferente, segue-se que o intervalo de $H$ deve consistir em pelo menos $2^{12}$pontos diferentes. Desde a$\{0,1\}^n$ tem $2^n$ pontos, concluímos que $n \geq 12$.