Symmetric shift registers

Jan Søreng

Vol. 85 (1979), No. 1, 201–229

DOI: 10.2140/pjm.1979.85.201

Abstract

We will study symmetric shift registers over the field GF(2) = {0,1}. The symmetric shift register 𝜃_s : {0,1}ⁿ →{0,1}ⁿ corresponding to a symmetric polynomial S(x₂,⋯,x_n) is defined by

p is a period of A ∈{0,1}ⁿ with respect to 𝜃_s if 𝜃_s^P(A) = A. If p is the least period of A, then A → 𝜃_s(A) →⋯ → 𝜃_S^P(A) = A is the cycle corresponding to A. This is the first of two papers where we will determine in a constructive way (for each S):

1. The minimal period for each A ∈{0,1}ⁿ.
2. The possible minimal periods.
3. The number of cycles corresponding to each minimal period.

Mathematical Subject Classification

Primary: 68D15, 68D15

Milestones

Received: 14 December 1977

Revised: 19 September 1978

Published: 1 November 1979