I asked this question on cs.stackexchange, but the community appears to be very small and I got no response.
In the Welch-Berlekamp algorithm for decoding Reed-Solomon codes, one is given a list of points $(a_i, b_i)$ representing a message with $e$ errors on the $b_i$ in unknown locations (and $e$ is given to the algorithm). The output is a polynomial passing through all of the given points except those in which errors occurred, provided $e$ is sufficiently small.
The method involves solving a system of linear equations of the form
$$b_i E(a_i) = Q(a_i)$$
for all $i$ where $E$ has degree $e$ and $Q$ has degree at most $e+k-1$. The variables are the coefficients of $E$ and $Q$.
To ensure that $E$ has degree $e$ one usually adds the constraint that the coefficient of $x^e$ is 1 to the linear system above. However, in practice one doesn't necessarily know $e$. One inefficient (but still polynomial time) way to deal with this is to try $e$ for all values starting with $(n+k-1)/2 - 1$ going down until a solution is found.
My question is: is there a more efficient way to determine $e$? Alternatively, is there a modification to the linear system that allows one to use an upper bound on $e$ instead of the exact value?
In particular I want to use this specific decoder for Reed-Solomon codes, and not a completely different algorithm based on other techniques.