We develop a computationally efficient soft-decision Reed-Solomon (RS) decoding algorithm. Our new algorithm has direct applications to soft-decision decoding procedures such as the generalized-minimum-distance decoding algorithm. Our particular soft-decision decoding technique is not the innovation of the algorithm. The innovation is a new errors-and-erasures RS decoding algorithm that only works with different sets of erasures where the size of each set of erasures is reduced by one for each iteration (i.e., generalized-minimum-distance decoding). A result of each iteration is an error-and-erasure locator polynomial (or locator polynomials) that any RS decoder would produce. Since the new soft-decision RS decoding algorithm makes no assumptions on the d-1 erasures, the algorithm is useful for soft-decision decoding techniques such as generalized-minimum-distance decoding.>

A novel acceptance criterion that is less stringent than previous criteria is developed. The criterion accepts the codeword that is closest to the received vector for many cases where previous criteria fail to accept any codeword. As a result, the performance of generalized minimum distance (GMD) decoding is better if the new criterion is used. For M-ary signaling, the weights used in GMD decoding are generalized to permit each of the possible M symbol values to have a different weight.>

The use of convolutional coding in packet radio systems introduces problems in evaluating performance, since the errors out of the decoder are not independent. A new bound on the packet error probability out of a Viterbi decoder may be used to evaluate these systems. We present results on the packet error probability for frequencyhop and direct-sequence spread-spectrum systems. In addition, we show that the assumption of independent errors out of the decoder gives an upper bound that is not as tight as our new bound. Comparisons are made with frequency-hop systems using Reed-Solomon codes.