توزیع پیچیدگی خطی واریانس 4
Abstract
1-Introduction
2-The main idea of the proposed structural method
3-Calculating Formulas for the 4-Variance Linear Complicacy
4-Conclusions
References
Abstract
In this paper, the method of calculating the k-variance linear complexity distribution with 2n-periodical sequences by the Games-Chan algorithm and sieve approach is affirmed for its generality. The main idea of this method is to decompose a binary sequence into some subsequences of critical requirements, hence the issue to find k-variance linear complexity distribution with 2n-periodical sequences becomes a combinatorial problem of these binary subsequences. As a result, we compute the whole calculating formulas on the k-variance linear complexity with 2n-periodical sequences of linear complexity less than 2n for k = 4, 5. With combination of results in the whole calculating formulas on the 3-variance linear complexity with 2n-periodical binary sequences of linear complexity 2n, we completely solve the problem of the calculating function distributions of 4-variance linear complexity with 2n-periodical sequences elegantly, which significantly improves the results in the relating references.
Introduction
The weight complicacy, as a measure on the linear complicacy of periodical series, was first presented in 1990 [1]. An advanced complicated method, where called as sphere complicacy, was presented by Ding, Xiao and Shan in 1991 [2]. Stamp and Martin [14] defined the k-variance linear complicacy, which is almost the same as the sphere complicacy. Precisely, suppose that s is a periodic series of period N. For any k(0 ≤ k ≤ N ), the k-variance linear complicacy Lk (s) of periodic series s is calculated as the shortest linear complicacy that can be reached when any k or fewer elements of the periodic series are altered in one period. Rueppel [13] obtained the account of 2n -periodical series with fixed linear complicacy L, 0 ≤ L ≤ 2n . When k = 1 and k = 2, Meidl [12] derived the whole calculating formulas on the k-variance linear complicacy with 2n -periodical series with linear complicacy 2n . When k = 2 and k = 3, Zhu and Qi [17] further characterized the whole calculating formulas on the k-variance linear complicacy with 2n – periodical series with linear complicacy 2n − 1.