Correção de erros Reed-Solomon

Os códigos Reed-Solomon são códigos de bloco. Isto significa que um bloco fixo de dados de entrada é processado em um bloco fixo de dados de saída. No caso do código R-S mais comumente usado (255, 223) - 223 símbolos de entrada Reed-Solomon (cada oito bits de comprimento) são codificados em 255 símbolos de saída.

• A maioria dos esquemas R-S ECC são sistemáticos. Isto significa que alguma parte da palavra de código de saída contém os dados de entrada em sua forma original.
• Um símbolo Reed-Solomon de oito bits foi escolhido porque os decodificadores para símbolos de tamanho maior seriam difíceis de implementar com a tecnologia atual. Esta escolha de projeto força o maior comprimento de palavra de código a ser 255 símbolos.
• O código Reed-Solomon padrão (255, 223) é capaz de corrigir até 16 erros do símbolo Reed-Solomon em cada palavra de código. Como cada símbolo é na verdade oito bits, isto significa que o código pode corrigir até 16 breves rajadas de erro devido ao decodificador convolutivo interno.

O código Reed-Solomon, assim como o código convolutivo, é um código transparente. Isto significa que se os símbolos do canal tiverem sido invertidos em algum lugar ao longo da linha, os decodificadores ainda funcionarão. O resultado será o complemento dos dados originais. Entretanto, o código Reed-Solomon perde sua transparência se for utilizado o preenchimento virtual de zero. Por este motivo, é obrigatório que o sentido dos dados (ou seja, verdadeiro ou complementado) seja resolvido antes da decodificação de Reed-Solomon.

No caso do programa Voyager, os códigos R-S atingem um desempenho quase ideal quando concatenados com o código interno (7, 1/2) convolutivo (Viterbi). Como são necessários dois símbolos de verificação para cada erro a ser corrigido, isto resulta em um total de 32 símbolos de verificação e 223 símbolos de informação por palavra de código.

Além disso, as palavras de código Reed-Solomon podem ser intercaladas com base em símbolos antes de serem codificadas de forma convolutiva. Como isto separa os símbolos em uma palavra de código, torna-se menos provável que um estouro do decodificador Viterbi perturbe mais de um símbolo Reed-Solomon em qualquer palavra de código.

A idéia chave por trás de um código Reed-Solomon é que os dados codificados são primeiramente visualizados como um polinômio. O código se baseia em um teorema de álgebra que afirma que quaisquer k pontos distintos determinam de forma única um polinômio de grau no máximo k-1.

O remetente determina um polinômio de grau k - 1, sobre um campo finito, que representa os pontos de dados k - 1 do tipo "k-1" do jogo. O polinômio é então "codificado" por sua avaliação em vários pontos, e estes valores são o que realmente é enviado. Durante a transmissão, alguns destes valores podem se corromper. Portanto, mais do que k pontos são realmente enviados. Desde que valores suficientes sejam recebidos corretamente, o receptor pode deduzir qual foi o polinômio original, e decodificar os dados originais.

No mesmo sentido em que se pode corrigir uma curva interpolando para além de uma lacuna, um código de Reed-Solomon pode colmatar uma série de erros em um bloco de dados para recuperar os coeficientes do polinômio que desenhou a curva original.

O código foi inventado em 1960 por Irving S. Reed e Gustave Solomon, que eram então membros do Laboratório MIT Lincoln. Seu artigo seminal era intitulado "Polinomial Codes over Certain Finite Fields" (Códigos Polinomiais sobre Certos Campos Finitos). Quando foi escrito, a tecnologia digital não estava suficientemente avançada para implementar o conceito. A primeira aplicação, em 1982, dos códigos RS em produtos produzidos em massa foi o disco compacto, onde dois códigos RS intercalados são utilizados. Um algoritmo de decodificação eficiente para códigos RS de grande distância foi desenvolvido por Elwyn Berlekamp e James Massey em 1969. Hoje os códigos RS são usados em discos rígidos, DVD, telecomunicação e protocolos de transmissão digital.