Multisequence shift register synthesis over commutative rings with identity with applications to decoding cyclic codes over integer residue rings
We present a new algorithm for solving the multisequence shift register synthesis problem over a commutative ring R with identity. Given a finite set of R-sequences, each of length L, the complexity of our algorithm in terms of R-multiplications is O(L-2) as L --> infinity. An important application of this algorithm is in the decoding of cyclic codes over Z(q) up to the Hartmann-Tzeng bound, where q is a prime power. Characterization of the set of monic characteristic polynomials of a prescribed set of multiple syndrome sequences leads to an efficient decoding procedure, which we further extend to decode cyclic codes over Z(m) where m is a product of prime powers.
decoding cyclic codes sequences galois rings minimal polynomials