Algoritmo de Berlekamp-Welch
O algoritmo de Berlekamp-Welch, também conhecido como algoritmo de Welch-Berlekamp, recebe o nome de Elwyn R. Berlekamp e Lloyd R. Welch. Trata-se de um algoritmo decodificador que corrige erros eficientemente em códigos de Reed-Solomon para um código , baseado na visão original de Reed-Solomon, onde uma mensagem é usada como coeficientes de um polinômio ou usada com a interpolação de Lagrange para gerar o polinômio de grau para entradas e, em seguida, é aplicado a para criar uma palavra-código codificada .
Definindo e {\displaystyle e} como o número de erros, o conjunto chave de n {\displaystyle n} equações é Onde E ( a i ) = 0 {\displaystyle E(a_{i})=0} para os e {\displaystyle e} casos quando b i ≠ F ( a i ) {\displaystyle b_{i}\neq F(a_{i})} , e E ( a i ) ≠ 0 {\displaystyle E(a_{i})\neq 0} para os n − e {\displaystyle n-e} casos sem erro onde b i = F ( a i ) {\displaystyle b_{i}=F(a_{i})} . Essas equações não podem ser resolvidas diretamente, mas definindo Q ( ) {\displaystyle Q()} como o produto de E ( ) {\displaystyle E()} e F ( ) {\displaystyle F()} : e adicionando a restrição de que o coeficiente mais significativo de E ( a i ) = e e = 1 {\displaystyle E(a_{i})=e_{e}=1} , o resultado levará a um conjunto de equações que podem ser resolvidas com álgebra linear. onde q = n − e − 1 {\displaystyle q=n-e-1} . Como e e {\displaystyle e_{e}} é restrito a 1 {\displaystyle 1} , as equações se tornam:
Considere um exemplo simples onde um conjunto redundante de pontos é usado para representar a reta y = 5 − x {\displaystyle y=5-x} , e um dos pontos está incorreto. Os pontos que o algoritmo recebe como entrada são ( 1 , 4 ) , ( 2 , 3 ) , ( 3 , 4 ) , ( 4 , 1 ) {\displaystyle (1,4),(2,3),(3,4),(4,1)} , onde ( 3 , 4 ) {\displaystyle (3,4)} é o ponto defeituoso. O algoritmo deve resolver o seguinte sistema de equações: Dada uma solução Q {\displaystyle Q} e E {\displaystyle E} para este sistema de equações, é evidente que em qualquer um dos pontos x = 1 , 2 , 3 , 4 {\displaystyle x=1,2,3,4} uma das seguintes afirmações deve ser verdadeira: ou Q ( x i ) = E ( x i ) = 0 {\displaystyle Q(x_{i})=E(x_{i})=0} , ou P ( x i ) = Q ( x i ) E ( x i ) = y i {\displaystyle P(x_{i})={\frac {Q(x_{i})}{E(x_{i})}}=y_{i}} . Como E {\displaystyle E} é definido tendo apenas grau um, a primeira opção só pode ser verdadeira em um ponto. Portanto, P ( x i ) {\displaystyle P(x_{i})} deve ser igual a y i {\displaystyle y_{i}} nos outros três pontos.
Considere RS ( 7 , 3 ) {\displaystyle {\text{RS}}(7,3)} ( n = 7 {\displaystyle n=7} , k = 3 {\displaystyle k=3} ) definido em GF ( 7 ) {\displaystyle {\text{GF}}(7)} com α = 3 {\displaystyle \alpha =3} e valores de entrada: a i = i − 1 : { 0 , 1 , 2 , 3 , 4 , 5 , 6 } {\displaystyle a_{i}=i-1:\{0,1,2,3,4,5,6\}} . A mensagem a ser codificada sistematicamente é { 1 , 6 , 3 } {\displaystyle \{1,6,3\}} . Usando a interpolação de Lagrange, F ( a i ) = 3 x 2 + 2 x + 1 {\displaystyle F(a_{i})=3x^{2}+2x+1} , e aplicando F ( a i ) {\displaystyle F(a_{i})} de a 4 = 3 {\displaystyle a_{4}=3} até a 7 = 6 {\displaystyle a_{7}=6} , resulta na palavra-código { 1 , 6 , 3 , 6 , 1 , 2 , 2 } {\displaystyle \{1,6,3,6,1,2,2\}} . Assuma que ocorrem erros em c 2 {\displaystyle c_{2}} e c 5 {\displaystyle c_{5}} , resultando na palavra-código recebida { 1 , 5 , 3 , 6 , 3 , 2 , 2 } {\displaystyle \{1,5,3,6,3,2,2\}} . Comece com e = 2 {\displaystyle e=2} e resolva as equações lineares:
