DECODING CYCLIC AND BCH CODES UP TO ACTUAL MINIMUM DISTANCE USING NONRECURRENT SYNDROME DEPENDENCE RELATIONS

The decoding capabilities of algebraic algorithms, mainly the Berlekamp-Massey algorithm, the Euclidean algorithm and our generalizations of these algorithms, are basically constrained by the minimum distance bounds of the codes. Thus, when the actual minimum distance of the codes is greater than that given by the bounds, these algorithms usually cannot fully utilize the error-correcting capability of the codes. The limitation is seen to be rooted in the original Peterson decoding procedure adhered to by these algorithms. Thus, these algorithms all require the determination of the error-locator polynomial from Newton's identities which in turn require that the syndromes be contiguous in forming a set or multiple sets of linear recurrences. A procedure is introduced that breaks away from this restriction and can determine the error locations from nonrecurrent syndrome dependence relations. This procedure employs an algorithm that has recently been introduced as a basis for the derivation of the Berlekamp-Massey algorithm and its generalization. It can decode many cyclic and BCH codes up to their actual minimum distance and is seen to be a generalization of Peterson's procedure.