logo

SCIENCE CHINA Information Sciences, Volume 64 , Issue 5 : 152207(2021) https://doi.org/10.1007/s11432-020-2981-4

A novel synthesis method for reliable feedback shift registers via Boolean networks

More info
  • ReceivedMar 6, 2020
  • AcceptedJun 19, 2020
  • PublishedMar 25, 2021

Abstract


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61973078, 61903339), Natural Science Foundation of Jiangsu Province of China (Grant No. BK20170019), Jiangsu Province Six Talent Peaks Project (Grant No. 2015-ZNDW-002), Fundamental Research Funds for the Central Universities (Grant No. 2242019k1G013), and Postgraduate Research Practice Innovation Program of Jiangsu Province (Grant No. KYCX19_0111).


Supplement

Appendix

In Theorem 3.14, we proved that for any $n$-stage monotonous FSR, the total number of cyclic attractors is no more than $2^{n-2}$, but we did not prove that there exists a cyclic attractor including $\delta_{2^{n}}^{\alpha}$ and $\delta_{2^{n}}^{\frac{\alpha}{2}+2^{n-1}}$ rather than including $\delta_{2^{n}}^{\alpha}$ and $\delta_{2^{n}}^{\frac{\alpha}{2}}$ for any even integer $\alpha\in~[\mathcal~{O}_{2}]$. In the following, we prove that there is definitely no such cycle $\delta_{2^{n}}^{\alpha}\rightarrow~\delta_{2^{n}}^{2(\alpha-2^{n-1})}\rightarrow\cdots\rightarrow~\delta_{2^{n}}^{\frac{\alpha}{2}}\rightarrow~\delta_{2^{n}}^{\alpha}$ but there possibly exists the cycle $\delta_{2^{n}}^{\alpha}\rightarrow~\delta_{2^{n}}^{2(\alpha-2^{n-1})}\rightarrow\cdots\rightarrow~\delta_{2^{n}}^{\frac{\alpha}{2}+2^{n-1}}\rightarrow~\delta_{2^{n}}^{\alpha}$.

