Asymptotic Behavior of Normalized Linear Complexity of Ultimately Nonperiodic Binary Sequences

Abstract

For an ultimately nonperiodic binary sequence s={s/sub t/}/sub t/spl ges/0/, it is shown that the set of the accumulation values of the normalized linear complexity, L/sub s/(n)/n, is a closed interval centered at 1/2, where L/sub s/(n) is the linear complexity of the length n prefix s/sup n/=(s/sub 0/,s/sub 1/,...,s/sub n-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-/spl Delta/, 1/2+/spl Delta/](0/spl les//spl Delta//spl les/1/2) as the set of the accumulation values of its normalized linear complexity.