Códigos de Hamming e Reed-Solomon

Prévia do material em texto

10.1 Códigos de Hamming
O código de Hamming foi muito usado para o controle de erros nos sistemas de comunicações
digitais. Esse código opera sobre bits individuais. Nesse código, os bits da palavra de código são
numerados consecutivamente da esquerda para a direita, onde o bit mais da esquerda é o 1, o próximo
bit imediatamente à sua direita é 2, e assim por diante. Os bits que são potência de dois (1,2,4,8,16,...)
são os bits de verificação, os demais bits (3,5,6,7,9,...) são preenchidos com os m bits de dados. Cada
bit de verificação força a paridade de algum conjunto de bits a ser par ou ímpar. Um bit somente é
verificado por aqueles bits de verificação que ocorrem em sua expansão, ou seja, o bit 11 é verificado
pelos bits 1, 2 e 8. 
Nesse exemplo, o código resultante é de distância igual a 3, ou seja, pode corrigir erros simples
ou detectar erros duplos. O receptor, ao receber uma palavra de código, refaz os cálculos do bit de
verificação, incluindo os valores dos bits de verificação recebidos. Se os bits de verificação estiverem
corretos, e se a paridade for par, o resultado de cada verificação deve ser igual a 0, e a palavra de
código é válida, caso contrário, se os resultados da verificação não for 0, um erro foi detectado. Este
conjunto de resultados é denominado síndrome de erro, e é usada para localizar e corrigir o erro. A
figura 31 mostra um exemplo de erro de um bit.
 10.2 Códigos de Reed-Solomon
Os códigos de Reed-Solomon operam sobre m símbolos de bit, diferentemente dos códigos de
Hamming, que operam sobre bits individuais, por esse motivo, esse código é mais complicado do que o
código de Hamming. Nos códigos de Reed-Solomon, cada polinômio de grau n é determinado
unicamente por n + 1 pontos. Como exemplo, podemos imaginar dois pontos de dados que representam
uma linha, estes dois pontos são enviados com mais dois pontos de verificação escolhidos para que se
encontrem na mesma linha. Se ocorrer erro em um desses pontos, pode-se recuperar os dados passando
uma linha pelos pontos recebidos. Os três pontos sem erros estarão na linha, e o ponto com erro não
estará. Encontrando a linha, o erro será corrigido.
Esse código funciona de maneira semelhante ao exemplo citado, porém, são definidos como
polinômios que operam em campos finitos. Para símbolos de m bits, as palavras de código possuem 2m
– 1 símbolos de comprimento. Um jeito mais simples, é tornar m = 8, no qual os símbolos são bytes,
Figura 31: Exemplo de um código de Hamming (11,7) corrigindo um único erro.
	10 Códigos Corretores de Erro
	10.1 Códigos de Hamming
	10.2 Códigos de Reed-Solomon