LINEAR COMPLEXITY AND RANDOM SEQUENCES WITH PERIOD 2~n

摘要

Let （?）=（S,S,…）be a binary random sequence with period N=2n,where S=(S₀,…,S_N-1)is its one period with N independent and uniformly distributed binary random variables.The main results of this paper are as follows.1)Var c（?）=2-（2N+1）2-N-2-2N;2)E|c（?）-c（?）|=[2c（?）+1-2]2-Nfor any sequence （?） with period 2n;3)N-1+2-N-(n/2+1-2-（N-n）)≤E[（?）c（?）]≤N-1+2-N4)2-2-（N-1）≤E[（?）|c（?）-c（?）|]≤2-2-N+n/2-2-（N-n）,where E and Var stand for taking expectation and variance respectively,c（?） is the linearcomplexity of the sequence （?） and W（b） the Hamming weight of one period of the seqnence （?）.