  In this paper, we characterize the decoding region of algebraic soft decoding
(ASD) of Reed-Solomon (RS) codes over erasure channels and binary symmetric
channel (BSC). Optimal multiplicity assignment strategies (MAS) are
investigated and tight bounds are derived to show the ASD can significantly
outperform conventional Berlekamp Massey (BM) decoding over these channels for
a wide code rate range. The analysis technique can also be extended to other
channel models, e.g., RS coded modulation over erasure channels.
