The Adjacency Graphs of Some Feedback Shift Registers
Ming Li, Yupeng Jiang, Dongdai Lin · 2015
The adjacency graphs of feedback shift registers (FSRs) with characteristic function of the form g = (x0+x1)∗f are considered in this paper. Some properties about these FSRs are given. It is proved that these FSRs contains only prime cycles and these cycles can be divided into two sets such that each set contains no adjacent cycles. When f is a linear function, more properties about these FSRs are derived. It is shown that, when f is a linear function and contains an odd number of terms, the adjacency graph of FSR((x0 + x1) ∗ f) can be determined directly from the adjacency graph of FSR(f). As an application of these results, we determine the adjacency graphs of FSR((1 + x)p(x)) and FSR((1 + x)p(x)), where p(x) is a primitive polynomial, and construct a large class of de Bruijn sequences from them.