Um caractere ASCII estendido é representado por uma quantidade de 8 bits. A codificação de Hamming associada a cada caractere pode então ser representada por uma sequência de três dígitos hexa. Codifique o seguinte texto ASCII estendido de cinco caracteres usando um código de Hamming com paridade par: Earth. Mostre sua resposta como uma sequência de dígitos hexa.

Passo 1

O que o problema pede e os dados que temos.
  • O texto a codificar é: “Earth” (cinco caracteres).
  • Cada caractere é um byte de 8 bits (ASCII estendido). Vou usar os códigos ASCII padrão para essas letras (esses valores estão todos dentro de 0–127, então não há ambiguidade):
    • E tem código 0x45 que em binário de 8 bits é 01000101.
    • a tem código 0x61 que em binário de 8 bits é 01100001.
    • r tem código 0x72 que em binário de 8 bits é 01110010.
    • t tem código 0x74 que em binário de 8 bits é 01110100.
    • h tem código 0x68 que em binário de 8 bits é 01101000.
O que devemos devolver: a codificação de Hamming (paridade par) associada a cada caractere, representada por uma sequência de três dígitos hex cada (ou seja, 12 bits por caractere). A resposta final deve ser uma sequência hexa para os cinco caracteres.

Passo 2

Explicação didática do código de Hamming que vamos usar (passo-a-passo, sem pular etapas).
  • Para codificar 8 bits de dados com Hamming usando 4 bits de paridade obtemos um código de 12 bits: é o Hamming (12,8).
  • Convenção de posicionamento (essa convenção é a mais usada e a que vou seguir):
    • Numero as posições de bits de 1 a 12, com 1 sendo o bit menos significativo (LSB, à direita) e 12 o bit mais significativo (MSB, à esquerda). Esta numeração (direita → esquerda) facilita a definição dos conjuntos de paridade.
    • Os bits de paridade ficam nas posições que são potências de dois: 1,2,4,8. Chamo-os p_1 (posição 1), p_2 (posição 2), p_4 (posição 4) e p_8 (posição 8).
    • Os 8 bits de dado (do byte) chamam-se d_1,\dots,d_8. Vou mapear d_1 para o bit menos significativo do byte (LSB) e d_8 para o bit mais significativo (MSB) do byte. Ou seja, d_k corresponde ao bit b_{k-1} do byte, onde b_0 é o LSB.
    • Os dados d_1,\dots,d_8 são colocados nas posições restantes, na ordem crescente de posição: posições 3,5,6,7,9,10,11,12.
  • Como calcular cada bit de paridade (paridade par):
    • O bit de paridade na posição 2^k cobre todas as posições (incluindo a própria 2^k) cujo índice em binário tem o bit k (contando do LSB) igual a 1.
    • Para obter paridade par, o valor do bit de paridade é escolhido de modo que a soma (em \bmod 2) de todos os bits cobertos (incluindo o próprio bit de paridade) seja 0 (ou seja, número total de 1’s par). Em prática, calcula-se a soma XOR dos bits de dados cobertos e define-se o bit de paridade para tornar a soma total par.
Resumo prático (conjuntos):
  • p_1 (posição 1) cobre posições 1,3,5,7,9,11.
  • p_2 (posição 2) cobre posições 2,3,6,7,10,11.
  • p_4 (posição 4) cobre posições 4,5,6,7,12.
  • p_8 (posição 8) cobre posições 8,9,10,11,12.
Depois de calcular os p_i, teremos um vetor de 12 bits nas posições 12,\dots,1. Para escrever em hexadecimal, agrupo esses 12 bits em 3 grupos de 4 bits, do MSB (posição 12) para o LSB (posição 1), e converto cada grupo para um dígito hexa.

Passo 3

