  A new Chase-type soft-decision decoding algorithm for Reed-Solomon codes is
proposed, referred to as tree-based Chase-type algorithm}. The proposed
tree-based Chase-type algorithm takes the set of all vectors as the set of
testing patterns, and hence definitely delivers the most-likely codeword
provided that the computational resources are allowed. All the testing patterns
are arranged in an ordered rooted tree according to the likelihood bounds of
the possibly generated codewords, which is an extension of Wu and Pados' method
from binary into $q$-ary linear block codes. While performing the algorithm,
the ordered rooted tree is constructed progressively by adding at most two
leafs at each trial. The ordered tree naturally induces a sufficient condition
for the most-likely codeword. That is, whenever the tree-based Chase-type
algorithm exits before a preset maximum number of trials is reached, the output
codeword must be the most-likely one. But, in fact, the algorithm can be
terminated by setting a discrepancy threshold instead of a maximum number of
trials. When the tree-based Chase-type algorithm is combined with
Guruswami-Sudan (GS) algorithm, each trial can be implement in an extremely
simple way by removing from the gradually updated Grobner basis one old point
and interpolating one new point. Simulation results show that the tree-based
Chase-type algorithm performs better than the recently proposed Chase-type
algorithm by Bellorado et al with less trials (on average) given that the
maximum number of trials is the same.
