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
a
cuja distância de Hamming mínima entre quaisquer dois códigos seja
. Informações dadas e objetivo:
- Símbolos a codificar: os dígitos
. - Requisito: a distância de Hamming entre quaisquer dois códigos deve ser pelo menos
. - 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
e de mesmo comprimento , a distância de Hamming é o número de posições em que eles diferem. Formalmente,
- A condição “distância de Hamming 2” significa que, para qualquer par de códigos distintos
e atribuídos a dois dígitos diferentes, vale
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
dos vetores para caberem
códigos com
?
- Considere o hipercubo binário de dimensão
. 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
. Logo existe um código com distância mínima de tamanho . Também não é possível ter conjunto independente maior que porque cada aresta conecta as duas partes e a maior parte tem vértices. - Portanto o tamanho máximo de um código binário de comprimento
com é . Para acomodar códigos precisamos
- Calculando:
e . Assim o menor possível é . Conclusão: é suficiente e necessário trabalhar com códigos de bits (não existe arranjo com códigos de bits com distância ).
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
bits dos dígitos a e acrescentar um bit de paridade tal que o total de uns do código de bits seja par. Ou seja, se é a representação em bits, definimos o bit de paridade
e o código final é
. Assim todos os códigos terão paridade par.
- Por que isso garante
? Seja duas representações de bits e . Temos . Note que a paridade de e de difere se, e somente se, é ímpar. Logo o bit de paridade difere quando é ímpar e coincide quando é par. A distância entre e é
- Agora examine os casos:
- Se
(os 4 bits diferem em uma posição), então . - Se
, então automaticamente (pelo menos as diferenças nos primeiros 4 bits).
Logo em todo caso. Essa construção funciona e tem comprimento mínimo .
- Se
Passo 5
Vou aplicar a construção: representação em
bits dos números
a
, calcular a paridade e formar o código
-bit com paridade par. As representações em
bits (MSB à esquerda) são:
Agora cálculo do bit de paridade
(soma dos uns módulo
) e código final
-bit (coloquei o bit de paridade como o último bit):
- Para
o número de uns é (par), então . Código . - Para
o número de uns é (ímpar), então . Código . - Para
número de uns → . Código . - Para
número de uns → . Código . - Para
número de uns → . Código . - Para
número de uns → . Código . - Para
número de uns → . Código . - Para
número de uns → . Código . - Para
número de uns → . Código . - Para
número de uns → . Código .
(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
bits distintos (só há um código por dígito). - Exemplo de par que difere em 1 bit nos 4 bits originais:
( ) e ( ) têm ; seus códigos e diferem nos últimos dois bits, então . - Exemplo de par que difere em 2 bits originais:
( ) e ( ) têm — ok esse é . Outro exemplo: ( ) e ( ) têm então claramente . Em todos os casos acima a desigualdade 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
bits (o comprimento mínimo possível) usando o bit de paridade para garantir que não haja pares a distância . - Essa construção é simples, eficiente e fácil de implementar na prova: lembra sempre — pegar a representação em
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:
1:
2:
3:
4:
5:
6:
7:
8:
9:
1:
2:
3:
4:
5:
6:
7:
8:
9: