On the 2-adic complexity and the κ-error 2-adic complexity of periodic binary sequences

被引：15
|
作者：
Hu, Honggang [1 ]
Feng, Dengguo [1 ]
机构：
[1] Chinese Acad Sci, Inst Software, State Key Lab Informat Secur, Beijing 100080, Peoples R China
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2008年 / 54卷 / 02期
基金：
加拿大自然科学与工程研究理事会;
关键词：
2-adic complexity; expected value; k-error 2-adic complexity; k-error symmetric 2-adic complexity; l-sequence; periodic binary sequence; symmetric 2-adic complexity; variance;
D O I：
10.1109/TIT.2007.913238
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
A significant difference between the linear complexity and the 2-adic complexity of periodic binary sequences is pointed out in this correspondence. Based on this observation, we present the concept of the symmetric 2-adic complexity of periodic binary sequences. The expected value of the 2-adic complexity is determined, and a lower bound on the expected value of the symmetric 2-adic complexity of periodic binary sequences is derived. We study the variance of the 2-adic complexity of periodic binary sequences, and the exact value for it is given. Because the 2-adic complexity of periodic binary sequences is unstable, we present the concepts of the k-error 2-adic complexity and the k-error symmetric 2-adic complexity, and lower bounds on them are also derived. In particular, we give tighter upper and lower bounds for the minimum 2-adic complexity of I-sequences by substituting two symbols within one period.
引用
收藏
页码：874 / 883
页数：10
相关论文
共 50 条
  • [11] On stability of 2-adic complexity of periodic sequence
    Wang, Lei
    Cai, Mian
    Xiao, Guozhen
    Xi'an Dianzi Keji Daxue Xuebao/Journal of Xidian University, 2000, 27 (03): : 348 - 350
  • [12] ON THE JOINT 2-ADIC COMPLEXITY OF BINARY MULTISEQUENCES
    Zhao, Lu
    Wen, Qiao-Yan
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2012, 46 (03): : 401 - 412
  • [13] The 2-adic complexity and the 1-error 2-adic complexity of single cycle T-functions
    You, Wei
    Qi, Wen-Feng
    Tongxin Xuebao/Journal on Communications, 2014, 35 (03): : 135 - 139
  • [14] The 2-adic complexity of a class of binary sequences with optimal autocorrelation magnitude
    Yuhua Sun
    Tongjiang Yan
    Zhixiong Chen
    Lianhai Wang
    Cryptography and Communications, 2020, 12 : 675 - 683
  • [15] On the 2-Adic Complexity of the Ding-Helleseth-Martinsen Binary Sequences
    Zhang, Lulu
    Zhang, Jun
    Yang, Minghui
    Feng, Keqin
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (07) : 4613 - 4620
  • [16] The 2-adic complexity of a class of binary sequences with optimal autocorrelation magnitude
    Sun, Yuhua
    Yan, Tongjiang
    Chen, Zhixiong
    Wang, Lianhai
    CRYPTOGRAPHY AND COMMUNICATIONS-DISCRETE-STRUCTURES BOOLEAN FUNCTIONS AND SEQUENCES, 2020, 12 (04): : 675 - 683
  • [17] 2-Adic Complexity of Two Classes of Generalized Cyclotomic Binary Sequences
    Xiao, Zibi
    Zeng, Xiangyong
    Sun, Zhimin
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2016, 27 (07) : 879 - 893
  • [18] Linear complexity and 2-adic complexity of binary interleaved sequences with optimal autocorrelation magnitude
    Wang, Yan
    Cao, Ying
    Heng, Ziling
    Wang, Weiqiong
    AIMS MATHEMATICS, 2022, 7 (08): : 13790 - 13802
  • [19] On the expected value of the joint 2-adic complexity of periodic binary multisequences
    Hu, Honggang
    Hu, Lei
    Feng, Dengguo
    SEQUENCES AND THEIR APPLICATIONS - SETA 2006, 2006, 4086 : 199 - 208
  • [20] 2-adic complexity of SLCE sequence
    Wang Y.
    Li S.
    Xue G.
    Tongxin Xuebao/Journal on Communications, 2019, 40 (08): : 151 - 156
12345