Abstract
The linear complexity is an important and frequently used measure of unpredictably and pseudorandomness of binary sequences. In Part I of this paper, we extended this notion to two dimensions: we defined and studied the linear complexity of binary and bit lattices. In this paper, first we will estimate the linear complexity of a truly random bit (M,N)-lattice. Next we will extend the notion of k-error linear complexity to bit lattices. Finally, we will present another alternative definition of linear complexity of bit lattices.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aly, H., Meidl, W., Winterhof, A.: On the k-error linear complexity of cyclomatic sequences. J. Math. Cryptol. 1, 283–296 (2007)
Gyarmati, K., Mauduit, C., Sárközy, A.: On the linear complexity of binary lattices. Ramanujan J. (2012) doi:10.1007/s11139-012-9433-3
Gyarmati, K., Mauduit, C., Sárközy, A.: Measures of pseudorandomness of families of binary lattices, I. (Definitions, a construction using quadratic characters). Publ. Math. (Debr.) 79, 445–460 (2011)
Gyarmati, K., Mauduit, C., Sárközy, A.: Measures of pseudorandomness of families of binary lattices, II. (A further construction). Publ. Math. (Debr.) 80, 481–504 (2012)
Gyarmati, K., Mauduit, C., Sárközy, A.: Measures of pseudorandomness of finite binary lattices, III. (Q k , correlation, normality, minimal values). Unif. Distrib. Theory 5, 183–207 (2010)
Hubert, P., Mauduit, C., Sárközy, A.: On pseudorandom binary lattices. Acta Arith. 125, 51–62 (2006)
Landau, E.: Handbuch der Lehre der Verteilung der Primzahlen, I–II, 2nd edn. Chelsea, New York (1953)
Mauduit, C., Sárközy, A.: On finite pseudorandom binary sequences, I. Measure of pseudorandomness, the Legendre symbol. Acta Arith. 82, 365–377 (1997)
Rueppel, R.A.: Linear complexity and random sequences. In: Proc. Advances in Cryptology—EUROCRYPT ’85. LNCS, Linz, Austria, April 9–12, vol. 219, pp. 167–188 (1985)
Stamp, M., Martin, C.F.: An algorithm for the k-error linear complexity of binary sequences with period 2n. IEEE Trans. Inf. Theory 39(4), 1398–1401 (1993)
Wigert, S.: Sur l’ordre de grandeur du nombre des diviseurs d’un entier. In: Arkiv för Matematik, Astronomi Och. Fysik, vol. 3 (1906–1907). 9 p.
Winterhof, A.: Linear complexity and related complexity measures. In: Woungang, I. (ed.) Selected Topics in Information and Coding Theory 7, pp. 3–40. World Scientific, Singapore (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research partially supported by ERC-AdG.228005, Hungarian National Foundation for Scientific Research Grants Nos. K100291 and NK104183, the János Bolyai Research Fellowship, the Agence Nationale de la Recherche grant ANR-10-BLAN 0103 MUNUM and French-Hungarian exchange program TÉT-09-01-2010-0056.
Rights and permissions
About this article
Cite this article
Gyarmati, K., Mauduit, C. & Sárközy, A. On linear complexity of binary lattices, II. Ramanujan J 34, 237–263 (2014). https://doi.org/10.1007/s11139-013-9500-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11139-013-9500-4