计算p^n-周期二元序列的最小错线性复杂度新算法

传统的计算序列k-错线性复杂度的算法，每一步都要计算和存储序列改变的代价，基于节省计算量和存储空间的考虑，提出了一种计算周期为pn的二元序列的最小错线性复杂度的新算法，其中p为素数，2为模p2的一个本原根。新算法省去了序列代价的存储和计算，主要研究在k为最小错，即使得序列线性复杂度第一次下降的k值时，序列线性复杂度的计算方法，给出了理论证明，并用穷举法与传统算法对序列的计算结果进行了比对。结果完全一致且比传统算法节省了一半以上的存储空间和计算时间，是一种有效的研究特殊周期序列稳定性的计算方法。

New algorithm for computing minerror linear complexity of p~n-periodic binary sequences

The cost of a sequence must be calculated and stored in each step by using a classical k-error linear complexity algorithm. If only considering the first drop of its linear complexity namely the minerror linear complexity, a lot of calculation and memory space could be saved. A new algorithm for computing the minerror linear complexity of pn-periodic binary sequences was proposed in this paper. Here p is an odd prime, and 2 is a primitive root (module p2). The new algorithm eliminated the storage and computation of the cost of a sequence, focused on the method of calculation of the linear complexity when k was the minerror which made the first drop of its linear complexity. Besides, theoretical proof was given. Although the new algorithm saved more than half of the storage space and computation time, the results were totally same as the classical algorithm. It is an effective algorithm on the research of sequence's stability.