ON THE CORRELATION FUNCTIONS OF M-SEQUENCES

In this paper we develop some properties for the correlation functions of M-sequences whichare important for applications.Let (?)=(a_0,a_1,…,a_(N-1),…) and =(b_0,b_1,…,b_(N-1),…)be two M-se-quences of order n,where a_i and b_i are elements of the binary field F_2 and N=2~n is theirperiod.The cross-correlation function of the sequences and is defined byr(?)(k)=sum from i=0 to N-1 u_iv_i+k,k=0,1,…,N-1,where u_i=cosa_iπ and v_i=cosb_iπ.The auto-correlation function of the sequence is defined byr_(?)(k)=r_(?)(k)=sum from i=0 to N-1 u_iu_(i+k),k=0,1,…,N-1.Theorem 1.For an arbitrary pair of M-sequences (?) and (?) with same order n,thecross-correlation function r_(?)(k)possesses the following properties1)sum from k=0 to N-1 r_(?)(k)=0;2)r_(?)(k)=4A_(0k)-2~n=4A_(1k)-2~n=2~n-4D_(0k)=2~n-4D_(1k),where A_(0k),A_(1k),D_(0k),D_(1k),k=0,1,…,N-1,denote respectively the times of(u_i,v_(i+k)),(0,0),(1,1),(0,1),(1,0),when i runs from 0 through to N-1;3)For n≥2 and each k,(?)(k)is a multiple of four.Theorem 2.For an arbitrary M-sequence with order n,its auto-correlation function(?)(k)has the following bound0≤(?)r_a(k)≤2~n-4[2~n/(2n)],where[x]denotes the smallest integer greater than or equal to x.Let (?) denote a special class of M-sequences generated by adding a 0 to the M-seque-nces.For this class of M-sequences,the bound given by theorem 2 can be improved.Theorem 3.If (?),then the N cyclic shifts of (?) generate an asymptotic orthogonalcode,ρ(?)(0)=1,(?)ρ(?)(k)=0,1≤k≤N-1,whereρ(?)(k)=(?)(k)/r(?)(0).LetI_(?){i_1,i_2,…,i_k}={i;a_i=1,0≤i≤N-1},where i_1i_2…i_k,D_(?)~+={i_l-i_j;j1}is its positive difference set.Theorem 4.If (?)∈(?) and its state s_(N-n)=(a_(N-n),a_(N-n+1),…,a_(N-1))=(0,0,…,0),then we have(?)(k)=4(c_k-c_(k-1)),2≤k≤N-1,where (?) denotes the number of k in the set D_(?)~+.Applying theorem 5 we can calculate the auto-correlation function r_(?)(k),1≤k≤N-1,more easily with an algorithm.