Vladimir Edemskiy, Aleksey Minin



About the Linear Complexity of the Almost Perfect Sequences

pdf PDF


We calculate the linear complexity of almost perfect binary sequences. Also we study the linear complexity of binary sequences obtained from series of almost perfect ternary sequences and the ternary sequences with two nonzero autocorrelation sidelobe levels.


linear complexity, almost perfect sequences


[1] K.T. Arasu, S.L. Ma, N.J. Voss, On a class of almost perfect sequences, J. Algebra, 192, 1997, pp. 47–56.

[2] T.W. Cusick, C. Ding, A. Renvall. Stream Ciphers and Number Theory, North-Holland Publishing Co., Amsterdam 1998

[3] S.W. Golomb, G. Gong. Signal Design for Good Correlation: For Wireless Communications, Cryptography and Radar Applications. Cambridge University Press 2005

[4] M. Hall, Combinatorial Theory, Wiley, New York 1975

[5] D. Jungnickel, A. Pott, Perfect and almost perfect sequences, Discrete Applied Mathematics, 95, 1999, pp. 331–359.

[6] E.I. Krengel, Almost-perfect and odd-perfect ternary sequences, Proc. 2004 Inter. Conf. on Sequences and Their Applications (SETA ’04), Seoul, Korea, LNCS 3486, Springer-Verlag Berlin, 2005, pp.197-207.

[7] E.I. Krengel, A method of construction of perfect sequences, Radiotehnika, 11, 2009, pp. 15– 21 (in Russian).

[8] E.I. Krengel, P.V. Ivanov, New terhary sequences with two nonzero autocorrelation sidelobe levels and peak factor close to unity, DSPA- 2016 (in Russian).

[9] Ph. Langevin, Some sequences with good autocorrelation properties, Finite Fields, 168, 1994, pp. 175-185.

[10] Ph. Langevin, Almost perfect binary function, Applicable Algebra in Engineering, Communication and Computing, 4, 1993, pp.95–102.

[11] K.H. Leung, S. Ling, S.L. Ma, K.B. Tay, Almost perfect sequences with θ = 2, Arch. Math., 70, 1998, pp. 128–131.

[12] A. Pott, S. Bradley, Existence and nonexistence of almost-perfect autocorrelation sequences, IEEE Trans. Inf. Theory, IT-41 (1), 1995, pp. 301–304.

[13] Wolfmann J. Almost perfect autocorrelation sequences, IEEE Trans. Inf. Theory, IT-38 (4), 1992, pp. 1412–1418.

[14] H. D. Schotten, H. D. Luke, New perfect and w-cyclic-perfect sequences, IEEE International Symposium on Information Theory, 12, 1996, pp. 82–85

[15] Q. Wang, X.N. Du, The linear complexity of binary sequences with optimal autocorrelation, IEEE Trans. Inf. Theory, 56 (12), 2010, pp. 6388–6397

Cite this paper

Vladimir Edemskiy, Aleksey Minin. (2016) About the Linear Complexity of the Almost Perfect Sequences. International Journal of Communications, 1, 223-226


Copyright © 2017 Author(s) retain the copyright of this article.
This article is published under the terms of the Creative Commons Attribution License 4.0