  Under polynomial time reduction, the maximum likelihood decoding of a linear
code is equivalent to computing the error distance of a received word. It is
known that the decoding complexity of standard Reed-Solomon codes at certain
radius is at least as hard as the discrete logarithm problem over certain large
finite fields. This implies that computing the error distance is hard for
standard Reed-Solomon codes. Using some elegant algebraic constructions, we are
able to determine the error distance of received words whose degree is k+1 to
the Standard Reed-Solomon code or Primitive Reed-Solomon code exactly.
Moreover, we can precisely determine the error distance of received words of
degree k+2 to the Standard Reed-Solomon codes. As a corollary, we can simply
get the results of Zhang-Fu-Liao and Wu-Hong on the deep hole problem of
Reed-Solomon codes.
