×

zbMATH — the first resource for mathematics

Theory of transformation groups of polynomials over \(\mathrm{GF}(2)\) with applications to linear shift register sequences. (English) Zbl 0238.20060
Summary: The group of unimodular transformations on the roots of polynomials over \(\mathrm{GF}(2)\) is considered, and those polynomials with symmetries in the unimodular group are identified. The cross-correlation function between two maximum-length linear shift register sequences of the same degree is shown to be computable as an explicit linear transformation, in matrix form, on either one of the sequences, regarded as a vector. The underlying vector space is the “cyclotomic algebra”, generated by the cyclotomic cosets, or by what Gauss termed the “periods” of the cyclotomic equation. A variety of numerical examples are worked in detail.

MSC:
94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
11T22 Cyclotomy
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Golomb, S.W., Shift register sequences, (1967), Holden-Day
[2] Selmer, E.S., Linear recurrence relations over finite fields, (1966), Department of Mathematics, Univ. of Bergen Norway
[3] Kasami, Tadao, Weight distribution formula for some class of cyclic codes, () · Zbl 1059.94035
[4] Solomon, G.; McEleice, R., Weights of cyclic codes, Journal of combinatorial theory, Vol. 1, No. 4, (December, 1966)
[5] Gold, R., Optimum binary sequences for spread-spectrum multiplexing, IEEE trans. on information theory, (October, 1967)
[6] Gold, R., Maximal recursive sequences with three-valued recursive cross-correlation function, IEEE trans. on information theory, (January, 1968)
[7] Welch, L.R., Trace mappings in finite fields and shift register cross-correlation properties, (), to appear
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.