Detecção e correção de erros for dummies

O assunto detecção e correção de erros parece algo completamente inacessível à maioria das mentes, incluindo muita gente que trabalha com informática. Uma sugestão didática é começar a abordar o assunto usando um animal que todo mundo conhece: dígitos verificadores de contas bancárias, documentos, etc.

Todo mundo já viu um dígito verificador. Na conta bancária: 12345-7. No CPF tem dois até: 111.111.111-80. Eles parecem feitos para encher o saco, pois quase sempre são muito diferentes dos demais números. São difíceis de lembrar; você lembra de todos os números exceto o dígito, e não pode executar uma operação ou completar o formulário...

O dígito verificador (abreviado DV) existe para "pegar" erros de digitação e transcrição, de forma simples e eficiente. Via de regra, o DV é sempre resultado de um cálculo feito em cima dos números anteriores. Ou seja, o DV não adiciona informação nova ao código, ele sempre pode ser calculado de novo, desde que você saiba o algoritmo.

Supondo que o DV seja a soma dos dígitos do código original, o código 1234 torna-se 1234-0. (4+3+2+1=10, então pegamos o último dígito da soma -- "módulo 10").

Se digitarmos 4234-0, o cálculo do DV mostra imediatamente que este código é inválido, pois 4+2+3+4=13. O último dígito (3) não bate com o DV digitado (0) portanto algum número tem de estar errado.

Quantos erros um dígito verificador pode pegar?

Assumindo um algoritmo ideal, um DV pega qualquer erro de digitação simples, ou seja, onde apenas um número foi digitado erradamente. No caso dos CPFs, que têm 2 DVs, a capacidade teórica é de pegar quaisquer erros de até 2 números. Três dígitos, pega até 3 erros. É simples assim.

No caso de erros mais graves, ficamos na mão da sorte. Um DV deixará passar um entre dez (10%) de erros aleatórios. O motivo é muito simples: errando dois números, há 10% de chance de "colidirmos" com outro código perfeitamente válido. É como se digitássemos por engano a conta bancária de um amigo no NetBanking em vez da nossa; não há como o DV pegar um erro desse tipo.

O CPF possui 2 DVs, então ele é muito mais resistente a erros de muitos dígitos. Apenas um em cem (1%) desses erros passariam, pelo mesmo motivo: 1% de chance do CPF digitado errado coincidir perfeitamente com o CPF de outra pessoa.

Quanto mais dígitos verificadores, mais forte fica a resistência a erros de "burst" (rajada) onde diversos números são digitados erradamente.

Como é possível o dígito veriicador detectar erros?

A mecânica da detecção de erros é na verdade muito simples. Vamos considerar um código de 3 dígitos, digamos a conta bancária de uma agência pequena. Com 3 dígitos, temos 1.000 possíveis contas bancárias.

Adicionando um dígito verificador, a conta passa a ter 4 dígitos, perfazendo um total de 10.000 possíveis códigos. Só que, desses 10.000, apenas 10% (1.000) são realmente válidos, pois correspondem a um código principal + DV válido.

Em havendo (relativamente) poucas contas bancárias válidas numa faixa numérica relativamente grande, a chance de uma conta válida ser digitada por engano diminui muito. Isso garante que, para um DV, 90% de qualquer erro vai ser pego.

É interessante mencionar que este poder de detecção de erros independe do tamanho código, Se o código tiver 15 dígitos, o DV de 2 dígitos continua sendo capaz de pegar até 2 erros sem furo. Claro que um código de 15 dígitos tem muito mais chance de ser digitado errado...

Já a garantia que 1 DV pega 100% dos erros de 1 dígito, ou 2 DVs pegam 100% dos erros de 1 ou 2 dígitos, é um pouco mais difícil de provar, depende de análise combinatória.

Ressaltando novamente, estas capacidades do DV em pegar erros são os máximos possíveis, e assumem um algoritmo de cálculo de DV ideal. Achar esse algoritmo "ideal" é um outro problema.

Como calcular um dígito verificador?

Não é fácil achar uma fórmula de DV que entregue a proteção contra erros que foi prometida nos parágrafos anteriores. Por outro lado, é facílimo achar fórmulas imprestáveis para DV. Exemplo:

