Double Adjacencies Between Cycles of a Circulating Shift Register
E.J. Van Lantschoot · IEEE Transactions on Computers · 1973
A circulating shift register is an n-stage binary shift register with feedback from stage n to stage 1. We refer to the state cycles of the circulating shift register as natural cycles. Two natural cycles are adjacent if there is a state in the first natural cycle that differs from a state in the second only in the first digit. Double adjacencies between natural cycles occur quite frequently. A necessary and sufficient condition for their existence is developed. A contained cycle arises when both transition possibilities between two doubly adjacent natural cycles are exploited. A formula for the length of contained cycles is given, and an algorithm for finding contained cycles of prespecified length is developed. Reversible natural cycles are cycles that contain, for any n-tuple, also the same n-tuple written backwards (allowing for a cyclical shift). It is shown how double adjacencies are related to reversibility. It is also shown that double adjacencies come in strings that may be of two types, either connecting reversible or connecting nonreversible natural cycles.