Em teoria, a codificação códigos de Reed-Solomon (RS), é um grupo de códigos cíclicos de correção de erros não binários,inventados por Irving S. Reed e Gustave Solomon. Os Códigos RS constituem uma sub-classe de uma ampla classe de códigos cíclicos denominada de Códigos BCH (Bose–Chaudhuri–Hocquenghem). Eles descreveram uma forma sistemática de construção de códigos capazes de detectar e corrigir vários erros aleatórios de símbolos. Ao adicionar símbolos de verificação aos dados, um código RS pode detectar qualquer combinação de até símbolos errados, e corrigir até símbolos. Como erasure code consegue corrigir até faltas conhecidas, ou pode detectar e corrigir uma combinação de erros e faltas. Além disso, os códigos RS são adequados como códigos de correção de multiple-burst bit-error, uma vez que uma sequência de erros consecutivos afeta no máximo dois símbolos de tamanho . A escolha de é arbitrária sendo efectuada pelo criador do código, e podendo ser seleccionado dentro de limites amplos.
Os Códigos RS encontram-se entre os códigos mais poderosos no que diz respeito à capacidade de correção de erro, sendo largamente utilizados em muitos sistemas digitais tais como: Comunicações de missões espaciais, CDs, DVDs, aDSL, WiMAX, DVB, QRCode, sistemas RAID 6 e sistemas de telecomunicações como DWDM.
História Os códigos de Reed-Solomon foram desenvolvidos em 1960 por Irving S. Reed e Gustave Solomon, que eram então membros da equipe do MIT Lincoln Laboratory. O seu artigo seminal foi intitulado "Polynomial Codes over Certain Finite Fields". O esquema de codificação original descrito no artigo de Reed e Solomon usava um polinômio variável baseado na mensagem a ser codificada, onde apenas um conjunto fixo de valores (pontos de avaliação) a serem codificados é conhecido pelo codificador e pelo decodificador. O decodificador teórico original gerava polinômios potenciais baseados em subconjuntos de (comprimento da mensagem não codificada) a partir de (comprimento da mensagem codificada) valores de uma mensagem recebida, escolhendo o polinômio mais popular como o correto, o que era impraticável para todos os casos, exceto os mais simples. Isso foi inicialmente resolvido alterando o esquema original para um esquema semelhante ao código BCH baseado em um polinômio fixo conhecido por ambos, codificador e decodificador, mas, posteriormente, decodificadores práticos baseados no esquema original foram desenvolvidos, embora mais lentos que os esquemas BCH. O resultado disso é que existem dois tipos principais de códigos de Reed-Solomon: aqueles que usam o esquema de codificação original e aqueles que usam o esquema de codificação BCH.
Também em 1960, um decodificador prático de polinômio fixo para códigos BCH desenvolvido por Daniel Gorenstein e Neal Zierler foi descrito em um relatório do MIT Lincoln Laboratory por Zierler em janeiro de 1960 e, mais tarde, em um artigo em junho de 1961. O decodificador de Gorenstein-Zierler e o trabalho relacionado sobre códigos BCH são descritos no livro "Error-Correcting Codes" de W. Wesley Peterson (1961). Por volta de 1963 (ou possivelmente antes), J.J. Stone (e outros) reconheceram que os códigos de Reed-Solomon poderiam usar o esquema BCH de utilizar um polinômio gerador fixo, tornando tais códigos uma classe especial de códigos BCH, mas os códigos de Reed-Solomon baseados no esquema de codificação original não são uma classe de códigos BCH e, dependendo do conjunto de pontos de avaliação, eles nem sequer são códigos cíclicos.
Em 1969, um decodificador de esquema BCH aprimorado foi desenvolvido por Elwyn Berlekamp e James Massey e desde então ficou conhecido como o algoritmo de decodificação de Berlekamp-Massey.
Em 1975, outro decodificador de esquema BCH aprimorado foi desenvolvido por Yasuo Sugiyama, baseado no algoritmo de Euclides estendido. miniaturadaimagem|350x350px Em 1977, os códigos de Reed-Solomon foram implementados no Programa Voyager na forma de códigos de correção de erro concatenados. A primeira aplicação comercial em produtos de consumo produzidos em massa apareceu em 1982 com o compact disc (CD), onde são usados dois códigos de Reed-Solomon entrelaçados. Hoje, os códigos de Reed-Solomon são amplamente implementados em dispositivos de armazenamento digital e padrões de comunicação digital, embora estejam sendo lentamente substituídos pelos códigos Bose-Chaudhuri-Hocquenghem (BCH). Por exemplo, os códigos de Reed-Solomon são usados no padrão de Digital Video Broadcasting (DVB) DVB-S, em conjunto com um código interno convolucional, mas os códigos BCH são usados com LDPC no seu sucessor, o DVB-S2.
Em 1986, um decodificador de esquema original conhecido como o Algoritmo de Berlekamp-Welch foi desenvolvido.
Em 1996, variações dos decodificadores de esquema original chamadas de decodificadores em lista (list decoders) ou decodificadores de decisão suave (soft decoders) foram desenvolvidas por Madhu Sudan e outros, e o trabalho continua nesses tipos de decodificadores (veja Algoritmo de decodificação em lista de Guruswami-Sudan).
Em 2002, outro decodificador de esquema original foi desenvolvido por Shuhong Gao, baseado no algoritmo de Euclides estendido..
Aplicações
Armazenamento de dados A codificação de Reed-Solomon é amplamente utilizada em sistemas de armazenamento em massa para corrigir os erros em rajada associados a defeitos na mídia.
A codificação de Reed-Solomon é um componente-chave do CD (compact disc). Foi o primeiro uso de codificação forte para correção de erros num produto de consumo produzido em massa, e o DAT e o DVD usam esquemas semelhantes. No CD, duas camadas de codificação Reed-Solomon separadas por um entrelaçador convolucional de 28 vias produzem um esquema chamado Codificação Reed-Solomon de Entrelaçamento Cruzado (CIRC). O primeiro elemento de um decodificador CIRC é um código Reed-Solomon interno relativamente fraco, encurtado de um código com símbolos de 8 bits. Este código pode corrigir até erros de byte por bloco de 32 bytes. Mais importante ainda, ele sinaliza como apagamentos (erasures) quaisquer blocos incorrigíveis, ou seja, blocos com mais de erros de byte. Os blocos de 28 bytes decodificados, com indicações de apagamento, são então distribuídos pelo desentrelaçador para diferentes blocos do código externo . Graças ao desentrelaçamento, um bloco de 28 bytes apagado do código interno torna-se um único byte apagado em cada um dos 28 blocos do código externo. O código externo corrige isso facilmente, já que pode lidar com até apagamentos desse tipo por bloco.
O resultado é um CIRC que pode corrigir completamente rajadas de erros de até **4000 bits**, ou cerca de **2,5 mm** na superfície do disco. Esse código é tão forte que a maioria dos erros de reprodução de CD é quase certamente causada por erros de rastreamento que fazem o laser pular de trilha, não por rajadas de erros incorrigíveis.
Os DVDs usam um esquema semelhante, mas com blocos muito maiores, um código interno e um código externo .
A correção de erros de Reed-Solomon também é usada em arquivos parchive que são comumente postados acompanhando arquivos multimídia na USENET. O serviço distribuído de armazenamento online Wuala (descontinuado em 2015) também usava Reed-Solomon ao fragmentar arquivos.
Código de barras Quase todos os códigos de barras bidimensionais, como PDF-417, MaxiCode, Datamatrix, QR Code, Aztec Code e Han Xin code, usam a correção de erros de Reed-Solomon para permitir a leitura correta mesmo que uma parte do código de barras esteja danificada. Quando o leitor de código de barras não consegue reconhecer um símbolo do código, ele o tratará como um apagamento.
A codificação de Reed-Solomon é menos comum em códigos de barras unidimensionais, mas é usada pela simbologia PostBar.
Transmissão de dados Formas especializadas de códigos Reed-Solomon, especificamente Cauchy-RS e Vandermonde-RS, podem ser usadas para superar a natureza não confiável da transmissão de dados em canais de apagamento. O processo de codificação pressupõe a geração de um código que resulta em palavras-código de comprimento de símbolos, cada uma armazenando símbolos de dados, que são então enviadas através de um canal de apagamento.
Qualquer combinação de palavras-código recebidas na outra extremidade é suficiente para reconstruir todas as palavras-código. A taxa de código é geralmente definida como , a menos que a probabilidade de apagamento do canal possa ser modelada adequadamente e verifique-se ser menor. Em conclusão, geralmente é , o que significa que pelo menos metade de todas as palavras-código enviadas deve ser recebida para que seja possível reconstruir a totalidade das palavras-código enviadas.
Os códigos Reed-Solomon também são usados em sistemas xDSL e nas Space Communications Protocol Specifications do CCSDS como uma forma de correção antecipada de erros (FEC).
Transmissão espacial direita|miniaturadaimagem|350x350px|Sistema de codificação concatenada de espaço profundo. Notação: (comprimento de restrição = 7, taxa de código = ) Uma aplicação significativa da codificação de Reed-Solomon foi na codificação das imagens digitais enviadas de volta pelo Programa Voyager.
A Voyager introduziu a codificação Reed-Solomon concatenada com códigos convolucionais, uma prática que desde então se tornou muito difundida em comunicações de espaço profundo e via satélite (por exemplo, transmissão digital direta).
Os decodificadores de Viterbi tendem a produzir erros em rajadas curtas. A correção desses erros em rajada é um trabalho feito da melhor forma por códigos de Reed-Solomon curtos ou simplificados.
Versões modernas da codificação convolucional decodificada por Viterbi e concatenada com Reed-Solomon foram e são usadas nas missões Mars Pathfinder, Galileo, Mars Exploration Rover e Cassini, onde operam a cerca de **1** a **1,5 dB** do limite máximo, a capacidade de Shannon.
Estes códigos concatenados estão agora a ser substituídos por turbo códigos mais poderosos: +Esquemas de codificação de canal usados por missões da NASAAnosCódigoMissão(ões)1958–presenteNão codificadoExplorer, Mariner, muitas outras1968–1978códigos convolucionais (CC) Pioneer, Venus1969–1975Código de Reed-Muller Mariner, Viking1977–presenteCódigo de Golay binárioVoyager1977–presenteVoyager, Galileo, muitas outras1989–2003Voyager1989–2003Galileo1996–presenteCassini, Mars Pathfinder, outras2004–presenteTurbo códigosMessenger, Stereo, MRO, MSL, outrasest. 2009Códigos LDPCConstellation, M2020, MAVEN
Construções (codificação) O código de Reed-Solomon é na verdade uma família de códigos, onde cada código é caracterizado por três parâmetros: o tamanho do alfabeto , um comprimento de bloco e um comprimento de mensagem , com . O conjunto de símbolos do alfabeto é interpretado como o corpo finito de ordem e, assim, deve ser uma potência de primo. Nas parametrizações mais úteis do código de Reed-Solomon, o comprimento do bloco costuma ser algum múltiplo constante do comprimento da mensagem, isto é, a taxa é alguma constante, e além disso, o comprimento do bloco é igual ao tamanho do alfabeto ou um a menos que ele, isto é, ou .
A visão original de Reed & Solomon: A palavra-código como uma sequência de valores