Código Reed–Solomon

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 $t$ símbolos de verificação aos dados, um código RS pode detectar qualquer combinação de até $t$ símbolos errados, e corrigir até $t/2$ símbolos. Como erasure code consegue corrigir até $t$ 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 $b+1$ erros consecutivos afeta no máximo dois símbolos de tamanho $b$. [2] A escolha de $t$ é 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 $k$ (comprimento da mensagem não codificada) a partir de $n$ (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.

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 $(32,28)$ relativamente fraco, encurtado de um código $(255,251)$ com símbolos de 8 bits. Este código pode corrigir até $2$ 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 $2$ 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 $(28,24)$. 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é $4$ 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 $(208,192)$ e um código externo $(182,172)$.

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 ${\text{RS}}(N,K)$ que resulta em $N$ palavras-código de comprimento de $N$ símbolos, cada uma armazenando $K$ símbolos de dados, que são então enviadas através de um canal de apagamento.

Qualquer combinação de $K$ palavras-código recebidas na outra extremidade é suficiente para reconstruir todas as $N$ palavras-código. A taxa de código é geralmente definida como $1/2$, a menos que a probabilidade de apagamento do canal possa ser modelada adequadamente e verifique-se ser menor. Em conclusão, $N$ geralmente é $2K$, 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

Sistema de codificação concatenada de espaço profundo. Notação: ${\text{RS}}(255,223)+{\text{CC}}$ (comprimento de restrição = 7, taxa de código = $1/2$)

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 NASA

Anos	Código	Missão(ões)
1958–presente	Não codificado	Explorer, Mariner, muitas outras
1968–1978	códigos convolucionais (CC) $(25,1/2)$	Pioneer, Venus
1969–1975	Código de Reed-Muller $(32,6)$	Mariner, Viking
1977–presente	Código de Golay binário	Voyager
1977–presente	${\text{RS}}(255,223)+{\text{CC}}(7,1/2)$	Voyager, Galileo, muitas outras
1989–2003	${\text{RS}}(255,223)+{\text{CC}}(7,1/3)$	Voyager
1989–2003	${\text{RS}}(255,223)+{\text{CC}}(14,1/4)$	Galileo
1996–presente	${\text{RS}}+{\text{CC}}(15,1/6)$	Cassini, Mars Pathfinder, outras
2004–presente	Turbo códigos	Messenger, Stereo, MRO, MSL, outras
est. 2009	Códigos LDPC	Constellation, 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 $q$, um comprimento de bloco $n$ e um comprimento de mensagem $k$, com $k<n\leq q$. O conjunto de símbolos do alfabeto é interpretado como o corpo finito $F$ de ordem $q$ e, assim, $q$ 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 $R={\frac {k}{n}}$ é alguma constante, e além disso, o comprimento do bloco é igual ao tamanho do alfabeto ou um a menos que ele, isto é, $n=q$ ou $n=q-1$.^{[carece de fontes]}

A visão original de Reed & Solomon: A palavra-código como uma sequência de valores

Existem diferentes procedimentos de codificação para o código de Reed-Solomon e, assim, há diferentes formas de descrever o conjunto de todas as palavras-código. Na visão original de Reed e Solomon, cada palavra-código do código de Reed-Solomon é uma sequência de valores de uma função polinomial de grau menor que $k$. Para obter uma palavra-código do código de Reed-Solomon, os símbolos da mensagem (cada um dentro do alfabeto de tamanho $q$) são tratados como os coeficientes de um polinômio $p$ de grau menor que $k$, sobre o corpo finito $F$ com $q$ elementos. Por sua vez, o polinômio $p$ é avaliado em um conjunto de $n\leq q$ pontos distintos em qualquer ordem $a_{1},\dots ,a_{n}$ do corpo $F$, e a sequência de valores é a palavra-código correspondente. Escolhas comuns para um conjunto de pontos de avaliação incluem $\{0,1,2,\dots ,n-1\}$, $\{0,1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-2}\}$, ou para $n<q$, $\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}$, ... , onde $\alpha$ é um elemento primitivo de $F$.

Formalmente, o conjunto $\mathbf {C}$ de palavras-código do código de Reed-Solomon é definido da seguinte forma: $$\mathbf {C} ={\Bigl \{}\;{\bigl (}p(a_{1}),p(a_{2}),\dots ,p(a_{n}){\bigr )}\;{\Big |}\;p{\text{ é um polinômio sobre }}F{\text{ de grau }}<k\;{\Bigr \}}\,.$$ Como quaisquer dois polinômios distintos de grau menor que $k$ concordam em no máximo $k-1$ pontos, isso significa que quaisquer duas palavras-código do código de Reed-Solomon discordam em pelo menos $n-(k-1)=n-k+1$ posições. Além disso, existem dois polinômios que concordam em $k-1$ pontos mas não são iguais e, assim, a distância do código de Reed-Solomon é exatamente $d=n-k+1$. Então a distância relativa é $\delta =d/n=1-k/n+1/n=1-R+1/n\sim 1-R$, onde $R=k/n$ é a taxa. Esse compromisso entre a distância relativa e a taxa é assintoticamente ótimo já que, pelo Limite de Singleton, todo código satisfaz $\delta +R\leq 1+1/n$. Sendo um código que alcança este compromisso ótimo, o código de Reed-Solomon pertence à classe dos códigos separáveis de distância máxima (MDS).

Enquanto o número de polinômios diferentes de grau menor que $k$ e o número de mensagens diferentes são ambos iguais a $q^{k}$, e portanto cada mensagem pode ser mapeada de forma única para um tal polinômio, existem diferentes formas de fazer esta codificação. A construção original de Reed & Solomon interpreta a mensagem $x$ como os coeficientes do polinômio $p$, ao passo que construções subsequentes interpretam a mensagem como os valores do polinômio nos primeiros $k$ pontos $a_{1},\dots ,a_{k}$ e obtêm o polinômio $p$ interpolando esses valores com um polinômio de grau menor que $k$. O último procedimento de codificação, embora seja ligeiramente menos eficiente, tem a vantagem de dar origem a um código sistemático, ou seja, a mensagem original está sempre contida como uma subsequência da palavra-código.

Procedimento de codificação simples: A mensagem como uma sequência de coeficientes

Na construção original de Reed e Solomon, a mensagem $m=(m_{0},\dots ,m_{k-1})\in F^{k}$ é mapeada para o polinômio $p_{m}$ com $$p_{m}(a)=\sum _{i=0}^{k-1}m_{i}a^{i}=m_{0}+m_{1}a+m_{2}a^{2}+\cdots +m_{k-1}a^{k-1}$$ A palavra-código de $m$ é obtida avaliando $p_{m}$ em $n$ pontos diferentes $a_{0},\dots ,a_{n-1}$ do corpo $F$. Assim, a função de codificação clássica $C:F^{k}\to F^{n}$ para o código de Reed-Solomon é definida da seguinte forma: $$C(m)={\begin{bmatrix}p_{m}(a_{0})&p_{m}(a_{1})&\cdots &p_{m}(a_{n-1})\end{bmatrix}}$$

