# On Stability of Multi-Valued Nonlinear Feedback Shift Registers

Authors: Haiyan Wang; Qiuzhen Lin; Jianyong Chen; Jianqiang Li; Jianghua Zhong; Dongdai Lin; Jia Wang; Lijia Ma
Journal: Complexity
 (2019)

---

## Abstract

Nonlinear feedback shift registers (NFSRs) are the main building blocks in many convolutional decoders, and a stable NFSR can limit decoding error propagation. Due to lack of efficient algebraic tools, the stability of multi-valued NFSRs has been much less studied. This paper studies the stability of multi-valued NFSRs using a logic network approach. A multi-valued NFSR can be viewed as a logic network. Based on its logic network representation, some sufficient and necessary conditions are provided for globally (locally) stable multi-valued NFSRs, explicit forms are given for the set of basins, and the algorithm for obtaining the set of basins is provided as well. Finally, a new method is presented for constructing stablen+1-stage NFSRs from stable n-stage NFSRs by the properties of D-morphism.


---

## Body

## 1. Introduction

Nonlinear feedback shift registers (NFSRs) are the main building blocks in many convolutional decoders. However, in the process of decoding, a decoding error tends to induce indefinitely long decoding errors. A stable NFSR is an alternative to limit this error propagation. Some studies have focused on the stability of NFSRs. In 1964, Massey and Liu [1] proposed that using a stable nonlinear feedback shift register (NFSR) as the main building block in a convolutional decoder is able to limit such an error propagation. In their NFSR-based decoder, the feedback function represents a decoding algorithm. They gave an example to highlight the application of the NFSR-based decoder. Mowle [2] proved that the number of n-stage globally stable NFSRs is 22n-n-1 and also showed that all these NFSRs are binomially distributed. In [3, 4], the author gave the enumeration and classification of stable FSRs and an algorithm to generate all of them. A direct algorithm for the synthesis of stable NFSRs was proposed [5]. It is notable to point out that only binary NFSRs were concerned in the above work. In addition, Lempel [6] gave some results on k-stable NFSRs. Since then, the stability of NFSRs has not been further studied due to lack of efficient mathematical tools, although numerous other efforts have been made on NFSRs over the past decades.In [7–9], the authors studied the stability for binary NFSRs by viewing them as Boolean networks. A Boolean network is a finite state automaton evolving through Boolean functions. It was firstly introduced by Kauffman in 1969 to model a genetic network whose variables take only two possible values, “on" and “off" (or equivalently, 1 and 0, resp.) [10]. Over the last decades, Boolean networks have attracted much attention in many communities, such as biology [11–13], physics [14–16], system sciences [17–21], and control theory [22, 23]. In the community of system sciences, Cheng and his collaborators [24] developed an algebraic framework for Boolean networks using a semitensor product approach. In the algebraic framework, a Boolean network can be equivalently converted into a conventional discrete-time linear system. A logic network is a generalization of a Boolean network. The variables of a logical network usually take multiple values. If they take only two values, say 0 and 1, then the logical network is reduced to a Boolean network. The studies of multi-valued logical networks can refer to, for instance, [25–27].Multi-valued NFSRs have been investigated in several studies. For example, some construction methods were given for de Bruijn sequences generated from multi-valued NFSRs [28–30]. A necessary and sufficient condition was given for the nonsingularity of multi-valued NFSRs [31]. Recently, the multi-valued NFSRs were studied in [32–34]. Some necessary and sufficient conditions were given for the stability of multi-valued NFSRs in [35].In this paper, we study the stability of multi-valued NFSRs using a logic network approach. A multi-valued NFSR can be viewed as a logic network. Based on its logic network representation, we give the state transition matrix [34], which shows the simple relation with the truth table of the feedback function of the NFSR. From this viewpoint, it is more explicit than the state transition matrix introduced in [31], where the state transition matrices are expressed as the products of some structure matrices of the components of the vectorial function. In fact, from the cryptography perspective, it is very important and useful to show the explicit relation between the truth table of the feedback function and the state transition matrix in order to analyze and design an NFSR. This paper is an extension of our previous work [35], which is more complete and more substantial due to the following contributions:(1)
Because the stability of an NFSR completely depends on the basin of the NFSR, we give the explicit forms for the set of basins, and the algorithm for obtaining the set of basins is provided as well.(2)
A stable NFSR is an alternative to limit error propagation in the process of decoding; therefore we give a new method for constructing stablen+1-stage NFSRs from stable n-stage NFSRs over the binary field.The remainder of this paper is organized as follows. Section2 briefly reviews some related works on logic networks. Sections 3 and 4 are our main results. Some sufficient and necessary conditions are given for globally (locally) stable NFSRs in Section 3. In Section 4, we present the method to construct stable NFSRs, and examples are presented to show the effectiveness of the proposed method. The paper is concluded in Section 5.


## 2. Logic Network Representation of NFSR

In this section, we first briefly review the semitensor product of matrices and recall the multi-linear form of nonlinear logic function that is obtained by the semi-tensor product. Finally, we revisit the logic network representation of a multi-valued NFSR, which is very useful to investigate the stability of NFSRs.For the statement ease, we first give some notations:(i)
Dk={0,1,2,…,k-1}; when k=2, we denote F2, that is, binary field.(ii)
Dkn: n-dimensional vectors over Dk; when k=2, we denote F2n, that is, n-dimensional vector space over F2.(iii)
In: the identity matrix of dimension n.(iv)
δni: the i-th column of the identity matrix In.(v)
Δn={δni|i=1,2,…,n}.(vi)
Δnm: the set of all m-dimensional vectors over Δn.(vii)
Cj(A): the j-th column of a matrix A.(viii)
ord(B): the order of a square matrix B of dimension n, that is, the least power p satisfying Bp=In.(ix)
Ln×m: the set of n×m matrices, whose columns belong to Δn. If L∈Ln×m, then it can be expressed as L=δni1δni2⋯δnin. For the sake of compactness, it is briefly denoted by L=δni1i2⋯in.


### 2.1. Semi-Tensor Product and Multilinear Form of Logic Network

Semi-tensor product of matrices was introduced by Cheng [24]. It is a generalization of the conventional matrix product and works for any two matrices regardless of their sizes, while it retains all major properties of the conventional matrix product. Before reviewing the semitensor product, we first recall what the Kronecker product is.Definition 1 (see [36]).
LetA=(aij) and B be matrices of dimensions n×m and p×q, respectively. The Kronecker product of A and B is defined as an np×mq matrix, given by(1)A⊗B=a11Ba12B⋯a1mBa21Ba22B⋯a2mB⋮⋮⋮⋮an1Ban2B⋯anmB.Definition 2 (see [24]).
LetA and B be matrices of dimensions n×m and p×q, respectively, and let α be the least common multiple of m and p. The (left) semitensor product of A and B is defined as an nα/m×qα/p matrix, given by(2)A⋉B=A⊗Iα/mB⊗Iα/p.Clearly, ifm=p, the semi-tensor product A⋉B is reduced to their conventional matrix product AB.A logical functionf with n variables is a mapping from Dkn to Dk. Let i be the decimal number corresponding to the tuple (i1,i2,…,in)∈Dkn via the mapping i=i1kn-1+i2kn-2+⋯+in. Then i ranges from 0 to kn-1. For the sake of simplicity, we denote f(i)=f(i1,i2,…,in). Then [f(0),f(1),…,f(kn-1)] is the truth table of f, arranged in the alphabet order, while [f(kn-1),f(kn-2),…,f(0)] is truth table of f, arranged in the reverse alphabet order.Identify a variablex∈Dk as a vector X=δkk-x∈Δk. Then a logic function f with n variable from Dkn to Dk is changed to a function from Δkn to Δk.Lemma 3 (see [24]).
For any logical functionf(X1,X2,…,Xn) with Xi∈Δk,i=1,2,…,n, let [s1,s2,…,skn] be the truth table of f, arranged in the reverse alphabet order. Then f can be expressed as a multilinear form:(3)fX1,X2,…,Xn=M⋉X1⋉X2⋉⋯⋉Xn,where M=δk[k-s1k-s2⋯k-skn] is called the structure matrix of f.Lemma 4 (see [24]).
Suppose(4)x=X1⋉X2⋉⋯⋉Xnwith Xi∈Δk, i=1,2,…,n. Then x∈Δkn. Moreover, For any j∈{1,2,…,kn}, the state x=δknj∈Δkn and the state (x1,x2,…,xn)T∈Dkn, which satisfy kn-1x1+kn-2x2+⋯+xn=kn-j, are one-to-one correspondent.Definition 5 (see [37]).
LetA=A1A2⋯An and B=B1B2⋯Bn be matrices of dimensions m×n and p×n, respectively, where Ai and Bi, i=1,2,…,n, are the i-th column of matrices A and B, respectively. The Khatri-Rao product of A and B is defined as an mp×n matrix, given by(5)A∗B=A1⊗B1A2⊗B2⋯An⊗Bn,and a logical network withn-nodes can be described as the following system:(6)Xt+1=gXt,where X=(x1,x2,…,xn)T∈Dkn, and g=(g1,g2,…,gn)T, with gi:Dkn→Dk for all i=1,2,…,n. Let Gi be the structure matrix of the function gi for any i∈{1,2,…,n}. System (6) can be equivalently described as a linear system [21]:(7)xt+1=Lxt,where x=X1⋉X2⋉⋯⋉Xn∈Δkn is the state and L=G1∗G2∗⋯∗Gn∈Lkn×kn is the state transition matrix.


