Código Hamming: detecção e correção de erros com exemplos

O que é um erro?

Os dados transmitidos podem ser corrompidos durante a comunicação. É provável que seja afetado por ruídos externos ou outras falhas físicas. Em tal situação, os dados de entrada não podem ser iguais aos dados de saída. Essa incompatibilidade é conhecida como “Erro”.

Os erros de dados podem resultar na perda de dados importantes ou seguros. A maior parte da transferência de dados em sistemas digitais ocorrerá na forma de “transferência de bits”. Mesmo uma pequena mudança pode afetar o desempenho de todo o sistema. Em uma sequência de dados, se 1 for alterado para 0 ou 0 for alterado para 1, isso é chamado de “erro de bit”.

Tipos de erros

Existem principalmente três tipos de erros de bit que ocorrem na transmissão de dados do remetente para o destinatário.

• Erros de bit único
• Vários erros de bits
• Erros de explosão

Erros de bit único

A alteração feita em um bit em toda a sequência de dados é conhecida como “Erro de bit único”. No entanto, a ocorrência de erros de bit único não é tão comum. Além disso, este erro ocorre apenas em um sistema de comunicação paralelo porque os dados são transferidos bit a bit em uma única linha. Portanto, há mais chances de que uma única linha possa apresentar ruído.

Vários erros de bits

Na sequência de dados, se houver uma alteração em dois ou mais bits de uma sequência de dados de um transmissor para um receptor, isso é conhecido como “Erros de bits múltiplos”.

Este tipo de erro ocorre principalmente em redes de comunicação de dados do tipo serial e paralela.

Erros de explosão

A mudança do conjunto de bits na sequência de dados é conhecida como “Erro de burst”. Este tipo de erro de dados é calculado desde a alteração do primeiro bit até a última alteração do bit.

O que é detecção e correção de erros?

No sistema de comunicação digital, o erro será transferido de um sistema de comunicação para outro. Se esses erros não forem detectados e corrigidos, os dados serão perdidos. Para uma comunicação eficaz, os dados do sistema devem ser transferidos com alta precisão. Isso será feito primeiro identificando os erros e corrigindo-os.

A detecção de erros é um método de detecção de erros que estão presentes nos dados transmitidos de um transmissor para um receptor em um sistema de comunicação de dados.

Aqui, você pode usar códigos de redundância para encontrar esses erros, adicionando-os aos dados quando eles são transmitidos da fonte. Esses códigos são chamados de “códigos de detecção de erros”.

Três tipos de códigos de detecção de erros são:

• Verificação de paridade
• Verificação de Redundância Cíclica (CRC)
• Verificação de Redundância Longitudinal (LRC)

Verificação de paridade

• Também é conhecido como verificação de paridade.
• Possui um mecanismo econômico para detecção de erros.
• Nesta técnica, o bit redundante é conhecido como bit de paridade. Ele é anexado para cada unidade de dados. O número total de 1s na unidade deve ser par, o que é conhecido como bit de paridade.

Verificação de Redundância Longitudinal

Nesta técnica de detecção de erros, um bloco de bits é organizado em formato tabular. O método LRC ajuda a calcular o bit de paridade para cada coluna. O conjunto desta paridade também é enviado junto com os dados originais. O bloco de paridade ajuda a verificar a redundância.

Verificação de redundância Cíclica

A Verificação de Redundância Cíclica é uma sequência de redundância que deve ser anexada ao final da unidade. É por isso que a unidade de dados resultante deve ser divisível por um segundo número binário predeterminado.

No destino, os dados recebidos precisam ser divididos pelo mesmo número. Caso não haja resto, a unidade de dados é considerada correta e aceita. Caso contrário, indica que a unidade de dados foi danificada na transmissão e, portanto, deve ser rejeitada.

No código de Hamming, a fonte codifica a mensagem adicionando bits redundantes à mensagem. Esses bits redundantes são principalmente inseridos e gerados em determinadas posições da mensagem para realizar o processo de detecção e correção de erros.

História do código de Hamming

• O código de Hamming é uma técnica desenvolvida por RWHamming para detectar erros.
• O código de Hamming deve ser aplicado a unidades de dados de qualquer comprimento e utiliza a relação entre dados e bits de redundância.
• Ele trabalhou no problema do método de correção de erros e desenvolveu um conjunto cada vez mais poderoso de algoritmos chamado código de Hamming.
• Em 1950, ele publicou o Código de Hamming, hoje amplamente utilizado em aplicações como memória ECC.

Aplicação do código de Hamming

Aqui estão algumas aplicações comuns de uso do código de Hamming:

• Satélites
• Memória do computador
• Modems
• PlasmaCAM
• Conectores abertos
• Fio de blindagem
• Processador Embarcado

Vantagens do código de Hamming

• O método do código de Hamming é eficaz em redes onde os fluxos de dados são fornecidos para erros de bit único.
• O código de Hamming não apenas fornece a detecção de um erro de bit, mas também ajuda a recuar o bit que contém o erro para que ele possa ser corrigido.
• A facilidade de uso dos códigos de Hamming os torna mais adequados para uso em memória de computador e correção de erros únicos.