Esta função $C$ é um mapeamento linear, isto é, ela satisfaz $C(m)=mA$ para a seguinte matriz $A$ de dimensões $k\times n$ com elementos de $F$.

$$C(m)=mA={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &m_{k-1}\end{bmatrix}}{\begin{bmatrix}1&1&1&\dots &1\\a_{0}&a_{1}&a_{2}&\dots &a_{n-1}\\a_{0}^{2}&a_{1}^{2}&a_{2}^{2}&\dots &a_{n-1}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\a_{0}^{k-1}&a_{1}^{k-1}&a_{2}^{k-1}&\dots &a_{n-1}^{k-1}\end{bmatrix}}$$

Esta matriz é uma Matriz de Vandermonde sobre $F$. Em outras palavras, o código de Reed-Solomon é um código linear, e no procedimento clássico de codificação, sua matriz geradora é $A$.

Procedimento de codificação sistemática: A mensagem como uma sequência inicial de valores

Existem procedimentos de codificação alternativos que produzem um código de Reed-Solomon sistemático. Um método usa a Interpolação polinomial de Lagrange para calcular o polinômio $p_{m}$ tal que $$p_{m}(a_{i})=m_{i}{\text{ para todo }}i\in \{0,\dots ,k-1\}.$$ Então $p_{m}$ é avaliado nos outros pontos $a_{k},\dots ,a_{n-1}$.

$$C(m)={\begin{bmatrix}p_{m}(a_{0})&p_{m}(a_{1})&\cdots &p_{m}(a_{n-1})\end{bmatrix}}$$

Esta função $C$ é um mapeamento linear. Para gerar a matriz de codificação sistemática correspondente $G$, multiplica-se a matriz $A$ pela inversa da submatriz quadrada à esquerda de $A$.

$$G=({\text{submatriz quadrada à esquerda de }}A)^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}$$

$C(m)=mG$ para a seguinte matriz $G$ de dimensões $k\times n$ com elementos de $F$. $$C(m)=mG={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &m_{k-1}\end{bmatrix}}{\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}$$

Transformada discreta de Fourier e sua inversa

Uma transformada discreta de Fourier é essencialmente o mesmo que o procedimento de codificação; ela usa o polinômio gerador $p_{m}$ para mapear um conjunto de pontos de avaliação nos valores da mensagem como mostrado acima: $$C(m)={\begin{bmatrix}p_{m}(a_{0})&p_{m}(a_{1})&\cdots &p_{m}(a_{n-1})\end{bmatrix}}$$

A transformada inversa de Fourier poderia ser usada para converter um conjunto livre de erros de $n<q$ valores de mensagem de volta no polinômio de codificação de $k$ coeficientes, com a restrição de que para isso funcionar, o conjunto de pontos de avaliação usado para codificar a mensagem deve ser um conjunto de potências crescentes de $\alpha$: $$a_{i}=\alpha ^{i}$$ $$a_{0},\dots ,a_{n-1}=\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}$$

Contudo, a interpolação de Lagrange realiza a mesma conversão sem a restrição sobre o conjunto de pontos de avaliação ou a exigência de um conjunto livre de erros de valores de mensagem e é usada para codificação sistemática, e em um dos passos do decodificador de Gao.

A visão BCH: A palavra-código como uma sequência de coeficientes

Note que o Código BCH e a maioria das implementações da visão BCH têm o termo mais significativo primeiro. Nesta visão, a mensagem é interpretada como os coeficientes de um polinômio $m(x)$:

$$m(x)=m_{k-1}x^{k-1}+m_{k-2}x^{k-2}+\cdots +m_{1}x+m_{0}$$

Um polinômio gerador $g(x)$ é definido como o polinômio cujas raízes são potências sequenciais do elemento primitivo do Corpo de Galois $\alpha$

$$g(x)=\left(x-\alpha ^{i}\right)\left(x-\alpha ^{i+1}\right)\cdots \left(x-\alpha ^{i+n-k-1}\right)=x^{n-k}+g_{n-k-1}x^{n-k-1}+\cdots +g_{1}x+g_{0}$$

Para um "código em sentido estrito" (narrow sense code), $i=1$.

A codificação calcula um polinômio de palavra-código $c(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots +c_{1}x+c_{0}$ que é um múltiplo exato de $g(x)$.

Procedimento de codificação simples

O remetente calcula um polinômio relacionado $c(x)$ de grau $n-1$ onde $n\leq q-1$ e envia o polinômio $c(x)$. O polinômio $c(x)$ é construído multiplicando o polinômio da mensagem $m(x)$, que tem grau $k-1$, com o polinômio gerador $g(x)$ de grau $n-k$ que é conhecido por ambos, remetente e receptor. $c(x)=m(x)g(x)$.

Esta função $C$ é um mapeamento linear, isto é, ela satisfaz $C(m)=mA$ para a seguinte matriz $A$ de dimensões $k\times n$ com elementos de $F$.

$$A={\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}$$

$C(m)=mA$ para a seguinte matriz $G$ de dimensões $k\times n$ com elementos de $F$.

$$c(x)=mA={\begin{bmatrix}m_{k-1}&\cdots &m_{1}&m_{0}\end{bmatrix}}{\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}$$

Procedimento de codificação sistemática

O procedimento de codificação para a visão BCH dos códigos de Reed-Solomon pode ser modificado para produzir um procedimento de codificação sistemático, no qual cada palavra-código contém a mensagem como um prefixo, e simplesmente adiciona símbolos de correção de erros como um sufixo. Aqui, em vez de enviar $c(x)=m(x)g(x)$, o codificador constrói o polinômio transmitido $c(x)$ tal que os coeficientes dos $k$ maiores monômios são iguais aos coeficientes correspondentes de $m(x)$, e os coeficientes de menor ordem de $c(x)$ são escolhidos de tal maneira que $c(x)$ torna-se exatamente divisível por $g(x)$. Então os coeficientes de $m(x)$ são uma subsequência dos coeficientes de $c(x)$. Para obter um código que seja globalmente sistemático, nós construímos o polinômio de mensagem $c(x)$ interpretando a mensagem como a sequência de seus coeficientes.

Formalmente, a construção é feita multiplicando $c(x)$ por $x^{t}$ para dar espaço aos $t=n-k$ símbolos de verificação, dividindo esse produto por $g(x)$ para encontrar o resto, e depois compensando esse resto o subtraindo. Os $t$ símbolos de verificação são criados computando o resto $r(x)$: $$r(x)=c(x)\cdot x^{t}\ {\bmod {\ }}g(x).$$

O resto tem grau de no máximo $t-1$, enquanto que os coeficientes de $x^{t-1},x^{t-2},\dots ,x^{1},x^{0}$ no polinômio $c(x)\cdot x^{t}$ são zero. Portanto, a seguinte definição da palavra-código $c(x)$ tem a propriedade de que os primeiros $k$ coeficientes são idênticos aos coeficientes de $c(x)$: $$c(x)=m(x)\cdot x^{t}-r(x)\,.$$

Como resultado, $c(x)$ é exatamente divisível por $g(x)$:

$$c(x)\equiv m(x)\cdot x^{t}-r(x)\equiv r(x)-r(x)\equiv 0\mod g(x)\,.$$

Esta função $C$ é um mapeamento linear. Para gerar a matriz de codificação sistemática correspondente $G$, multiplica-se a matriz $A$ pela inversa da submatriz quadrada à esquerda de $A$ (ou define a submatriz quadrada à esquerda de $G$ como a matriz identidade e codifica cada linha).

$$G=({\text{submatriz quadrada à esquerda de }}A)^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}$$

