Invente um código para os dígitos 0 a 9 cuja distância de Hamming seja 2.

Passo 1

O enunciado pede: inventar um código para os dígitos de 0 a 9 cuja distância de Hamming mínima entre quaisquer dois códigos seja 2. Informações dadas e objetivo:
  • Símbolos a codificar: os dígitos 0,1,2,\dots,9.
  • Requisito: a distância de Hamming entre quaisquer dois códigos deve ser pelo menos 2.
  • Não há restrição explícita sobre o tamanho dos códigos, então podemos escolher o comprimento dos vetores binários (quantos bits) livremente, desde que a condição de distância seja satisfeita.

Passo 2

O que é distância de Hamming (explicação didática):
  • Para dois vetores binários x=(x_1,\dots,x_n) e y=(y_1,\dots,y_n) de mesmo comprimento n, a distância de Hamming é o número de posições em que eles diferem. Formalmente,
d_H(x,y)=\sum_{i=1}^{n} |x_i-y_i|.
  • A condição “distância de Hamming 2” significa que, para qualquer par de códigos distintos x e y atribuídos a dois dígitos diferentes, vale
d_H(x,y)\ge 2.
Isso garante que não exista par de códigos que difira em exatamente 1 bit (útil, por exemplo, para detectar um erro simples de 1 bit).

Passo 3

Qual deve ser o comprimento mínimo n dos vetores para caberem 10 códigos com d_H\ge2?
  • Considere o hipercubo binário de dimensão n. Ele é bipartido: os vetores com número de uns par e os com número de uns ímpar formam as duas partes; arestas (distância 1) conectam sempre um vetor par a um ímpar.
  • Assim, o conjunto de todos os vetores de paridade par (ou, alternativamente, todos de paridade ímpar) forma um conjunto independente (nenhum par a distância 1) com tamanho 2^{n-1}. Logo existe um código com distância mínima \ge2 de tamanho 2^{n-1}. Também não é possível ter conjunto independente maior que 2^{n-1} porque cada aresta conecta as duas partes e a maior parte tem 2^{n-1} vértices.
  • Portanto o tamanho máximo de um código binário de comprimento n com d_{\min}\ge2 é 2^{n-1}. Para acomodar 10 códigos precisamos
2^{n-1}\ge 10.
  • Calculando: 2^{3}=8<10 e 2^{4}=16\ge10. Assim o menor n possível é n=5. Conclusão: é suficiente e necessário trabalhar com códigos de 5 bits (não existe arranjo com 10 códigos de 4 bits com distância \ge2).

Passo 4

Estratégia prática e por que funciona (explicação passo a passo, bem didática e com exemplo):
  • Uma construção simples e natural é pegar a representação binária em 4 bits dos dígitos 0 a 9 e acrescentar um bit de paridade tal que o total de uns do código de 5 bits seja par. Ou seja, se x=(x_1,x_2,x_3,x_4) é a representação em 4 bits, definimos o bit de paridade
p(x)=\bigl(x_1+x_2+x_3+x_4\bigr)\bmod 2,
e o código final é c(x)=(x_1,x_2,x_3,x_4,p(x)). Assim todos os códigos terão paridade par.
  • Por que isso garante d_H\ge2? Seja x\neq y duas representações de 4 bits e d=d_H(x,y). Temos d\ge1. Note que a paridade de x e de y difere se, e somente se, d é ímpar. Logo o bit de paridade difere quando d é ímpar e coincide quando d é par. A distância entre c(x) e c(y) é
d_H(c(x),c(y))=d + \bigl(d\bmod 2\bigr).
  • Agora examine os casos:
    • Se d=1 (os 4 bits diferem em uma posição), então d_H(c(x),c(y))=1+1=2.
    • Se d\ge2, então d_H(c(x),c(y))\ge2 automaticamente (pelo menos as d diferenças nos primeiros 4 bits).
      Logo em todo caso d_H(c(x),c(y))\ge2. Essa construção funciona e tem comprimento mínimo 5.

Passo 5

Vou aplicar a construção: representação em 4 bits dos números 0 a 9, calcular a paridade e formar o código 5-bit com paridade par. As representações em 4 bits (MSB à esquerda) são:
  • 0:\;0000
  • 1:\;0001
  • 2:\;0010
  • 3:\;0011
  • 4:\;0100
  • 5:\;0101
  • 6:\;0110
  • 7:\;0111
  • 8:\;1000
  • 9:\;1001
Agora cálculo do bit de paridade p (soma dos uns módulo 2) e código final 5-bit (coloquei o bit de paridade como o último bit):
  • Para 0:\;0000 o número de uns é 0 (par), então p=0. Código 0000\;0.
  • Para 1:\;0001 o número de uns é 1 (ímpar), então p=1. Código 0001\;1.
  • Para 2:\;0010 número de uns 1 p=1. Código 0010\;1.
  • Para 3:\;0011 número de uns 2 p=0. Código 0011\;0.
  • Para 4:\;0100 número de uns 1 p=1. Código 0100\;1.
  • Para 5:\;0101 número de uns 2 p=0. Código 0101\;0.
  • Para 6:\;0110 número de uns 2 p=0. Código 0110\;0.
  • Para 7:\;0111 número de uns 3 p=1. Código 0111\;1.
  • Para 8:\;1000 número de uns 1 p=1. Código 1000\;1.
  • Para 9:\;1001 número de uns 2 p=0. Código 1001\;0.
(Para clareza, escrevo cada código como os 5 bits concatenados, sem espaço entre os bits.)

Passo 6

Checagem rápida de coerência (exemplos para ganhar confiança):
  • Os códigos são todos de 5 bits distintos (só há um código por dígito).
  • Exemplo de par que difere em 1 bit nos 4 bits originais: 1 ( 0001) e 0 ( 0000) têm d=1; seus códigos 00011 e 00000 diferem nos últimos dois bits, então d_H=2.
  • Exemplo de par que difere em 2 bits originais: 3 ( 0011) e 2 ( 0010) têm d=1 — ok esse é d=1. Outro exemplo: 5 ( 0101) e 2 ( 0010) têm d=3 então claramente d_H\ge3. Em todos os casos acima a desigualdade d_H\ge2 mantém-se, conforme o argumento geral do Passo 4.

Passo 7

Resumo do método e motivação final (breve incentivo):
  • Construímos códigos de 5 bits (o comprimento mínimo possível) usando o bit de paridade para garantir que não haja pares a distância 1.
  • Essa construção é simples, eficiente e fácil de implementar na prova: lembra sempre — pegar a representação em 4 bits e acrescentar o bit de paridade que torna o total de uns par. Você já sai com detecção garantida de um erro simples. Dá pra usar isso rapidinho na prova, sem calculadora. Força aí, dá pra entender e aplicar!

Resposta

0: 00000
1: 00011
2: 00101
3: 00110
4: 01001
5: 01010
6: 01100
7: 01111
8: 10001
9: 10010

Exercícios relacionados