Study On Error Linear Complexity Distribution Of Periodic Sequence

The linear complexity, the k-error linear complexity and m-tight error linear complexity ofa sequence have been used as important measures of keystream sequence strength and stability.This dissertation using the theories of linear complexity, k-error linear complexity, k-error linearcomplexity profile, the minimum error of sequence and m-tight error linear complexity, thestability of the linear complexity is studied. By studying linear complexity of periodic sequences,it is proposed that the computation of k-error linear complexity should be converted to findingerror sequences with minimal Hamming weight.The k-error linear complexity distribution ofthese periodic sequences is discussed.The main results are as follows:1. The new structure of the algorithm is given for computing the k-error linear complexity of2pn-periodc binary sequences, where p is a prime and2is a primitive root modulo p2.2. An efficient algorithm is invented for computing m-tight error linear complexity of binarysequences with period2pnby utilizing joint cost, where p is a prime and2is a primitive rootmodulo p2.3. Based on Games-Chan algorithm,4-error linear complexity distribution of2n-periodicbinary sequences with linear complexity2n-9is discussed. And the complete countingfunctions on the4-error linear complexity of2n-periodic binary sequences with linearcomplexity2n-9is presented.4. The distribution of the k-error linear complexity of2n-periodic binary sequences with linearcomplexity2nis discussed. The upper and lower bounds of the expectation of the k-errorlinear complexity of these periodic sequences are presented. Moreover, the conclusion hereis the generalization of one of the main results in the bibliography.5. By studying the distribution of the k-error linear complexity of2n-periodic binary sequenceswith linear complexity less than2n, the upper and lower bounds of the expectation of the k-error linear complexity of these periodic sequences are derived.