$C(m)=mG$ para a seguinte matriz $G$ de dimensões $k\times n$ com elementos de $F$.

$$c(x)=mG={\begin{bmatrix}m_{k-1}&\ldots &m_{1}&m_{0}\end{bmatrix}}{\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}$$

Propriedades

O código de Reed-Solomon é um código $[n,k,n-k+1]$; em outras palavras, é um código de bloco linear de comprimento $n$ (sobre $F$) com dimensão $k$ e distância de Hamming mínima $d_{\min }=n-k+1$. O código de Reed-Solomon é ótimo no sentido de que a distância mínima tem o valor máximo possível para um código linear de tamanho $(n,k)$; isto é conhecido como o Limite de Singleton. Um código desse tipo também é chamado de código separável de distância máxima (MDS).

A capacidade de correção de erros de um código de Reed-Solomon é determinada pela sua distância mínima, ou equivalentemente, por $n-k$, a medida de redundância no bloco. Se as localizações dos símbolos errôneos não forem conhecidas antecipadamente, então um código de Reed-Solomon pode corrigir até $(n-k)/2$ símbolos errôneos, ou seja, pode corrigir metade dos erros em relação ao número de símbolos redundantes adicionados ao bloco. Às vezes, as localizações dos erros são conhecidas antecipadamente (por exemplo, "informação lateral" nas relações sinal-ruído do demodulador) — estes são chamados de apagamentos (erasures). Um código de Reed-Solomon (como qualquer código MDS) é capaz de corrigir o dobro de apagamentos em relação a erros, e qualquer combinação de erros e apagamentos pode ser corrigida desde que a relação $2E+S\leq n-k$ seja satisfeita, onde $E$ é o número de erros e $S$ é o número de apagamentos no bloco.

Desempenho teórico da BER do código de Reed-Solomon (N=255, K=233, QPSK, AWGN). Característica em forma de degrau

O limite de erro teórico pode ser descrito através da seguinte fórmula para o canal AWGN para FSK: $$P_{b}\approx {\frac {2^{m-1}}{2^{m}-1}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }$$ e para outros esquemas de modulação: $$P_{b}\approx {\frac {1}{m}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }$$ onde $t={\frac {1}{2}}(d_{\min }-1)$, $P_{s}=1-(1-s)^{h}$, $h={\frac {m}{\log _{2}M}}$, $s$ é a taxa de erro de símbolo no caso AWGN não codificado e $M$ é a ordem de modulação.

Para usos práticos dos códigos de Reed-Solomon, é comum usar um corpo finito $F$ com $2^{m}$ elementos. Neste caso, cada símbolo pode ser representado como um valor de $m$ bits. O remetente envia os pontos de dados como blocos codificados, e o número de símbolos no bloco codificado é $n=2^{m}-1$. Assim, um código de Reed-Solomon operando em símbolos de 8 bits tem $n=2^{8}-1=255$ símbolos por bloco. (Este é um valor muito popular devido à prevalência de sistemas de computador orientados a bytes). O número $k$, com $k<n$, de símbolos de dados no bloco é um parâmetro de projeto. Um código comumente usado codifica $k=223$ símbolos de dados de oito bits mais 32 símbolos de paridade de oito bits num bloco de $n=255$ símbolos; isto é denotado como um código $(n,k)=(255,223)$, e é capaz de corrigir até 16 erros de símbolo por bloco.

As propriedades do código de Reed-Solomon discutidas acima os tornam especialmente adequados para aplicações onde os erros ocorrem em rajadas (bursts). Isso ocorre porque não importa para o código quantos bits em um símbolo estão errados — se vários bits em um símbolo forem corrompidos, isso conta apenas como um único erro. Por outro lado, se um fluxo de dados não for caracterizado por rajadas de erros ou perdas de sinal (drop-outs), mas por erros aleatórios de bit único, um código de Reed-Solomon geralmente é uma escolha ruim em comparação com um código binário.

O código de Reed-Solomon, assim como o código convolucional, é um código transparente. Isso significa que se os símbolos do canal tiverem sido invertidos (bitwise NOT) em algum lugar ao longo da linha, os decodificadores ainda funcionarão. O resultado será a inversão dos dados originais. No entanto, o código de Reed-Solomon perde a sua transparência quando o código é encurtado (veja 'Observações' no final desta seção). Os bits "ausentes" em um código encurtado precisam ser preenchidos por zeros ou uns, dependendo se os dados estão complementados ou não. (Dito de outra forma, se os símbolos são invertidos, então o preenchimento com zeros precisa ser invertido para um preenchimento com uns.) Por este motivo, é obrigatório que o sentido dos dados (ou seja, verdadeiro ou complementado) seja resolvido antes da decodificação de Reed-Solomon.

O fato de o código de Reed-Solomon ser cíclico ou não depende de detalhes sutis da construção. Na visão original de Reed e Solomon, onde as palavras-código são os valores de um polinômio, pode-se escolher a sequência de pontos de avaliação de modo a tornar o código cíclico. Em particular, se $\alpha$ for uma raiz primitiva do corpo $F$, então por definição todos os elementos não nulos de $F$ assumem a forma $\alpha ^{i}$ para $i\in \{1,\dots ,q-1\}$, onde $q=|F|$. Cada polinômio $p$ sobre $F$ dá origem a uma palavra-código $(p(\alpha ^{1}),\dots ,p(\alpha ^{q-1}))$. Uma vez que a função $a\mapsto p(\alpha a)$ também é um polinômio de mesmo grau, esta função dá origem a uma palavra-código $(p(\alpha ^{2}),\dots ,p(\alpha ^{q}))$; como $\alpha ^{q}=\alpha ^{1}$ é válido, esta palavra-código é o deslocamento circular à esquerda da palavra-código original derivada de $p$. Portanto, escolher uma sequência de potências de raízes primitivas como os pontos de avaliação torna o código de Reed-Solomon da visão original cíclico. Os códigos de Reed-Solomon na visão BCH são sempre cíclicos porque os códigos BCH são cíclicos.

Observações

Os projetistas não são obrigados a usar os tamanhos "naturais" dos blocos de código de Reed-Solomon. Uma técnica conhecida como "encurtamento" (shortening) pode produzir um código menor de qualquer tamanho desejado a partir de um código maior.

Por exemplo, o código (255, 223) amplamente utilizado pode ser convertido em um código (160, 128) preenchendo a porção não utilizada do bloco de origem com 95 zeros binários e não os transmitindo. No decodificador, a mesma porção do bloco é carregada localmente com zeros binários.

