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 .
O objetivo do decodificador é recuperar o polinômio de codificação original , usando as entradas conhecidas e a palavra-código recebida com possíveis erros. Ele também calcula um polinômio de erro , onde corresponde aos erros na palavra-código recebida.
As equações chave Definindo como o número de erros, o conjunto chave de equações é
Onde para os casos quando , e para os casos sem erro onde . Essas equações não podem ser resolvidas diretamente, mas definindo como o produto de e :
e adicionando a restrição de que o coeficiente mais significativo de , o resultado levará a um conjunto de equações que podem ser resolvidas com álgebra linear.
onde . Como é restrito a , as equações se tornam:
resultando em um conjunto de equações que pode ser resolvido usando álgebra linear, com complexidade de tempo .
O algoritmo começa assumindo o número máximo de erros . Se as equações não puderem ser resolvidas (devido à redundância), é reduzido em e o processo é repetido, até que as equações possam ser resolvidas ou seja reduzido a , indicando a ausência de erros. Se tiver resto , então e os valores da palavra-código são calculados para as localizações onde para recuperar a palavra-código original. Se o resto , então um erro incorrigível foi detectado.
Exemplo simples miniaturadaimagem|O polinômio localizador de erros serve para "neutralizar" os erros em fazendo com que seja zero naqueles pontos, de modo que o sistema de equações lineares não seja afetado pela imprecisão na entrada. Considere um exemplo simples onde um conjunto redundante de pontos é usado para representar a reta , e um dos pontos está incorreto. Os pontos que o algoritmo recebe como entrada são , onde é o ponto defeituoso. O algoritmo deve resolver o seguinte sistema de equações:
Dada uma solução e para este sistema de equações, é evidente que em qualquer um dos pontos uma das seguintes afirmações deve ser verdadeira: ou , ou . Como é definido tendo apenas grau um, a primeira opção só pode ser verdadeira em um ponto. Portanto, deve ser igual a nos outros três pontos.
Fazendo e e trazendo para a esquerda, podemos reescrever o sistema assim:
Este sistema pode ser resolvido através da eliminação gaussiana, fornecendo os valores:
Assim, , . Dividir os dois fornece:
se ajusta a três dos quatro pontos dados, então é o mais provável de ser o polinômio original.
Exemplo Considere (, ) definido em com e valores de entrada: . A mensagem a ser codificada sistematicamente é . Usando a interpolação de Lagrange, , e aplicando de até , resulta na palavra-código . Assuma que ocorrem erros em e , resultando na palavra-código recebida . Comece com e resolva as equações lineares:
Começando pela parte inferior da matriz à direita, e com a restrição :
com resto .
em e Calcule e para produzir a palavra-código corrigida .
Ver também
Correção de erros de Reed-Solomon
Referências
Ligações externas
Notas de Aula do MIT sobre Teoria de Códigos Essencial – Dr. Madhu Sudan Notas de Aula da Universidade de Buffalo sobre Teoria de Códigos – Dr. Atri Rudra Algebraic Codes on Lines, Planes and Curves, An Engineering Approach – Richard E. Blahut Welch Berlekamp Decoding of Reed–Solomon Codes – L. R. Welch – A patente por Lloyd R. Welch e Elwyn R. Berlekamp