{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,5]],"date-time":"2026-07-05T00:24:00Z","timestamp":1783211040162,"version":"3.54.6"},"reference-count":28,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T00:00:00Z","timestamp":1427846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Pseudorandom binary sequences have important uses in many fields, such as spread spectrum communications, statistical sampling and cryptography. There are two kinds of method in evaluating the properties of sequences, one is based on the probability measure, and the other is based on the deterministic complexity measures. However, the relationship between these two methods still remains an interesting open problem. In this paper, we mainly focus on the widely used nonlinear complexity of random sequences, study on its distribution, expectation and variance of memoryless sources. Furthermore, the relationship between nonlinear complexity and Shannon\u2019s entropy is also established here. The results show that the Shannon\u2019s entropy is strictly monotonically decreased with nonlinear complexity.<\/jats:p>","DOI":"10.3390\/e17041936","type":"journal-article","created":{"date-parts":[[2015,4,7]],"date-time":"2015-04-07T03:47:46Z","timestamp":1428378466000},"page":"1936-1945","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["On Nonlinear Complexity and Shannon\u2019s Entropy of Finite Length Random Sequences"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0298-0191","authenticated-orcid":false,"given":"Lingfeng","family":"Liu","sequence":"first","affiliation":[{"name":"School of Software, Nanchang University, Nanchang 330031, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Suoxia","family":"Miao","sequence":"additional","affiliation":[{"name":"Faculty of Science, Nanchang Institute of Technology, Nanchang 330099, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bocheng","family":"Liu","sequence":"additional","affiliation":[{"name":"School of Software, Nanchang University, Nanchang 330031, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2015,4,1]]},"reference":[{"key":"ref_1","unstructured":"Kalouptsidis, N. (1996). Signal Processing Systems: Theory and Design, Wiley."},{"key":"ref_2","unstructured":"Golomb, S.W. (1967). Shift Register Sequences, Holden-Day."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1016\/j.ins.2012.09.037","article-title":"Secure chaotic system with application to chaotic ciphers","volume":"221","author":"Wang","year":"2013","journal-title":"Inf. Sci."},{"key":"ref_4","unstructured":"Menezes, A.J., van Oorschot, P.C., and Vanstone, S.A. (1996). Handbook of applied cryptography, CRC Press."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1109\/81.915385","article-title":"Chaos-based random number generators-part I: Analysis [cryptography]","volume":"48","author":"Stojanovski","year":"2001","journal-title":"IEEE Trans. Circ. Syst. I"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1109\/TSP.2004.839924","article-title":"Embeddable ADC-based true random number generator for cryptographic applications exploiting nonlinear signal processing and chaos","volume":"53","author":"Callegari","year":"2005","journal-title":"IEEE Trans. Signal Process."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1109\/TCSI.2005.856670","article-title":"A feedback strategy to improve the entropy of a chaos-based random bit generator","volume":"53","author":"Addabbo","year":"2006","journal-title":"IEEE Trans. Circ. Syst. I"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s10470-012-9893-9","article-title":"Discrete-time chaotic-map truly random number generators: Design, implementation and variability analysis of the zigzag map","volume":"73","author":"Nejati","year":"2012","journal-title":"Analog Integr. Circuits Signal Process."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1537","DOI":"10.1049\/el.2012.2762","article-title":"Zigzag map: A variability-aware discrete-time chaotic map truly random number generator","volume":"48","author":"Beirami","year":"2012","journal-title":"Electron. Lett."},{"key":"ref_10","unstructured":"Shannon, C.E., and Weaver, W. (1949). The Mathematical Theory of Communication, University of Illinois Press."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1109\/18.567654","article-title":"Statistics of chaotic binary sequences","volume":"43","author":"Kohda","year":"1997","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1111\/1467-9892.00180","article-title":"Correlational properties of Chebyshev chaotic sequences","volume":"21","author":"Kodha","year":"2000","journal-title":"J. Time Ser. Anal."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1109\/18.661497","article-title":"Source codes as random number generators","volume":"44","author":"Visweswariah","year":"1998","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_14","first-page":"446","article-title":"A framework for investigating the performance of chaotic-map truly random number generators","volume":"60","author":"Beirami","year":"2013","journal-title":"IEEE Trans. Circ. Syst. II"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Beirami, A., Nejati, H., and Callegari, S. (2014, January 1\u20133). Fundamental performance limits of chaotic-map random number generators. Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2014.7028581"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1109\/TIT.1969.1054260","article-title":"Shift register synthesis and BCH decoding","volume":"15","author":"Massey","year":"1969","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Limniotis, K., Kolokotronis, N., and Kalouptsidis, N. (2006, January 9\u201314). New results on the linear complexity of binary sequences. Seattle, WA, USA.","DOI":"10.1109\/ISIT.2006.261900"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1023\/A:1008295603824","article-title":"An approximate distribution for the maximum order complexity","volume":"10","author":"Erdmann","year":"1997","journal-title":"Des. Codes Cryptogr."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1555","DOI":"10.1109\/TIT.2005.844090","article-title":"Results on the nonlinear span of binary sequences","volume":"51","author":"Rizomiliotis","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","article-title":"On the complexity of finite sequences","volume":"22","author":"Lempel","year":"1976","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_22","unstructured":"Hamano, K., and Yamamoto, H. (July, January 28). A differential equation method to derive the formulas of the T-complexity and the LZ-complexity. Seoul, Korea."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Davies, D.W. (1991). Advances in Cryptology\u2014Eurocrypt\u201991, Springer.","DOI":"10.1007\/3-540-46416-6"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"6696","DOI":"10.1109\/TIT.2014.2343225","article-title":"Sequences with high nonlinear complexity","volume":"60","author":"Niederreiter","year":"2014","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"4293","DOI":"10.1109\/TIT.2007.907442","article-title":"On the nonlinear complexity and Lempel-Ziv complexity of finite length sequences","volume":"53","author":"Limniotis","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Brassard, G. (1990). Advances Cryptology\u2014CRYPTO\u201989, Springer.","DOI":"10.1007\/0-387-34805-0"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1142\/S0219493701000047","article-title":"Partition-based entropies of deterministic and stochastic maps","volume":"1","author":"Ebeling","year":"2001","journal-title":"Stoch. Dyn."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Liu, L.F., Miao, S.X., Hu, H.P., and Deng, Y.S. (2014). On the eigenvalue and Shannon\u2019s entropy of finite length random sequences. Complexity.","DOI":"10.1002\/cplx.21587"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/17\/4\/1936\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:44:14Z","timestamp":1760215454000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/17\/4\/1936"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,1]]},"references-count":28,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2015,4]]}},"alternative-id":["e17041936"],"URL":"https:\/\/doi.org\/10.3390\/e17041936","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,1]]}}}