Codificação do caractere E (detalhado passo-a-passo).
  • Byte ASCII de E: 0x45. Em binário 8 bits: 01000101Vou listar os bits do byte como b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0 = 0\;1\;0\;0\;0\;1\;0\;1.
    Portanto: d_1=b_0=1,\; d_2=b_1=0,\; d_3=b_2=1,\; d_4=b_3=0,\; d_5=b_4=0,\; d_6=b_5=0,\; d_7=b_6=1,\; d_8=b_7=0.
  • Colocando nos lugares do código (posições 1…12, com ? para paridade ainda desconhecida): \begin{array}{c|cccccccccccc} \text{pos} & 12 & 11 & 10 & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1\\hline \text{bit} & d_8 & d_7 & d_6 & d_5 & p_8 & d_4 & d_3 & d_2 & p_4 & d_1 & p_2 & p_1 \end{array}Substituindo os d: \text{pos: }12\,11\,10\,9\,8\,7\,6\,5\,4\,3\,2\,1 = 0,\,1,\,0,\,0,\,?,\,0,\,1,\,0,\,?,\,1,\,?,\,?.Ou seja, inicialmente: \begin{array}{l} \text{pos }3=1,\;5=0,\;6=1,\;7=0,\;9=0,\;10=0,\;11=1,\;12=0. \end{array}
  • Calcular paridades (paridade par):
    • Para p_1 (posições 1,3,5,7,9,11): bits conhecidos são pos3=1,\;pos5=0,\;pos7=0,\;pos9=0,\;pos11=1. Soma de uns = 1+0+0+0+1=2 (par). Então p_1=0 para manter paridade par.
    • Para p_2 (posições 2,3,6,7,10,11): pos3=1,\;pos6=1,\;pos7=0,\;pos10=0,\;pos11=1. Soma = 1+1+0+0+1=3 (ímpar). Então p_2=1.
    • Para p_4 (posições 4,5,6,7,12): pos5=0,\;pos6=1,\;pos7=0,\;pos12=0. Soma = 0+1+0+0=1 (ímpar). Então p_4=1.
    • Para p_8 (posições 8,9,10,11,12): pos9=0,\;pos10=0,\;pos11=1,\;pos12=0. Soma = 0+0+1+0=1 (ímpar). Então p_8=1.
  • Agora o vetor de 12 bits (posição 12 → 1) é: 0\;1\;0\;0\;1\;0\;1\;0\;1\;1\;1\;0.Agrupando em 3 nibbles (4 bits) do MSB para LSB: 0100\;1010\;1110.Esses nibbles em hexa são 4,\;A,\;E. Logo o código de Hamming de E é 0x4AE.

Passo 4

Codificação do caractere a.
  • Byte ASCII a: 0x61. Em binário: 01100001Bits: b_7..b_0 = 0\;1\;1\;0\;0\;0\;0\;1.
    Assim: d_1=1,\;d_2=0,\;d_3=0,\;d_4=0,\;d_5=0,\;d_6=1,\;d_7=1,\;d_8=0.
  • Posicionando nos 12 bits (com paridades ?): \text{pos 12..1} = 0,\,1,\,1,\,0,\,?,\,0,\,0,\,0,\,?,\,1,\,?,\,?.Mais claramente: pos3=1,\;pos5=0,\;pos6=0,\;pos7=0,\;pos9=0,\;pos10=1,\;pos11=1,\;pos12=0.
  • Calcular paridades:
    • p_1 cobre 1,3,5,7,9,11: 1+0+0+0+1=2 (par) → p_1=0.
    • p_2 cobre 2,3,6,7,10,11: 1+0+0+1+1=3 (ímpar) → p_2=1.
    • p_4 cobre 4,5,6,7,12: 0+0+0+0=0 (par) → p_4=0.
    • p_8 cobre 8,9,10,11,12: 0+0+1+1+0=2 (par) → p_8=0.
  • Vetor 12 bits pos 12→1: 0\;1\;1\;0\;0\;0\;0\;0\;0\;1\;1\;0.Nibbles: 0110\;0000\;0110 → hex 6\;0\;6. Código: 0x606.

Passo 5

