Reed-Solomon usando números decimais
Reed-Solomon usando números decimais
A compreensão de códigos de detecção de erros fica bem mais fácil quando estabelecemos um paralelo com dígitos verificadores, que é algo com que todo mundo está acostumado a lidar. Qual o desenvolvedor de software que nunca implementou validação de CPF, ou um dígito verificador módulo-11?
O mesmo não acontece com códigos de correção de erros. Noves fora códigos simples como o Hamming, não existe material que tente apresentar um código Reed-Solomon usando apenas números decimais. É esta lacuna que este texto pretende cobrir.
Se você está procurando uma implementação de "dígito verificador que corrige erros", pode ir direto para esta página do GitHub onde ofereço uma implementação em Python.
A geração de um código Reed-Solomon é semelhante ao código CRC, e também é semelhante ao cálculo de um dígito verificador. Toda a aritmética dos cálculos é modular, ou seja, é a "aritmética dois ponteiros do relógio", onde só existem inteiros e igualdades absurdas como 11+2=1 são verdadeiras.
No relógio, o "campo" de valores possíveis vai de 0 a 11, mas aritmética modular com 12 elementos não forma um campo; forma apenas um anel. Precisamos de um campo de Galois, cujo número de elementos é primo ou potência de primo. O mais próximo de 10 é 11, então adotamos o campo GF(11).
Por que não existem campos GF(12), ou GF(10)? Uma razão é que certos truques só funcionam num campo de Galois. Em GF(11), multiplicar qualquer número positivo por 1, 2, 3... permite gerar todos os demais números do campo. Exemplo que usa o número 3 como gerador:
3 x 1 = 3 3 x 2 = 6 3 x 3 = 9 3 x 4 = 12 % 11 = 1 3 x 5 = 15 % 11 = 4 3 x 6 = 18 % 11 = 7 3 x 7 = 21 % 11 = 10 3 x 8 = 24 % 11 = 2 3 x 9 = 27 % 11 = 5 3 x 10 = 30 % 11 = 8 3 x 11 = 33 % 11 = 0 3 x 12 = 36 % 11 = 3 ...
Na aritmética do relógio, o truque acima só funciona quando o gerador não divide 12. Outro truque do campo de Galois é gerar os elementos positivos usando potenciação:
2 ^ 0 = 1 2 ^ 1 = 2 2 ^ 2 = 4 2 ^ 3 = 8 2 ^ 4 = 16 % 11 = 5 2 ^ 5 = 32 % 11 = 10 2 ^ 6 = 64 % 11 = 9 2 ^ 7 = 128 % 11 = 7 2 ^ 8 = 256 % 11 = 3 2 ^ 9 = 512 % 11 = 6 2 ^ 10 = 1024 % 11 = 1 2 ^ 11 = 2048 % 11 = 2 ...
Mesmo num campo de Galois, nem todo número positivo é um gerador sob potenciação. No caso de GF(11), são geradores: 2, 6, 7 e 8. A potenciação de geradores é importante pois permitirá simplificar brutalmente equações onde há potenciação envolvida.
O inverso da potenciação é o logaritmo discreto. Por exemplo: num campo GF(11) e gerador 2, o logaritmo discreto de 5 é 4, pois, conforme a memória de cálculo acima, 2^4=5. Calcular o logaritmo discreto é difícil, porém os campos utilizados em Reed-Solomon são pequenos e podemos usar uma tabela.
Existem muitas formas de calcular o código RS. A maioria das documentações faz uso de códigos BCH, por ser voltada a números binários. No nosso caso, podemos adotar o método "clássico", sugerido pelos próprios autores, que se parece bastante com o dígito verificador módulo-11.
Em vez de ficar explicando longamente, vou linkar uma planilha do Google Sheets, onde você pode ver as fórmulas de cálculo diretamente. Clique aqui para abrir.
Na planilha de exemplo, a mensagem original é o número 3141592, com 7 símbolos. Desejamos calcular mais 3 dígitos verificadores, obtendo assim um código que detecte todos os erros de até 3 dígitos, e corrija erros de 1 dígito.
A fórmula para cada dígito do código RS, para a mensagem 3141592, é um polinômio cujos coeficientes são os símbolos da mensagem:
3*x^7 + 1*x^6 + 4*x^5 + 1*x^4 + 5*x^3 + 9*x^2 + 2*x^1
Na planilha, calculamos cada termo do polinômio em separado (bloco de células C5:I7), e a soma de cada linha forma um dígito RS (coluna J). Todas as fórmulas usam a função MOD(x,11) pois tudo é feito sob aritmética modular.
O valor de "x" no polinômio acima é diferente para cada dígito RS, e deve obedecer a alguma seqüência ordeira; o artigo original sugere várias. Adotamos uma seqüência de potências do gerador 2: 2^0, 2^1 e 2^2, que resultam simplesmente em 1, 2 e 4 que estão no bloco B5:B7 lilás. O uso desta seqüência em particular vai nos ajudar mais tarde.
(Analisando em retrospecto, o ideal seria começar a seqüência em 2^1, pois isto garante que o primeiro dígito detecte erros de 'swap', muito comuns em digitação. É o tipo de consideração que não se aplica a um código binário, mas é relevante num código decimal em que a maior parte dos erros será introduzida por fatores humanos.)
Note que o valor de "x" é novamente elevado a diversas potências no polinômio, de modo que ele continua funcionando como gerador, produzindo uma seqüencia bem espalhada. Uma pequena mudança na mensagem muda completamente os dígitos RS calculados.
Apesar de termos invocado os malditos polinômios, na verdade é tudo muito parecido com o algoritmo do dígito verificado módulo-11. Até aqui, a única grande diferença é que nosso código RS tem 3 "dígitos verificadores" em vez de um.
Tanto em nosso código RS quanto um dígito verificador, o dígito pode assumir 11 valores possíveis, inclusive o número "10". Isto é esperado, já que o campo tem 11 elementos. No caso do módulo-11, algumas implementacões usam "X" para representar o 10, porém a maioria simplesmente usa 0 ou 1 no lugar. (Se você já se perguntou por que contas do Banco do Brasil têm às vezes um "X" no dígito verificador, eis a resposta.)
De acordo com o exemplo da planilha, nosso código RS ficou em 313, então a mensagem final a ser transmitida será 3141592-313.
Ao receber uma mensagem com código RS, a primeira coisa é verificar se há erros. O método é o mesmo do CRC e do dígito verificador: repetir o mesmos cálculo feito no lado transmissor, e ver se algum dígito RS ficou diferente.
Na planilha, você pode alterar algum número da faixa C10:I10 para simular um erro. Supondo que a mensagem recebida seja 3141692-313, o cálculo no receptor resulta em 491, diferente de 313, então temos erros. Note que todos os dígitos mudaram. Esta mudança em todos os dígitos não é 100% garantida, mas é quase sempre o que acontece.
E se o erro fosse no próprio código RS? Por exemplo, se a mensagem recebida fosse 3141592-333? Neste caso, o cálculo na recepção nos diria que o código RS deveria se 313 em vez de 333. Há uma boa chance do erro estar no código, não na mensagem. Se o algoritmo a seguir falhar, podemos considerar esta hipótese.
Voltando à mensagem errada 3141692-313, calculada 491. Para descobrir a posição e a magnitude do erro, começamos pela síndrome. A síndrome é a diferença entre os códigos RS recebido e calculado. A conta é feita dígito a dígito, sem empréstimo ou transporte:
4 - 3 = 1 9 - 1 = 8 1 - 3 = -2 = 9 (módulo 11)
A síndrome 189 é o código RS da mensagem hipotética 0000100, entre outras. Note que 0000100 é exatamente a diferença entre a mensagem recebida 3141692 e a original 3141592, calculada dígito a dígito, sem transporte nem empréstimo. 0000100 nos informa tanto a magnitude do erro (um) quanto a posição do mesmo (terceira casa).
Ou seja, existe um forte "parentesco" entre a síndrome e o erro da mensagem. O objetivo agora é descobrir o valor do erro com base na síndrome. Isto não é tão simples pois existem inúmeras mensagens cujo código RS é igual a 189.
Ah, nós sabemos de mais uma coisa. O valor do erro só tem um dígito diferente de zero. Nosso código RS tem três dígitos, então só pode corrigir um erro. Neste caso em particular, só precisamos testar 63 valores diferentes. Se nenhum desses valores possuir um código RS igual a 189, significa que há dois ou mais erros, e não podemos corrigí-los.
Esta busca exaustiva não é prática quando o código RS pode corrigir múltiplos erros. Neste caso, temos de fazer do jeito certo, usando a matemática.
A técnica básica é montar um sistema de equações com base no polinômio do valor do erro. Se podemos corrigir 5 erros, o polinômio teria 5 termos. No nosso humilde exemplo, só podemos corrigir até 1 erro, então só precisamos de um termo:
a * x ^ b a = magnitude do erro
b = posição do erro
Quando codificamos a mensagem, calculamos cada dígito RS usando um valor diferente para "x": 1, 2 e 4. Faremos o mesmo agora, só que já sabemos o resultado, que é a síndrome. A incógnita é o polinômio da mensagem:
a * (1) ^ b = 1 a * (2) ^ b = 8 a * (4) ^ b = 9
Para "n" incógnitas, precisamos de um sistema de "n" equações ou mais. No sistema acima, temos as incógnitas "a" e "b", e três equações, então já sabemos que podemos descobrir "a" e "b". Só não sabemos como.
Se o código RS tivesse 4 dígitos e quiséssemos achar 2 erros, o polinômio teria dois termos e quatro incógnitas (a, b, c, d). A síndrome teria 4 dígitos, e formaríamos um sistema de equações com 4 linhas e 4 incógnitas.
Voltando ao sistema de equações do exemplo, o valor de "a" está particularmente fácil de resolver:
a * (1) ^ b = 1 a = 1
Agora vamos substituir o valor de "a" numa outra equação para achar "b":
a * (2) ^ b = 8 1 * 2 ^ b = 8 2 ^ b = 8 (segundo a tabela, o logaritmo discreto de 8 é 3) b = 3
Achar "b" usando a terceira equação não seria tão fácil, mas é interessante fazer porque ilustra as técnicas empregadas quando há múltiplos erros:
a * (4) ^ b = 9 1 * 4 ^ b = 9 Lembrando que 4 = 2^2, (2 ^ 2) ^ b = 9 2 ^ (2b) = 9 O logaritmo discreto de 9 é 6, então 2 ^ (2b) = 2 ^ 6 2b = 6 (aqui é mod 10, não mais mod 11 - vide nota!) b = 3
No exemplo acima, o fato de termos usado potências do gerador 2 começou a dar lucro, e permitiu simplificássemos a equação até remover as potências.
É importante salientar que, quando manipulamos potências sob aritmética modular, o módulo passa a ser o Totiente de Euler. O totiente de 11 é 10. Assim que transicionamos da equação exponencial para a forma linear 2b=6, é tudo módulo 10. (O exemplo não foi dos melhores pois o resultado não foi afetado pela mudança de módulo.)
Infelizmente, esta última parte não está implementada na planilha de exemplo, pois lá não temos o logaritmo discreto.
Como vimos, corrigir apenas um erro é fácil, tanto pela via da busca exaustiva como pela própria matemática. Quando há muitos erros, o sistema de equações vai apresentar polinômios semelhantes a este:
a * x ^ (4b) + c * x ^ (4c) = 3 a * x ^ (8b) + c * x ^ (8c) = 9
Temos dois problemas aqui. O primeiro é a dificuldade de simplificar equações onde soma e potenciação aparecem ao mesmo tempo. O segundo problema é resolver um sistema de equações grande de forma eficiente.
O artigo original de Reed e Solomon não abordou nenhum destes problemas. Eles foram resolvidos, aos poucos, por outros pesquisadores ao longo das décadas. Roma não foi feita em um dia.
A "linearização" das equações tira partido dos geradores e dos logaritmos discretos. Conforme vimos lá no começo, todos os números do campo, exceto o zero, podem ser representados pela potência de um gerador. Vamos trabalhar uma equação nesta direção:
a * x ^ (4b) + c * x ^ (4d) = 3 Assumindo que vamos avaliar a equação com x=2^3, e fazendo a=2^A, c=2^C, e sabendo que 2^8=3, 2^2=4, 2^3=8, 2^A.(2^3)^(4.b) + 2^C.(2^3)^(4.d) = 2^8 2^A.2^(12.b) + 2^C.(2^12.d) = 2^8 2^(A + 12.b) + 2^(C + 12.d) = 2^8 (mod 11) ou ainda 2^(A + 12.b) + 2^(C + 12.d) - 2^8 = 0 2^(A + 12.b) + 2^(C + 12.d) + 2^3 = 0 (pois -3 = +8 em mod 11)
Neste ponto, temos uma equação que ainda tem potências, mas a base de todas é o gerador. Ocorre que, em matemática discreta, podemos usar logaritmos discretos no lugar dos valores originais:
Dado um número x tal que x = 2^y, definimos a função de mapeamento N(x), tal que N(x) = log(x) + 1 = y + 1 e N(0) = 0
Seria ótimo se, com o mapeamento acima, pudéssemos obter uma equação linear diretamente:
2^(A + 12.b) + 2^(C + 12.d) + 2^3 = 0 (mod 11) N(2^(A + 12.b)) + N(2^(C + 12.d)) + N(2^3) = 0 (mod 10) A + 12.b + C + 12.d + 3 = 0 (mod 10, errada)
Somar duas potências de gerador no domínio dos logaritmos discretos é possível, mas exige a intermediação de uma ferramenta adicional chamada logaritmo de Zech:
Z(x) = logaritmo de Zech
a^i + a^j = a^(i + Z(j - i))
Conversão de soma de potências para o domínio
dos logaritmos discretos (N(x)):
a^i + a^j => (N(a^j) + Z(N(a^i) - N(a^j)) - 1) mod 10) + 1
=> (j + 1 + Z(i + 1 - j - 1)) - 1) mod 10) + 1
=> (j + Z(i - j)) mod 10) + 1
Com esta ferramenta, conseguimos transformar o sistema de equações em um sistema linear.
Decoding algorithms of Reed-Solomon code — Szymon Czynszak