Correção de Erros
Recuperação de Erros
Uma vez que o erro tenha sido detectado e sua extensão identificada, é o momento de removê-lo do sistema. Existem duas técnicas gerais para realizar a recuperação de erros:
- Recuperação para trás ou por retorno (Backward Recovery) - Neste modelo, o estado do sistema é retornado a um estado anterior, na esperança de que este novo estado esteja livre de erros. Para isso, checkpoints periódicos são estabelecidos em um repositório estável. Quando algum erro é detectado, o sistema sofre uma volta (rollback) para o último checkpoint. Este método é bem geral e um dos mais usados, além de não depender muito da natureza da falha. A principal desvantagem é o overhead necessário, pois além de ser necessário criar checkpoints frequentemente, o rollback envolve certa computação pelo sistema.
- Recuperação para frente ou por avanço (Forward Recovery) - Neste modelo, nenhum estado anterior está disponível. Ao contrário, é feita uma tentativa de se “ir para frente”, e tentar tornar o estado livre de erros aplicando-se medidas corretivas. Conceitualmente é interessante pois não há overhead. Entretanto, na prática se torna difícil, pois depende de uma avaliação e suposições precisas sobre o estrago.
Paridade combinada
Combinando-se a paridade vertical (simples) com a paridade horizontal, temos uma análise bidimensional dos dados, permitindo assim que seja feita não apenas a detecção do erro, mas também a sua correção, uma vez que é possível localizar-se a alteração do bit.
Código de Hamming
Essa técnica adiciona bits de redundância (paridade) a um bloco de dados, permitindo a detecção de até dois bits de erro ou a correção de 1 bit. A adição dessa redundância ocorre nos bits de ordem com potência de dois (bits 1, 2, 4, 8, …). Para se determinar a quantidade de bits adicionais (bits de Hamming), deve-se obedecer a seguinte regra: d + p <= 2^p - 1, onde d é o número de bits de dados e p o número de bits de paridade (Hamming). O limite máximo de bits de dados que determinado número de bits de Hamming podem analisar é representado pela condição de igualdade. O código é representado pela dupla (c,d), onde c representa o número total de bits (dados + Hamming) e d representa o número de bits de dados.
O algoritmo funciona da seguinte forma: para cada bit de dado com o valor 1, escreve-se em binário a sua posição. Por exemplo, se for o bit 3, representamos 011, se for o 5, 101. Em seguida, faz-se o XOR entre as posições, 2 a 2. O resultado final identifica o valor dos bits de Hamming, em ordem invertida. Por exemplo, se o resultado for 100, significa que o primeiro bit de Hamming é 0, o segundo também, e o terceiro é 1.
Na decodificação, realiza-se um processo semelhante. Para cada bit com valor 1, escreve-se sua posição em número binário e aplica-se a operação XOR aos valores obtidos. Se o resultado for 0, não houve erros na transmissão, caso contrário, o resultado representa a posição em que se encontra o erro. Por exemplo, se o resultado for 101, quer dizer que o bit 5 está incorreto.
Outra possibilidade de análise é feita utilizando diagramas de Venn, onde cada bit representa uma interseção entre os conjuntos e os bits de Hamming são os bits de paridade (par) adicionados para cada conjunto. Numa mensagem com 4 bits, por exemplo, temos 3 conjuntos e 3 bits de Hamming. O problema dessa análise é que torna-se muito complexo trabalhar com mais de 3 conjuntos, devido à dificuldade de visualização das interseções entre eles.
Vamos exemplificar com uma mensagem de 8 bits a ser enviada, com 4 bits de Hamming. Considere a mensagem m1m2m3m4m5m6m7m8 a ser transmitida. A esse dado de 8 bits, vamos acrescentar 4 bits, formando o seguinte código de Hamming de 12 bits: x1x2x3x4x5x6x7x8x9x10x11x12, onde x3 = m1, x5 = m2, x6 = m3, x7 = m4, x9 = m5, x10 = m6, x11 = m7 e x12 = m8. Os 4 bits adicionais x1, x2, x4 e x8 são calculados como é mostrado a seguir:
x1 = x3 ⊕ x5 ⊕ x7 ⊕ x9 ⊕ x11
x2 = x3 ⊕ x6 ⊕ x7 ⊕ x10 ⊕ x11
x4 = x5 ⊕ x6 ⊕ x7 ⊕ x12
x8 = x9 ⊕ x10 ⊕ x11 ⊕ x12
Para verificar os bits recebidos, suponha que seja recebida a mensagem y1y2y3y4y5y6y7y8y9y10y11y12. Fazemos então os seguintes cálculos:
k1 = y1 ⊕ y3 ⊕ y5 ⊕ y7 ⊕ y9 ⊕ y11
k2 = y2 ⊕ y3 ⊕ y6 ⊕ y7 ⊕ y10 ⊕ y11
k3 = y4 ⊕ y5 ⊕ y6 ⊕ y7 ⊕ y12
k4 = y8 ⊕ y9 ⊕ y10 ⊕ y11 ⊕ y12
Se k1 = k2 = k3 = k4 = 0, não houve nenhum erro na transmissão. Caso contrário, a sequência k4k3k2k1 determina a posição do bit errado. Por exemplo, k4k3k2k1 = 0111, o bit y7 está errado.
Para calcular a eficiência do uso dos bits basta utilizarmos a seguinte fórmula: R = (2^p - p - 1)/(2^p - 1).
