若干二元周期序列的紧错线性复杂度

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (10): 49-53.

若干二元周期序列的紧错线性复杂度

周建钦1，2，上官成2，赵泽茂1

1.杭州电子科技大学通信工程学院，杭州 310018
2.安徽工业大学计算机学院，安徽马鞍山 243002

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-04-01 发布日期:2011-04-01

Tight error linear complexity of periodic binary sequences

ZHOU Jianqin1，2，SHANGGUAN Cheng2，ZHAO Zemao1

1.Telecommunication School，Hangzhou Dianzi University，Hangzhou 310018，China
2.Computer Science School，Anhui University of Technology，Maanshan，Anhui 243002，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-04-01 Published:2011-04-01

摘要/Abstract

摘要： 综合线性复杂度、k错线性复杂度、k错线性复杂度曲线和最小错误minerror（S）的概念，提出m紧错线性复杂度的概念。序列S的m紧错线性复杂度是一个二元组（km，LCm）。序列S的k错线性复杂度曲线的第m个跃变点对应的km值和对应km错线性复杂度LCm，称为序列S的m紧错线性复杂度。通过使用简洁的cost二维结构，给出了周期为2n的二元序列的紧错线性复杂度算法，并证明具有Stamp-Martin模式的线性复杂度算法均可以简单地推广为求紧错线性复杂度的算法。与现有k错线性复杂度算法不同，该算法中省去了原来序列元素的运算。在王-张-肖算法基础上，通过使用cost二维结构，给出了周期为pn的二元序列的紧错线性复杂度算法，其中p是一个素数，2是一个模p2的本原根。

关键词: 周期序列, 线性复杂度, k错线性复杂度, m紧错线性复杂度

Abstract: Based on the earlier notions of linear complexity，k-error linear complexity，k-error linear complexity profile and minerror，the concept of m-tight error linear complexity is presented to study the stability of the linear complexity of sequences.The m-tight error linear complexity of sequence S is defined as a two tuple （km，LCm），which is the m-th jump point of the k-error linear complexity profile of sequence S.An algorithm is given for the m-tight error linear complexity of binary
sequences with period 2n by using the modified cost different from that used in the Stamp-Martin algorithm.The new algorithm is free of computations relating the sequence elements.Based on the Wang-Zhang-Xiao algorithm，an efficient algorithm for computing m-tight error linear complexity of binary sequences with period pn is given，where p is a prime and 2 is a primitive root modulus p2.

Key words: periodic sequence, linear complexity, k-error linear complexity, m-tight error linear complexity

周建钦1，2，上官成2，赵泽茂1. 若干二元周期序列的紧错线性复杂度[J]. 计算机工程与应用, 2011, 47(10): 49-53.

ZHOU Jianqin1，2，SHANGGUAN Cheng2，ZHAO Zemao1. Tight error linear complexity of periodic binary sequences[J]. Computer Engineering and Applications, 2011, 47(10): 49-53.

[1]	王锦玲，邹慧仙. 关于[m-]序列模加实现的自缩序列[J]. 计算机工程与应用, 2015, 51(19): 110-113.
[2]	马陵勇¹，魏仕民². 特殊周期序列k-错线性复杂度曲线的快速算法[J]. 计算机工程与应用, 2011, 47(5): 80-82.
[3]	王锦玲，陈亚华，兰娟丽. 扩展在上GF（3）新型自缩序列模型及研究[J]. 计算机工程与应用, 2009, 45(35): 114-119.
[4]	傅赛虹,游林. 修正de Bruijn序列的线性复杂度研究[J]. 计算机工程与应用, 2009, 45(15): 58-60.
[5]	刘古胜. 一类具有低相关特性和较大线性复杂度的序列集[J]. 计算机工程与应用, 2008, 44(12): 63-65.