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 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 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 {\displaystyle k} (comprimento da mensagem não codificada) a partir de n {\displaystyle 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.
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 ) {\displaystyle (32,28)} relativamente fraco, encurtado de um código ( 255 , 251 ) {\displaystyle (255,251)} com símbolos de 8 bits. Este código pode corrigir até 2 {\displaystyle 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 {\displaystyle 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 ) {\displaystyle (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 {\displaystyle 4} apagamentos desse tipo por bloco.
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 RS ( N , K ) {\displaystyle {\text{RS}}(N,K)} que resulta em N {\displaystyle N} palavras-código de comprimento de N {\displaystyle N} símbolos, cada uma armazenando K {\displaystyle K} símbolos de dados, que são então enviadas através de um canal de apagamento. Qualquer combinação de K {\displaystyle K} palavras-código recebidas na outra extremidade é suficiente para reconstruir todas as N {\displaystyle N} palavras-código. A taxa de código é geralmente definida como 1 / 2 {\displaystyle 1/2} , a menos que a probabilidade de apagamento do canal possa ser modelada adequadamente e verifique-se ser menor. Em conclusão, N {\displaystyle N} geralmente é 2 K {\displaystyle 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.
Transmissão espacial
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.
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 {\displaystyle q} , um comprimento de bloco n {\displaystyle n} e um comprimento de mensagem k {\displaystyle k} , com k < n ≤ q {\displaystyle k<n\leq q} . O conjunto de símbolos do alfabeto é interpretado como o corpo finito F {\displaystyle F} de ordem q {\displaystyle q} e, assim, q {\displaystyle 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 = k n {\displaystyle 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 {\displaystyle n=q} ou n = q − 1 {\displaystyle 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 {\displaystyle 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 {\displaystyle q} ) são tratados como os coeficientes de um polinômio p {\displaystyle p} de grau menor que k {\displaystyle k} , sobre o corpo finito F {\displaystyle F} com q {\displaystyle q} elementos. Por sua vez, o polinômio p {\displaystyle p} é avaliado em um conjunto de n ≤ q {\displaystyle n\leq q} pontos distintos em qualquer ordem a 1 , … , a n {\displaystyle a_{1},\dots ,a_{n}} do corpo F {\displaystyle 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 , … , n − 1 } {\displaystyle \{0,1,2,\dots ,n-1\}} , { 0 , 1 , α , α 2 , … , α n − 2 } {\displaystyle \{0,1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-2}\}} , ou para n < q {\displaystyle n<q} , { 1 , α , α 2 , … , α n − 1 } {\displaystyle \{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}} , ... , onde α {\displaystyle \alpha } é um elemento primitivo de F {\displaystyle F} .
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 ) {\displaystyle m(x)} : m ( x ) = m k − 1 x k − 1 + m k − 2 x k − 2 + ⋯ + m 1 x + m 0 {\displaystyle 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 ) {\displaystyle g(x)} é definido como o polinômio cujas raízes são potências sequenciais do elemento primitivo do Corpo de Galois α {\displaystyle \alpha } g ( x ) = ( x − α i ) ( x − α i + 1 ) ⋯ ( x − α i + n − k − 1 ) = x n − k + g n − k − 1 x n − k − 1 + ⋯ + g 1 x + g 0 {\displaystyle 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}}
O código de Reed-Solomon é um código [ n , k , n − k + 1 ] {\displaystyle [n,k,n-k+1]} ; em outras palavras, é um código de bloco linear de comprimento n {\displaystyle n} (sobre F {\displaystyle F} ) com dimensão k {\displaystyle k} e distância de Hamming mínima d min = n − k + 1 {\displaystyle 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 ) {\displaystyle (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 {\displaystyle 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 {\displaystyle (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 2 E + S ≤ n − k {\displaystyle 2E+S\leq n-k} seja satisfeita, onde E {\displaystyle E} é o número de erros e S {\displaystyle S} é o número de apagamentos no bloco.
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).
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
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). A mensagem transmitida, ( c 0 , … , c i , … , c n − 1 ) {\displaystyle (c_{0},\dots ,c_{i},\dots ,c_{n-1})} , é vista como os coeficientes de um polinômio s ( x ) = ∑ i = 0 n − 1 c i x i . {\displaystyle s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}.} Como resultado do procedimento de codificação de Reed-Solomon, s ( x ) {\displaystyle s(x)} é divisível pelo polinômio gerador g ( x ) = ∏ j = 1 n − k ( x − α j ) , {\displaystyle g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),} onde α {\displaystyle \alpha } é um elemento primitivo.
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 Λ ( x ) {\displaystyle \Lambda (x)} com um número presumido de erros e {\displaystyle e} : Δ = S i + Λ 1 S i − 1 + ⋯ + Λ e S i − e {\displaystyle \Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}} e então ajusta Λ ( x ) {\displaystyle \Lambda (x)} e e {\displaystyle e} para que um Δ {\displaystyle \Delta } recalculado seja zero. O artigo do Algoritmo de Berlekamp-Massey traz uma descrição detalhada do procedimento. No exemplo a seguir, C ( x ) {\displaystyle C(x)} é usado para representar Λ ( x ) {\displaystyle \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 ) {\displaystyle S(x)} , Λ ( x ) {\displaystyle \Lambda (x)} e Ω ( x ) {\displaystyle \Omega (x)} para t {\displaystyle t} síndromes e e {\displaystyle e} erros: S ( x ) = S t x t − 1 + S t − 1 x t − 2 + ⋯ + S 2 x + S 1 Λ ( x ) = Λ e x e + Λ e − 1 x e − 1 + ⋯ + Λ 1 x + 1 Ω ( x ) = Ω e x e + Ω e − 1 x e − 1 + ⋯ + Ω 1 x + Ω 0 {\displaystyle {\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}}}
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 ) {\displaystyle c(x)=s(x)} a palavra-código codificada. r ( x ) {\displaystyle r(x)} e e ( x ) {\displaystyle e(x)} são iguais aos descritos acima. Defina C ( x ) {\displaystyle C(x)} , E ( x ) {\displaystyle E(x)} e R ( x ) {\displaystyle R(x)} como as transformadas discretas de Fourier de c ( x ) {\displaystyle c(x)} , e ( x ) {\displaystyle e(x)} e r ( x ) {\displaystyle r(x)} . Como r ( x ) = c ( x ) + e ( x ) {\displaystyle r(x)=c(x)+e(x)} , e como uma transformada discreta de Fourier é um operador linear, R ( x ) = C ( x ) + E ( x ) {\displaystyle R(x)=C(x)+E(x)} .
Decodificação além do limite de correção de erros
O Limite de Singleton afirma que a distância mínima d {\displaystyle d} de um código de bloco linear de tamanho ( n , k ) {\displaystyle (n,k)} é limitada superiormente por n − k + 1 {\displaystyle n-k+1} . A distância d {\displaystyle d} era geralmente entendida como um limite à capacidade de correção de erros em ⌊ ( d − 1 ) / 2 ⌋ {\displaystyle \lfloor (d-1)/2\rfloor } . O código de Reed-Solomon atinge esse limite com igualdade e, portanto, pode corrigir até ⌊ ( n − k ) / 2 ⌋ {\displaystyle \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 G F ( 2 m ) {\displaystyle GF(2^{m})} e suas extensões.
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.
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 {\displaystyle a_{1}} a a n {\displaystyle 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 {\displaystyle n} valores de palavras-código, tomados k {\displaystyle 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, ( n k ) = n ! ( n − k ) ! k ! {\displaystyle {\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 ) {\displaystyle (255,249)} que pode corrigir 3 {\displaystyle 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 ) {\displaystyle O(n^{3})} , onde n {\displaystyle 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. Usando RS(7,3), GF(929), e o conjunto de pontos de avaliação a i = i − 1 {\displaystyle a_{i}=i-1} Erros de transmissão podem fazer com que isto seja recebido em vez disso:
Decodificador de Gao
Em 2002, um decodificador aprimorado foi desenvolvido por Shuhong Gao, baseado no algoritmo de Euclides estendido. Para duplicar os polinômios gerados por Berlekamp-Welch, divida Q ( x ) {\displaystyle Q(x)} e E ( x ) {\displaystyle E(x)} pelo coeficiente mais significativo de E ( x ) {\displaystyle E(x)} , que é 708 {\displaystyle 708} . Recalcule P ( x ) {\displaystyle P(x)} onde E ( x ) = 0 : { 2 , 3 } {\displaystyle E(x)=0:\{2,3\}} para corrigir b {\displaystyle b} , resultando na palavra-código corrigida:
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 / α i ) {\displaystyle (1/\alpha _{i})} , e uma tabela de pesquisa (lookup table) é usada para converter as raízes em deslocamentos (offsets) de palavra-código. Um polinômio é definido: L = ∏ i = 0 n − 1 ( x − α i ) {\displaystyle L=\prod _{i=0}^{n-1}(x-\alpha _{i})} . Um conjunto de n {\displaystyle n} polinômios é definido: L i = L / ( x − α i ) {\displaystyle L_{i}=L/(x-\alpha _{i})} .
