Title | ||
---|---|---|
Asymptotic behavior of normalized linear complexity of ultimately nonperiodic binary sequences |
Abstract | ||
---|---|---|
For an ultimately nonperiodic binary sequence s={st}t≥0, it is shown that the set of the accumulation values of the normalized linear complexity, Ls(n)/n, is a closed interval centered at 1/2, where Ls(n) is the linear complexity of the length n prefix sn=(s0,s1,...,sn-1) of the sequence s. It was known that the limit value of the normalized linear complexity is equal to 0 or 1/2 if it exists. A method is also given for constructing a sequence to have the closed interval [1/2-Δ, 1/2+Δ](0≤Δ≤1/2) as the set of the accumulation values of its normalized linear complexity. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1109/TIT.2004.836704 | international symposium on information theory |
Keywords | Field | DocType |
nonperiodic binary sequence,linear complexity,length n prefix sn,closed interval,limit value,asymptotic behavior,accumulation value,normalized linear complexity,continued fraction,binary sequence,computational complexity | Discrete mathematics,Combinatorics,Normalization (statistics),Pseudorandom binary sequence,Prefix,Linear complexity,Asymptotic analysis,Mathematics,Binary number,Computational complexity theory | Journal |
Volume | Issue | ISSN |
50 | 11 | null |
ISBN | Citations | PageRank |
0-7803-8280-3 | 7 | 0.63 |
References | Authors | |
4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zong-duo Dai | 1 | 203 | 25.53 |
Shaoquan Jiang | 2 | 147 | 17.46 |
K. Imamura | 3 | 8 | 1.03 |
Guang Gong | 4 | 1717 | 160.71 |