### 2.2. Logic Network Representation of Multi-Valued NFSR

Ann-stage multi-valued Fibonacci NFSR can be described as Figure 1. It is a collection of n storage devices, whose contents are denoted by the variables x1,x2,…,xn, taking values from the set Dk={0,1,…,k-1}. Here the logical function f(x1,x2,…,xn) is called the feedback function of the NFSR. For any i∈{1,2,…,n-1}, the content xi+1 is shifted to xi at each periodic interval determined by a master clock. However, to obtain a new value for the variable xn, we compute the function f(x1,x2,…,xn) of all the present contents in the shift register.Figure 1
Ann-stage nonlinear feedback shift register.The state diagram of ann-stage k-valued NFSR is a directed graph consisting of kn nodes and kn directed edges. Each node represents a state of the NFSR, and an edge from state X to state Y means that X is shifted to the state Y. X is called a predecessor of Y, and Y is called the successor of X. Every state of an NFSR has a unique successor but may have no predecessor or a single predecessor or m predecessors with a positive integer m satisfying 1≤m≤k. The state with more than one predecessor is called a branch state, while the state without predecessors is called a starting state. A sequence of p distinct states, X1,X2,…,Xp, is called a cycle of length p if X1 is the successor of Xp, and Xi+1 is a successor of Xi for any i∈{1,2,…,p-1}. Similarly, a sequence of p distinct states, X1,X2,…,Xp, is called a transient of length p, if the following conditions are satisfied: (1) none of them lies on a cycle; (2)X1 is a starting state; (3)Xi+1 is a successor of Xi for any i∈{1,2,…,p-1}; (4) the successor of Xp lies on a cycle.For the sake of statement simplicity, in the sequel ann-stage NFSR means an n-stage multi-valued Fibonacci NFSR over Dk.View then-stage NSFR in Figure 1 as a logic network. Then it can be expressed as(8)Xt+1=gXt,where X=(x1,x2,…,xn)T∈Dkn is the state and g=(g1,g2,…,gn)T is the state transition function, satisfying(9)g1Xt=x2t,⋮gn-1Xt=xnt,gnXt=fx1t,x2t,…,xnt.For any positive integer N, let gN+1(X(t))=g(gN(X(t))), which indicates that the state g(X(t)) is shifted N times from X(t).Lemma 6 (see [34]).
For ann-stage NFSR with a feedback function f, assume the truth table of f to be [s1,s2,…,skn], arranged in the reverse alphabet order. Then the NFSR can be equivalently expressed as a linear system(10)xt+1=Lxt,where x∈Δkn is the state and L∈Lkn×kn is the state transition matrix, expressed as(11)L=δknη1η2⋯ηkn,where(12)ηm=m-1modkn-1+1k-sm,m=1,2,…,kn.


## 2.1. Semi-Tensor Product and Multilinear Form of Logic Network

Semi-tensor product of matrices was introduced by Cheng [24]. It is a generalization of the conventional matrix product and works for any two matrices regardless of their sizes, while it retains all major properties of the conventional matrix product. Before reviewing the semitensor product, we first recall what the Kronecker product is.Definition 1 (see [36]).
LetA=(aij) and B be matrices of dimensions n×m and p×q, respectively. The Kronecker product of A and B is defined as an np×mq matrix, given by(1)A⊗B=a11Ba12B⋯a1mBa21Ba22B⋯a2mB⋮⋮⋮⋮an1Ban2B⋯anmB.Definition 2 (see [24]).
LetA and B be matrices of dimensions n×m and p×q, respectively, and let α be the least common multiple of m and p. The (left) semitensor product of A and B is defined as an nα/m×qα/p matrix, given by(2)A⋉B=A⊗Iα/mB⊗Iα/p.Clearly, ifm=p, the semi-tensor product A⋉B is reduced to their conventional matrix product AB.A logical functionf with n variables is a mapping from Dkn to Dk. Let i be the decimal number corresponding to the tuple (i1,i2,…,in)∈Dkn via the mapping i=i1kn-1+i2kn-2+⋯+in. Then i ranges from 0 to kn-1. For the sake of simplicity, we denote f(i)=f(i1,i2,…,in). Then [f(0),f(1),…,f(kn-1)] is the truth table of f, arranged in the alphabet order, while [f(kn-1),f(kn-2),…,f(0)] is truth table of f, arranged in the reverse alphabet order.Identify a variablex∈Dk as a vector X=δkk-x∈Δk. Then a logic function f with n variable from Dkn to Dk is changed to a function from Δkn to Δk.Lemma 3 (see [24]).
For any logical functionf(X1,X2,…,Xn) with Xi∈Δk,i=1,2,…,n, let [s1,s2,…,skn] be the truth table of f, arranged in the reverse alphabet order. Then f can be expressed as a multilinear form:(3)fX1,X2,…,Xn=M⋉X1⋉X2⋉⋯⋉Xn,where M=δk[k-s1k-s2⋯k-skn] is called the structure matrix of f.Lemma 4 (see [24]).
Suppose(4)x=X1⋉X2⋉⋯⋉Xnwith Xi∈Δk, i=1,2,…,n. Then x∈Δkn. Moreover, For any j∈{1,2,…,kn}, the state x=δknj∈Δkn and the state (x1,x2,…,xn)T∈Dkn, which satisfy kn-1x1+kn-2x2+⋯+xn=kn-j, are one-to-one correspondent.Definition 5 (see [37]).
LetA=A1A2⋯An and B=B1B2⋯Bn be matrices of dimensions m×n and p×n, respectively, where Ai and Bi, i=1,2,…,n, are the i-th column of matrices A and B, respectively. The Khatri-Rao product of A and B is defined as an mp×n matrix, given by(5)A∗B=A1⊗B1A2⊗B2⋯An⊗Bn,and a logical network withn-nodes can be described as the following system:(6)Xt+1=gXt,where X=(x1,x2,…,xn)T∈Dkn, and g=(g1,g2,…,gn)T, with gi:Dkn→Dk for all i=1,2,…,n. Let Gi be the structure matrix of the function gi for any i∈{1,2,…,n}. System (6) can be equivalently described as a linear system [21]:(7)xt+1=Lxt,where x=X1⋉X2⋉⋯⋉Xn∈Δkn is the state and L=G1∗G2∗⋯∗Gn∈Lkn×kn is the state transition matrix.


## 2.2. Logic Network Representation of Multi-Valued NFSR