DV = último dígito do código original
1234 => 1234-4

Esta fórmula hipotética é obviamente ruim, pois só pega erros de digitação cometidos no último dígito principal. Além disso, todos os códigos válidos ficarão parecidos: 1234-4, 2344-4, 4444-4...

DV = soma dos dígitos originais, módulo 10
1234 => 1234-0

Este DV é muito melhor que o outro, pois seu valor depende de todos os dígitos. A troca de qualquer dígito gera um código inválido.

Porém ele tem uma fraqueza imperdoável: a inversão de dois dígitos passa batida. Isto é um problema pois a inversão é um erro de digitação muito, muito comum. Note que 1234-0, 4321-0, 1324-0 e 1243-0 são todos códigos válidos usando o algoritmo de somas.

Uma versão real do algoritmo módulo-10 usa um truque para detectar inversões: multiplica cada dígito original por 1 ou por 2, alternadamente, contando da direita para a esquerda. Assim:

1234 => 1*2 + 2*1 + 3*2 + 4*1 = 14 => 1234-4
1243 => 1*2 + 2*1 + 4*2 + 3*1 = 15 => 1243-5

Este algoritmo é consideravelmente mais forte que os anteriores, mas seria ainda melhor se cada dígito fosse multiplicado por um peso diferente. É exatamente isto que o famoso algoritmo "módulo-11" faz: multiplica os dígitos por 2, 3, 4, 5, 6, 7, e só então retornando a 2.

A força do módulo-11 aproxima-se muito da capacidade máxima de correção de um dígito verificador, e por este motivo é o mais utilizado.

O módulo, ou seja, o resto da divisão, é a ferramenta mais utilizada como geradora de DVs pois ela tem diversas vantagens. Se o divisor é um número primo, ela "espalha" bem os DVs, evitando que se tornem repetitivos ou previsíveis. Por sua própria natureza, o módulo retorna um resultado limitado a um campo, ou seja, uma faixa de números. O módulo-11 retorna números de 0 a 10, nem mais nem menos.

Existem outros tipos de DV mais exóticos, que levam em conta os erros de digitação mais comuns etc. Considerando que o bloco numérico é igual em todo computador, faria sentido proteger mais fortemente contra erros de digitação mais comuns. O número 1 vai ser mais facilmente por um 4 do que por um 9. Fórmulas como módulo-11 não levam isto em conta.

Mas como tais DVs "exóticos" são baseados parcialmente em tabelas, não apenas numa única fórmula simples, normalmente não vale o esforço de implementação.

Proteger contra Murphy e/ou contra Maquiavel?

É importante entender que dígitos verificadores protegem de erros de boa-fé, mas não protegem de fraudes. Há três motivos básicos para isto:

a) a fórmula do DV é publicamente conhecida, assim qualquer um pode recriar o DV sem conhecê-lo;
b) e as fórmulas comumente utilizadas para DV podem ser calculadas "de trás para frente", ou seja, dado um dígito verificador (digamos, 9), é fácil chegar a um código válido (XXXXX-9).
c) o número de dígitos verificadores normalmente utilizados (1 ou 2) é insuficiente para proteger contra a procura de códigos válidos por tentativa-e-erro.

Existem formas de resolver os 3 problemas acima e chegar a um super-DV que proteja contra fraude. Um código de correção de erros que também seja capaz de proteger contra fraude denomina-se "hash".

Mas eu nunca vi tal "hash" ser usado com números decimais. Por outro lado, hashes baseados em números binários como MD5 ou SHA1 são comuns. Ainda assim, vou mostrar as técnicas básicas de tornar um DV "inquebrável".

Uma tática é calcular o DV repetidamente, desprezando os resultados intermediários. Exemplo, usando módulo 11:

1234 => 1234-3
12343 => 12343-9
12349 => 12349-8
1234-8

Calculamos o DV em três "rounds" e chegamos a um DV final (8) completamente diferente do original (3). Executar esse cálculo cascateado de trás para frente é consideravelmente mais difícil do que a fórmula módulo 11 singela. Infelizmente, ainda é possível invertê-lo.

