【摘要】 k 错复杂度是指改变序列一个周期段中k个或少于k个符号后所得到的序列的最小线性复杂度,k 错复杂度曲线即为该序列的k 错复杂度序列,该指标完全反映了当序列改变的比特数目不断增加时线性复杂度的变化情况.文中给出了一个确定周期为pn的q元周期序列k 错复杂度曲线的算法,这里p,q为奇素数,并且q是模p2的一个本原根.该算法分别推广了肖 魏 林等人计算q元pn周期序列线性复杂度和魏 董 肖计算q元pn周期序列k 错复杂度的算法.采用文中的算法计算q元pn周期序列的k 错复杂度曲线至多需要Θ(2n+1)步运算.更多还原

【Abstract】 The k-error linear complexity of a periodic sequence is defined as the smallest linear complexity that can be obtained by changing k or fewer bits of the sequence per period. k-error linear complexity profile of a sequence is the ordered list of k-error linear complexities. The index reveals how the linear complexity of the sequence varies as an increasing number of the bits of the sequence are changed. A fast algorithm is presented for determining k-error linear complexity profile of a q-ary sequence with a period pⁿ, where p, q is an odd prime and q is a primitive root modulo p². The algorithm generalizes both the Xiao, Wei, Lam, Imamura and Wei, Dong, Xiao algorithms, which compute the linear complexity and k-error linear complexity of a q-ary sequence of a period pⁿ, respectively. The algorithm we present computes the k-error linear complexity profile for the q-ary sequence of a period pⁿ using at most Θ(2ⁿ⁺¹) steps.更多还原