We describe a number theoretic view on binary shift registers. We illustrate this approach on some basic shift registers by revisiting known and obtaining new results, which we prove using tools from basic number theory, including modular arithmetic.
Hinweise
This work was supported by The Research Council of Norway under project 247742/O70. An extended abstract version was presented at Sequences and Their Applications 2020.
1 Introduction
The cycles produced by binary shift registers, as well as the representative member used to denote them, are for reasons of brevity sometimes given in decimal notation instead of as binary sequences, see for example [3, 6, 12]. This simple observation piqued our interest to investigate an alternative view on the theory of shift registers where we move away from the traditional approach of binary sequences and work entirely with the corresponding integers.
After providing basic information on the necessary theory using the new approach in Section 2, we apply it on some basic registers to study their cycle structure (Section 3) and adjacency graphs (Section 4) using tools from basic number theory, including modular arithmetic. Apart from re-obtaining known results, our contributions include simple criteria for determining cycle lengths, the enumeration of cycles of fixed length, and a new connection between the pure and complemented cycling and summing registers.
Anzeige
Our main aim is to provide a unified description of this number theoretic approach. Its general usefulness as a tool for studying shift registers beyond the examples given here remains to be seen.
2 From binary sequences to modular arithmetic
Any non-singular binary feedback shift register of order n can be defined in terms of a bijective map \(g: \mathbb {F}_2^n \rightarrow \mathbb {F}_2^n\) given by
$$\begin{aligned} g(s_0,\ldots ,s_{n-1})=(s_{1},\ldots ,s_{n-1},s_0\oplus F ( s_{1},\ldots ,s_{n-1} )), \end{aligned}$$
(1)
for some Boolean function \(F: \mathbb {F}_2^{n-1} \rightarrow \mathbb {F}_2\) [4].
We can shift from binary tuples to modular arithmetic by considering each k-tuple \((s_0,\ldots ,s_{k-1})\in \mathbb {F}_2^k\) as the binary representation of the integer \({\sum }_{i=0}^{k-1}s_i2^{k-1-i} \in \mathbb {Z}_{2^{k}}\). The corresponding functions will be \(F:\mathbb {Z}_{2^{n-1}} \rightarrow \mathbb {Z}_2\) and \(g: \mathbb {Z}_{2^{n}} \rightarrow \mathbb {Z}_{2^{n}}\) given by
Rewriting this in terms of the support of F, namely the set \(\mathcal {D}\subseteq \mathbb {Z}_{2^{n-1}}\) such that \(x\in \mathcal {D}\) if and only if \(F(x)=1\), we obtain
We can also define the complemetary map of \(g_{n,\mathcal {D}}\) as \(\overline{g}_{n,\mathcal {D}}=g_{n,\mathbb {Z}_{2^{n-1}}\setminus \mathcal {D}}\enspace\).
Example 1
Two basic, yet important maps are \(g_{n,\emptyset }\), called the Pure Cycling Register of order n (\(PCR_n\)), and its complementary map \(g_{n,\mathbb {Z}_{2^{n-1}}}\), called the Complemented Cycling Register of order n (\(CCR_n\)). For brevity we will be respectively denoting them by \(g_{p_n}\) and \(g_{c_n}\). They are given by
For each \(x \in \mathbb {Z}_{2^n}\), the smallest \(i \in \mathbb {Z}\) such that \(x=g_{n,\mathcal {D}}^i(x)\) is called its period with respect to\(g_{n,\mathcal {D}}\) and denoted by \(p_{g_{n,\mathcal {D}}}(x)\), where \(g_{n,\mathcal {D}}^i\) denotes the composition of \(g_{n,\mathcal {D}}\) with itself i times. Each map \(g_{n,\mathcal {D}}\) partitions \(\mathbb {Z}_{2^n}\) into cycles. We say \(x_1,x_2 \in \mathbb {Z}_{2^n}\) belong to the same cycle if and only if \(x_2=g_{n,\mathcal {D}}^i(x_1)\) for some i such that \(1\le i < p_{g_{n,\mathcal {D}}}(x_1)\). We shall denote each cycle by \(C_t\) where t is its smallest member. The number of elements in a cycle is called its length and equals their period. In case there is a single cycle we call it a maximal length or full or de Bruijn cycle. Mykkeltveit [9] proved the conjecture of Golomb [4] that no more than \(Z(n)=\frac{1}{n}\sum _{d \mid n}\phi (d)2^{n/d}\) cycles can be obtained from any map \(g_{n,\mathcal {D}}\), where \(\phi\) is Euler’s Totient function.
Example 2
The 8 cycles from \(PCR_5\) are \(C_0=\{0\}\), \(C_1=\{\)1,2,4,8,16\(\}\), \(C_3=\)\(\{\)3,6,12,24,17\(\}\), \(C_5=\{\)5,10,20,9,18\(\}\), \(C_7=\{\)7,14,28,25,19\(\}\), \(C_{11}=\)\(\{\)11,22,13,26,21\(\}\), \(C_{15}=\{\)15,30,29,27,23\(\}\), and \(C_{31}=\{\)31\(\}\). The 4 cycles from \(CCR_5\) are \(C_0=\{\)0,1,3,7,15,31,30,28,24,16\(\}\), \(C_2=\{\)2,5,11,23,14,29,26,20,8,17\(\}\), \(C_4=\{\)4,9,19,6,13,27,22,12,25,18\(\}\) and \(C_{10}=\{\)10,21\(\}\).
Complements and weights
For \(x \in \mathbb {Z}_{2^n}\), its complement is \(\overline{x}=2^n-1-x\) and its weight, denoted by \(\text {wt}(x)\), is the number of ones in its binary representation. By (1) we can deduce that \(\text {wt}(x)-1\le \text {wt}(g_{n,\mathcal {D}}(x))\le \text {wt}(x)+1\), and clearly
The function F in (1) for \(PCR_n\) is 0 and for \(CCR_n\) 1 for all inputs. Thus, for any \(x \in \mathbb {Z}_{2^n}\), \(PCR_n\) simply cyclically shifts the binary representation of x and therefore
\(CCR_n\) also complements the last bit after shifting, thus weights differ by one:
$$\begin{aligned} \text {wt}(g_{c_n}(x)) = \left\{ \begin{array}{rl} \text {wt}(x)+1 &{} \text { if } x < 2^{n-1}\\ \text {wt}(x)-1 &{} \text { if } x \ge 2^{n-1}.\\ \end{array}\right. \end{aligned}$$
(7)
If the complements of a cycle’s elements are all on one cycle of the same length, we say the two cycles are the complement of each other. A self-dual cycle is one that is its own complement, and thus has to have even length.
Example 4
In \(PCR_5\), the complements of \(C_0\), \(C_1\), \(C_3\) and \(C_5\) are respectively \(C_{31}\), \(C_{15}\), \(C_7\) and \(C_{11}\). Every \(CCR_5\) cycle is self-dual.
Adjacency graphs
The adjacency graph of a map \(g_{n,\mathcal {D}}\) is the undirected connected graph with vertices the map’s cycles, and for each \(x \in \mathbb {Z}_{2^{n-1}}\) an edge labelled x between the cycle containing x and the cycle containing \(\overline{g}_{n,\mathcal {D}}(x)\). An edge from a cycle to itself is called intracyclic, and extracyclic otherwise. For brevity, we represent multiple edges between two cycles by a single edge labelled by the set of the corresponding labels that we call the adjacency set.
Fig. 1
The adjacency graph of \(PCR_5\) (above) and \(CCR_5\) (below)
×
Example 5
The adjacency graphs of \(PCR_5\) and \(CCR_5\) are given in Fig. 1.
The study of adjacency sets provides guidelines for joining and splitting cycles from a map \(g_{n,\mathcal {D}}\). Adding an element of an adjacency set to \(\mathcal {D}\) if it does not exist, or removing it if it does, affects the cycles connected by the edge it labels. If the edge is extracyclic then the two cycles sharing it merge into a single cycle, otherwise the corresponding cycle splits into two cycles. By joining all cycles, we obtain a de Bruijn cycle.
Two distinct \(x_1,x_2 \in \mathbb {Z}_{2^{n-1}}\) belong to the same adjacency set in the graph of a map \(g_{n,\mathcal {D}}\) if either
A.
\(x_1\) and \(x_2\) belong to the same cycle and \(\overline{g}_{n,\mathcal {D}}(x_1)\) and \(\overline{g}_{n,\mathcal {D}}(x_2)\) belong to the same cycle, in which case we shall call \(x_1\) and \(x_2\) an intracyclic pair, or
B.
\(x_1\) and \(\overline{g}_{n,\mathcal {D}}(x_2)\) belong to the same cycle and \(x_2\) and \(\overline{g}_{n,\mathcal {D}}(x_1)\) belong to the same cycle, in which case we shall cal \(x_1\) and \(x_2\) an extracyclic pair.
Example 6
An intracyclic pair in the graph of \(PCR_5\) are 2 and 4 which are on \(C_1\) while \(g_{c_n}(2)=5\) and \(g_{c_n}(4)=9\) are on \(C_5\). An extracyclic pair in the graph of \(CCR_5\) are 5 and 10 since 5 and \(g_{p_n}(10)=20\) are on \(C_2\), and \(g_{p_n}(5)=10\).
The two conditions for intracyclic pairs can be expressed formally as (a\(_1\)) \(x_2=g_{n,\mathcal {D}}^i(x_1)\), and (a\(_2\)) \(\overline{g}_{n,\mathcal {D}}(x_1)=g_{n,\mathcal {D}}^j(\overline{g}_{n,\mathcal {D}}(x_2))\), for some i, j such that \(1\le i < p_1\) and \(1\le j < p_2\), where \(p_1=p_{g_{n,\mathcal {D}}}(x_1)\) and \(p_2=p_{g_{n,\mathcal {D}}}(\overline{g}_{n,\mathcal {D}}(x_1))\). Together they imply
Conditions (a\(_1\)) and (a\(_2\)) are equivalent to \(x_1=g_{n,\mathcal {D}}^{p_1-i}(x_2)\) and \(\overline{g}_{n,\mathcal {D}}(x_2)= g_{n,\mathcal {D}}^{p_2-j}(\overline{g}_{n,\mathcal {D}}(x_1))\) respectively. Hence, if one member of an intracyclic pair satisfies (8) with the pair of exponents (i, j), the other member satisfies it with the pair of exponents \((p_1-i,p_2-j)\).
Similarly, the two extracyclic pair conditions can be expressed as (b\(_1\)) \(x_1=g_{n,\mathcal {D}}^i(\overline{g}_{n,\mathcal {D}}(x_2))\) and (b\(_2\)) \(x_2=g_{n,\mathcal {D}}^j(\overline{g}_{n,\mathcal {D}}(x_1))\), for some i, j such that \(1\le i < p_1\) and \(1\le j < p_2\), where \(p_1\) and \(p_2\) are as above. Together they imply
3 On the cycle structure of some basic shift registers
3.1 The pure cycling register
\(PCR_n\) was defined in Example 1. Since \(g_{p_n}(2^n-1)=2^n-1\), the \(PCR_n\) cycle \(C_{2^n-1}\) is of length 1. For any \(x \in \mathbb {Z}_{2^n}\setminus \{2^{n}-1\}\), (3) can be expressed as
The length of the cycle containing \(x \in \mathbb {Z}_{2^n}\setminus \{2^{n}-1\}\) is equal to the period \(p_{g_{p_n}}(x)\), the smallest positive exponent i such that \(2^ix \equiv x \mod 2^n-1\), or equivalently
the multiplicative order of 2 modulo this ratio. It follows that when x is coprime to \(2^n-1\), its period is equal to n, the maximum possible. Therefore, there are at least \(\frac{\phi (2^n-1)}{n}\) cycles of length n.
Proposition 1
The length of any \(PCR_n\) cycle divides n.
Proof
Suppose a \(PCR_n\) cycle has length k not dividing n, in which case \(n=ak+b\) for positive integers a and \(b<k\). For every element x in the cycle we have \(g_{p_n}^n(x)=2^nx\equiv x \mod 2^n-1\), where \(2^nx=2^{ak+b}x=2^{b}2^{ak}x \equiv 2^{b}x \mod 2^n-1\) since \(2^kx \equiv x \mod 2^n-1\). Thus \(2^{b}x\equiv x \mod 2^n-1\), a contradiction on the minimality of k. □
Let \(\zeta _n(k)\) denote the number of \(PCR_n\) cycles of length k. This number is in fact equal to the number of binary Lyndon words and irreducible polynomials of degree k over \(\mathbb {Z}_2\) [2, 13] restricted to divisors of n:
where \(\mu\) is the M\(\ddot{\mathrm {o}}\)bius function.
Golomb [4] proved that \(PCR_n\) partitions \(\mathbb {Z}_{2^n}\) into exactly Z(n) cycles. Summing \(\zeta _n(k)\) over all divisors of n, an alternative formula can be obtained.
This viewpoint reveals that the \(PCR_n\) cycles (excluding \(C_{2^n-1}\)) are in fact the same as the cyclotomic classes of 2 modulo \(2^n-1\) defined by Carlet et al. [1] in a different context. These authors also showed that the cardinality of these classes is given by (10) and that their number is \(\sum _{d \mid 2^n-1}\phi (d)/p_{g_{p_n}}(d)\).
It is easy to check that \({g_{p_n}}(\overline{x})=\overline{{g_{p_n}}(x)}\), hence every \(PCR_n\) cycle has a complement (that \(p_{{g_{p_n}}}(x)=p_{{g_{p_n}}}(\overline{x})\) also follows from (10)). By (6), all elements in a cycle have the same weight, henceforth the weight of the cycle. These two observations together with (5) imply that for each cycle of weight w there exists a distinct cycle of weight \(n-w\) of the same length, with the exception of self-dual cycles, which might exist if n is even and \(w=n/2\). Since such a (self-dual) cycle contains both x and \(\overline{x}\), we have \(2^ix\equiv -x \mod 2^n-1\) for some positive exponent i. Simplifying and combining with (10) gives
This condition cannot hold if x is coprime to \(2^n-1\) as \(2^{n/2}+1 \not \equiv 0 \mod 2^n-1\).
Let \(Z^O(n)\) and \(Z^E(n)\) respectively denote the number of \(PCR_n\) cycles of odd and even weight, and \(\zeta _n^O(k)\) and \(\zeta _n^E(k)\) those of odd and even weight and length k. From the above we can deduce that for odd n, complementary cycles have different weight parity, thus \(\zeta _n^O(k)=\zeta _n^E(k)=\zeta _n(k)/2\) and \(Z^O(n)=Z^E(n)=Z(n)/2\). We will complete the picture by determining these numbers also for even n, in which case complementary cycles have the same weight parity. Knowing \(\zeta _n(k)\) and Z(n), it in fact suffices to obtain \(\zeta _n^O(k)\) and \(Z^O(n)\).
Proposition 2
For any \(x \in {\mathbb {Z}}_n\), its weight \(\text {wt}(x)\) is divisible by \(n/p_{{g_{p_n}}}(x)\).
Proof
Consider \(x \in {\mathbb {Z}}_n\) of period \(p_{{g_{p_n}}}(x)=k\). We have \(2^kx \equiv x \mod 2^n-1\) which means \(2^n-1\) divides \((2^k-1)x\), and since k divides n, \((2^n-1)/(2^k-1)=\sum _{i=1}^{n/k}2^{n-ki}\) divides x. In other words, \(x=a\sum _{i=1}^{n/k}2^{n-ki}\) for some integer \(0\le a \le 2^k-1\). Letting \(a=\sum _{j=0}^{k-1}a_j2^{j}\), where the \(a_j\)\(\in \{0,1\}\), we get \(x=\sum _{i=1}^{n/k} \sum _{j=0}^{k-1}a_j2^{n-ki+j}\). The weight of x would be a multiple of n/k provided the powers of 2 in this sum are all distinct. This is indeed the case, as otherwise we would have \(2^{n-ki+j}=2^{n-ki^{\prime }+j^{\prime }}\) for distinct \(1 \le i,i^{\prime } \le n/k\) and \(0\le j, j^{\prime }\le k-1\), implying \(k(i^{\prime }-i)=j^{\prime }-j\), a contradiction since \(j-j^{\prime }\le k-1\). □
Corollary 2
The weight of any \(PCR_n\) cycle of length k is divisible by n/k.
where \({\nu _2}\) is the dyadic valuation, the highest power of 2 that divides an integer.
Proof
By Corollary 2, the weight of a \(PCR_n\) cycle of length k is of the form wn/k, for \(0\le w \le k\). It is odd when both w and n/k are odd, the latter implying \({\nu _2}(n)={\nu _2}(k)\), or equivalently that \(k=2^{{\nu _2}(n)}d\) for any divisor d of \(n/2^{{\nu _2}(n)}\). Also, since \({\mathbb {Z}}_{2^n}\) contains equally many elements of odd and even weight, \(\sum _{k \mid n}k~\zeta _n^O(k)=2^{n-1}\). Therefore, \(\sum _{d \mid n/2^{{\nu _2}(n)} }2^{{\nu _2}(n)}d~\zeta _n^O(2^{{\nu _2}(n)}d)=2^{n-1}\). Substituting \(n^{\prime }=n/2^{{\nu _2}(n)}\) in the sum’s range and the RHS, and applying M\(\ddot{\text {o}}\)bius inversion we obtain \(\zeta _n^O(2^{{\nu _2}(n)}d)= \frac{1}{2^{{\nu _2}(n)}d} \sum _{d^{\prime } \mid d}\mu (d^{\prime })2^{2^{{\nu _2}(n)} \frac{d}{d^{\prime }} -1}\). Finally, using \(k=2^{{\nu _2}(n)}d\) gives the required form. □
Summing \(\zeta _n^O({2^{{\nu _2}(n)}d})\) over all divisors d of \(n/2^{{\nu _2}(n)}\) we obtain \(Z^O(n)\). Then, we can obtain a closed formula for \(Z^E(n)=Z(n)-Z^O(n)\), despite being unable to obtain a nice one for \(\zeta _n^E(k)=\zeta _n(k)-\zeta _n^O(k)\). The proof is a straightforward simplification of this difference, using \(\sum _{d\mid n}f(d)=\sum _{d\mid n/2^{{\nu _2}(n)}}\sum _{l=0}^{{\nu _2}(n)}f(2^ld)\).
The length of the \(CCR_n\) cycle containing \(x \in {\mathbb {Z}}_{2^n}\) is equal to the period \(p_{{g_{c_n}}}(x)\), the smallest positive exponent i such that \({g_{c_n}^i}(x)=x\). Using (14) this is equivalent to \(2^i(x+1) \equiv x+1 \mod 2^n+1\), or
the multiplicative order of 2 modulo this ratio. It follows that when \(x+1\) is coprime to \(2^n+1\), the length of the cycle containing it is equal to 2n, the maximum possible. Hence, there are at least \(\frac{\phi (2^n+1)}{2n}\) cycles of length 2n.
Hauge [5] proved that the length of each cycle is even and divides 2n with an odd quotient. We reformulate this as follows.
Proposition 3
Any \(CCR_n\) cycle has even length that divides 2n but not n.
Proof
From (14) we can see that \(g_{c_n}^{2n}(x) \equiv x \mod 2^n+1\), and since \(2^n \equiv -1 \mod 2^n+1\), also that \(g_{c_n}^{n}(x) \equiv \overline{x} \not \equiv x \mod 2^n+1\) for all \(x \in {\mathbb {Z}}_{2^n}\). If a cycle had length k dividing n, that would contradict the inequality, and if it did not divide 2n then we would reach a contradiction as in the proof of Proposition 1. Consequently, k is even. □
Proposition 4
All \(CCR_n\) cycles are self-dual.
Proof
Consider any \(CCR_n\) cycle and let 2p be its length and x one of its elements. We need to show that it also contains \(\overline{x}\). By Proposition 3, p must divide n with an odd quotient, say \(n=(2a+1)p\) for some positive integer a. Then, \(\overline{x} \equiv g_{c_n}^n(x) \equiv g_{c_n}^{2pa+p}(x) \equiv g_{c_n}^p(x) \mod 2^n+1\), thus \(\overline{x}\) is indeed on the cycle. □
In fact, each cycle has the form \(\{x_1,\ldots ,x_p,\overline{x_1},\ldots ,\overline{x_p}\}\), where 2p is its length. From this, or alternatively by (13), we can also deduce that for any \(x \in {\mathbb {Z}}_{2^n}\),
Let \(\zeta _n^*(k)\) denote the number of \(CCR_n\) cycles of length 2k.
Lemma 2
\(\zeta _n^*(k)=\zeta _n^O(k)\).
Proof
By Proposition 3, 2k must divide 2n but not n. It is not difficult to check that for any integer n, the divisors of 2n that are not divisors of n are of the form \(2^{{\nu _2}(n)+1}d\) where d divides \(n/2^{{\nu _2}(n)}\). Hence, \(\sum _{d \mid n/2^{{\nu _2}(n)} }2^{{\nu _2}(n)+1}d~\zeta _n^*(2^{{\nu _2}(n)}d)=|{\mathbb {Z}}_{2^n}|=2^n\), which is exactly what we had in the proof of Lemma 1 for \(\zeta _n^O(2^{{\nu _2}(n)}d)\) and thus M\(\ddot{\text {o}}\)bius inversion would yield the same expression. □
Golomb [4] states that \(CCR_n\) generates \(Z^*(n)=\frac{1}{2n}\sum _{\text {odd } d \mid n}\phi (d)2^{n/d}\) cycles. An alternative formula for this is (11), since by Lemma 2, \(Z^*(n)=Z^O(n)\).
3.3 The pure and complemented summing registers
Another two well-known examples of mutually complemetary shift registers are the Pure Summing (\(PSR_n\)) and Complemented Summing (\(CSR_n\)) registers of order n. As the name suggests, the function F in (1) for \(PSR_n\) is the sum of its inputs modulo 2. Under the number theoretic viewpoint, the corresponding support is \(\mathcal D_{psr}=\{x \in {\mathbb {Z}}_{2^{n-1}} \ | \ \text {wt}(x) \text { is odd}\}\). Using it in (2) we get the maps
At a first glance, a way to unify their description as we did for \({g_{p_n}}\) and \({g_{c_n}}\) in (9) and (13) is not evident. As a start, we can eliminate the current split (which is according to the parity of the weight) by mapping the elements of \({\mathbb {Z}}_{2^n}\) to the elements of \({\mathbb {Z}}_{2^{n+1}}\) of either odd or even weight. One obvious way of doing this is by mapping elements with the chosen weight parity to themselves, and mapping the rest of the elements to themselves plus \(2^n\). This yields two invertible maps, one per weight parity, namely \(h_n: {\mathbb {Z}}_{2^n} \rightarrow \{x \in {\mathbb {Z}}_{2^{n+1}} \ | \ \text {wt}(x) \text { is even} \}\) and \(h^{\prime }_n: {\mathbb {Z}}_{2^n} \rightarrow \{x \in {\mathbb {Z}}_{2^{n+1}} \ | \ \text {wt}(x) \text { is odd} \}\) given by
$$\begin{aligned} h_n(x)=\left\{ \begin{array}{rl} 2^n+x &{} \text {if } \text {wt}(x) \text { is odd}\\ x &{} \text {if } \text {wt}(x) \text { is even}\\ \end{array} \right. \text { with } h^{-1}_n(x)=\left\{ \begin{array}{rl} x &{} \text {if } x < 2^n\\ x-2^n &{} \text {if } x \ge 2^n\\ \end{array}\right. \end{aligned}$$
(17)
and
$$\begin{aligned} h^{\prime }_n(x)=\left\{ \begin{array}{rl} x &{} \text {if } \text {wt}(x) \text { is odd}\\ 2^n+x &{} \text {if } \text {wt}(x) \text { is even}\\ \end{array}\right. \text { with } h'^{-1}_n(x)=\left\{ \begin{array}{rl} x &{} \text {if } x < 2^n\\ x-2^n &{} \text {if } x \ge 2^n .\\ \end{array} \right. \end{aligned}$$
Note that by construction, for all \(x \in {\mathbb {Z}}_{2^n}\), \(\text {wt}(h_n(x))\) is even and \(\text {wt}(h^{\prime }_n(x))\) odd. The next result establishes a connection between the four basic registers.
Since all equalities can be proven in a similar way, we only provide proof for the first one. In fact, we will show that for any \(x \in {\mathbb {Z}}_{2^n}\),
By (17), for \({g_{p_{n+1}}}(h_n(x))\) we need to consider two cases, namely \(\text {wt}(x)\) even and odd. For \(\text {wt}(x)\) even, \({g_{p_{n+1}}}(h_n(x))={g_{p_{n+1}}}(x)=2x \mod 2^{n+1}=2x\), by (3) and since \(x<2^n\) means there is no modular reduction. Similarly, for \(\text {wt}(x)\) odd, \({g_{p_{n+1}}}(h_n(x))={g_{p_{n+1}}}(2^n+x)=2x+2^{n+1}+1\mod 2^{n+1}=2x+1\).
Next, by (16), we need to consider two cases for \(h_n({g_{psr_n}}(x))\) as well: \(\text {wt}(x)\) even and odd. For \(\text {wt}(x)\) even, \(h_n({g_{psr_n}}(x))=h_n(2x \mod 2^n)\), which by (17) further depends on the parity of \(\text {wt}(2x \mod 2^n)\). This also being even means \(x<2^{n-1}\), and being odd means \(x \ge 2^{n-1}\). In the first case, \(h_n(2x \mod 2^n)=2x \mod 2^n=2x\), since there is no modular reduction. In the second case, \(h_n(2x \mod 2^n)=(2x \mod 2^n) +2^n=2x\), since for the range of x we have \(2x \mod 2^n=2x-2^n\). The case for \(\text {wt}(x)\) odd is almost identical, giving \(h_n({g_{psr_n}}(x))=2x+1\) for both subcases, as required. □
The length of the \(PSR_n\) cycle containing \(x \in {\mathbb {Z}}_{2^n}\) is equal to the period \(p_{{g_{psr_n}}}(x)\), the smallest positive exponent i such that \({g_{psr}}_n^i(x)=x\). By repeated application of Theorem 1 this is equivalent to \(2^ih_n(x) \equiv h_n(x) \mod 2^{n+1}-1\), or
the multiplicative order of 2 modulo this ratio. It follows that when \(h_n(x)\) is coprime to \(2^{n+1}-1\), \(p_{{g_{psr_n}}}(x)=n+1\), the maximum possible. Similarly, the length of the \(CSR_n\) cycle containing x is the smallest positive i such that
the multiplicative order of 2 modulo this ratio, and when \(h^{\prime }_n(x)\) is coprime to \(2^{n+1}-1\), \(p_{{g_{csr_n}}}(x)=n+1\), the maximum possible.
From Theorem 1 and (6), we can deduce that there is a one-to-one correspondence respectively between the \(PSR_n\) and \(CSR_n\) cycles, and the \(PCR_{n+1}\) cycles of even and odd weight. For example, given a \(PSR_n\) cycle \(\{x_1,\ldots ,x_p\}\), then \(\{h_n(x_1),\ldots ,h_n(x_p)\}\) is a \(PCR_{n+1}\) cycle of even weight. In the other direction, given for instance a \(PCR_{n+1}\) cycle \(\{y_1,\ldots ,y_l\}\) of odd weight, then \(\{h'^{-1}_n(y_1),\ldots ,h'^{-1}_n(y_l)\}\) is a \(CSR_n\) cycle.
Let \(\sigma _n(k)\) and \(\sigma _n^*(k)\) respectively denote the number of \(PSR_n\) and \(CSR_n\) cycles of length k. The following corollaries stem from the observation above.
Corollary 4
The length of any \(PSR_n\) and \(CSR_n\) cycle divides \(n+1\).
Corollary 5
\(\sigma _n(k)=\zeta _{n+1}^E(k)\) and \(\sigma ^*_n(k)=\zeta _{n+1}^O(k)\).
Golomb [4] states that \(PSR_n\) generates \(S(n)=Z(n+1)-Z^*(n+1)\) cycles and \(CSR_n\) generates \(S^*(n)=Z^*(n+1)\) cycles, thus \(S(n)+S^*(n)=Z(n+1)\), all being later verified using the D-morphism introduced by Lempel [7]. We have just observed the latter in the discussion above, and can obtain the former two from Lemma 2 and Corollary 5, with (12) being an alternative formula to \(S(n)=\frac{1}{2(n+1)}\sum _{d \mid n+1}\phi (2d)2^{\frac{n+1}{d}}\) given in [11].
4 On the adjacency sets of the pure cycling register
In this section we will show how the new approach can also be used for studying adjacency sets. We do so by revisiting those of \(PCR_n\).
We begin with the fact that by (15), if an edge exists between two \(PCR_n\) cycles, then an edge exists between their complements, with the corresponding adjacency sets containing the complements of each other’s elements.
Next, by (7), edges can only exist between cycles whose weights differ by one. As a consequence, no intracyclic edge exists in \(PCR_n\) [5]. A contradiction with respect to weights asserts that no extracyclic pairs exist either: On one hand, since \(x_2 < 2^{n-1}\), \({g_{c_n}}(x_2)\) being on the same cycle as \(x_1\) implies \(\text {wt}(x_1)=\text {wt}({g_{c_n}}(x_2))=\text {wt}(x_2)+1\). On the other hand, since \(x_1 < 2^{n-1}\), \({g_{c_n}}(x_1)\) being on the same cycle as \(x_2\) implies \(\text {wt}(x_2)=\text {wt}({g_{c_n}}(x_1))=\text {wt}(x_1)+1\).
Regarding intracyclic pairs, 0 and \(2^n-1\), which have period 1, and \(2^{n-1}-1\), for which \({g_{c_n}}(2^{n-1}-1)=2^n-1 \in C_{2^n-1}\), need not be considered. For any \(x \in {\mathbb {Z}}_{2^{n-1}}\setminus \{2^{n-1}-1\}\), (4) can be expressed as
for some i, j such that \(1\le i < p_{{g_{p_n}}}(x_1)\) and \(1\le j < p_{{g_{p_n}}}({g_{c_n}}(x_1))\). In fact, Lemma 3 below asserts that \(1\le i,j \le n-1\).
We note that we must have \(i+j \ne n\), otherwise the LHS of (18) would be congruent to 0, leading to a contradiction as the RHS can never be congruent to 0. Then, the congruence is solvable if and only if \(\text { gcd }(2^{i+j}-1,2^n-1)=2^{\text { gcd }(n,i+j)}-1\) divides \(2^j-1\), which implies \(\text { gcd }(n,i+j)\) divides j.
Lemma 3
In \(PCR_n\), intracyclic pairs label edges between length n cycles only.
Proof
Let \(x_1\) and \(x_2\) be an intracyclic pair in \(PCR_n\), and denote the length of the cycle containing them by \({{p_1}}\), and that of the cycle containing \({g_{c_n}}(x_1)\) and \({g_{c_n}}(x_2)\) by \({{p_2}}\). To prove the lemma it suffices to show \({{p_1}}={{p_2}}=n\).
First, multiplying both sides of (18) by \(2^{p_1}\), using that \(2^{p_1}x_1\equiv x_1 \mod 2^n-1\) and applying (18) on the LHS, and rearranging, we obtain
We must have that each of the summands on the LHS is congruent to a distinct summand on the RHS modulo \(2^n-1\). Such pairwise congruences are equivalent to pairwise congruences in the exponents modulo n. The range of j implies \(j \not \equiv 0 \mod n\), hence the only possibility left is \(p_1 \equiv 0 \mod n\) giving \(p_1=n\) as required.
Next, we multiply both sides of (18) by \(2^{p_2}\). On the LHS we have
where in the second step we used \(2^{p_2}(2x_1+1)\equiv (2x_1+1) \mod 2^n-1\), and in the third we applied (18). Combining this with the RHS and rearranging, we obtain
Working as above, since \(i\not \equiv 0 \mod n\), we are left with \(p_2=n\) as required. □
Magleby [8] and Fredricksen (as acknowledged in [5]) proved in different ways that the adjacency sets in \(PCR_n\) have size at most 2. The number of adjacency sets of this maximal size was determined in [10, 12] and later on in [5], each using a different method. We provide an alternative proof for both results.
Lemma 4
All intracyclic pairs in \(PCR_n\) are disjoint.
Proof
Suppose on the contrary that there exist two non-disjoint intracyclic pairs in \(PCR_n\), say \(x_1\) with \(x_2\) and \(x_1\) with \(x_3\). Apart from the exponent pair (i, j) that connects \(x_1\) and \(x_2\) as above and yields (18), there exists an exponent pair \((i^{\prime },j^{\prime })\), \(1\le i^{\prime },j^{\prime } \le n-1\), connecting \(x_1\) and \(x_3\) and yielding
Considering pairwise congruences as in the proof of Lemma 3, three cases arise:
First, \(i+j+j^{\prime } \equiv i^{\prime }+j^{\prime }+j \mod n\), which implies \(i\equiv i^{\prime } \mod n\). Then, as \(j \not \equiv i+j \mod n\), we are left with \(j\equiv j^{\prime } \mod n\). Given that \(1\le i,j,i^{\prime },j^{\prime } \le n-1\), we must have \(i=i^{\prime }\) and \(j=j^{\prime }\), yielding \(x_2=x_3\) and contradicting that they are distinct.
Second, \(i+j+j^{\prime } \equiv j^{\prime } \mod n\), implying \(i+j \equiv 0 \mod n\), which is impossible as we have seen that \(i+j\ne n\).
Third, \(i+j+j^{\prime } \equiv i+j \mod n\) implies \(j^{\prime } \equiv 0 \mod n\) and contradicts the range of \(j^{\prime }\).
Since all cases lead to a contradiction, our assumption must be false and all intracyclic pairs in \(PCR_n\) must be disjoint. □
Corollary 6
[8] The size of adjacency sets in \(PCR_n\) is at most 2.
Proof
Suppose on the contrary that there exists an adjacency set in \(PCR_n\) containing more than two distinct elements, and consider three of them. Since no extracyclic pairs exist in \(PCR_n\), pairwise these three elements form non-disjoint intracyclic pairs, in contradiction to Lemma 4. □
Corollary 7
[10, 12] In \(PCR_n\), adjacency sets of size 2 label edges between cycles of length n only.
Proof
This is a direct consequence of Lemma 3 and Corollary 6. □
Theorem 2
[10, 12] In \(PCR_n\), the number of adjacency sets of size 2 is
$$\begin{aligned} p(n)=\frac{1}{2} \sum \limits _{\begin{array}{c} d \mid n \\ d \ne n \end{array}} \phi \left( \frac{n}{d} \right) \left( \frac{n}{d}-2 \right) 2^{d-1}. \end{aligned}$$
Proof
Adjacency sets of size 2 in \(PCR_n\) correspond to intracyclic pairs. Therefore, we begin by counting the number of suitable pairs of exponents (i, j) that render (18) solvable. As we have seen, we must have \(i+j\ne n\) and \(\text { gcd }(n,i+j)\) dividing j. Any proper divisor d of n is a possible \(\text { gcd }\), and any integer m such that \(\text { gcd }(n,m)=d\) and \(1\le m \le n-1\) (due to reduction modulo n in the exponents) is a possibility for \(i+j\). There are \(\phi (n/d)\) of them. The possibilities for j are the multiples of d excluding \(i+j\) (since \(i\ne 0\)) such that \(1\le j \le n-1\). There are \(n/d-2\) of them.
Next, for each suitable d, i and j there are \(2^d-1\) possible solutions to (18) given by \(x_1=x_0+ \frac{2^n-1}{2^d-1}k\) for each integer k in the interval \(0 \le k \le 2^d-2\), where
We are only interested in those solutions such that both \(x_1< 2^{n-1}\) and \(x_2={g_{p}}_n^i(x_1)<2^{n-1}\). When \(d=1\), there is a single solution, given by \(x_1 \equiv \sum _{l=1}^{-j(i+j)^{-1}\bmod n}2^{-1-l(i+j)} \mod 2^n-1\). It is in fact straightforward to verify that it satisfies (18). If \(x_1>2^{n-1}\) then \(2^{n-1}\) must appear as one of the summands, and we would have \(-1-l(i+j)\equiv n-1 \mod n\) which is only possible if either 0 or n were in the range of the sum. This however does not happen as \(j(i+j)^{-1}\not \equiv 0 \mod n\). Thus all \(x_1\) are acceptable, and by Remark 1 and the fact that if the congruence is solvable for the pair of exponents (i, j) then it is also solvable for the pair \((n-i,n-j)\), so are all the corresponding \(x_2\).
For \(d>1\), we have \(x_0<\frac{2^n-1}{2^d-1}<2^{n-1}\) due to the modulus, hence \(k=0\) is suitable. Since \(x_0\) is between 0 and the modulus, the maximum suitable value of k is \(k_m\) such that \(k_m\left( \frac{2^n-1}{2^d-1} \right) < 2^{n-1}\) and \((k_m+1)\left( \frac{2^n-1}{2^d-1} \right) > 2^{n-1}\). After simple operations, this becomes \(2^{d-1}-1-\frac{2^{n-1}-2^{d-1}}{2^n-1}\le k_m < 2^{d-1}-\frac{2^{n-1}-2^{d-1}}{2^n-1}\). Since the fraction is less than one, \(k_m=2^{d-1}-1\). Hence, the suitable solutions are for \(0\le k \le 2^{d-1}-1\), which means that only \(2^{d-1}\) out of the \(2^d-1\) possible solutions are suitable. With the same arguments as for the case \(d=1\), \(x_2={g_{p_n}^i}(x_0)\) corresponding to \(k=0\) is also suitable. The suitability of those corresponding to the remaining values of k is established by noticing that \({g_{p_n}^i}(\frac{2^n-1}{2^d-1})=2^i\frac{2^n-1}{2^d-1}=(2^n-1)\frac{2^i-1}{2^d-1}+\frac{2^n-1}{2^d-1} \equiv \frac{2^n-1}{2^d-1} \mod 2^n-1\), where in the third step we used the fact that d divides i (as it divides j) and thus \(2^d-1\) divides \(2^i-1\).
Finally, putting everything together gives us the number of suitable solutions to (18). The required number of distinct intracyclic pairs is half this number as by Remark 1 we would be otherwise counting each pair twice. □
5 Conclusions
We have presented an alternative view on binary feedback shift registers where we convert binary sequences to integers and use number theory to treat the related problems. We have tried to illustrate the approach by some examples on basic shift registers, and it seemed to be useful in determining cycle lengths and describing conditions for adjacency sets of size 2 in the pure cycling register via simple congruences. It also led to uncovering a previously unknown connection between the pure cycling register and the cyclotomic classes defined in [1].
One of the differences with the traditional approach is that shift registers are now represented by two equations that depend on the support of their feedback function and the input. What facilitated the detailed study of the four basic examples presented here was our ability to obtain unified descriptions for them as a single equation irrespective of the input. This was made possible by the trivial support of two of them, and the simple support of the other two that lead to the discovery of an isomorphism between their description and that of the first two.
Determining more supports of feedback functions that can lead to unified descriptions, and more generally finding out whether this viewpoint will prove to be a useful tool in studying other shift registers or not is a natural direction for future work, as is generalising it to non-binary alphabets.
Acknowledgements
The author would like to thank Prof. Tor Helleseth for valuable discussions and encouragement. He would also like to express his appreciation towards the reviewers and the associate editor for comments that helped improve the manuscript.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