Ann-stage multi-valued Fibonacci NFSR can be described as Figure 1. It is a collection of n storage devices, whose contents are denoted by the variables x1,x2,…,xn, taking values from the set Dk={0,1,…,k-1}. Here the logical function f(x1,x2,…,xn) is called the feedback function of the NFSR. For any i∈{1,2,…,n-1}, the content xi+1 is shifted to xi at each periodic interval determined by a master clock. However, to obtain a new value for the variable xn, we compute the function f(x1,x2,…,xn) of all the present contents in the shift register.Figure 1
Ann-stage nonlinear feedback shift register.The state diagram of ann-stage k-valued NFSR is a directed graph consisting of kn nodes and kn directed edges. Each node represents a state of the NFSR, and an edge from state X to state Y means that X is shifted to the state Y. X is called a predecessor of Y, and Y is called the successor of X. Every state of an NFSR has a unique successor but may have no predecessor or a single predecessor or m predecessors with a positive integer m satisfying 1≤m≤k. The state with more than one predecessor is called a branch state, while the state without predecessors is called a starting state. A sequence of p distinct states, X1,X2,…,Xp, is called a cycle of length p if X1 is the successor of Xp, and Xi+1 is a successor of Xi for any i∈{1,2,…,p-1}. Similarly, a sequence of p distinct states, X1,X2,…,Xp, is called a transient of length p, if the following conditions are satisfied: (1) none of them lies on a cycle; (2)X1 is a starting state; (3)Xi+1 is a successor of Xi for any i∈{1,2,…,p-1}; (4) the successor of Xp lies on a cycle.For the sake of statement simplicity, in the sequel ann-stage NFSR means an n-stage multi-valued Fibonacci NFSR over Dk.View then-stage NSFR in Figure 1 as a logic network. Then it can be expressed as(8)Xt+1=gXt,where X=(x1,x2,…,xn)T∈Dkn is the state and g=(g1,g2,…,gn)T is the state transition function, satisfying(9)g1Xt=x2t,⋮gn-1Xt=xnt,gnXt=fx1t,x2t,…,xnt.For any positive integer N, let gN+1(X(t))=g(gN(X(t))), which indicates that the state g(X(t)) is shifted N times from X(t).Lemma 6 (see [34]).
For ann-stage NFSR with a feedback function f, assume the truth table of f to be [s1,s2,…,skn], arranged in the reverse alphabet order. Then the NFSR can be equivalently expressed as a linear system(10)xt+1=Lxt,where x∈Δkn is the state and L∈Lkn×kn is the state transition matrix, expressed as(11)L=δknη1η2⋯ηkn,where(12)ηm=m-1modkn-1+1k-sm,m=1,2,…,kn.


## 3. The Properties of Stable Multi-Valued NFSR

In this section, we first briefly review some existing basic concepts of the stability of NFSRs. Then we show that the error-propagation effect is closely related to the stability of an NFSR. Finally, we give some sufficient and necessary conditions for their stability.


### 3.1. Basic Concepts

Definition 7 (see [2]).
A stateX(t) is called an equilibrium state of the logic network (6), if g(X(t))=X(t). For a k-valued NFSR, the equilibrium state of its logic network representation (8) is also called an equilibrium state of the NFSR.Note that an equilibrium state of an NFSR forms a cycle of length1, that is, unit cycle, in the state diagram of the NFSR.Definition 8.
The setE is called the basin of an equilibrium state X of an NFSR, if E is a set of states eventually reaching the equilibrium state X.Definition 9 (see [1]).
Ann-stage NFSR is globally stable to the equilibrium state 0, if, for any state X(t), there exists a positive integer N such that the state transition function of its logic network representation (8) satisfies gN(X(t))=0; that is, 0 is the unique equilibrium state and there are no other cycles in the state diagram of the NFSR.Definition 10 (see [1]).
Ann-stage NFSR is locally stable to the equilibrium state 0, if there exists some state X(t)≠0 such that for some positive integer N the state transition function of its logic network representation (8) satisfies gN(X(t))=0.Since ann-stage multi-valued NFSR has an equivalent logic network representation in a linear system (10), accordingly, we give an equivalent definition of globally (locally) stable multi-valued NFSR as follows.Definition 11.
Ann-stage NFSR is globally stable to the equilibrium state 0, if, for any state x(t), there exists a positive integer N such that the state transition matrix L of its logic network representation (8) satisfies LNx(t)=δknkn.Definition 12.
Ann-stage NFSR is locally stable to the equilibrium state 0, if there exists some state x(t)≠δknkn such that for some positive integer N the state transition matrix L of its logic network representation (8) satisfies LNx(t)=δknkn.In the sequel, an NFSR is globally (resp., locally) stable meaning that an NFSR is globally (resp., locally) stable to the equilibrium state0. From their definitions, it is easy to see that a globally stable NFSR must be locally stable but not the vice versa.Definition 13 (see [2]).
An NFSR is called a globally stable maximum transient NFSR if it is globally stable and has a single starting state.


### 3.2. Decoder NFSR

We show below that the error-propagation effect is closely related to the stability of an NFSR. The relevant portion of a decoder is shown in Figure2 and is seen to constitute an NFSR. The first m terms of the syndrome sequence are stored in the shift register, and the current input is sm+1, at the time when the decoder forms e0iΔ. Let the vector s=(s1,s2,…,sm) represent the shift register contents and let 0 denote the all-zero vector. s will be referred to as the state of the NFSR. The decoding algorithm is represented by the function F(sm+1,s); that is, F(sm+1,s)=e0iΔ. For any reasonable decoding algorithm, F(0,0)=0, since this is the case where all parity checks are satisfied. From Figure 2, it should be clear that m consecutive correct decoding decisions will clear the decoder of any spurious symbols introduced by a decoding error and hence will terminate the error propagation. The ability of the decoder to affect such a “reconvergence” is conveniently studied by considering the shift register to be loaded with some initial states s and the syndrome input sequence to be all zeros; that is, all succeeding parity checks are satisfied. Finally, the shift register will enter state 0 when reconvergence has been achieved. Thus the problem of studying error propagation will be reduced to the stability analysis of an NFSR in Figure 1.Figure 2
Decoder NFSR.


### 3.3. Necessary and Sufficient Conditions for Stability

