Asymptotic analysis on the normalized k-error linear complexity of binary sequences

Linear complexity and k-error linear complexity are the important measures for sequences in stream ciphers. This paper discusses the asymptotic behavior of the normalized k-error linear complexity ({L_{n,k}(underline{s})/n}) of random binary sequences ({underline{s}}) , which is based on one of Niederreiter’s open problems. For k = n θ, where 0 ≤ θ ≤ 1/2 is a fixed ratio, the lower and upper bounds on accumulation points of ({L_{n,k}(underline{s})/n}) are derived, which holds with probability 1. On the other hand, for any fixed k it is shown that ({lim_{nrightarrowinfty} L_{n,k}(underline{s})/n = 1/2}) holds with probability 1. The asymptotic bounds on the expected value of normalized k-error linear complexity of binary sequences are also presented.