Desvantagens do código de Hamming

• Código de detecção e correção de erros de bit único. No entanto, se vários bits apresentarem erro, o resultado poderá resultar em outro bit que deveria estar correto para ser alterado. Isso pode fazer com que os dados tenham ainda mais erros.
• O algoritmo de código de Hamming pode resolver apenas problemas de bits únicos.

Como codificar uma mensagem no Código de Hamming

O processo usado pelo remetente para codificar a mensagem inclui as três etapas a seguir:

• Cálculo do número total de bits redundantes.
• Verificando a posição dos bits redundantes.
• Por último, calculando os valores desses bits redundantes.

Quando os bits redundantes acima são incorporados à mensagem, ela é enviada ao usuário.

Passo 1) Cálculo do número total de bits redundantes.

Suponhamos que a mensagem contenha:

• n– número de bits de dados
• p – número de bits redundantes que são adicionados a ele para que np possa indicar pelo menos (n + p + 1) estados diferentes.

Aqui, (n + p) representa a localização de um erro em cada uma das posições de bit (n + p) e um estado extra indica nenhum erro. Como p bits podem indicar 2^p estados, 2^p tem que pelo menos ser igual a (n + p + 1).

Passo 2) Colocando os bits redundantes em sua posição correta.

Os p bits redundantes devem ser colocados em posições de bits de potências de 2. Por exemplo, 1, 2, 4, 8, 16, etc.₁ (na posição 1), p₂ (na posição 2), p₃ (na posição 4), etc.

Passo 3) Cálculo dos valores do bit redundante.

Os bits redundantes devem ser bits de paridade, tornando o número de 1s par ou ímpar.

Os dois tipos de paridade são?

• O número total de bits na mensagem torna-se par e é chamado de paridade par.
• O número total de bits na mensagem que se torna ímpar é chamado de paridade ímpar.

Aqui, todo o bit redundante, p1, deve ser calculado como paridade. Deve cobrir todas as posições de bits cuja representação binária deve incluir um 1 na 1ª posição excluindo a posição de p1.

P1 é o bit de paridade para todos os bits de dados em posições cuja representação binária inclui um 1 na posição menos importante, não incluindo 1 Como (3, 5, 7, 9,….)

P2 é o bit de paridade para todos os bits de dados em posições cuja representação binária inclui 1 na posição 2 da direita, não incluindo 2 Como (3, 6, 7, 10, 11,…)

P3 é o bit de paridade para cada bit em posições cuja representação binária inclui um 1 na posição 3 da direita, não incluindo 4 Como (5-7, 12-15,…)

Descriptografando uma mensagem em código de Hamming

O receptor recebe mensagens que exigem recálculos para localizar e corrigir erros.

O processo de recálculo é feito nas seguintes etapas:

• Contando o número de bits redundantes.
• Posicionamento correto de todos os bits redundantes.
• Verificação de paridade

Passo 1) Contando o número de bits redundantes

Você pode usar a mesma fórmula para codificação, o número de bits redundantes

2^p ? n + p + 1

Aqui, o número de bits de dados ep é o número de bits redundantes.

Passo 2) Posicionando corretamente todos os bits redundantes

Aqui, p é um bit redundante que está localizado em posições de bits de potências de 2, por exemplo, 1, 2, 4, 8, etc.

Passo 3) Verificação de paridade

Os bits de paridade precisam ser calculados com base nos bits de dados e nos bits redundantes.

p1 = paridade(1, 3, 5, 7, 9, 11…)

p2 = paridade (2, 3, 6, 7, 10, 11… )

p3 = paridade(4-7, 12-15, 20-23… )

Resumo

• Os dados transmitidos podem ser corrompidos durante a comunicação
• Três tipos de erro de bit são 1) Erros de bit único 2) Erro de bits múltiplos 3) Erros de bit burst
• A alteração feita em um bit em toda a sequência de dados é conhecida como “erro de bit único”.
• Na sequência de dados, se houver uma alteração em dois ou mais bits de uma sequência de dados de um transmissor para um receptor, isso é conhecido como “Erros de bits múltiplos”.
• A mudança do conjunto de bits na sequência de dados é conhecida como “Erro de burst”.
• A detecção de erros é um método de detectar os erros que estão presentes nos dados transmitidos de um transmissor para um receptor em um sistema de comunicação de dados.
• Três tipos de códigos de detecção de erros são 1) Verificação de paridade 2) Verificação de redundância cíclica (CRC) 3) Verificação de redundância longitudinal (LRC)
• O código de Hamming é um código de linha útil para detecção de erros de até dois erros de bit imediatos. É capaz de erros de bit único.
• O código de Hamming é uma técnica desenvolvida por RWHamming para detectar erros.
• Aplicações comuns de uso do código de Hamming são memória de computador de satélites, modems, processador incorporado, etc.
• O maior benefício do método do código de Hamming é eficaz em redes onde os fluxos de dados são fornecidos para erros de bit único.
• A maior desvantagem do método do código de Hamming é que ele pode resolver apenas problemas de bits únicos.
• Podemos realizar o processo de criptografia e decodificação da mensagem com a ajuda do código de Hamming.