Asymptotic analysis on the normalized <Emphasis Type="Italic">k</Emphasis>-error linear complexity of binary sequences |
| |
Authors: | Lin Tan Wen-Feng Qi Hong Xu |
| |
Institution: | (1) Sabancı University, MDBF, Orhanlı, Tuzla, 34956 İstanbul, Turkey |
| |
Abstract: | 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_{n\rightarrow\infty} 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|