  In this paper we devise a rational curve fitting algorithm and apply it to
the list decoding of Reed-Solomon and BCH codes. The proposed list decoding
algorithms exhibit the following significant properties. 1 The algorithm
corrects up to $n(1-\sqrt{1-D})$ errors for a (generalized) $(n, k, d=n-k+1)$
Reed-Solomon code, which matches the Johnson bound, where $D\eqdef \frac{d}{n}$
denotes the normalized minimum distance. In comparison with the Guruswami-Sudan
algorithm, which exhibits the same list correction capability, the former
requires multiplicity, which dictates the algorithmic complexity,
$O(n(1-\sqrt{1-D}))$, whereas the latter requires multiplicity $O(n^2(1-D))$.
With the up-to-date most efficient implementation, the former has complexity
$O(n^{6}(1-\sqrt{1-D})^{7/2})$, whereas the latter has complexity
$O(n^{10}(1-D)^4)$. 2. With the multiplicity set to one, the derivative list
correction capability precisely sits in between the conventional hard-decision
decoding and the optimal list decoding. Moreover, the number of candidate
codewords is upper bounded by a constant for a fixed code rate and thus, the
derivative algorithm exhibits quadratic complexity $O(n^2)$. 3. By utilizing
the unique properties of the Berlekamp algorithm, the algorithm corrects up to
$\frac{n}{2}(1-\sqrt{1-2D})$ errors for a narrow-sense $(n, k, d)$ binary BCH
code, which matches the Johnson bound for binary codes. The algorithmic
complexity is $O(n^{6}(1-\sqrt{1-2D})^7)$.