Codificação do caractere r.
  • Byte r: 0x72. Binário: 01110010Bits: b_7..b_0 = 0\;1\;1\;1\;0\;0\;1\;0. d_1=0,\;d_2=1,\;d_3=0,\;d_4=0,\;d_5=1,\;d_6=1,\;d_7=1,\;d_8=0.
  • Posicionando: pos3=0,\;pos5=1,\;pos6=0,\;pos7=0,\;pos9=1,\;pos10=1,\;pos11=1,\;pos12=0.
  • Paridades:
    • p_1 (1,3,5,7,9,11): 0+1+0+1+1=3 (ímpar) → p_1=1.
    • p_2 (2,3,6,7,10,11): 0+0+0+1+1=2 (par) → p_2=0.
    • p_4 (4,5,6,7,12): 1+1+0+0=2 (par) → p_4=1 — atenção: aqui o bit na posição 4 era paridade que ajustamos para tornar o total par; calculando sem o próprio p_4 deu soma 1 ímpar, então escolhemos p_4=1. (Explicando: os bits conhecidos que p_4 cobre exceto ele mesmo foram pos5=1,pos6=0,pos7=0,pos12=0 somando 1; portanto p_4 tem que ser 1.)
    • p_8 (8,9,10,11,12): 1+1+1+0=3 (ímpar) → p_8=1.
  • Vetor pos 12→1: 0\;1\;1\;1\;1\;0\;0\;1\;1\;0\;0\;1.Nibbles: 0111\;1001\;1001 → hex 7\;9\;9. Código: 0x799.

Passo 6

Codificação do caractere t.
  • Byte t: 0x74. Binário: 01110100Bits b_7..b_0 = 0\;1\;1\;1\;0\;1\;0\;0. d_1=0,\;d_2=0,\;d_3=1,\;d_4=0,\;d_5=1,\;d_6=1,\;d_7=1,\;d_8=0.
  • Posicionando: pos3=0,\;pos5=0,\;pos6=1,\;pos7=0,\;pos9=1,\;pos10=1,\;pos11=1,\;pos12=0.
  • Paridades:
    • p_1 (1,3,5,7,9,11): 0+0+0+1+1=2 (par) → p_1=0.
    • p_2 (2,3,6,7,10,11): 0+1+0+1+1=3 (ímpar) → p_2=1.
    • p_4 (4,5,6,7,12): 0+0+1+0=1 (ímpar) → p_4=1.
    • p_8 (8,9,10,11,12): 1+1+1+0=3 (ímpar) → p_8=1.
  • Vetor pos 12→1: 0\;1\;1\;1\;1\;0\;1\;0\;1\;0\;1\;0.Nibbles: 0111\;1010\;1010 → hex 7\;A\;A. Código: 0x7AA.

Passo 7

Codificação do caractere h.
  • Byte h: 0x68. Binário: 01101000Bits b_7..b_0 = 0\;1\;1\;0\;1\;0\;0\;0. d_1=0,\;d_2=0,\;d_3=0,\;d_4=1,\;d_5=0,\;d_6=1,\;d_7=1,\;d_8=0.
  • Posicionando: pos3=0,\;pos5=0,\;pos6=0,\;pos7=1,\;pos9=0,\;pos10=1,\;pos11=1,\;pos12=0.
  • Paridades:
    • p_1 (1,3,5,7,9,11): 0+0+1+0+1=2 (par) → p_1=0.
    • p_2 (2,3,6,7,10,11): 0+0+1+1+1=3 (ímpar) → p_2=1.
    • p_4 (4,5,6,7,12): 1+0+0+0=1 (ímpar) → p_4=1.
    • p_8 (8,9,10,11,12): 0+0+1+0=1 (ímpar) → p_8=0 — cuidado: a soma dos dados cobertos por p_8 (excluindo p_8) foi pos9=0,pos10=1,pos11=1,pos12=0 somando 2 que é par, então p_8 = 0. (Rechecagem: 0+1+1+0=2 → par → p8=0.)
  • Vetor pos 12→1: 0\;1\;1\;0\;0\;1\;0\;0\;1\;0\;1\;0.Nibbles: 0110\;0100\;1010 → hex 6\;4\;A. Código: 0x64A.

Resposta

\text{4AE 606 799 7AA 64A}

Exercícios relacionados