The Adjacency Graphs of FSRs With Affine Characteristic Functions.

We study the adjacency graphs of feedback shift registers (FSRs) with affine characteristic functions. We first show that, similar to the linear case, the output sequences of FSRs with affine characteristic functions also have the direct sum decompositions. The only difference from the linear case is that one component of the decomposition is a family of affine sequences, rather than linear sequences. Then, based on this fact, we give a relationship between the adjacency graphs of FSRs with affine characteristic functions and the generalized adjacency graphs of FSRs whose characteristic functions correspond to the components of the decomposition. This relationship establishes the algebraic structure of adjacency graphs and greatly simplifies the calculation of them. At last, we especially study the adjacency graph of the FSR whose characteristic function is $q_{k}(x)+1$ where $q_{k}(x)$ is the linear function corresponding to the polynomial $(1+x)^{k}$. We prove that for any two cycles of this FSR, the number of conjugate pairs shared by them is no more than 4 if $k$ is a power of 2, and no more than 2 if $k$ is not a power of 2. [ABSTRACT FROM AUTHOR]