Theorem 14.
An NFSR is locally stable if and only if the feedback function satisfiesf(0,…,0)=0, and there is at least one i∈{1,2,…,k-1} such that f(i,0,…,0)=0.Proof.
Necessity: Clearly, according to Definition9, f(0,…,0)=0 is a necessary condition for a locally stable NFSR. For any NFSR, the state 0 has the possible predecessors: itself and (i,0,…,0)T with i∈{1,2,…,k-1}. If the NFSR is locally stable, then there exist some states X(t)≠0 such that, for some integers N, gN(X(t))=0. Thus, 0 has a predecessor different to itself. Hence, there is at least one i∈{1,2,…,k-1} such that f(i,0,…,0)=0.
Sufficiency:f(0,…,0)=0 implies that 0 is an equilibrium state of the NFSR. If there is at least an i∈{1,2,…,k-1} such that f(i,0,…,0)=0, and then (i,0,…,0)T is a predecessor of 0. In other words, there exists a state X(t)=(i,0,…,0)T≠0 such that g(X(t))=0, which implies that the NFSR is locally stable.Corollary 15.
LetL=δknη1η2…ηkn be the state transition matrix of the logic network representation (10) in a linear system of an n-stage NFSR. Then the NFSR is locally stable if and only if there exists at least one i∈{1,2,…,k-1} such that ηkn=η(k-i)kn-1=kn.Proof.
Let the truth table of the feedback functionf of the NFSR be s1s2⋯skn, arranged in the reverse alphabet order. According to Theorem 14, the NFSR is locally stable if and only if the feedback function satisfies f(0,…,0)=0, and there is at least one i∈{1,2,…,k-1} such that f(i,0,…,0)=0, that is, skn=s(k-i)kn-1=0. Then the result follows from (12).Proposition 16.
LetL be the state transition matrix of the logic network representation (10) in a linear system of an n-stage NFSR. If Ckn(L)=δknkn, there exists an integer l such that Cr(Ll)=δknkn with some r≠kn. Then the NFSR is locally stable to δknkn.Proof.
LetL=δknη1η2…ηkn, and let the truth table of the feedback function f of the NFSR be s1s2⋯skn, arranged in the reverse alphabet order. Since Ckn(L)=δknkn, we have ηkn=kn. According to (12), we have skn={[(kn-1)modkn-1]+1}k-ηkn=0, that is, f(0,…,0)=0. Since there exists an integer l, such that Cr(Ll)=δknkn, we have Llδknr=δknkn. According to Definition 10, the NFSR is locally stable to δknkn.Theorem 17.
If the NFSR is globally stable maximum transient, then there exists a uniquei∈{1,2,…,k-1} such that f(0,0,…,0)=f(i,0,…,0)=0.Proof.
If the NFSR is globally stable maximum transient, then except the starting state and the state0, the other states have their own unique predecessor and unique successor. The state 0 has the possible predecessors: itself and (i,0,…,0)T with i∈{1,2,…,k-1}. Since the NFSR is globally stable maximum transient, 0 has a unique predecessor different to itself. Then the result follows.Remark 18.
Theorem14 shows that there is at least one i∈{1,2,…,k-1} such that f(0,0,…,0)=f(i,0,…,0)=0 is sufficient and necessary condition for a locally stable NFSR. However, Theorem 17 shows that there exists a unique i∈{1,2,…,k-1} such that f(0,0,…,0)=f(i,0,…,0)=0 for globally stable maximum transient NFSR, which is nothing but necessary condition.Theorem 19.
LetL be the state transition matrix of the logic network representation (10) in a linear system of an n-stage NFSR. The NFSR is globally stable, if and only if there exists an integer N≤kn-1 such that each column of LN is equal to δknkn. Moreover, the NFSR is globally stable maximum transient, if and only if each column of Lkn-1 is equal to δknkn.Proof.
Necessity: As the equilibrium state0∈Dkn is uniquely corresponding to the state δknkn∈Δkn, that an n-stage NFSR is globally stale to the equilibrium state 0 is equivalent to that the n-stage NFSR is globally stable to the state δknkn. Clearly, any state of an n-stage globally stable NFSR with one more starting state must be shifted fewer times to reach the equilibrium state 0 than the n-stage globally stable maximum transient NFSR. For an n-stage globally stable maximum transient NFSR, the starting state x0=δkni must shift kn-1 times to go through all other states and finally reaches the state δknkn (or, equivalently, the state 0) and keeps staying at this state. Therefore, N=kn-1 is the largest power such that each column of LN is equal to δknkn.
Sufficiency: There exists an integerN≤kn-1 such that each column of LN is equal to δknkn. Therefore, for the state δkni with any i∈{1,2,…,kn}, we have LNδkni=δknkn. According to Definition 9, the NFSR is globally stable. In particular, N=kn-1 means that the starting state δkni for any i∈{1,2,…,kn} eventually reaches the equilibrium state δknkn and keeps staying at this state. Thus, the result follows.Theorem 20.
Given a globally stable maximum transientk-valued n-stage NFSR, its starting state is (0,0,…,0,i)T with some i∈{1,2,…,k-1}.Proof.
For a given globally stable maximum transientk-valued n-stage NFSR, the state 00⋯0T has only two predecessors, itself and (a,0,…,0)T with some a∈{1,2,…,k-1}. Assume that all k-1 states (0,0,…,0,i)T, for any i∈{1,2,…,k-1}, are not the starting state of the NFSR. Let the predecessor of any given state (0,0,…,0,i)T be (bi,0,…,0)T, with some bi∈{1,2,…,k-1}. Then there exists bi0 with some i0∈{1,2,…,k-1} such that (bi0,0,…,0)T=(a,0,…,0)T, which implies that bi0=a. Note that the successor of (bi0,0,…,0)T is (0,0,…,i0)T with i0∈{1,2,…,k-1}, and the successor of (a,0,…,0)T is 00⋯0T. Then (a,0,…,0)T has two different successors, (0,0,…,0)T and (0,0,…,0,i0)T with some i0∈{1,2,…,k-1}, which is a contradiction that any state has a unique successor. Hence, for any given globally stable maximum transient k-valued n-stage NFSR, there exists some i∈{1,2,…,k-1} such that (0,0,…,0,i)T is the starting state of the NFSR.Example 21.
Whenk=3 and n=2, we consider two nonlinear feedback shift registers, NFSR1 and NFSR2. Their feedback functions are, respectively, as follows:(13)f1x1,x2=x2+x1x22+1and(14)f2x1,x2=2x1+x2+x12+x1x22+x12x22.Computations show that the state transition matrices of the logic network representations of both NFSRs, respectively, are(15)L1=δ9347268159and(16)L2=δ9267269159.We use the same notations in previous sections. For the state transition matrix L1, η3≠9,η6≠9. According to Corollary 15, we get that NFSR1 is not locally stable. Meanwhile, for the state transition matrix L2, η6=9, and L25=δ9999999999. From Theorem 17 and Theorem 19, we obtain that NFSR2 is globally stable. Moreover η1=η4=2,η2=η5=6, and according to Proposition13 in [34], the NFSR2 has two branch states: δ92 and δ96. Actually, the NFSR2 has three starting states. All those features are consistent with their state diagrams, which are shown in Figures 3 and 4.Figure 3
State diagram of NFSR1 in Example21.Figure 4
State diagram of NFSR2 in Example21.Example 22.
Whenk=3,n=2, we consider two nonlinear feedback shift registers, NFSR3 and NFSR4. Their feedback functions are, respectively, as follows:(17)f3x1,x2=2x1+x2+2x1x2+x1x22+x12+x12x2and(18)f4x1,x2=2x1+x2+x1x2+2x12+2x12x2.Computations show that the state transition matrices of the logic network representations of both NFSRs, respectively, are(19)L3=δ9267349159and(20)L4=δ9269348159.We use the same notations in previous sections. For the state transition matrix L3 and L4, we obtain L38=L48=δ9999999999. According to Theorem 19, both NFSR3 and NFSR4 are globally stable maximum transient. Their state diagrams are shown in Figure 5.Figure 5
State diagram of NFSR1 in Example22.Clearly,(0,1)T (resp., (0,2)T) is the starting state of NFSR3 (resp., NFSR4), which is consistent with the result in Theorem 20. It also shows that different globally stable maximum transient k-valued NFSRs with k>2 may have different starting states, which is unlike the globally stable maximum transient binary NFSRs whose starting states are the same, that is, (0,0,…,0,1)T.


### 3.4. Basin of the Equilibrium State of NFSRs