Assume that there exists a cyclic attractor with length $\kappa$ in an $n$-stage monotonous FSR: $X_{1}\rightarrow~X_{2}\rightarrow~\cdots\rightarrow~X_{\kappa}$. Then by Definition 3.4, we have that $w(X_{\kappa})\leq~w(X_{\kappa-1})\leq\cdots\leq~w(X_{1})\leq~w(X_{\kappa})$. Therefore, $w(X_{\kappa})=~w(X_{\kappa-1})=\cdots=w(X_{1})=~w(X_{\kappa})$ [2]. If there exists the cycle $\delta_{2^{n}}^{\alpha}\rightarrow~\delta_{2^{n}}^{2(\alpha-2^{n-1})}\rightarrow\cdots\rightarrow~\delta_{2^{n}}^{\frac{\alpha}{2}}\rightarrow~\delta_{2^{n}}^{\alpha}$, then $w(X_{\alpha})=w(X_{\frac{\alpha}{2}})$, where $X_{\alpha}=(a_{1},~a_{2},\ldots,~a_{n})^{\rm~T}\sim~\delta_{2^{n}}^{\alpha},~X_{\frac{\alpha}{2}}=(a'_{1},~a'_{2},\ldots,~a'_{n})^{\rm~T}\sim~\delta_{2^{n}}^{\frac{\alpha}{2}}$, and $\alpha$ satisfies the following condition: \begin{equation} \alpha=2^{n}-(a_{1}2^{n-1}+a_{2}2^{n-2}+\cdots+a_{n}). \tag{10}\end{equation} Multipling both sides of Eq. (10) by $\frac{1}{2}$ results in \begin{align} \frac{\alpha}{2}=&2^{n-1}-(a_{1}2^{n-2}+a_{2}2^{n-3} +\cdots+a_{n-1}+\frac{a_{n}}{2}) \\ =&2^{n}-(2^{n-1}+a_{1}2^{n-2}+a_{2}2^{n-3} +\cdots+a_{n-1}), \tag{11} \end{align} which implies that $X_{\frac{\alpha}{2}}=(1,~a_{1},\ldots,~a_{n-1})^{\rm~T}$ by Lemma 2.1, and then we have $a_{i}=a'_{i+1}$, $i\in~[1,~n-1]$. It follows from Lemma 3.16 that $\alpha$ is an even integer, and then we have $a_{n}=0$, and $X_{\alpha}=(a_{1},~a_{2},\ldots,~a_{n-1},~0)^{\rm~T}$. Based on the analysis, we have that $w(X_{\alpha})\neq~w(X_{\frac{\alpha}{2}})$ and $w(X_{\alpha})-~w(X_{\frac{\alpha}{2}})=1$, which contradicts with $w(X_{\alpha})=w(X_{\frac{\alpha}{2}})$. Therefore, there does not exist the cycle $\delta_{2^{n}}^{\alpha}\rightarrow~\delta_{2^{n}}^{2(\alpha-2^{n-1})}\rightarrow\cdots\rightarrow~\delta_{2^{n}}^{\frac{\alpha}{2}}\rightarrow~\delta_{2^{n}}^{\alpha}$.

But for another sequence $\delta_{2^{n}}^{\alpha},~\delta_{2^{n}}^{2(\alpha-2^{n-1})},\ldots,~\delta_{2^{n}}^{\frac{\alpha}{2}+2^{n-1}},~\delta_{2^{n}}^{\alpha}$, it is possible to form a cycle. The proof is given as follows. Based on Eq. (8) and Lemma 3.16, the subpaths $\delta_{2^{n}}^{\alpha}\rightarrow~\delta_{2^{n}}^{2(\alpha-2^{n-1})}$ and $\delta_{2^{n}}^{\frac{\alpha}{2}+2^{n-1}}\rightarrow~\delta_{2^{n}}^{\alpha}$ are determined, but the rest path $\delta_{2^{n}}^{2(\alpha-2^{n-1})}\rightarrow~\cdots\rightarrow~\delta_{2^{n}}^{\frac{\alpha}{2}+2^{n-1}}$ with $\delta_{2^{n}}^{2(\alpha-2^{n-1})}\in~\mathcal~{O}_{1}$ is indeterminate, and depends on $b_{i},~i\in~[1,~2^{n-1}]$. Therefore, we only consider these two determined subpaths. That is, if $w(X_{\alpha})=w(X_{2(\alpha-2^{n-1})})$ and $w(X_{\alpha})=w(X_{\frac{\alpha}{2}+2^{n-1}})$, then the cycle is possible; otherwise, it must be impossible.

By doubling both sides of Eq. (10), one has that \begin{equation*} 2\alpha=2^{n+1}-(a_{1}2^{n}+a_{2}2^{n-1}+\cdots+2a_{n}).\end{equation*} Then subtracting both sides of the above equation by $2^{n-1}$ results in \begin{equation} 2(\alpha-2^{n-1})=2^{n}-(a_{1}2^{n}+a_{2}2^{n-1}+\cdots+2a_{n}). \tag{12}\end{equation} Since $\alpha\in~[\mathcal~{S}_{1}]$, which means $a_{1}=0$, Eq. (12) can be rewritten as \begin{equation} 2(\alpha-2^{n-1})=2^{n}-(a_{2}2^{n-1}+\cdots+2a_{n}+0), \tag{13}\end{equation} which implies that $X_{2(\alpha-2^{n-1})}=(a_{2},~a_{3},\ldots,~a_{n},~0)^{\rm~T}$. Therefore, $w(X_{\alpha})=w(X_{2(\alpha-2^{n-1})})$.

On the other hand, adding both sides of Eq. (10) by $2^{n-1}$ results in \begin{align} \frac{\alpha}{2}+2^{n-1} =&2^{n}-(a_{1}2^{n-2}+a_{2}2^{n-3} +\cdots+a_{n-1}) \\ =&2^{n}-(0\cdot2^{n-1}+a_{1}2^{n-2}+a_{2}2^{n-3} +\cdots+a_{n-1}), \tag{14} \end{align} which implies that $X_{\frac{\alpha}{2}+2^{n-1}}=(0,~a_{1},~a_{2},\ldots,~a_{n-1})^{\rm~T}$, and $w(X_{\alpha})=w(X_{\frac{\alpha}{2}+2^{n-1}})$. Therefore, $w(X_{\alpha})=w(X_{\frac{\alpha}{2}+2^{n-1}})=w(X_{2(\alpha-2^{n-1})})$.

Based on the above analysis, we can conclude that for any even integer $\alpha\in~[\mathcal~{O}_{2}]$, the cycle $\delta_{2^{n}}^{\alpha}\rightarrow~\delta_{2^{n}}^{2(\alpha-2^{n-1})}\rightarrow\cdots\rightarrow~\delta_{2^{n}}^{\frac{\alpha}{2}}\rightarrow~\delta_{2^{n}}^{\alpha}$ cannot exist but the cycle $\delta_{2^{n}}^{\alpha}\rightarrow~\delta_{2^{n}}^{2(\alpha-2^{n-1})}\rightarrow\cdots\rightarrow~\delta_{2^{n}}^{\frac{\alpha}{2}+2^{n-1}}\rightarrow~\delta_{2^{n}}^{\alpha}$ may exist. Therefore, for any $n$-stage monotonous FSR, the total number of cyclic attractors is no more than $2^{n-2}$. Additionally, the above analysis also proved that it is impossible to have a cyclic attractor including $(0~1~1~0)^{\rm~T}$ and $(1~0~1~1)^{\rm~T}$ in Remark 3.15.


References

[1] Massey J, Liu R. Application of Lyapunov's direct method to the error-propagation effect in convolutional codes (Corresp.). IEEE Trans Inform Theor, 1964, 10: 248-250 CrossRef Google Scholar

[2] Wan Z X, Dai Z D, Liu M L, et al. Nonlinear Feedback Shift Registers (in Chinese). Beijing: Science Press, 1978. Google Scholar

[3] Ma Z, Qi W F, Tian T. On the decomposition of an NFSR into the cascade connection of an NFSR into an LFSR. J Complexity, 2013, 29: 173-181 CrossRef Google Scholar

[4] Jia-Min Zhang , Wen-Feng Qi , Tian Tian . Further Results on the Decomposition of an NFSR Into the Cascade Connection of an NFSR Into an LFSR. IEEE Trans Inform Theor, 2015, 61: 645-654 CrossRef Google Scholar

[5] Kauffman S A. Metabolic stability and epigenesis in randomly constructed genetic nets. J Theor Biol, 1969, 22: 437-467 CrossRef Google Scholar

[6] Zhang Y, Liu Y. Nonlinear second-order multi-agent systems subject to antagonistic interactions without velocity constraints. Appl Math Computation, 2020, 364: 124667 CrossRef Google Scholar

[7] Li N, Cao J D. Synchronization criteria for multiple memristor-based neural networks with time delay and inertial term. Sci China Technol Sci, 2018, 61: 612-622 CrossRef ADS Google Scholar

[8] Cheng D Z, Qi H S, Li Z Q. Analysis and Control of Boolean Networks: A Semi-tensor Product Approach. Berlin: Springer, 2010. Google Scholar

[9] Cheng D, Qi H. Controllability and observability of Boolean control networks. Automatica, 2009, 45: 1659-1667 CrossRef Google Scholar

[10] Liang S, Li H, Wang S. Structural controllability of Boolean control networks with an unknown function structure. Sci China Inf Sci, 2020, 63: 219203 CrossRef Google Scholar

[11] Hou B, Li X, Chen G. Structural Controllability of Temporally Switching Networks. IEEE Trans Circuits Syst I, 2016, 63: 1771-1781 CrossRef Google Scholar

[12] Zhu S, Liu Y, Lou Y. Stabilization of logical control networks: an event-triggered control approach. Sci China Inf Sci, 2020, 63: 112203 CrossRef Google Scholar

[13] Xu M, Liu Y, Lou J. Set Stabilization of Probabilistic Boolean Control Networks: A Sampled-Data Control Approach. IEEE Trans Cybern, 2020, 50: 3816-3823 CrossRef Google Scholar

[14] Lin L, Cao J, Rutkowski L. Robust Event-Triggered Control Invariance of Probabilistic Boolean Control Networks. IEEE Trans Neural Netw Learning Syst, 2020, 31: 1060-1065 CrossRef Google Scholar

[15] Zhong J, Li B, Liu Y. Output feedback stabilizer design of Boolean networks based on network structure. Front Inform Technol Electron Eng, 2020, 21: 247-259 CrossRef Google Scholar

[16] Liu A, Li H. On feedback invariant subspace of Boolean control networks. Sci China Inf Sci, 2020, 63: 229201 CrossRef Google Scholar

[17] Zhu Q, Liu Y, Lu J. Observability of Boolean control networks. Sci China Inf Sci, 2018, 61: 092201 CrossRef Google Scholar

[18] Liu H, Liu Y, Li Y. Observability of Boolean networks via STP and graph methods. 22 CrossRef Google Scholar

[19] Chen H, Liang J, Huang T. Synchronization of Arbitrarily Switched Boolean Networks. IEEE Trans Neural Netw Learning Syst, 2017, 28: 612-619 CrossRef Google Scholar

[20] Zhao J, Chen Z, Liu Z. Modeling and analysis of colored petri net based on the semi-tensor product of matrices. Sci China Inf Sci, 2018, 61: 010205 CrossRef Google Scholar

[21] Li H, Wang Y. Boolean derivative calculation with application to fault detection of combinational circuits via the semi-tensor product method. Automatica, 2012, 48: 688-693 CrossRef Google Scholar

[22] Li H, Zhao G, Meng M. A survey on applications of semi-tensor product method in engineering. Sci China Inf Sci, 2018, 61: 010202 CrossRef Google Scholar

[23] Liu Z, Wang Y, Cheng D. Nonsingularity of feedback shift registers. Automatica, 2015, 55: 247-253 CrossRef Google Scholar

[24] Zhong J, Lin D. Stability of nonlinear feedback shift registers. Sci China Inf Sci, 2016, 59: 1-12 CrossRef Google Scholar

[25] Li B, Lu J. Boolean-network-based approach for construction of filter generators. Sci China Inf Sci, 2020, 63: 212206 CrossRef Google Scholar

[26] Lu J, Li M, Liu Y. Nonsingularity of Grain-like cascade FSRs via semi-tensor product. Sci China Inf Sci, 2018, 61: 010204 CrossRef Google Scholar

[27] Dubrova E. Finding Matching Initial States for Equivalent NLFSRs in the Fibonacci and the Galois Configurations. IEEE Trans Inform Theor, 2010, 56: 2961-2966 CrossRef Google Scholar

[28] Lu J, Li M, Huang T. The transformation between the Galois NLFSRs and the Fibonacci NLFSRs via semi-tensor product of matrices. Automatica, 2018, 96: 393-397 CrossRef Google Scholar

[29] Hu H, Gong G. PERIODS ON TWO KINDS OF NONLINEAR FEEDBACK SHIFT REGISTERS WITH TIME VARYING FEEDBACK FUNCTIONS. Int J Found Comput Sci, 2011, 22: 1317-1329 CrossRef Google Scholar

[30] Zhong J, Lin D. On Minimum Period of Nonlinear Feedback Shift Registers in Grain-Like Structure. IEEE Trans Inform Theor, 2018, 64: 6429-6442 CrossRef Google Scholar

[31] Golomb S. Shift Register Sequences. Aegean Park Press, 1982. Google Scholar

[32] Mowle F J. J ACM, 1967, 14: 529-542 CrossRef Google Scholar

  • Figure 1

    The state transition graph $T(V,~E)$ of system (9), where each $4$-tuple represents a state $(x_{1},~x_{2},~x_{3},~x_{4})^{\rm~T}$.

  • Figure 2

    The $PT(V,~E')$ of a $4$-stage monotonous FSR, where each $4$-tuple represents a state $(x_{1},~x_{2},~x_{3},~x_{4})^{\rm~T}$. A node with an arrow in a solid line (or two arraws in dotted lines) represents that it has one successor (or two potential successors).

  • Figure 3

    The $PT(V,~E')$ of a $4$-stage monotonous FSR after deleting some edges based on Lemma 3.16, where each $4$-tuple represents a state $(x_{1},~x_{2},~x_{3},~x_{4})^{\rm~T}$, and the dashed line with a “$\times$” means the path has been deleted.

  • Figure 4

    The pseudo-state transition graph of a $5$-stage monotonous FSR, where each $5$-tuple represents a state $(x_{1},~x_{2},~x_{3},$ $x_{4},~x_{5})^{\rm~T}$.

  • Figure 5

    The $PT(V,~E')$ of a $5$-stage monotonous FSR by deleting some edges based on Theorem 3.20, where each $5$-tuple represents a state $(x_{1},~x_{2},~x_{3},~x_{4},~x_{5})^{\rm~T}$, and the dashed line with a “$\times$” means the path has been deleted.

  •   

    Algorithm 1 Find all the states in set $\mathcal~{S}_{2}$ that can reach $\mathcal~{S}_{1}$.

    Initial set $\mathcal~{S}_{1}=\{\delta_{2^{n}}^{2^{n-1}+1},~\delta_{2^{n}}^{2^{n-1}+2},\ldots,~\delta_{2^{n}}^{2^{n-1}+2^{n-2}}\}$;

    for $i=2^{n-1}+1$ to $2^{n-1}+2^{n-2}$

    $x=i$, $F_{i}=\emptyset$;

    $F_{i}=F_{i}\cup{\delta_{2^{n}}^{x}}$;

    while $(x<~2^{n})\wedge$ ($x$ is even) do

    $x=\frac{x}{2}+2^{n-1}$;

    $F_{i}\leftarrow~\delta_{2^{n}}^{x}$;

    end while

    Output $F_{i}$;

    end for

qqqq

Contact and support