O código QR, Versão 3 (29×29) usa blocos entrelaçados. A mensagem tem 26 bytes de dados e é codificada usando dois blocos de código de Reed-Solomon. Cada bloco é um código de Reed-Solomon (255, 233) encurtado para um código (35, 13).

O teorema de Delsarte-Goethals-Seidel ilustra um exemplo de aplicação de códigos de Reed-Solomon encurtados. Paralelamente ao encurtamento, uma técnica conhecida como perfuração (puncturing) permite omitir alguns dos símbolos de paridade codificados.

Decodificadores da visão BCH

Os decodificadores descritos nesta seção usam a visão BCH de uma palavra-código como uma sequência de coeficientes. Eles usam um polinômio gerador fixo conhecido tanto pelo codificador quanto pelo decodificador.

Decodificador de Peterson-Gorenstein-Zierler

Ver artigo principal: Algoritmo de Peterson-Gorenstein-Zierler

Daniel Gorenstein e Neal Zierler desenvolveram um decodificador que 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 estão descritos no livro Error Correcting Codes de W. Wesley Peterson (1961).

Formulação

A mensagem transmitida, $(c_{0},\dots ,c_{i},\dots ,c_{n-1})$, é vista como os coeficientes de um polinômio $$s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}.$$

Como resultado do procedimento de codificação de Reed-Solomon, $s(x)$ é divisível pelo polinômio gerador $$g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),$$ onde $\alpha$ é um elemento primitivo.

Uma vez que $s(x)$ é um múltiplo do gerador $g(x)$, segue-se que ele "herda" todas as suas raízes: $$s(x){\bmod {(}}x-\alpha ^{j})=g(x){\bmod {(}}x-\alpha ^{j})=0.$$ Portanto, $$s(\alpha ^{j})=0,\ j=1,2,\dots ,n-k.$$

O polinômio transmitido é corrompido em trânsito por um polinômio de erro $$e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}$$ para produzir o polinômio recebido $$r(x)=s(x)+e(x).$$

O coeficiente $e_{i}$ será zero se não houver erro naquela potência de $x$, e não nulo se houver um erro. Se houver $\nu$ erros em potências distintas $i_{k}$ de $x$, então $$e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}.$$

O objetivo do decodificador é encontrar o número de erros ($\nu$), as posições dos erros ($i_{k}$) e os valores dos erros nessas posições ($e_{i_{k}}$). A partir disso, $e(x)$ pode ser calculado e subtraído de $r(x)$ para obter a mensagem enviada originalmente $s(x)$.

Decodificação por síndrome

O decodificador começa avaliando o polinômio conforme recebido nos pontos $\alpha ^{1}\dots \alpha ^{n-k}$. Chamamos os resultados dessa avaliação de "síndromes" $S_{j}$. Elas são definidas como $${\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})\\&=e(\alpha ^{j})\\&=\sum _{k=1}^{\nu }e_{i_{k}}{(\alpha ^{j})}^{i_{k}},\quad j=1,2,\dots ,n-k.\end{aligned}}$$ Note que $s(\alpha ^{j})=0$ porque $s(x)$ tem raízes em $\alpha ^{j}$, como mostrado na seção anterior.

A vantagem de analisar as síndromes é que o polinômio da mensagem é descartado. Em outras palavras, as síndromes referem-se apenas ao erro e não são afetadas pelo conteúdo real da mensagem sendo transmitida. Se todas as síndromes forem zero, o algoritmo para aqui e relata que a mensagem não foi corrompida em trânsito.

Localizadores de erros e valores de erros

Por conveniência, defina os localizadores de erros $X_{k}$ e os valores de erros $Y_{k}$ como $$X_{k}=\alpha ^{i_{k}},\quad Y_{k}=e_{i_{k}}.$$

Então as síndromes podem ser escritas em termos desses localizadores e valores de erros como $$S_{j}=\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}.$$

Esta definição dos valores de síndrome é equivalente à anterior, uma vez que ${(\alpha ^{j})}^{i_{k}}=\alpha ^{j\cdot i_{k}}={(\alpha ^{i_{k}})}^{j}=X_{k}^{j}$.

As síndromes fornecem um sistema de $n-k\geq 2\nu$ equações em $2\nu$ incógnitas, mas esse sistema de equações é não linear nos $X_{k}$ e não tem uma solução óbvia. No entanto, se os $X_{k}$ fossem conhecidos (veja abaixo), então as equações de síndrome forneceriam um sistema linear de equações $${\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &\ddots &\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots \\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}},$$ que pode ser facilmente resolvido para os valores de erro $Y_{k}$.

Consequentemente, o problema consiste em encontrar os $X_{k}$, porque assim a matriz mais à esquerda seria conhecida e ambos os lados da equação poderiam ser multiplicados pela sua inversa, produzindo os $Y_{k}$.

Na variante deste algoritmo onde as localizações dos erros já são conhecidas (quando está sendo usado como um código de apagamento), este é o fim. As localizações dos erros ($X_{k}$) já são conhecidas por algum outro método (por exemplo, numa transmissão FM, as seções onde o fluxo de bits estava obscuro ou sobrecarregado com interferência são probabilisticamente determináveis a partir da análise de frequência). Neste cenário, até $n-k$ erros podem ser corrigidos.

O resto do algoritmo serve para localizar os erros e exigirá valores de síndrome até $2\nu$, em vez de apenas os $\nu$ usados até agora. É por isso que é necessário adicionar o dobro de símbolos de correção de erros em relação à quantidade de erros que podem ser corrigidos sem conhecer suas localizações.

Polinômio localizador de erros

Existe uma relação de recorrência linear que dá origem a um sistema de equações lineares. A resolução dessas equações identifica essas localizações de erro $X_{k}$.

Defina o polinômio localizador de erros $\Lambda (x)$ como $$\Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }.$$

Os zeros de $\Lambda (x)$ são os recíprocos $X_{k}^{-1}$. Isso decorre da construção da notação de produto acima, uma vez que se $x=X_{k}^{-1}$, então um dos termos multiplicados será zero, $(1-X_{k}^{-1}\cdot X_{k})=1-1=0$, fazendo com que todo o polinômio seja avaliado como zero: $$\Lambda (X_{k}^{-1})=0.$$

Seja $j$ um inteiro qualquer tal que $1\leq j\leq \nu$. Multiplique ambos os lados por $Y_{k}X_{k}^{j+\nu }$, e o resultado ainda será zero: $${\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0,\\&Y_{k}X_{k}^{j+\nu }(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu })=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0.\end{aligned}}$$

Somando para $k=1$ até $\nu$, ainda será zero: $$\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j})=0.$$

Agrupe cada termo em sua própria soma: $$\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\left(\sum _{k=1}^{\nu }\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}\right)+\left(\sum _{k=1}^{\nu }\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\left(\sum _{k=1}^{\nu }\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0.$$

Extraia os valores constantes de $\Lambda$ que não são afetados pelo somatório: $$\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -1}\right)+\Lambda _{2}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0.$$

