An Improvement to Generalized - Minimum - Distance Decoding
Taipale, Dana John
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69382
Description
Title
An Improvement to Generalized - Minimum - Distance Decoding
Author(s)
Taipale, Dana John
Issue Date
1987
Doctoral Committee Chair(s)
Pursley, Michael B.
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Abstract
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)$.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
