Como corrigir uma mensagem usando o Código Hamming

Question

Então eu quero trabalhar neste projeto de verão para corrigir erros em uma transmissão de mensagem usando o Código Hamming, mas eu não consigo descobrir como ele realmente funciona. Eu li muitos artigos on-line, mas eu realmente não entendo o algoritmo. Alguém pode explicar em termos simples?

Graças.

Answer 1

É tudo sobre Hamming distância .

A distância de Hamming entre dois valores de base-2 é o número de bits na qual eles diferem. Então, se você transmitir um, mas eu recebo B, então o número de bits que deve ter sido comutado na transmissão é a distância de Hamming entre A e B.

códigos

Hamming são úteis quando os bits em cada palavra de código são transmitidos de alguma forma separadamente. Nós não nos importamos se eles são de série ou em paralelo, mas eles não são, por exemplo combinados em um valor analógico representando vários bits, ou comprimido / criptografado após a codificação.

Assim, cada bit é independentemente (ao acaso com alguma probabilidade fixa), seja recebido correctamente, ou invertido. Assumindo que a transmissão é bastante confiável, a maioria dos bits são recebidos corretamente. Então erros em um pequeno número de bits é mais provável, e os erros simultâneos em grandes números de bits são improváveis.

Assim, um código de Hamming, normalmente aponta para erros de 1 bit corretos, e / ou para detectar erros de 2 bits (ver artigo de Wikipedia para obter detalhes sobre os dois principais tipos). Códigos que corrigir / detectar erros maiores podem ser construídos, mas AFAIK não são utilizados como muito.

O código funciona uniformemente espaçamento entre os pontos de código no "espaço Hamming", o que em termos matemáticos é o espaço métrico constituído por todos os valores do tamanho da palavra relevante, com Hamming distância como a métrica. Imagine que cada ponto de código é cercado por um pouco de "zona tampão" de valores inválidos. Se um valor é recebido que não é um ponto de código, em seguida, um erro deve ter ocorrido, porque apenas pontos de código válidos são sempre transmitidos.

Se um valor na zona tampão é recebido, em seguida, no pressuposto de que ocorreu um erro de 1 bit , o valor que foi transmitida devem ser distância um em relação ao valor recebido. Mas porque os pontos de código estão espalhados, há apenas um ponto de código tão perto. Por isso é "corrigida" a esse ponto de código, em razão de que um erro de 1-bit é mais provável que o erro maior que seria necessário para qualquer outro ponto de código para produzir o valor recebido. Em termos de probabilidade, a probabilidade condicional que lhe enviou o ponto de código próxima é maior do que a probabilidade condicional que você envia qualquer outro ponto de código, uma vez que recebi o valor que eu fiz. Então eu acho que você enviou a uma vizinha, com uma certa confiança com base na confiabilidade da transmissão e o número de bits em cada palavra.

Se um valor inválido for recebido que é equidistante de dois pontos de código, então eu não posso dizer que um é mais provável que seja o verdadeiro valor do que o outro. Então eu detectar o erro, mas não posso corrigi-lo.

Obviamente erros 3 bits não são corrigidos por um código SECDED Hamming. O valor recebido está mais longe do valor que você realmente enviou, que é para algum outro ponto de código, e eu erroneamente "correta" para o valor errado. Então você quer uma transmissão necessidade bastante confiável, que você não se preocupa com eles, ou então você precisa de detecção de erro de nível superior, bem como (por exemplo, um CRC mais de uma mensagem inteira).

Answer 2

Especificamente a partir Wikipedia , o algoritmo é a seguinte:

1. N os bits a partir de 1:. Bit 1, 2, 3, 4, 5, etc
2. Escreva os números de bits em binário. 1, 10, 11, 100, 101, etc.
3. Todas as posições de bits que são potências de dois (têm apenas um 1 bit na forma binária de sua posição) são bits de paridade.
4. Todas as outras posições de bit, com bits dois ou mais bits 1 na forma binária de sua posição, são dados.
5. Cada bit de dados é incluída num conjunto único de 2 ou mais bits de paridade, como determinado pelo formato binário da sua posição de bit.
   1. 1 bit de paridade cobre todas as posições de bit que possuem o bit menos significativo:. 1 bit (o bit de paridade em si), 3, 5, 7, 9, etc.
   2. bit de paridade 2 cobre todas as posições de bit que possuem o segundo bit menos significativo conjunto:. 2 bits (o bit de paridade em si), 3, 6, 7, 10, 11, etc
   3. bit de paridade 4 cobrir todas as posições de bits que têm o terceiro set bit menos significativo:. Pedaços 4-7, 12-15, 20-23, etc
   4. 8 bit de paridade cobre todas as posições de bit que possuem o quarto bit menos significativo conjunto:. Os bits 8-15, 24-31, 40-47, etc.
   5. Em geral, cada bit de paridade abrange todos os bits onde o binário e da posição de paridade e a posição do bit é diferente de zero.

Answer 3

O wikipedia artigo explica muito bem.

Se você não entender um aspecto específico do algoritmo, então você vai precisar reformular (ou detalhe) a sua pergunta, para que alguém possa dirigir sua parte específica do problema.