Hashes como MD5 usam cálculos muito mais apropriados que um módulo-11 para determinar os "dígitos verificadores", de modo a dificultar para valer o cålculo inverso.

Outra tática para reforçar o DV é adicionar o comprimento do código como um dígito extra, calcular o DV, e omitir o comprimento no resultado final:

1234 => 12344 => 12344-7 => 1234-7

Para inverter o cálculo, o atacante agora terá de levar também em conta o tamanho original do código. Se ele não sabe esse tamanho original, já dificulta bastante.

A terceira tática, menos geral por exigir segredo de um elemento, mas muito utilizada, é adicionar um sufixo "secreto" ao código. Supondo que nosso sufixo secreto é 666:

1234 => 1234666 => 1234666-2 => 1234-2

Se o atacante não souber qual é o sufixo secreto, vai ficar bem difícil para ele descobrir como "fabricar" dígitos verificadores a partir dos códigos originais "pelados". Ele também não conseguirá gerar um código válido a partir de um dígito conhecido.

Um "hash" calculado com base numa mensagem que foi "temperada" com um prefixo ou sufixo secreto, denomina-se MAC (Message Authentication Code), com aplicações muito importantes em criptografia.

Naturalmente, todos os exemplos acima usam apenas um dígito verificador, o que é insuficiente para uma proteção séria contra fraudes. Uma proteção efetiva exigiria 40 dígitos ou mais, o que equivale aos 128 bits do MD5. E sufixar uma conta bancária de 5 dígitos com um DV de 40 números não é exatamente algo prático, o que explica a pouca popularidade da técnica no reino dos números decimais...

Correção de erros

Às vezes, não basta detectar erros, é preciso corrigí-los sem exigir uma segunda digitação ou transcrição. Por exemplo, a informação mandada por um míssil, satélite, sonda espacial, bóia ou balão metereológico nunca se repete; é preciso garantir que a informação original possa ser reconstruída mesmo na presença de erros.

Parece bruxaria, mas é perfeitamente possível e nem tão difícil de entender. A idéia básica é utilizar muitos dígitos verificadores, de modo que possamos determinar a "distância" entre o valor "errado" e um valor correto, e assim assumir que a informação original era o valor correto mais próximo.

A capacidade máxima de correção de erro de um código é: metade do número de dígitos menos um. Um DV de três dígitos é capaz de corrigir erros de até 1 dígito -- embora, como já vimos, seja capaz de detectar erros de até 3 dígitos com perfeição. Um DV de 2 dígitos não consegue corrigir nenhum erro, embora detecte quase todos...

Construir um código de correção de erros não é tão difícil. Uma forma boba seria repetir duas vezes o mesmo código, ou seja, transmitir a informação original três vezes:

1234 => vira 1234-1234-1234

Neste código, qualquer erro de 1 dígito pode ser corrigido. Supondo que recebemos o código com erros, desta forma:

1234-1235-1234

Está claro que há erro, mas nós não sabemos se o erro é de apenas um dígito. Correção de erros exige um passo de fé: precisamos estimar um teto para a quantidade e erros.

Se partirmos do princípio que há apenas um dígito errado, está claro que o valor original era 1234, pois dois trechos "votam" em 1234, enquanto apenas um "vota" em 1235.

Por outro lado, se recebêssemos o código assim:

1234-1235-1237

fica difícil determinar o valor original pois não temos como determinar qual é o valor correto "mais próximo". Só sabemos que o código está errado e que o erro está no quarto dígito, mas não podemos recuperar o valor correto.

Uma coisa é certa: o algoritmo acima é muito fraco, pois adicionamos 8 dígitos a mais e apenas 2 dígitos errados já frustraram a correção do erro. Com 8 dígitos, uma fórmula realmente boa conseguiria consertar até (8-1)/2 = 3 dígitos errados, em quaisquer posições.

