An Improvement to Generalized - Minimum - Distance Decoding

87 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987.The generalized-minimum-distance decoding algorithm developed by Forney combined an efficient method of finding candidate codewords with an acceptance criterion. If a codeword meets the acceptance criterion, then it is known to have smaller generalized distance than any other element of the code. Although this condition is sufficient, it is not necessary. It is possible that all codewords fail to satisfy the condition even if there is a unique codeword with smallest generalized distance.In this thesis, a new acceptance criterion is developed. It is shown that any codeword that satisfies the acceptance condition for generalized-minimum-distance decoding must satisfy the new condition. In addition, it is apparent that the new criterion can be satisfied when generalized-minimum-distance decoding fails to find an acceptable codeword. The conditions for which this difference is significant are discussed.The performance of this new algorithm is found for three different channels. First, the performance is evaluated for a channel with binary orthogonal signaling and additive white Gaussian noise. Next, the codeword error probability is found for a channel with M-ary orthogonal signaling. Finally, the performance is evaluated for a frequency-hopping multiple-access network. The conditions of this network are such that the packet error probability is dominated by the multiple-access interference.For generalized-minimum-distance decoding, a successful decoding can require up to $d/2$ applications of an errors-and-erasures decoding algorithm to find all possible candidate codewords ($d$ is the minimum distance of the code). For Reed-Solomon codes, each application of an errors-and-erasures decoding algorithm such as the Sugiyama algorithm or the Berelkamp-Massey algorithm requires up to $O(d\sp2)$ multiplications and/or additions. These two algorithms are modified so that the original algorithm need be applied only once. The additional applications of the errors-and-erasure decoding algorithm are replaced by an update algorithm. The update algorithm reuses the intermediate results from the original application of the errors-and-erasures algorithm to find the next candidate. It is shown that the total number of multiplications and/or additions needed to find the error locator polynomial and the error evaluator polynomial is reduced to $O(d\sp2)$.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD