Comment déterminez-vous le nombre d'erreurs dans l'algorithme Welch-Berlekamp?

Dans l'algorithme Welch-Berlekamp de décodage des codes Reed-Solomon, on donne une liste de points$(a_i, b_i)$ représentant un message avec $e$ erreurs sur le $b_i$ dans des emplacements inconnus (et $e$ est donné à l'algorithme). La sortie est un polynôme passant par tous les points donnés à l'exception de ceux dans lesquels des erreurs se sont produites.

La méthode consiste à résoudre un système d'équations linéaires de la forme

pour tout $i$ où $E$ a le degré $e$ et $Q$ a le degré au plus $e+k$ . Les variables sont les coefficients de $E$ et $Q$ .

Pour s'assurer que $E$ a le degré $e$ on ajoute généralement la contrainte que le coefficient de $x^e$ est 1 au système linéaire ci-dessus. Cependant, dans la pratique, on ne sait pas nécessairement $e$ . Une façon inefficace (mais toujours polynomiale) de résoudre ce problème consiste à essayer $e$ pour toutes les valeurs commençant par $(n+k-1)/2 - 1$ descendant jusqu'à ce qu'une solution soit trouvée.

Ma question est: existe-t-il un moyen plus efficace de déterminer $e$ ? Sinon, y a-t-il une modification du système linéaire qui permet d'utiliser une borne supérieure sur $e$ au lieu de la valeur exacte?

En particulier, je veux utiliser ce décodeur spécifique pour les codes Reed-Solomon, et non un algorithme complètement différent basé sur d'autres techniques.

En réponse à la réponse de DW, voici mon exemple de travail. Tout est fait modulo 7.

plain message is: [2, 3, 2]
polynomial is: 2 + 3 t^1 + 2 t^2
encoded message is: [[0, 2], [1, 0], [2, 2], [3, 1], [4, 4]]
corrupted message is: [[0, 2], [1, 0], [2, 3], [3, 1], [4, 4]]

L'erreur se situe donc au troisième point.

Lorsque $e=2$ l'équation polynomiale en question est

Et brancher donne le système sous forme matricielle:$x = 0,1,2,3,4$

[2, 0, 0, 6, 0, 0, 0, 0, 0]
[0, 0, 0, 6, 6, 6, 6, 6, 0]
[3, 6, 5, 6, 5, 3, 6, 5, 0]
[1, 3, 2, 6, 4, 5, 1, 3, 0]
[4, 2, 1, 6, 3, 5, 6, 3, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 1]

La dernière ligne est la contrainte que . En appliquant l'élimination gaussienne, nous obtenons$e_2 = 1$

[1, 0, 0, 0, 0, 0, 1, 4, 0]
[0, 1, 0, 0, 0, 0, 3, 3, 1]
[0, 0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 0, 2, 1, 0]
[0, 0, 0, 0, 1, 0, 2, 2, 5]
[0, 0, 0, 0, 0, 1, 4, 5, 2]

Et en choisissant 1 pour les deux variables libres, nous obtenons un vecteur de solution de

[2, 2, 1, 4, 1, 0, 1, 1]

Ce qui se traduit par

E is 2 + 2 t^1 + 1 t^2
Q is 4 + 1 t^1 + 0 t^2 + 1 t^3 + 1 t^4

Et ne divise pas Q . Notez que Q facteurs comme$E$$Q$$Q$$(t + 6) (t^3 + 2t^2 + 2t + 3) \mod 7$

Pour j'obtiens une bonne solution:$e=1$

system is:    
[2, 0, 6, 0, 0, 0, 0]
[0, 0, 6, 6, 6, 6, 0]
[3, 6, 6, 5, 3, 6, 0]
[1, 3, 6, 4, 5, 1, 0]
[4, 2, 6, 3, 5, 6, 0] 
[0, 1, 0, 0, 0, 0, 1]

reduced system is:

[1, 0, 0, 0, 0, 0, 5]
[0, 1, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 3]
[0, 0, 0, 1, 0, 0, 3]
[0, 0, 0, 0, 1, 0, 6]
[0, 0, 0, 0, 0, 1, 2]

solution is [5, 1, 3, 3, 6, 2]
Q is 3 + 3 t^1 + 6 t^2 + 2 t^3
E is 5 + 1 t^1
P(x) = 2 + 3 t^1 + 2 t^2 # this is correct!
r(x) = 0

Notez que bien que le contre-exemple ci-dessus ait été généré par du code que j'ai écrit à partir de zéro (c'était essentiellement la première chose que j'essayais), on peut vérifier que les solutions sont valides à la main, donc même si mon code est bogué, c'est toujours un contre-exemple valide pour la revendication que l'utilisation de fonctionne.$e=2$

$e$

$E(x)$$a_i$$E(x)$$e$

$e$$E(x)$$e$$e$$E(x)$$e$

$E(x)$$e$$E(x)$$E(x)$$n-e$

Pour documenter le résultat de la conversation sur le "contre-exemple" dans la question:

$n-k+1$$(n-k)/2$$n=5$$k=3$$(n-k)/2=1$$e=1$$e=2$

Ainsi, le contre-exemple n'est pas réellement un contre-exemple, et il ne contredit pas ma réponse ci-dessus.