×

On stability of multi-valued nonlinear feedback shift registers. (English) Zbl 1421.94033

Summary: 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 stable \(n + 1\)-stage NFSRs from stable \(n\)-stage NFSRs by the properties of \(D\)-morphism.

MSC:

94A55 Shift register sequences and sequences over finite alphabets in information and communication theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Massey, J. L.; Liu, R. W., Application of Lyapunovs direct method to the error-propagation effect in convolutional codes, IEEE Transactions on Information Theory, 10, 3, 248-250 (1964) · Zbl 0119.34202
[2] Mowle, F. J., Relations between \(P_n\) cycles and stable feedback shift registers, IEEE Transactions on Electronic Computers, 15, 375-378 (1966)
[3] Mowle, F. J., Enumeration and classification of stable feedback shift-registers, Tech. Rept. EE-661 (January 1966), Notre Dame, Ind., USA: University of Notre Dame, Notre Dame, Ind., USA
[4] Mowle, F. J., An Algorithm for Generating Stable Feedback Shift Registers of Order \(n\), Journal of the ACM, 14, 3, 529-542 (1967) · Zbl 0241.94024
[5] Zhang, Y., A direct algorithm for synthesis of stable feedback shift registers, International Journal of Electronics, 57, 79-84 (1984)
[6] Lampel, A., On \(k\)-stable feedback shift registers, IEEE Transactions on Computers, 18, 7, 652-660 (1969) · Zbl 0187.13102
[7] Zhong, J.; Lin, D., Linearization of nonlinear filter generators and its application to cryptanalysis of stream ciphers, Journal of Complexity, 35, 29-45 (2016) · Zbl 1342.94103
[8] Zhong, J.; Lin, D., Driven stability of nonlinear feedback shift registers with inputs, IEEE Transactions on Computers, 64, 6, 1-12 (2016)
[9] Zhong, J.; Lin, D., On minimum period of nonlinear feedback shift registers in grain-like structure, IEEE Transactions on Information Theory, 64, 9, 6429-6442 (2018) · Zbl 1401.93068
[10] Kauffman, S. A., Metabolic stability and epigenesis in randomly constructed genetic nets, Journal of Theoretical Biology, 22, 3, 437-467 (1969) · doi:10.1016/0022-5193(69)90015-0
[11] Harris, S. E.; Sawhill, B. K.; Wuensche, A.; Kauffman, S., A model of transcriptional regulatory networks based on biases in the observed regulation rules, Complexity, 7, 4, 23-40 (2002)
[12] Zhu, P.; Han, J., Stochastic multiple-valued gene networks, IEEE Transactions on Biomedical Circuits and Systems, 8, 1, 42-53 (2013)
[13] Zhang, H.; Wang, X.; Lin, X., Synchronization of Boolean networks with different update schemes, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11, 5, 965-972 (2014)
[14] Aldana, M., Boolean dynamics of networks with scale-free topology, Physica D Nonlinear Phenomena, 185, 45-66 (2003) · Zbl 1039.94016
[15] Lizier, J.; Pritam, S.; Prokopenko, M., Information dynamics in small-world Boolean networks, Artificial Life, 17, 4, 293-314 (2011)
[16] Kowshik, H.; Kumar, P. R., Optimal computation of symmetric Boolean functions in collocated networks, IEEE Journal on Selected Areas in Communications, 31, 4, 639-654 (2013)
[17] Cheng, D., Disturbance decoupling of Boolean control networks, IEEE Transactions on Automatic Control, 56, 1, 2-10 (2011) · Zbl 1368.93100 · doi:10.1109/tac.2010.2050161
[18] Hochma, G.; Margaliot, M.; Fornasini, E.; Valcher, M. E., Symbolic dynamics of Boolean control networks, Automatica, 49, 8, 2525-2530 (2013) · Zbl 1364.93380
[19] Li, H.; Wang, Y., Logical matrix factorization with application to topological structure analysis of Boolean network, IEEE Transactions on Automatic Control, 60, 5, 1380-1385 (2015) · Zbl 1360.94478
[20] Lü, Q.; Li, H., Event-triggered discrete-time distributed consensus optimization over time-varying graphs, Complexity, 2017 (2017) · Zbl 1407.90254
[21] Cheng, D.; Qi, H., A linear representation of dynamics of Boolean networks, IEEE Transactions on Automatic Control, 55, 10, 2251-2258 (2010) · Zbl 1368.37025
[22] Liu, Q.; Zeng, Q.; Huang, J.; Li, D., Optimal intervention in semi-markov-based asynchronous probabilistic boolean networks, Complexity, 2018 (2018) · Zbl 1405.92106
[23] Zhu, S.; Lou, J.; Liu, Y.; Li, Y.; Wang, Z., Event-triggered control for the stabilization of probabilistic boolean control networks, Complexity, 2018 (2018) · Zbl 1405.93227
[24] Cheng, D.; Qi, H.; Li, Z., Analysis and Control of Boolean Networks (2011), London, UK: Springer-Verlag, London, UK · Zbl 1209.93001
[25] Li, Z.; Cheng, D., Algebraic approach to dynamics of multi-valued networks, International Journal of Bifurcation and Chaos, 20, 561-582 (2010) · Zbl 1193.94003
[26] Li, F.; Sun, J., Stability and stabilization of multivalued logical networks, Nonlinear Analysis: Real World Applications, 12, 3701-3712 (2011) · Zbl 1231.94083
[27] Luo, C.; Wang, X., Algebraic representation of asynchronous multiple-valued networks and its dynamics, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10, 4, 927-938 (2013)
[28] Yoshioka, D., A construction method of maximum length NFSR sequences based on linear equations, Proceedings of the IEEE 11th International Symposium on Spread Spectrum Techniques and Applications
[29] Fredricksen, H.; Maiorana, J., Necklaces of beads in \(k\) colors and \(k\)-ary de Bruijn sequences, Discrete Mathematics, 23, 3, 207-210 (1978) · Zbl 0384.05004
[30] Etzion, T., An algorithm for constructing \(m\)-ary de Bruijn sequences, Journal of Algorithms, 7, 3, 331-340 (1986) · Zbl 0619.68060
[31] Lai, X., Condition for the nonsingularity of a feedback shiftregister over a general finite field, IEEE Transactions on Information Theory, 33, 747-757 (1987) · Zbl 0633.68040
[32] Qi, H., On shift register via semi-tensor product approach, Proceedings of the 32th Chinese Control Conference
[33] Liu, Z.; Wang, Y.; Zhao, Y., Nonsingularity of feedback shift registers, Automatica, 55, 247-253 (2015) · Zbl 1423.94042
[34] Wang, H.; Zhong, J.; Lin, D., Linearization of multi-valued nonlinear feedback shift registers, Journal of Systems Science and Complexity, 30, 2, 494-509 (2017) · Zbl 1369.94513
[35] Wang, H.; Zhong, J.; Lin, D., Stability of multi-valued nonlinear feedback shift registers, Proceedings of the IEEE International Conference on Information and Automation
[36] Roger, A. H.; Johnson, C. R., Topics in Matrix Analysis (1991), UK: Cambridge University Press, UK · Zbl 0729.15001
[37] Zhang, X.; Yang, Z.; Cao, C., Inequalities involving Khatri-Rao products of positive semi-definite matrices, Applied Mathematics E-Notes, 2 (2002) · Zbl 0998.15026
[38] Lampel, A., On a homomorphism of the de bruijn graph and its applications to the design of feedback shift registers, IEEE Transactions on Computers, 19, 12, 1204-1209 (1970) · Zbl 0225.94028
[39] Li, C.; Zeng, X.; Helleseth, T.; Li, C.; Hu, L., The properties of a class of linear FSRs and their applications to the construction of nonlinear FSRs, IEEE Transactions on Information Theory, 60, 5, 3052-3061 (2014) · Zbl 1360.94281
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.