Esses somatórios agora são equivalentes aos valores de síndrome, que conhecemos e podemos substituir. Isso, portanto, se reduz a $$S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0.$$

Subtraindo $S_{j+\nu }$ de ambos os lados, obtemos $$S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }.$$

Lembre-se de que $j$ foi escolhido como sendo qualquer inteiro entre $1$ e $\nu$ inclusive, e essa equivalência é verdadeira para todos esses valores. Portanto, temos $\nu$ equações lineares, não apenas uma. Este sistema de equações lineares pode, assim, ser resolvido para os coeficientes $\Lambda _{i}$ do polinômio localizador de erros: $${\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &\ddots &\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}.$$

O raciocínio acima assume que o decodificador conhece o número de erros $\nu$, mas esse número ainda não foi determinado. O decodificador PGZ não determina $\nu$ diretamente, mas sim o busca testando valores sucessivos. O decodificador inicialmente assume o maior valor para um $\nu$ de teste e monta o sistema linear para esse valor. Se as equações puderem ser resolvidas (ou seja, o determinante da matriz for diferente de zero), então esse valor de teste é o número de erros. Se o sistema linear não puder ser resolvido, então o $\nu$ de teste é reduzido em um e o próximo sistema menor é examinado.

Encontrar as raízes do polinômio localizador de erros

Use os coeficientes $\Lambda _{i}$ encontrados no último passo para construir o polinômio de localização de erros. As raízes do polinômio de localização de erros podem ser encontradas por busca exaustiva. Os localizadores de erro $X_{k}$ são os recíprocos dessas raízes. A ordem dos coeficientes do polinômio de localização de erros pode ser invertida; nesse caso, as raízes desse polinômio invertido são os localizadores de erro $X_{k}$ (não seus recíprocos $X_{k}^{-1}$). A Busca de Chien é uma implementação eficiente deste passo.

Calcular os valores dos erros

Uma vez que os localizadores de erros $X_{k}$ são conhecidos, os valores dos erros podem ser determinados. Isso pode ser feito pela solução direta para $Y_{k}$ na matriz de equações de erro dada acima, ou usando o Algoritmo de Forney.

Calcular as localizações dos erros

Calcule $i_{k}$ tomando o logaritmo na base $\alpha$ de $X_{k}$. Isso geralmente é feito usando uma tabela de pesquisa (lookup table) pré-calculada.

Corrigir os erros

Finalmente, $e(x)$ é gerado a partir de $i_{k}$ e $e_{i_{k}}$ e então é subtraído de $r(x)$ para obter a mensagem enviada originalmente $s(x)$, com os erros corrigidos.

Exemplo

Considere o código de Reed-Solomon definido em $GF(929)$ com $\alpha =3$ e $t=4$ (isto é usado nos códigos de barras PDF417) para um código RS(7,3). O polinômio gerador é $$g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522.$$ Se o polinômio da mensagem é $p(x)=3x^{2}+2x+1$, então uma palavra-código sistemática é codificada da seguinte forma: $$s_{r}(x)=p(x)\,x^{t}{\bmod {g}}(x)=547x^{3}+738x^{2}+442x+455,$$ $$s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474.$$ Erros na transmissão podem fazer com que isto seja recebido em seu lugar: $$r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474.$$ As síndromes são calculadas avaliando $r$ em potências de $\alpha$: $$S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732,$$ $$S_{2}=r(3^{2})=637,\quad S_{3}=r(3^{3})=762,\quad S_{4}=r(3^{4})=925,$$ resultando no sistema $${\begin{bmatrix}732&637\\637&762\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-762\\-925\end{bmatrix}}={\begin{bmatrix}167\\004\end{bmatrix}}.$$

Usando a eliminação gaussiana, $${\begin{bmatrix}001&000\\000&001\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}329\\821\end{bmatrix}},$$ portanto $$\Lambda (x)=329x^{2}+821x+001,$$ com raízes $x_{1}=757=3^{-3}$ e $x_{2}=562=3^{-4}$. Os coeficientes podem ser invertidos: $$R(x)=001x^{2}+821x+329,$$ para produzir raízes $27=3^{3}$ e $81=3^{4}$ com expoentes positivos, mas tipicamente isso não é usado. O logaritmo das raízes invertidas corresponde às localizações dos erros (da direita para a esquerda, a localização 0 é o último termo na palavra-código).

Para calcular os valores dos erros, aplique o Algoritmo de Forney: $$\Omega (x)=S(x)\Lambda (x){\bmod {x}}^{4}=546x+732,$$ $$\Lambda '(x)=658x+821,$$ $$e_{1}=-\Omega (x_{1})/\Lambda '(x_{1})=074,$$ $$e_{2}=-\Omega (x_{2})/\Lambda '(x_{2})=122.$$

Subtraindo $e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}$ do polinômio recebido $r(x)$ reproduz-se a palavra-código original $s$.

Decodificador de Berlekamp-Massey

O Algoritmo de Berlekamp-Massey é um procedimento iterativo alternativo para encontrar o polinômio localizador de erros. Durante cada iteração, ele calcula uma discrepância baseada numa instância atual de $\Lambda (x)$ com um número presumido de erros $e$: $$\Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}$$ e então ajusta $\Lambda (x)$ e $e$ para que um $\Delta$ recalculado seja zero. O artigo do Algoritmo de Berlekamp-Massey traz uma descrição detalhada do procedimento. No exemplo a seguir, $C(x)$ é usado para representar $\Lambda (x)$.

Exemplo

Usando os mesmos dados do exemplo de Peterson-Gorenstein-Zierler acima:

$n$	$S_{n+1}$	$d$	$C$	$B$	$b$	$m$
0	732	732	$197x+1$	1	732	1
1	637	846	$173x+1$	1	732	2
2	762	412	$634x^{2}+173x+1$	$173x+1$	412	1
3	925	576	$329x^{2}+821x+1$	$173x+1$	412	2

O valor final de $C$ é o polinômio localizador de erros, $\Lambda (x)$.

Decodificador de Sugiyama

Outro método iterativo para calcular tanto o polinômio localizador de erros quanto o polinômio de valor de erro é baseado na adaptação de Sugiyama do algoritmo de Euclides estendido.

Defina $S(x)$, $\Lambda (x)$ e $\Omega (x)$ para $t$ síndromes e $e$ erros: $${\begin{aligned}S(x)&=S_{t}x^{t-1}+S_{t-1}x^{t-2}+\cdots +S_{2}x+S_{1}\\[1ex]\Lambda (x)&=\Lambda _{e}x^{e}+\Lambda _{e-1}x^{e-1}+\cdots +\Lambda _{1}x+1\\[1ex]\Omega (x)&=\Omega _{e}x^{e}+\Omega _{e-1}x^{e-1}+\cdots +\Omega _{1}x+\Omega _{0}\end{aligned}}$$

A equação chave é: $$\Lambda (x)S(x)=Q(x)x^{t}+\Omega (x)$$

