Theory of transformation groups of polynomials over \(\mathrm{GF}(2)\) with applications to linear shift register sequences.

*(English)*Zbl 0238.20060Summary: 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.) |

##### Keywords:

group of unimodular transformations; roots of polynomials over Galois Field (2); polynomials with symmetries; linear shift register sequences
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.