Definition 23.
The setE is called the basin of an equilibrium state X of an NFSR, if E is a set of states eventually reaching the equilibrium state X.We letE(δknkn) be the basin of the equilibrium state δknkn. The stability of an NFSR in Figure 1 completely depends on the basin E(δknkn). In the following, we will focus on how to get the basin of the equilibrium state. Reference [34] gives a way to find all starting states of an NFSR, shown in the following lemma.Lemma 24 (see [34]).
LetL be a state transition matrix of an n-stage NFSR. δkni is a starting state if and only if δkni is not a column of the state transition matrix L, where i∈{1,2,…,kn}.Theorem 25.
LetL be a state transition matrix of an n-stage NFSR. Then the basin of the equilibrium state δknkn is E(knkn)={Lkδkni|1≤k≤Ki, Ki is the smallest ki satisfying Lkδkni=δknkn, and δkni∈C(L) with some positive integer i≤kn}.Proof.
The result follows from Lemmas6 and 24.
In fact, it is easy to get the whole state transition graph of an NFSR when its state transition matrixL is known. For any L∈Lkn×kn,Ci(L)=δknj, we have that δkni is the predecessor state of δknj and δknj is the successor state of δkni; that is, Lδkni=Ci(L). For example, we consider the NFSR2 in Example 21. Its state transition matrix L=δ9267269159. Obviously, only δ93,δ94,δ98∈C(L), and according to Lemma 24, they are all starting states of NFSR2. For the state δ94, it is easy to see that Lδ94=C4(L)=δ92, and L2δ94=Lδ92=C2(L)=δ96 and L3δ94=L2δ92=Lδ96=C6(L)=δ99. Thus, according to Theorem 25, we have δ94,δ92,δ96,δ99∈E(knkn). Similarly, for the state δ93,δ98, we can also use the same method. Finally, we have E(knkn)={δ91,δ92,δ93,δ94,δ95,δ96,δ97,δ98,δ99}. All those features are consistent with the logic network expression of its state diagrams, which are shown in Figure 6. In the following, we strive to give an algorithm to obtain the basin E(knkn). We define E(kn) to be the set of elements that represent the positions of the entry 1s of all elements in E(knkn). Precisely speaking, if E(knkn)={δkni1,δkni2,…,δknim}, then E(kn)={i1,i2,…,im}. For the sake of convenience, we also called E(kn) the basin. For an n-stage NFSR, we first find its starting states according to Lemma 24. Let U be a set of starting states, and denote its cardinality as |U|. Suppose that the starting state set U has been obtained in terms of Lemma 24, and its elements are denoted by δknjl,l=1,2,…,|U|. Let M={j1,j2,…,j|U|}, which is a set of the positions of the entry 1s of all the elements in the starting states U. Second, we assume that the state transition matrix of the NFSR L=δknη1η2⋯ηkn is known. Following by Lδkni=Ci(L), we define a mapping(21)ψ:ψi=ηi.Actually, Note that any starting state of an NFSR eventually reaches a cycle and keeps staying on it. E(kn) is constituted by the starting states that eventually reach the state δknkn and the states that those starting states go through. Finally, we need to take away repeat states.
Finally, we give Algorithm1 to obtain the basin E(kn) for an n-stage NFSR based on the mapping ψ and the set M if we knew the starting states of the NFSR.Algorithm 1:Basin.
1: Setl=1 and E(kn)=∅. 2: Seti=jl and E1=∅. 3: Computeψ(i)=ηi, and set i=ψ(i). 4: Ifi<kn and (i∉E1 or i∉E(kn), then E1=E1∪{i} and goto step 3; ifi<kn and (i∈E1 or i∈E(kn), then l=l+1; ifi=kn, then set E(kn)=E(kn)∪E1∪{i}. 5: Ifl≤|U|, then goto step 2. Otherwise output E(kn) and stop.Figure 6
Basin diagram of NFSR2 in Example22.


## 3.1. Basic Concepts

Definition 7 (see [2]).
A stateX(t) is called an equilibrium state of the logic network (6), if g(X(t))=X(t). For a k-valued NFSR, the equilibrium state of its logic network representation (8) is also called an equilibrium state of the NFSR.Note that an equilibrium state of an NFSR forms a cycle of length1, that is, unit cycle, in the state diagram of the NFSR.Definition 8.
The setE is called the basin of an equilibrium state X of an NFSR, if E is a set of states eventually reaching the equilibrium state X.Definition 9 (see [1]).
Ann-stage NFSR is globally stable to the equilibrium state 0, if, for any state X(t), there exists a positive integer N such that the state transition function of its logic network representation (8) satisfies gN(X(t))=0; that is, 0 is the unique equilibrium state and there are no other cycles in the state diagram of the NFSR.Definition 10 (see [1]).
Ann-stage NFSR is locally stable to the equilibrium state 0, if there exists some state X(t)≠0 such that for some positive integer N the state transition function of its logic network representation (8) satisfies gN(X(t))=0.Since ann-stage multi-valued NFSR has an equivalent logic network representation in a linear system (10), accordingly, we give an equivalent definition of globally (locally) stable multi-valued NFSR as follows.Definition 11.
Ann-stage NFSR is globally stable to the equilibrium state 0, if, for any state x(t), there exists a positive integer N such that the state transition matrix L of its logic network representation (8) satisfies LNx(t)=δknkn.Definition 12.
Ann-stage NFSR is locally stable to the equilibrium state 0, if there exists some state x(t)≠δknkn such that for some positive integer N the state transition matrix L of its logic network representation (8) satisfies LNx(t)=δknkn.In the sequel, an NFSR is globally (resp., locally) stable meaning that an NFSR is globally (resp., locally) stable to the equilibrium state0. From their definitions, it is easy to see that a globally stable NFSR must be locally stable but not the vice versa.Definition 13 (see [2]).
An NFSR is called a globally stable maximum transient NFSR if it is globally stable and has a single starting state.


## 3.2. Decoder NFSR

We show below that the error-propagation effect is closely related to the stability of an NFSR. The relevant portion of a decoder is shown in Figure2 and is seen to constitute an NFSR. The first m terms of the syndrome sequence are stored in the shift register, and the current input is sm+1, at the time when the decoder forms e0iΔ. Let the vector s=(s1,s2,…,sm) represent the shift register contents and let 0 denote the all-zero vector. s will be referred to as the state of the NFSR. The decoding algorithm is represented by the function F(sm+1,s); that is, F(sm+1,s)=e0iΔ. For any reasonable decoding algorithm, F(0,0)=0, since this is the case where all parity checks are satisfied. From Figure 2, it should be clear that m consecutive correct decoding decisions will clear the decoder of any spurious symbols introduced by a decoding error and hence will terminate the error propagation. The ability of the decoder to affect such a “reconvergence” is conveniently studied by considering the shift register to be loaded with some initial states s and the syndrome input sequence to be all zeros; that is, all succeeding parity checks are satisfied. Finally, the shift register will enter state 0 when reconvergence has been achieved. Thus the problem of studying error propagation will be reduced to the stability analysis of an NFSR in Figure 1.Figure 2
Decoder NFSR.


## 3.3. Necessary and Sufficient Conditions for Stability

Theorem 14.
An NFSR is locally stable if and only if the feedback function satisfiesf(0,…,0)=0, and there is at least one i∈{1,2,…,k-1} such that f(i,0,…,0)=0.Proof.
Necessity: Clearly, according to Definition9, f(0,…,0)=0 is a necessary condition for a locally stable NFSR. For any NFSR, the state 0 has the possible predecessors: itself and (i,0,…,0)T with i∈{1,2,…,k-1}. If the NFSR is locally stable, then there exist some states X(t)≠0 such that, for some integers N, gN(X(t))=0. Thus, 0 has a predecessor different to itself. Hence, there is at least one i∈{1,2,…,k-1} such that f(i,0,…,0)=0.
Sufficiency:f(0,…,0)=0 implies that 0 is an equilibrium state of the NFSR. If there is at least an i∈{1,2,…,k-1} such that f(i,0,…,0)=0, and then (i,0,…,0)T is a predecessor of 0. In other words, there exists a state X(t)=(i,0,…,0)T≠0 such that g(X(t))=0, which implies that the NFSR is locally stable.Corollary 15.
LetL=δknη1η2…ηkn be the state transition matrix of the logic network representation (10) in a linear system of an n-stage NFSR. Then the NFSR is locally stable if and only if there exists at least one i∈{1,2,…,k-1} such that ηkn=η(k-i)kn-1=kn.Proof.
Let the truth table of the feedback functionf of the NFSR be s1s2⋯skn, arranged in the reverse alphabet order. According to Theorem 14, the NFSR is locally stable if and only if the feedback function satisfies f(0,…,0)=0, and there is at least one i∈{1,2,…,k-1} such that f(i,0,…,0)=0, that is, skn=s(k-i)kn-1=0. Then the result follows from (12).Proposition 16.
LetL be the state transition matrix of the logic network representation (10) in a linear system of an n-stage NFSR. If Ckn(L)=δknkn, there exists an integer l such that Cr(Ll)=δknkn with some r≠kn. Then the NFSR is locally stable to δknkn.Proof.
LetL=δknη1η2…ηkn, and let the truth table of the feedback function f of the NFSR be s1s2⋯skn, arranged in the reverse alphabet order. Since Ckn(L)=δknkn, we have ηkn=kn. According to (12), we have skn={[(kn-1)modkn-1]+1}k-ηkn=0, that is, f(0,…,0)=0. Since there exists an integer l, such that Cr(Ll)=δknkn, we have Llδknr=δknkn. According to Definition 10, the NFSR is locally stable to δknkn.Theorem 17.
If the NFSR is globally stable maximum transient, then there exists a uniquei∈{1,2,…,k-1} such that f(0,0,…,0)=f(i,0,…,0)=0.Proof.
If the NFSR is globally stable maximum transient, then except the starting state and the state0, the other states have their own unique predecessor and unique successor. The state 0 has the possible predecessors: itself and (i,0,…,0)T with i∈{1,2,…,k-1}. Since the NFSR is globally stable maximum transient, 0 has a unique predecessor different to itself. Then the result follows.Remark 18.
Theorem14 shows that there is at least one i∈{1,2,…,k-1} such that f(0,0,…,0)=f(i,0,…,0)=0 is sufficient and necessary condition for a locally stable NFSR. However, Theorem 17 shows that there exists a unique i∈{1,2,…,k-1} such that f(0,0,…,0)=f(i,0,…,0)=0 for globally stable maximum transient NFSR, which is nothing but necessary condition.Theorem 19.
LetL be the state transition matrix of the logic network representation (10) in a linear system of an n-stage NFSR. The NFSR is globally stable, if and only if there exists an integer N≤kn-1 such that each column of LN is equal to δknkn. Moreover, the NFSR is globally stable maximum transient, if and only if each column of Lkn-1 is equal to δknkn.Proof.
Necessity: As the equilibrium state0∈Dkn is uniquely corresponding to the state δknkn∈Δkn, that an n-stage NFSR is globally stale to the equilibrium state 0 is equivalent to that the n-stage NFSR is globally stable to the state δknkn. Clearly, any state of an n-stage globally stable NFSR with one more starting state must be shifted fewer times to reach the equilibrium state 0 than the n-stage globally stable maximum transient NFSR. For an n-stage globally stable maximum transient NFSR, the starting state x0=δkni must shift kn-1 times to go through all other states and finally reaches the state δknkn (or, equivalently, the state 0) and keeps staying at this state. Therefore, N=kn-1 is the largest power such that each column of LN is equal to δknkn.
Sufficiency: There exists an integerN≤kn-1 such that each column of LN is equal to δknkn. Therefore, for the state δkni with any i∈{1,2,…,kn}, we have LNδkni=δknkn. According to Definition 9, the NFSR is globally stable. In particular, N=kn-1 means that the starting state δkni for any i∈{1,2,…,kn} eventually reaches the equilibrium state δknkn and keeps staying at this state. Thus, the result follows.Theorem 20.
Given a globally stable maximum transientk-valued n-stage NFSR, its starting state is (0,0,…,0,i)T with some i∈{1,2,…,k-1}.Proof.
For a given globally stable maximum transientk-valued n-stage NFSR, the state 00⋯0T has only two predecessors, itself and (a,0,…,0)T with some a∈{1,2,…,k-1}. Assume that all k-1 states (0,0,…,0,i)T, for any i∈{1,2,…,k-1}, are not the starting state of the NFSR. Let the predecessor of any given state (0,0,…,0,i)T be (bi,0,…,0)T, with some bi∈{1,2,…,k-1}. Then there exists bi0 with some i0∈{1,2,…,k-1} such that (bi0,0,…,0)T=(a,0,…,0)T, which implies that bi0=a. Note that the successor of (bi0,0,…,0)T is (0,0,…,i0)T with i0∈{1,2,…,k-1}, and the successor of (a,0,…,0)T is 00⋯0T. Then (a,0,…,0)T has two different successors, (0,0,…,0)T and (0,0,…,0,i0)T with some i0∈{1,2,…,k-1}, which is a contradiction that any state has a unique successor. Hence, for any given globally stable maximum transient k-valued n-stage NFSR, there exists some i∈{1,2,…,k-1} such that (0,0,…,0,i)T is the starting state of the NFSR.Example 21.
Whenk=3 and n=2, we consider two nonlinear feedback shift registers, NFSR1 and NFSR2. Their feedback functions are, respectively, as follows:(13)f1x1,x2=x2+x1x22+1and(14)f2x1,x2=2x1+x2+x12+x1x22+x12x22.Computations show that the state transition matrices of the logic network representations of both NFSRs, respectively, are(15)L1=δ9347268159and(16)L2=δ9267269159.We use the same notations in previous sections. For the state transition matrix L1, η3≠9,η6≠9. According to Corollary 15, we get that NFSR1 is not locally stable. Meanwhile, for the state transition matrix L2, η6=9, and L25=δ9999999999. From Theorem 17 and Theorem 19, we obtain that NFSR2 is globally stable. Moreover η1=η4=2,η2=η5=6, and according to Proposition13 in [34], the NFSR2 has two branch states: δ92 and δ96. Actually, the NFSR2 has three starting states. All those features are consistent with their state diagrams, which are shown in Figures 3 and 4.Figure 3
State diagram of NFSR1 in Example21.Figure 4
State diagram of NFSR2 in Example21.Example 22.
Whenk=3,n=2, we consider two nonlinear feedback shift registers, NFSR3 and NFSR4. Their feedback functions are, respectively, as follows:(17)f3x1,x2=2x1+x2+2x1x2+x1x22+x12+x12x2and(18)f4x1,x2=2x1+x2+x1x2+2x12+2x12x2.Computations show that the state transition matrices of the logic network representations of both NFSRs, respectively, are(19)L3=δ9267349159and(20)L4=δ9269348159.We use the same notations in previous sections. For the state transition matrix L3 and L4, we obtain L38=L48=δ9999999999. According to Theorem 19, both NFSR3 and NFSR4 are globally stable maximum transient. Their state diagrams are shown in Figure 5.Figure 5
State diagram of NFSR1 in Example22.Clearly,(0,1)T (resp., (0,2)T) is the starting state of NFSR3 (resp., NFSR4), which is consistent with the result in Theorem 20. It also shows that different globally stable maximum transient k-valued NFSRs with k>2 may have different starting states, which is unlike the globally stable maximum transient binary NFSRs whose starting states are the same, that is, (0,0,…,0,1)T.


## 3.4. Basin of the Equilibrium State of NFSRs

Definition 23.
The setE is called the basin of an equilibrium state X of an NFSR, if E is a set of states eventually reaching the equilibrium state X.We letE(δknkn) be the basin of the equilibrium state δknkn. The stability of an NFSR in Figure 1 completely depends on the basin E(δknkn). In the following, we will focus on how to get the basin of the equilibrium state. Reference [34] gives a way to find all starting states of an NFSR, shown in the following lemma.Lemma 24 (see [34]).
LetL be a state transition matrix of an n-stage NFSR. δkni is a starting state if and only if δkni is not a column of the state transition matrix L, where i∈{1,2,…,kn}.Theorem 25.
LetL be a state transition matrix of an n-stage NFSR. Then the basin of the equilibrium state δknkn is E(knkn)={Lkδkni|1≤k≤Ki, Ki is the smallest ki satisfying Lkδkni=δknkn, and δkni∈C(L) with some positive integer i≤kn}.Proof.
The result follows from Lemmas6 and 24.
In fact, it is easy to get the whole state transition graph of an NFSR when its state transition matrixL is known. For any L∈Lkn×kn,Ci(L)=δknj, we have that δkni is the predecessor state of δknj and δknj is the successor state of δkni; that is, Lδkni=Ci(L). For example, we consider the NFSR2 in Example 21. Its state transition matrix L=δ9267269159. Obviously, only δ93,δ94,δ98∈C(L), and according to Lemma 24, they are all starting states of NFSR2. For the state δ94, it is easy to see that Lδ94=C4(L)=δ92, and L2δ94=Lδ92=C2(L)=δ96 and L3δ94=L2δ92=Lδ96=C6(L)=δ99. Thus, according to Theorem 25, we have δ94,δ92,δ96,δ99∈E(knkn). Similarly, for the state δ93,δ98, we can also use the same method. Finally, we have E(knkn)={δ91,δ92,δ93,δ94,δ95,δ96,δ97,δ98,δ99}. All those features are consistent with the logic network expression of its state diagrams, which are shown in Figure 6. In the following, we strive to give an algorithm to obtain the basin E(knkn). We define E(kn) to be the set of elements that represent the positions of the entry 1s of all elements in E(knkn). Precisely speaking, if E(knkn)={δkni1,δkni2,…,δknim}, then E(kn)={i1,i2,…,im}. For the sake of convenience, we also called E(kn) the basin. For an n-stage NFSR, we first find its starting states according to Lemma 24. Let U be a set of starting states, and denote its cardinality as |U|. Suppose that the starting state set U has been obtained in terms of Lemma 24, and its elements are denoted by δknjl,l=1,2,…,|U|. Let M={j1,j2,…,j|U|}, which is a set of the positions of the entry 1s of all the elements in the starting states U. Second, we assume that the state transition matrix of the NFSR L=δknη1η2⋯ηkn is known. Following by Lδkni=Ci(L), we define a mapping(21)ψ:ψi=ηi.Actually, Note that any starting state of an NFSR eventually reaches a cycle and keeps staying on it. E(kn) is constituted by the starting states that eventually reach the state δknkn and the states that those starting states go through. Finally, we need to take away repeat states.
Finally, we give Algorithm1 to obtain the basin E(kn) for an n-stage NFSR based on the mapping ψ and the set M if we knew the starting states of the NFSR.Algorithm 1:Basin.
1: Setl=1 and E(kn)=∅. 2: Seti=jl and E1=∅. 3: Computeψ(i)=ηi, and set i=ψ(i). 4: Ifi<kn and (i∉E1 or i∉E(kn), then E1=E1∪{i} and goto step 3; ifi<kn and (i∈E1 or i∈E(kn), then l=l+1; ifi=kn, then set E(kn)=E(kn)∪E1∪{i}. 5: Ifl≤|U|, then goto step 2. Otherwise output E(kn) and stop.Figure 6
Basin diagram of NFSR2 in Example22.


## 4. The Construction of Stable Feedback Shift Registers over the Binary Field

Ann-stage k-valued NFSR can be described as Figure 1. Let the present state of the NFSR be s=(x1,x2,…,xn)∈Dkn, and then the successor of s can be (x2,x3,…,xn,a)∈Dkn,a∈{1,2,…,k-1}; that is, the state s can have k different successors. Then we construct directly the stable n+1-stage k-valued NFSRs from the stable n-stage k-valued NFSRs by the properties of D-morphism, which is not a trivial work. We will consider it in another new work, in which we will define a new mapping. Therefore, in this section, we first give a new method for constructing stable n+1-stage NFSRs from stable n-stage NFSRs by the properties of D-morphism over the binary field.


### 4.1.D-Morphism

In this subsection, we will give an overview of theD-morphism. Let n be a positive integer, and let s=(x1,x2,…,xn)∈F2n. We define s^, the conjugate of s, and s¯, the dual of s, by(22)s^=x1¯,x2,…,xn∈F2nand(23)s¯=x1¯,x2¯,…,xn¯∈F2n,where xi¯ denotes the Boolean complement of xi. We define a mapping D:F2n→F2n-1, n≥2, as follows. For s=(x1,x2,…,xn)∈F2n and s′=(x1+x2,x2+x3,…,xn-1+xn)∈F2n-1,(24)Dx1,x2,…,xn=x1+x2,x2+x3,…,xn-1+xn,and, in the sequel, we denote (24) as Ds=s′.Fors=(x1,x2,…,xn) and s¯=(x1¯,x2¯,…,xn¯), we have(25)Ds=Dx1,x2,…,xn=x1+x2,x2+x3,…,xn-1+xn,(26)Ds¯=Dx1¯,x2¯,…,xn¯=x1¯+x2¯,x2¯+x3¯,…,xn-1¯+xn¯=x1+1+x2+1,x2+1+x3+1,…,xn-1+1+xn+1=x1+x2,x2+x3,…,xn-1+xn.Equations (25) and (26) imply that the mapping D is a 2-to-1 mapping, and it maps (x1,x2,…,xn) and (x¯1,x¯2,…,x¯n) to the same element. Conversely, each (y1,y2,…,yn-1)∈F2n-1 has two preimages in F2n under D, which are given by(27)Dt-1y1,y2,…,yn-1=t,t+y1,t+y1+y2,…,t+y1+y2+⋯+yn-1,t=0,1.In the sequel, we denote (27) as Dt-1s′, t=0,1.Some properties ofD-morphism are recalled below. The n-th-order de Bruijn graph Gn is a directed graph with 2n vertices, labeled by the elements of F2n. The vertices x and y of Gn, x,y∈F2n, are jointed by an arc, directed from x to y. A factor of Gn is a partial graph of Gn, and it includes all the vertices of Gn. For example, the state graph of every nonsingular n-stage NFSR in F2n is a factor of Gn.Lemma 26 (see [38]).
Lets and s^ be a pair of conjugate states in Gn. Then {D0-1s,D1-1s^} are {D1-1s^,{D1-1s} two conjugate pairs in Gn+1.The mappingD induces a graph homomorphism (called D-morphism) from the n-th-order de Bruijn graph Gn to the (n-1)-th-order de Bruijn graph Gn-1 [38]. If H is a subgraph of Gn, then its D-morphism image D(H) is a subgraph of Gn-1. Obviously, the state diagram of an n-stage NFSR is a subgraph of Gn.


### 4.2. Synthesis Theory of Stable FSRs

Lemma 27 (see [39]).
LetC be a cycle in Gn, and let s be a state on C. Then the state D0-1s is on one of the cycles D0-1C and D1-1C, and D1-1s is on the other one.By Lemma27, it is easy to obtain the following corollary.Corollary 28.
LetGn′ be a factor of Gn, and let s be a state on Gn′. Then the state D0-1s is on one of D0-1G and D1-1G, and D1-1s is on the other one.Theorem 29.
LetSGn be the state diagram of an n-stage NFSR, and let s1,s2,s3 be pairwise different states on SGn. If s1 and s2 are two predecessors of s3, then D0-1s1 and D1-1s2 are two predecessors of one of D0-1s3 and D1-1s3, and D1-1s1 and D0-1s2 are two predecessors of the other one; or D1-1s1 and D0-1s2 are two predecessors of one of D0-1s3 and D1-1s3, and D0-1s1 and D1-1s2 are two predecessors of the other one.Proof.
Sinces1 and s2 are two predecessors of s3, we have (28)s1=x1,x2,…,xn,s2=x¯1,x2,…,xn,s3=x2,x3,…,xn,ywithsi∈Bn,i=1,2,3. Then, we have (29)D0-1s1=0,x1,x1+x2,…,x1+x2+⋯xn,D1-1s1=1,x1,1+x1+x2,…,1+x1+x2+⋯xn,D0-1s2=0,x¯1,x¯1+x2,…,x¯1+x2+⋯xn,D1-1s2=1,x¯1,1+x¯1+x2,…,1+x¯1+x2+⋯xn,D0-1s3=0,x2,x2+x3,…,x2+x3+⋯xn+y,D1-1s3=1,1+x2,1+x2+x3,…,1+x2+x3+⋯xn+y. Thus, if x1=0, we have that D0-1s1 and D1-1s2 are two predecessors of D0-1s3, and D1-1s1 and D0-1s2 are two predecessors of D1-1s3; if x1=1, we have that D0-1s1 and D1-1s2 are two predecessors of D1-1s3, and D1-1s1 and D0-1s2 are two predecessors of D0-1s3.By Theorem29, it is easy to obtain the following corollary.Corollary 30.
S G n is the state diagram of a stable n-stage NFSR; then there exists an (n+1)-stage NFSR such that D-1SGn is the state diagram of NFSR. Moreover, D-1SGn is two self-dual in Gn+1.Theorem 31.
IfSGn is the state diagram of an n-stage NFSR with the feedback function f(x1,x2,…,xn), then there exists an (n+1)-stage NFSR such that D-1SGn is its state diagram. Moreover, if the feedback function of the (n+1)-stage NFSR is f′, then f′(x1,x2,…,xn+1)=xn+1+f(x1+x2,x2+x3,…,xn+xn+1).Proof.
We define that the mappingsF′ and F are induced by the functions f′ and f, respectively; that is, for any given (x1,x2,…,xn+1)∈Bn+1, (y1,y2,…,yn)∈Bn,(30)F′:x1,x2,…,xn+1→x2,x3,…,xn+1,f′x1,x2…,xn+1,F:y1,y2,…,yn→y2,y3,…,yn,fy1,,y2,…,yn. According to Corollary 30, there exists a one-to-one correspondence between SGn and the self-dual D-1SGn. More explicitly, for any given s=(x1,x2,…,xn+1)∈Bn+1,(31)DF′s=FDs,where(32)DF′s=x2+x3,x3+x4,…,xn+xn+1,xn+1+f′x1,x2…,xn+1,(33)FDs=x2+x3,x3+x4,…,xn+xn+1,xn+1+fx1+x2,x2+x3,…,xn+xn+1.Then, the result follows from (31), (32), and (33); that is,(34)f′x1,x2…,xn+1=xn+1+fx1+x2,x2+x3,…,xn+xn+1.Letf(x1,x2,…,xn) be the feedback function of an n-stage NFSR1, and let(35)hx1,x2,…,xn=fx1,x2,…,xn+x1a1x2a2⋯xnanbe the feedback function of an n-stage NFSR2, where (a1,a2,…,an)∈Bn and xi1 and xi0 denote xi and x¯i, respectively. Note that x1a1x2a2⋯xnan=1 if and only if xi=ai for 1≤i≤n. Then, the values of two functions h and f have different values only at the state (a1,a2,…,an).Example 32.
Consider a3-stage stable NFSR with a feedback function(36)fx1,x2,x3=x2+x3+x1x2+x2x3.
According to Theorem31, we obtain a 4-variant function, which is the feedback function of the 4-NFSR as follows:(37)f′x1,x2,x3,x4=x4+fx1+x2,x2+x3,x3+x4=x3+x1x2+x1x3+x2x4+x3x4.
According to (35), we obtain a 4-stage stable NFSR with a feedback function(38)f′′x1,x2,x3,x4=f′x1,x2,x3,x4+x11x21x31x41=x3+x1x2+x1x3+x2x4+x3x4+x1x2x3x4.The state diagrams of the NFSRs with the feedback functions f,f′, and f′′ are shown in Figures 7, 8, and 9, respectively.Figure 7
State diagram of NFSR with the feedback functionsf in Example 32.Figure 8
State diagram of NFSR with the feedback functionsf′ in Example 32.Figure 9
State diagram of NFSR with the feedback functionsf′′ in Example 32.In summary, the theorems and corollaries in Section4.1 presented a procedure for constructing stable n+1-stage NFSRs from stable n-stage NFSRs. Step 1 determines the feedback function of the n+1-stage NFSR from stable n-stage NFSR according to Theorem 31. Step 2 is used in finding the feedback function of n+1-stage stable NFSR from n+1-stage NFSR obtained by step 1.


## 4.1.D-Morphism

In this subsection, we will give an overview of theD-morphism. Let n be a positive integer, and let s=(x1,x2,…,xn)∈F2n. We define s^, the conjugate of s, and s¯, the dual of s, by(22)s^=x1¯,x2,…,xn∈F2nand(23)s¯=x1¯,x2¯,…,xn¯∈F2n,where xi¯ denotes the Boolean complement of xi. We define a mapping D:F2n→F2n-1, n≥2, as follows. For s=(x1,x2,…,xn)∈F2n and s′=(x1+x2,x2+x3,…,xn-1+xn)∈F2n-1,(24)Dx1,x2,…,xn=x1+x2,x2+x3,…,xn-1+xn,and, in the sequel, we denote (24) as Ds=s′.Fors=(x1,x2,…,xn) and s¯=(x1¯,x2¯,…,xn¯), we have(25)Ds=Dx1,x2,…,xn=x1+x2,x2+x3,…,xn-1+xn,(26)Ds¯=Dx1¯,x2¯,…,xn¯=x1¯+x2¯,x2¯+x3¯,…,xn-1¯+xn¯=x1+1+x2+1,x2+1+x3+1,…,xn-1+1+xn+1=x1+x2,x2+x3,…,xn-1+xn.Equations (25) and (26) imply that the mapping D is a 2-to-1 mapping, and it maps (x1,x2,…,xn) and (x¯1,x¯2,…,x¯n) to the same element. Conversely, each (y1,y2,…,yn-1)∈F2n-1 has two preimages in F2n under D, which are given by(27)Dt-1y1,y2,…,yn-1=t,t+y1,t+y1+y2,…,t+y1+y2+⋯+yn-1,t=0,1.In the sequel, we denote (27) as Dt-1s′, t=0,1.Some properties ofD-morphism are recalled below. The n-th-order de Bruijn graph Gn is a directed graph with 2n vertices, labeled by the elements of F2n. The vertices x and y of Gn, x,y∈F2n, are jointed by an arc, directed from x to y. A factor of Gn is a partial graph of Gn, and it includes all the vertices of Gn. For example, the state graph of every nonsingular n-stage NFSR in F2n is a factor of Gn.Lemma 26 (see [38]).
Lets and s^ be a pair of conjugate states in Gn. Then {D0-1s,D1-1s^} are {D1-1s^,{D1-1s} two conjugate pairs in Gn+1.The mappingD induces a graph homomorphism (called D-morphism) from the n-th-order de Bruijn graph Gn to the (n-1)-th-order de Bruijn graph Gn-1 [38]. If H is a subgraph of Gn, then its D-morphism image D(H) is a subgraph of Gn-1. Obviously, the state diagram of an n-stage NFSR is a subgraph of Gn.


## 4.2. Synthesis Theory of Stable FSRs

Lemma 27 (see [39]).
LetC be a cycle in Gn, and let s be a state on C. Then the state D0-1s is on one of the cycles D0-1C and D1-1C, and D1-1s is on the other one.By Lemma27, it is easy to obtain the following corollary.Corollary 28.
LetGn′ be a factor of Gn, and let s be a state on Gn′. Then the state D0-1s is on one of D0-1G and D1-1G, and D1-1s is on the other one.Theorem 29.
LetSGn be the state diagram of an n-stage NFSR, and let s1,s2,s3 be pairwise different states on SGn. If s1 and s2 are two predecessors of s3, then D0-1s1 and D1-1s2 are two predecessors of one of D0-1s3 and D1-1s3, and D1-1s1 and D0-1s2 are two predecessors of the other one; or D1-1s1 and D0-1s2 are two predecessors of one of D0-1s3 and D1-1s3, and D0-1s1 and D1-1s2 are two predecessors of the other one.Proof.
Sinces1 and s2 are two predecessors of s3, we have (28)s1=x1,x2,…,xn,s2=x¯1,x2,…,xn,s3=x2,x3,…,xn,ywithsi∈Bn,i=1,2,3. Then, we have (29)D0-1s1=0,x1,x1+x2,…,x1+x2+⋯xn,D1-1s1=1,x1,1+x1+x2,…,1+x1+x2+⋯xn,D0-1s2=0,x¯1,x¯1+x2,…,x¯1+x2+⋯xn,D1-1s2=1,x¯1,1+x¯1+x2,…,1+x¯1+x2+⋯xn,D0-1s3=0,x2,x2+x3,…,x2+x3+⋯xn+y,D1-1s3=1,1+x2,1+x2+x3,…,1+x2+x3+⋯xn+y. Thus, if x1=0, we have that D0-1s1 and D1-1s2 are two predecessors of D0-1s3, and D1-1s1 and D0-1s2 are two predecessors of D1-1s3; if x1=1, we have that D0-1s1 and D1-1s2 are two predecessors of D1-1s3, and D1-1s1 and D0-1s2 are two predecessors of D0-1s3.By Theorem29, it is easy to obtain the following corollary.Corollary 30.
S G n is the state diagram of a stable n-stage NFSR; then there exists an (n+1)-stage NFSR such that D-1SGn is the state diagram of NFSR. Moreover, D-1SGn is two self-dual in Gn+1.Theorem 31.
IfSGn is the state diagram of an n-stage NFSR with the feedback function f(x1,x2,…,xn), then there exists an (n+1)-stage NFSR such that D-1SGn is its state diagram. Moreover, if the feedback function of the (n+1)-stage NFSR is f′, then f′(x1,x2,…,xn+1)=xn+1+f(x1+x2,x2+x3,…,xn+xn+1).Proof.
We define that the mappingsF′ and F are induced by the functions f′ and f, respectively; that is, for any given (x1,x2,…,xn+1)∈Bn+1, (y1,y2,…,yn)∈Bn,(30)F′:x1,x2,…,xn+1→x2,x3,…,xn+1,f′x1,x2…,xn+1,F:y1,y2,…,yn→y2,y3,…,yn,fy1,,y2,…,yn. According to Corollary 30, there exists a one-to-one correspondence between SGn and the self-dual D-1SGn. More explicitly, for any given s=(x1,x2,…,xn+1)∈Bn+1,(31)DF′s=FDs,where(32)DF′s=x2+x3,x3+x4,…,xn+xn+1,xn+1+f′x1,x2…,xn+1,(33)FDs=x2+x3,x3+x4,…,xn+xn+1,xn+1+fx1+x2,x2+x3,…,xn+xn+1.Then, the result follows from (31), (32), and (33); that is,(34)f′x1,x2…,xn+1=xn+1+fx1+x2,x2+x3,…,xn+xn+1.Letf(x1,x2,…,xn) be the feedback function of an n-stage NFSR1, and let(35)hx1,x2,…,xn=fx1,x2,…,xn+x1a1x2a2⋯xnanbe the feedback function of an n-stage NFSR2, where (a1,a2,…,an)∈Bn and xi1 and xi0 denote xi and x¯i, respectively. Note that x1a1x2a2⋯xnan=1 if and only if xi=ai for 1≤i≤n. Then, the values of two functions h and f have different values only at the state (a1,a2,…,an).Example 32.
Consider a3-stage stable NFSR with a feedback function(36)fx1,x2,x3=x2+x3+x1x2+x2x3.
According to Theorem31, we obtain a 4-variant function, which is the feedback function of the 4-NFSR as follows:(37)f′x1,x2,x3,x4=x4+fx1+x2,x2+x3,x3+x4=x3+x1x2+x1x3+x2x4+x3x4.
According to (35), we obtain a 4-stage stable NFSR with a feedback function(38)f′′x1,x2,x3,x4=f′x1,x2,x3,x4+x11x21x31x41=x3+x1x2+x1x3+x2x4+x3x4+x1x2x3x4.The state diagrams of the NFSRs with the feedback functions f,f′, and f′′ are shown in Figures 7, 8, and 9, respectively.Figure 7
State diagram of NFSR with the feedback functionsf in Example 32.Figure 8
State diagram of NFSR with the feedback functionsf′ in Example 32.Figure 9
State diagram of NFSR with the feedback functionsf′′ in Example 32.In summary, the theorems and corollaries in Section4.1 presented a procedure for constructing stable n+1-stage NFSRs from stable n-stage NFSRs. Step 1 determines the feedback function of the n+1-stage NFSR from stable n-stage NFSR according to Theorem 31. Step 2 is used in finding the feedback function of n+1-stage stable NFSR from n+1-stage NFSR obtained by step 1.


## 5. Conclusion

A stable NFSR is an alternative to limit this error propagation. This paper studied the stability of multi-valued NFSRs using a logic network approach. A multi-valued NFSR can be viewed as a logic network. Based on its logic network representation, we first gave some sufficient and necessary conditions for globally (locally) stable multi-valued NFSRs. Then, explicit forms have been given for the set of basins, and the algorithm for obtaining the set of basins is provided as well. The approach used in this paper is helpful to theoretically analyze multi-valued NFSRs. Finally, the method of constructing stable NFSRs is presented, so that we can get a stablen+1-stage NFSR from stable n-stage NFSR by the properties of D-morphism. Nonlinear feedback shift registers are subject to impulsive effects and time-delay effects, which might be interesting to be considered in the future work.



---

*Source: 8765970-2019-02-21.xml*