Para $t=6$ e $e=3$: $${\begin{bmatrix}\Lambda _{3}S_{6}&x^{8}\\\Lambda _{2}S_{6}+\Lambda _{3}S_{5}&x^{7}\\\Lambda _{1}S_{6}+\Lambda _{2}S_{5}+\Lambda _{3}S_{4}&x^{6}\\S_{6}+\Lambda _{1}S_{5}+\Lambda _{2}S_{4}+\Lambda _{3}S_{3}&x^{5}\\S_{5}+\Lambda _{1}S_{4}+\Lambda _{2}S_{3}+\Lambda _{3}S_{2}&x^{4}\\S_{4}+\Lambda _{1}S_{3}+\Lambda _{2}S_{2}+\Lambda _{3}S_{1}&x^{3}\\S_{3}+\Lambda _{1}S_{2}+\Lambda _{2}S_{1}&x^{2}\\S_{2}+\Lambda _{1}S_{1}&x\\S_{1}\end{bmatrix}}={\begin{bmatrix}Q_{2}x^{8}\\Q_{1}x^{7}\\Q_{0}x^{6}\\0\\0\\0\\\Omega _{2}x^{2}\\\Omega _{1}x\\\Omega _{0}\end{bmatrix}}$$

Os termos do meio são zero devido à relação entre $\Lambda$ e as síndromes.

O algoritmo de Euclides estendido pode encontrar uma série de polinômios da forma

$$A_{i}(x)S(x)+B_{i}(x)x^{t}=R_{i}(x)$$

onde o grau de $R$ diminui à medida que $i$ aumenta. Assim que o grau de $R_{i}(x)<t/2$, então $${\begin{aligned}A_{i}(x)&=\Lambda (x)\\B_{i}(x)&=-Q(x)\\R_{i}(x)&=\Omega (x).\end{aligned}}$$

$B(x)$ e $Q(x)$ não precisam ser salvos, de modo que o algoritmo se torna:

$R_{-1}:=x^{t}$
$R_{0}:=S(x)$
$A_{-1}:=0$
$A_{0}:=1$
$i:=0$
enquanto grau de $R_{i}\geq t/2$
    $i:=i+1$
    $Q:=R_{i-2}/R_{i-1}$
    $R_{i}:=R_{i-2}-QR_{i-1}$
    $A_{i}:=A_{i-2}-QA_{i-1}$

para definir o termo de menor ordem de $\Lambda (x)$ como 1, divida $\Lambda (x)$ e $\Omega (x)$ por $A_{i}(0)$: $${\begin{aligned}\Lambda (x)&=A_{i}/A_{i}(0)\\\Omega (x)&=R_{i}/A_{i}(0)\end{aligned}}$$ $A_{i}(0)$ é o termo constante (de menor ordem) de $A_{i}$.

Exemplo

Usando os mesmos dados do exemplo de Peterson-Gorenstein-Zierler acima:

$i$	$R_{i}$	$A_{i}$
−1	$001x^{4}+000x^{3}+000x^{2}+000x+000$	000
0	$925x^{3}+762x^{2}+637x+732$	001
1	$683x^{2}+676x+024$	$697x+396$
2	$673x+596$	$608x^{2}+704x+544$

$$\Lambda (x)=A_{2}/544=329x^{2}+821x+001$$ $$\Omega (x)=R_{2}/544=546x+732$$

Decodificador usando transformada discreta de Fourier

Uma transformada discreta de Fourier pode ser usada para decodificação. Para evitar conflito com os nomes das síndromes, seja $c(x)=s(x)$ a palavra-código codificada. $r(x)$ e $e(x)$ são iguais aos descritos acima. Defina $C(x)$, $E(x)$ e $R(x)$ como as transformadas discretas de Fourier de $c(x)$, $e(x)$ e $r(x)$. Como $r(x)=c(x)+e(x)$, e como uma transformada discreta de Fourier é um operador linear, $R(x)=C(x)+E(x)$.

Transforme $r(x)$ em $R(x)$ usando a transformada discreta de Fourier. Como o cálculo de uma transformada discreta de Fourier é igual ao cálculo das síndromes, $t$ coeficientes de $R(x)$ e $E(x)$ são iguais às síndromes: $$R_{j}=E_{j}=S_{j}=r(\alpha ^{j})\qquad {\text{para }}1\leq j\leq t$$

Use de $R_{1}$ até $R_{t}$ como síndromes (são as mesmas) e gere o polinômio localizador de erros utilizando os métodos de qualquer um dos decodificadores acima.

Seja $\nu$ = número de erros. Gere $E(x)$ usando os coeficientes conhecidos $E_{1}$ a $E_{t}$, o polinômio localizador de erros, e estas fórmulas: $${\begin{aligned}E_{0}&=-{\frac {1}{\Lambda _{\nu }}}(E_{\nu }+\Lambda _{1}E_{\nu -1}+\cdots +\Lambda _{\nu -1}E_{1})\\E_{j}&=-(\Lambda _{1}E_{j-1}+\Lambda _{2}E_{j-2}+\cdots +\Lambda _{\nu }E_{j-\nu })&{\text{para }}t<j<n\end{aligned}}$$

Em seguida, calcule $C(x)=R(x)-E(x)$ e aplique a transformada inversa (interpolação polinomial) de $C(x)$ para produzir $c(x)$.

Decodificação além do limite de correção de erros

O Limite de Singleton afirma que a distância mínima $d$ de um código de bloco linear de tamanho $(n,k)$ é limitada superiormente por $n-k+1$. A distância $d$ era geralmente entendida como um limite à capacidade de correção de erros em $\lfloor (d-1)/2\rfloor$. O código de Reed-Solomon atinge esse limite com igualdade e, portanto, pode corrigir até $\lfloor (n-k)/2\rfloor$ erros. No entanto, esse limite de correção de erros não é exato.

Em 1999, Madhu Sudan e Venkatesan Guruswami do MIT publicaram "Improved Decoding of Reed–Solomon and Algebraic-Geometry Codes" (Decodificação Melhorada de Códigos de Reed-Solomon e de Geometria Algébrica), introduzindo um algoritmo que permitia a correção de erros além da metade da distância mínima do código. Ele se aplica a códigos de Reed-Solomon e, mais geralmente, a códigos geométricos algébricos. Este algoritmo produz uma lista de palavras-código (é um algoritmo de decodificação em lista) e baseia-se na interpolação e fatoração de polinômios sobre $GF(2^{m})$ e suas extensões.

Em 2023, teóricos da codificação mostraram que códigos de Reed-Solomon definidos sobre pontos de avaliação aleatórios podem alcançar a capacidade de decodificação em lista (até $n-k$ erros) sobre alfabetos de tamanho linear com alta probabilidade. Esses resultados não fornecem um algoritmo para realizar a decodificação.

Decodificação por decisão suave (soft-decoding)

