2^n周期平衡二元序列的2错线性复杂度

On the 2-error linear complexity of 2n-periodic balanced binary sequences

线性复杂度和k错线性复杂度是度量密钥流序列的密码强度的重要指标。Meidl给出奇数个非零元素的2n周期二元序列的1错线性复杂度分布情况。基于Games-Chan算法,文中讨论了更为重要的偶数个非零元素的2n周期二元序列的2错线性复杂度分布情况。给出了对应k错线性复杂度序列的完整计数公式,k=2,3。对于一般的2n周期二元序列,也可以使用该方法给出对应k(k>2)错线性复杂度序列的计数公式。

Linear complexity and k-error linear complexity of a sequence are important measures of key stream sequence strength. After studying linear complexity of binary sequences with period 2n, it is proposed that the computation of k-error linear complexity should be converted to finding error sequences with minimal Hamming weight. Based on Games-Chan algorithm, 2-error linear complexity distribution of 2n-periodic balanced binary sequences is discussed. For k=2,3, the complete counting functions on the k-error linear complexity of 2n-periodic binary sequences are presented. It is concluded that for k〉2, the complete counting functions on the k-error linear complexity of 2~periodic binary sequences can be obtained with the similar approach.