Código de Hamming §

---

O Código de Hamming é um método de codificação de dados utilizado para detectar e corrigir erros em sistemas de comunicação e armazenamento. Desenvolvido por Richard Hamming na década de 1950, esse código é capaz de detectar até dois erros simultâneos e corrigir um único erro em um bloco de dados.

Conceitos fundamentais §

Bits de dados e bits de paridade §

• Bits de dados: São os bits que representam a informação original a ser transmitida ou armazenada.
• Bits de paridade: São bits adicionais adicionados ao bloco de dados original com a finalidade de detectar e corrigir erros.

Estrutura do Código de Hamming §

Para um código de Hamming (7,4), por exemplo:

• 7 é o número total de bits no código (incluindo bits de dados e bits de paridade).
• 4 é o número de bits de dados.

O número de bits de paridade em relação ao número de bits de dados pode ser calculado usando a fórmula:

Codificação do Código de Hamming §

Posicionamento dos bits de paridade §

• Os bits de paridade são posicionados em potências de 2 (1, 2, 4, 8, …).
• Para um código (7,4), os bits de paridade estarão nas posições 1, 2 e 4, e os bits de dados ocuparão as posições restantes.

Cálculo dos bits de paridade §

• Cada bit de paridade é calculado com base em uma combinação específica de bits de dados.
• O bit de paridade em posição verifica os bits cujas posições têm o -ésimo bit (contado da direita) igual a 1.

Exemplo §

Exemplo com 4 bits de dados :

• Dados: , , ,
• Posições:

Vamos calcular os bits de paridade:

• P1 verifica as posições 1, 3, 5, 7:
• P2 verifica as posições 2, 3, 6, 7:
• P4 verifica as posições 4, 5, 6, 7:

O código de Hamming resultante seria: 0100111.

Decodificação do Código de Hamming §

1. Recebimento do Código:

   • Suponha que o código de Hamming 0100111 seja recebido.

2. Cálculo dos Síndromes:

   • Cada bit de paridade é recalculado para verificar possíveis erros.
   • Comparação dos bits de paridade recalculados com os bits de paridade recebidos indica a posição do erro, se houver.

Exemplo:

• Recalcular os bits de paridade para 0100111:

Os síndromes (paridade recalculada) seriam comparados com os bits de paridade originais:

• Se houver discrepância, os bits de paridade formarão um número binário que indica a posição do erro.
• No exemplo, e , o que sugere uma discrepância na posição 4, mas não em 2, 1, ou 0. Se um único bit estiver errado, sua posição será apontada diretamente.

3. Correção do Erro:
   • O bit na posição indicada pelo síndromes é invertido para corrigir o erro.
   • No exemplo acima, se houvesse um erro em uma única posição, inverteríamos o bit dessa posição para corrigir o código.

Referências §

---

Aula 06 - Código de Correção de Erros