Os métodos de decodificação algébrica descritos acima são métodos de decisão rígida (hard-decision), o que significa que para cada símbolo é tomada uma decisão categórica sobre o seu valor. Por exemplo, um decodificador poderia associar a cada símbolo um valor adicional correspondente à confiança do demodulador do canal na exatidão do símbolo. O advento do LDPC e dos turbo códigos, que empregam métodos iterativos de decodificação por propagação de crenças de decisão suave (soft-decision) para alcançar um desempenho de correção de erros próximo ao limite teórico, estimulou o interesse em aplicar a decodificação de decisão suave a códigos algébricos convencionais. Em 2003, Ralf Koetter e Alexander Vardy apresentaram um algoritmo de decodificação em lista algébrica de decisão suave em tempo polinomial para códigos de Reed-Solomon, que foi baseado no trabalho de Sudan e Guruswami. Em 2016, Steven J. Franke e Joseph H. Taylor publicaram um novo decodificador de decisão suave.

Decodificadores da visão original de Reed-Solomon

Os decodificadores descritos nesta seção usam a visão original de Reed-Solomon de uma palavra-código como uma sequência de valores polinomiais, onde o polinômio é baseado na mensagem a ser codificada. O mesmo conjunto de valores fixos é usado pelo codificador e pelo decodificador, e o decodificador recupera o polinômio de codificação (e, opcionalmente, um polinômio localizador de erros) a partir da mensagem recebida.

Decodificador teórico

Reed e Solomon descreveram um decodificador teórico que corrigia erros encontrando o polinômio de mensagem mais popular. O decodificador conhece apenas o conjunto de valores $a_{1}$ a $a_{n}$ e qual método de codificação foi usado para gerar a sequência de valores da palavra-código. A mensagem original, o polinômio e quaisquer erros são desconhecidos. Um procedimento de decodificação poderia usar um método como a interpolação de Lagrange em vários subconjuntos de $n$ valores de palavras-código, tomados $k$ de cada vez, para produzir repetidamente polinômios potenciais, até que um número suficiente de polinômios correspondentes seja produzido para eliminar razoavelmente quaisquer erros na palavra-código recebida. Uma vez determinado um polinômio, quaisquer erros na palavra-código podem ser corrigidos recalculando os valores correspondentes da palavra-código. Infelizmente, em todos os casos, exceto nos mais simples, existem demasiados subconjuntos, tornando o algoritmo impraticável. O número de subconjuntos é o coeficiente binomial, ${\binom {n}{k}}={\frac {n!}{(n-k)!k!}}$, e a quantidade de subconjuntos é inviável até mesmo para códigos modestos. Para um código $(255,249)$ que pode corrigir $3$ erros, o decodificador teórico ingênuo examinaria 359 bilhões de subconjuntos.^{[carece de fontes]}

Decodificador de Berlekamp-Welch

Em 1986, um decodificador conhecido como o Algoritmo de Berlekamp-Welch foi desenvolvido como um decodificador que é capaz de recuperar o polinômio da mensagem original, bem como um polinômio "localizador" de erro que produz zeros para os valores de entrada que correspondem a erros, com complexidade de tempo $O(n^{3})$, onde $n$ é o número de valores em uma mensagem. O polinômio recuperado é então usado para recuperar (recalcular conforme necessário) a mensagem original.

Exemplo

Usando RS(7,3), GF(929), e o conjunto de pontos de avaliação $a_{i}=i-1$

$a=\{0,1,2,3,4,5,6\}$

Se o polinômio da mensagem é

$p(x)=003x^{2}+002x+001$

A palavra-código é

$c=\{001,006,017,034,057,086,121\}$

Erros de transmissão podem fazer com que isto seja recebido em vez disso:

$b=c+e=\{001,006,123,456,057,086,121\}$

A equação chave é:

$b_{i}E(a_{i})-Q(a_{i})=0$

Assuma o número máximo de erros: $e=2$. A equação chave se torna:

$b_{i}(e_{0}+e_{1}a_{i})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+q_{3}a_{i}^{3}+q_{4}a_{i}^{4})=-b_{i}a_{i}^{2}$

$${\begin{bmatrix}001&000&928&000&000&000&000\\006&006&928&928&928&928&928\\123&246&928&927&925&921&913\\456&439&928&926&920&902&848\\057&228&928&925&913&865&673\\086&430&928&924&904&804&304\\121&726&928&923&893&713&562\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}000\\923\\437\\541\\017\\637\\289\end{bmatrix}}$$

Usando a eliminação gaussiana:

$${\begin{bmatrix}001&000&000&000&000&000&000\\000&001&000&000&000&000&000\\000&000&001&000&000&000&000\\000&000&000&001&000&000&000\\000&000&000&000&001&000&000\\000&000&000&000&000&001&000\\000&000&000&000&000&000&001\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}006\\924\\006\\007\\009\\916\\003\end{bmatrix}}$$

$Q(x)=003x^{4}+916x^{3}+009x^{2}+007x+006$

$E(x)=001x^{2}+924x+006$

${\frac {Q(x)}{E(x)}}=P(x)=003x^{2}+002x+001$

Recalcule $P(x)$ onde $E(x)=0:\{2,3\}$ para corrigir $b$, resultando na palavra-código corrigida:

$c=\{001,006,017,034,057,086,121\}$

Decodificador de Gao

Em 2002, um decodificador aprimorado foi desenvolvido por Shuhong Gao, baseado no algoritmo de Euclides estendido.

Exemplo

• $R_{-1}=\prod _{i=1}^{n}(x-a_{i})$
• $R_{0}=$ interpolação de Lagrange de $(a_{i},b(a_{i}))$ para $i=1$ até $n$
• $A_{-1}=0$
• $A_{0}=1$
• gere $R_{i}$ e $A_{i}$ até que o grau de $R_{i}<(n+k)/2$; para este exemplo, $(n+k)/2=(7+3)/2=5$

$i$	$R_{i}$	$A_{i}$
−1	$001x^{7}+908x^{6}+175x^{5}+194x^{4}+695x^{3}+094x^{2}+720x+000$	$000$
0	$055x^{6}+440x^{5}+497x^{4}+904x^{3}+424x^{2}+472x+001$	$001$
1	$702x^{5}+845x^{4}+691x^{3}+461x^{2}+327x+237$	$152x+237$
2	$266x^{4}+086x^{3}+798x^{2}+311x+532$	$708x^{2}+176x+532$

$Q(x)=R_{2}=266x^{4}+086x^{3}+798x^{2}+311x+532$

$E(x)=A_{2}=708x^{2}+176x+532$

Para duplicar os polinômios gerados por Berlekamp-Welch, divida $Q(x)$ e $E(x)$ pelo coeficiente mais significativo de $E(x)$, que é $708$.

$Q(x)=003x^{4}+916x^{3}+009x^{2}+007x+006$

$E(x)=001x^{2}+924x+006$

${\frac {Q(x)}{E(x)}}=P(x)=003x^{2}+002x+001$

Recalcule $P(x)$ onde $E(x)=0:\{2,3\}$ para corrigir $b$, resultando na palavra-código corrigida:

$c=\{001,006,017,034,057,086,121\}$

Decodificador de síndrome