Uma fórmula "boa" levaria em consideração a "distância hamiltoniana" entre os números. Por exemplo, 999 é numericamente próximo de 1000, mas todos os dígitos são diferentes. Nenhum erro de digitação não-intencional transformaria 999 em 1000. Por outro lado, 1000 e 11000 estão muito distantes, mas basta repicar o 1 e a confusão está feita. Um bom código procura levar isso em conta, equilibrando (e diminuindo) as chances de erros entre quaisquer números válidos.

Finalmente, não adianta adicionar DVs a esmo, isto não é suficiente para corrigir erros. Não adianta adicionar três DVs calculados com módulo-11 e esperar que se possa corrigir quaisquer erros de 1 dígito a partir disso. A fórmula tem de visar o objetivo de corrigir erros.

De decimais para binários

Tudo que foi dito acima vale também para os números binários. Só que, usando números binários, temos uma grande vantagem: o número de dígitos cresce muito mais rapidamente. Um dígito decimal corresponde grosso modo a três dígitos binários. Assim, o nosso número de conta 1234-0, de 5 dígitos, vira um número de 18 bits em binário -- 14 para o número principal e 4 para o dígito verificador.

E por que isto é uma vantagem? Porque as garantias de um DV, ou seja, de um código de correção de erro, dependem muito do número de dígitos, não interessa se são decimais ou binários. E é fácil lidar com mensagens muito grandes em um computador, com grande número de bits.

Claro que isto não faz milagre. Supondo o exemplo da conta 1234-0 em binário, com 4 bits de DV, que chamaremos doravante de código de correção de erros (EDC), o poder de fogo é o seguinte:

* correção de 100% dos erros de até 4 bits
* deixa passar até 6% dos erros de mais de 4 bits

Como 4 bits corresponde a pouco mais de um dígito decimal, e 6% não é tão melhor que 10%, a proteção é mais ou menos a mesma que um DV decimal.

A vantagem começa a aparecer quando usamos um algoritmo de EDC de verdade, como o CRC-32, muito comum no mundo da informática. Ele tem 32 bits de comprimento, ou seja, detecta 100% dos erros de até 32 bits. Se pespegarmos um CRC-32 na conta bancária, que só tem 14 bits, garantimos que NENHUM erro passará despercebido.

Além disso, o CRC-32 só deixa passar 1 em cada 4 bilhões de erros aleatórios, envolvendo qualquer número de bits.

O CRC-32 não protege contra Maquiavel, ou seja, ele não serve para proteger contra fraude. Neste caso, podemos usar os algoritmos MD5 ou SHA1, que fornecem códigos de 128 e 160 bits respectivamente. MD5 e SHA1 são hashes de qualidade criptográfica e podem ser utilizados para gerar MACs.

Da mesma forma, existem diversos algoritmos de correção de erros (ECCs), como o Reed-Solomon que é utilizado em CDs, e permite que um CD seja tocado perfeitamente mesmo depois de alguns riscos.

As mesmas regras de contagem de dígitos também valem para correção de erros em números binários. Um código ECC de 32 bits consegue corrigir até (32-1)/2 = 15 bits errados.

Também vale a regra que o tamanho da mensagem original não importa. Não interessa se a mensagem original tem 16 bits ou 16000 bits. Um ECC de 32 bits corrige até 15 erros em ambas, e detecta quaisquer erros de 32 bits em ambas. Assim, mensagens muito grandes podem ser protegidas de forma muito "barata", com poucos bits.

Exceto pela paridade, que é um código de correção de erros de 1 bit, todas as fórmulas de EDC, ECC, hash etc. para números binários são bastante complicadas.

Assim como no caso dos dígitos verificadores decimais, o "coração" de cada fórmula costuma ser o módulo, ou seja, o resto de uma divisão. Mas no caso de números binários, por diversas razões (inclusive facilidade de implementação em hardware), é costumeiro usar divisão de polinômios num campo, e não a simples divisão de números naturais.

Por exemplo o CRC-32 é definido pelo seu "polinômio gerador", que será o divisor da operação módulo. Como o CRC-32 tem 32 bits, é necessário que o divisor possua 33 bits, de modo que o resto da divisão tenha até 32 bits. A escolha desses divisores é objeto de pesquisa ativa, pois o "poder de fogo" da detecção de erros depende da boa escolha do divisor.