zbMATH — the first resource for mathematics

A simple and general approach to the decimation of feedback shift- register sequences. (English) Zbl 0678.10011
The author proves two theorems: (1) For an arbitrary commutative ring R, let \(\sigma\) be a k-th order feedback-shift-register-sequence of elements of R and for \(h\geq 0\), \(d\geq 1\), let \(\sigma_ d^{(h)}\) be the decimated sequence starting at position h \((\sigma =(s_ n)^{\infty}_{n=0}\); \(\sigma_ d^{(h)}=(s_{h+dn})^{\infty}_{n=0})\). Then a characteristic polynomial for \(\sigma_ d^{(h)}\) is given by the characteristic polynomial of \(A^ d\), where A is the companion matrix of the characteristic polynomial of the sequence \(\sigma\). (2) The generalization of the previous theorem to the case where R is replaced by an arbitrary left R-module M.
Reviewer: H.J.Tiersma

11B37 Recurrences
11T99 Finite fields and commutative rings (number-theoretic aspects)
94B99 Theory of error-correcting codes and error-detecting codes