MALFUNCTION IN THE PETERSON-GORENSTEIN-ZIERLER DECODER

Most versions of the Peterson-Gorenstein-Zierler (PGZ) decoding algori thm are not true bounded distance decoding algorithms in the sense tha t when a received vector is not in the decoding sphere of any codeword , the algorithm does not always declare a decoding failure. For a t-er ror-correcting BCH code, if the received vector is at distance i, i le ss than or equal to t from a codeword in a supercede with BCH distance t + i + 1, the decoder Hill output that codeword from the supercede. If that codeword is not a member of the t-error-correcting code, then decoder malfunction is said to have occurred. We describe the necessar y and sufficient conditions for decoder malfunction, and show that mal function can be avoided in the PGZ decoder by checking t - v equations , where v is the number of errors hypothesized by the decoder. A formu la for the probability of decoder malfunction is also given, and the s ignificance of decoder malfunction is considered for PGZ decoders and high-speed Berlekamp-Massey decoders.