Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Cryptography and Communications
Published in: Cryptography and Communications 4/2019

31-08-2018

Binary sequences with period N and nonlinear complexity N − 2

Authors: Zibi Xiao, Xiangyong Zeng, Chaoyun Li, Yupeng Jiang

Published in: Cryptography and Communications | Issue 4/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, periodic sequences with period N and nonlinear complexity N − 2 are investigated. A necessary and sufficient condition for characterizing such sequences is established, and a recursive method is proposed to generate all possible binary sequences with period N and nonlinear complexity N − 2. The exact number of such sequences is also determined.
previous article On self-dual and LCD quasi-twisted codes of index two over a special chain ring
next article Deterministic constructions of compressed sensing matrices based on codes

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Literature
1.
Chan, A.H., Games, R.A.: On the quadratic spans of DeBruijn sequences. IEEE Trans. Inf. Theory 36(4), 822–829 (1990)CrossRefMATH
2.
3.
Ding, C., Helleseth, T., Shan, W.: On the linear complexity of Legendre sequences. IEEE Trans. Inf. Theory 44(3), 1276–1278 (1998)MathSciNetCrossRefMATH
4.
Erdmann, D., Murphy, S.: An approximate distribution for the maximum order complexity. Des. Codes Cryptogr. 10(3), 325–339 (1997)MathSciNetCrossRefMATH
5.
Jansen, C.J.A.: Investigations on nonlinear streamcipher systems: Construction and evaluation methods, Ph.D dissertation (1989)
6.
Jansen, C.J.A., Boekee, D.E.: The shortest feedback shift register that can generate a given sequence. In: Brassard, G (ed.) Advances in Cryptology-CRYPTO’89, Lecture Notes in Computer Science, vol. 435, pp. 90–99. Springer-Verlag, New York (1989)
7.
Kim, J.H., Song, H.Y.: On the linear complexity of Hall’s sextic residue sequences. IEEE Trans. Inf. Theory 47(5), 2094–2096 (2001)MathSciNetCrossRefMATH
8.
Kolokotronis, N., Kalouptsidis, N.: On the linear complexity of nonlinear filtered PN-sequences. IEEE Trans. Inf. Theory 49(11), 3047–3059 (2003)CrossRefMATH
9.
Lam, C., Gong, G.: A lower bound for the linear span of filtering sequences. In State of the Art of Stream Ciphers (SASC), pp. 220–233 (2004)
10.
Li, N., Tang, X.: On the linear complexity of binary sequences of period 4N with optimal autocorrelation value/magnitude. IEEE Trans. Inf. Theory 57(11), 7597–7604 (2011)MathSciNetCrossRefMATH
11.
Limniotis, K., Kolokotronis, N., Kalouptsidis, N.: On the nonlinear complexity and Lempel-Ziv complexity of finite length sequences. IEEE Trans. Inf. Theory 53(11), 4293–4302 (2007)MathSciNetCrossRefMATH
12.
Luo, Y., Xing, C., You, L.: Construction of sequences with high nonlinear complexity from function fields. IEEE Trans. Inf. Theory 63(12), 7646–7650 (2017)MathSciNetCrossRefMATH
13.
Menezes, A.J., Van Oorschot, P.C., Vanstone, S.A.: Handbook of Applied Cryptography. CRC Press (1996)
14.
Niederreiter, H.: Linear complexity and related complexity measures for sequences. In: Johansson, T., Maitra, S. (eds.) International Conference on Cryptology in India, INDOCRYPT 2003. Lecture Notes in Computer Science, vol. 2904, pp. 1–17. Springer, Berlin (2003)
15.
16.
Paterson, K.G.: Root counting, the DFT and the DFT and the linear complexity of nonlinear filtering. Des. Codes Cryptogr. 14(3), 247–259 (1998)MathSciNetCrossRefMATH
17.
Petrides, G., Mykkeltveit, J.: Composition of recursions and nonlinear complexity of periodic binary sequences. Des. Codes Cryptogr. 49(1), 251–264 (2008)MathSciNetCrossRefMATH
18.
Rizomiliotis, P., Kalouptsidis, N.: Results on the nonlinear span of binary sequences. IEEE Trans. Inf. Theory 51(4), 1555–1563 (2005)MathSciNetCrossRefMATH
19.
Rizomiliotis, P., Kolokotronis, N., Kalouptsidis, N.: On the quadratic span of binary sequences. IEEE Trans. Inf. Theory 51(5), 1840–1848 (2005)MathSciNetCrossRefMATH
20.
Rizomiliotis, P.: Constructing periodic binary sequences with maximum nonlinear span. IEEE Trans. Inf. Theory 52(9), 4257–4261 (2006)MathSciNetCrossRefMATH
21.
Sun, Z., Zeng, X., Li, C., Helleseth, T.: Investigations on periodic sequences with maximum nonlinear complexity. IEEE Trans. Inf. Theory 63(10), 6188–6198 (2017)MathSciNetCrossRefMATH
Metadata
Title
Binary sequences with period N and nonlinear complexity N − 2
Authors
Zibi Xiao
Xiangyong Zeng
Chaoyun Li
Yupeng Jiang
Publication date
31-08-2018
Publisher
Springer US
Published in
Cryptography and Communications / Issue 4/2019
Print ISSN: 1936-2447
Electronic ISSN: 1936-2455
DOI
https://doi.org/10.1007/s12095-018-0324-3

Other articles of this Issue 4/2019

Cryptography and Communications 4/2019 Go to the issue

OriginalPaper

Results on symmetric S-boxes constructed by concatenation of RSSBs

OriginalPaper

Frequency-hopping sequence sets with good aperiodic Hamming correlation property

OriginalPaper

Two constructions of asymptotically optimal codebooks

OriginalPaper

Binary linear complementary dual codes

OriginalPaper

Periodic state-space representations of periodic convolutional codes

OriginalPaper

Complete weight enumerators of a class of two-weight linear codes

Premium Partner

    Image Credits