具有2^n线性复杂度的2^n周期二元序列的3错线性复杂度  

On the 3-Error Linear Complexity of 2^n-Periodic Binary Sequences with Linear Complexity 2~n

作　　者：周建钦[1,2] 

机构地区：[1]杭州电子科技大学通信工程学院,杭州310018 [2]安徽工业大学计算机学院,马鞍山243002

出　　处：《应用数学学报》2013年第3期399-413,共15页Acta Mathematicae Applicatae Sinica

基　　金：浙江省自然科学基金(Y1100318);安徽省自然科学基金(1208085MF106)资助项目

摘　　要：线性复杂度和k错线性复杂度是度量密钥流序列的密码强度的重要指标.通过研究周期为2＂的二元序列线性复杂度,提出将k错线性复杂度的计算转化为求Hamming重量最小的错误序列.基于Games-Chan算法,讨论了线性复杂度为2^n的2^n周期二元序列的3错线性复杂度分布情况;给出了对应k错线性复杂度序列的完整计数公式,k=3,4.对于一般的线性复杂度为2^n-m的2^n周期二元序列,也可以使用该方法给出对应k错线性复杂度序列的计数公式.The linear complexity and the k-error linear complexity of a sequence have been used as important measures of keystream sequence strength. By studying linear complex-ity of binary sequences with period 2^n, it is proposed that the computing of k-error linear complexity should be converted to finding error sequences with minimal Hamming weight. Based on Games-Chart algorithm, 3-error linear complexity distribution of 2^n-periodic bi-nary sequences with linear complexity 2^n is discussed. For k = 3, 4, the complete counting functions on the k-error linear complexity of 2^n-periodic binary sequences with linear com-plexity 2^n are derived. Based on those results, the counting functions for the number of all 2^n-periodic binary sequences with given 3-error linear complexity can be obtained. Gener-ally, the complete counting functions on the k-error linear complexity of 2^n-periodic binary sequences with linear complexity 2^n - m can be obtained using a similar approach.

关 键 词：周期序列 线性复杂度 K错线性复杂度 k错线性复杂度分布 

分 类 号：TN911[电子电信—通信与信息系统] TN918.1[电子电信—信息与通信工程]