Por volta de 2015, um decodificador aprimorado foi desenvolvido. O decodificador gera síndromes e, semelhante à visão BCH, a equação chave entre o polinômio localizador de erros e as síndromes é a mesma, mas o polinômio localizador de erros tem raízes correspondentes a $(1/\alpha _{i})$, e uma tabela de pesquisa (lookup table) é usada para converter as raízes em deslocamentos (offsets) de palavra-código.

Inicialização:

Um polinômio é definido: $L=\prod _{i=0}^{n-1}(x-\alpha _{i})$.

Um conjunto de $n$ polinômios é definido: $L_{i}=L/(x-\alpha _{i})$.

Um conjunto de $n$ valores é gerado: $u_{i}=L_{i}(\alpha _{i})$.

Um conjunto de $n$ polinômios é gerado: $P_{i}=(u_{i}/(1-\alpha _{i}z)){\bmod {(}}z^{n-k})$

Decodificação - Uma palavra-código com possíveis erros é recebida: $r=\{r_{0},r_{1},\dots ,r_{n-1}\}$.

Um polinômio de síndrome é gerado: $S=\sum _{i=0}^{n-1}r_{i}P_{i}$.

Se $S=0$, então nenhum erro é detectado, caso contrário, o Euclides estendido começa com

$R_{-1}=z^{n-k}$, $R_{0}=S$, $A_{-1}=0$, $A_{0}=1$

e continua até que o grau de $R_{i}<(n-k)/2$

O polinômio localizador de erros é $\sigma =A_{i}$

e o polinômio de valor de erro é $\omega =R_{i}$

$\sigma$ e $\omega$ são divididos pelo termo menos significativo de $\sigma$

A derivada formal de $\sigma$ é gerada: $\sigma '$

Os deslocamentos $o$ dos erros correspondem às raízes de $\sigma$

para a raiz = $1/\alpha _{i}$, $o_{i}=i$

O valor de erro para $o_{i}$ é

$e_{i}=(-\alpha _{i}\ \omega (1/\alpha _{i}))/(u_{i}\ \sigma '(1/\alpha _{i}))$.

Se $\deg(\omega )=\deg(\sigma )$, então um valor de erro correspondente a $\alpha _{b}=0$

foi detectado no deslocamento $o_{b}=b$, e um valor de erro separado é calculado:

$B=\{b\mid \sigma (1/\alpha _{i})=0\}$, o conjunto de $\alpha _{i}$ correspondente às raízes de $\sigma$

$w=$ coeficiente mais significativo de $\omega$

$e_{b}=w\,u_{b}^{-1}\,\left(\prod _{\alpha \in B}(-\alpha )\right)^{-1}$

Exemplo

Usando os mesmos dados do exemplo de Berlekamp-Welch

Inicialização:

$a=\{000,001,002,003,004,005,006\}$

$u=\{040,689,600,129,600,689,040\}$

$i$	$P_{i}$
0	$040$
1	$689z^{3}+689z^{2}+689z+689$
2	$155z^{3}+542z^{2}+271z+600$
3	$696z^{3}+232z^{2}+387z+129$
4	$311z^{3}+310z^{2}+542z+600$
5	$657z^{3}+503z^{2}+658z+689$
6	$279z^{3}+511z^{2}+240z+040$

Decodificação:

$r=\{001,006,123,456,057,086,121\}$

$S=785\ z^{3}+213\ z^{2}+666\ z+055$

Euclides:

$i$	$R_{i}$	$A_{i}$
-1	$001z^{4}+000z^{3}+000z^{2}+000z+000$	$000$
0	$785z^{3}+213z^{2}+666z+055$	$001$
1	$658z^{2}+858z+323$	$200z+141$
2	$294z+709$	$905z^{2}+020z+925$

$\sigma =905\ z^{2}+020\ z+925$

$\omega =294\ z+709$

divida $\sigma$ e $\omega$ por $925$

$\sigma =006\ z^{2}+924\ z+1$

$\omega =391\ z+55$

$\sigma '=012\ z+924$

$o=\{002,003\}$

$e=\{000,000,106,422,000,000,000\}$

$c=\{001,006,017,034,057,086,121\}=r-e$

Bibliografia

• Cipra, Barry A. (1993), «The Ubiquitous Reed–Solomon Codes», SIAM News, 26 (1) 
• Berlekamp, Elwyn R. (1967), Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy 
• Berlekamp, Elwyn R. (1984) [1968], Algebraic Coding Theory, ISBN 0-89412-063-8 Revised ed. , Laguna Hills, CA: Aegean Park Press 
• Forney, Jr., G. (outubro de 1965), «On Decoding BCH Codes», IEEE Transactions on Information Theory, 11 (4): 549–557, doi:10.1109/TIT.1965.1053825 
• Gill, John (n.d.), EE387 Notes #7, Handout #28 (PDF), Stanford University, consultado em 21 de abril de 2010 
• Hong, Jonathan; Vetterli, Martin (agosto de 1995), «Simple Algorithms for BCH Decoding», IEEE Transactions on Communications, 43 (8): 2324–2333 
• Koetter, Ralf (2005), Reed–Solomon Codes, MIT Lecture Notes 6.451 (Video) ^{[ligação inativa]} 
• Lin, Shu; Costello, Jr., Daniel J. (1983), Error Control Coding: Fundamentals and Applications, ISBN 0-13-283796-X, New Jersey, NJ: Prentice-Hall 
• MacWilliams, F. J.; Sloane, N. J. A. (1977), The Theory of Error-Correcting Codes, New York, NY: North-Holland Publishing Company 
• Massey, J. L. (1969), «Shift-register synthesis and BCH decoding» (PDF), IEEE Transactions on Information Theory, IT-15 (1): 122–127 
• Peterson, Wesley W. (1960), «Encoding and Error Correction Procedures for the Bose-Chaudhuri Codes», Institute of Radio Engineers, IRE Transactions on Information Theory, IT–6: 459–470 
• Reed, Irving S.; Chen, Xuemin (1999), Error-Control Coding for Data Networks, Boston, MA: Kluwer Academic Publishers 
• Reed, Irving S.; Solomon, Gustave (1960), «Polynomial Codes over Certain Finite Fields», Journal of the Society for Industrial and Applied Mathematics (SIAM), 8 (2): 300–304, doi:10.1137/0108018 
• Welch, L. R. (1997), The Original View of Reed–Solomon Codes (PDF), Lecture Notes 

Ligações externas

• Schifra Open Source C++ Reed–Solomon Codec
• Henry Minsky's RSCode library, Reed–Solomon encoder/decoder
• Open source Verilog Reed-Solomon IP
• A Tutorial on Reed–Solomon Coding for Fault-Tolerance in RAID-like Systems
• Algebraic soft-decoding of Reed–Solomon codes
• Matlab implementation of errors and-erasures Reed–Solomon decoding
• Pure-Python implementation of a Reed-Solomon codec
• BBC R&D White Paper WHP031
• Geisel, William A. (agosto de 1990), Tutorial on Reed–Solomon Error Correction Coding (PDF), Technical Memorandum, NASA, TM-102162