A New Family of Binary Sequences and Its Correlation Distribution

?

A New Family of Binary Sequences and Its Correlation Distribution

XiaYongbo，ShangguanXiaotian

(College of Mathematics and Statistics，South-Central University for Nationalities，Wuhan 430074，China)

KeywordsRothaussequences；sequencefamily；correlationfunction；correlationdistribution；BCHcode

1Introduction

Sequencefamilieswithlowcorrelationhavewideapplicationsinspread-spectrumsystems,code-divisionmultiple-access(CDMA)systems,radarsystemandcryptography[1,2].Combininganm-sequenceanditsdecimatedsequencesisanefficientmethodtoconstructsequencefamilieswithlowcorrelationandlargefamilysize.Duringthepastdecades,numerousfamiliesofbinarysequenceswithgoodpropertieshavebeenconstructedbythismethod,seeRef[3-10],forexample.Amongthem,foroddm,Goldsequences[3,4]constituteoneofthefamilieswithoptimalcorrelationachievingtheSidelnikovbound[11],andforevenm,thesmallsetofKasamisequences[7]givessequenceswithoptimalcorrelationachievingtheWelch′slowerbound[12].

Inacode-divisionmultipleaccess(CDMA)system,maximumcorrelationandfamilysizearekeyparametersofasequencefamily.Largefamilysizeisrequiredtosupportalargenumberofsimultaneoususers,andlowcorrelationisrequiredtominimizeinterferenceamongdifferentusers.DuetoWelchbound[12],Sidelnikovbound[11],andLevenshteinbound[13],thereexistsatradeoffbetweenfamilysizeandmaximumcorrelation.Foraspecificapplication,iflowcorrelationismorecrucialthanlargefamilysizeintheapplication,wemayminimizethemaximumcorrelationfirstatthepriceofthedecreaseoffamilysize.Ontheotherhand,iflargefamilysizeismoreimportant,wemaysacrificethelowcorrelationtoincreasethefamilysize.AgoodexampleforcompromisebetweencorrelationandfamilysizeistheRothaussequencefamily[2,6].

Letmbeodd, m≥5.Rothaussequencefamilywasconstructedfrom

Recently, by making use of

(1)

insteadofEq.(1),RathaussequencefamilywasgeneralizedbyZhouandTanginRef[10],wheregcd(k,m)=1anditscorrelationdistributionisalsodetermined.

anewsequencefamilywillbeproposedanditscorrelationdistributionwillalsobedetermined.ThisnewsequencefamilyisidenticaltoRothaussequencefamilyintermsofmaximumcorrelationandfamilysize.However,notallthedecimationsusedherearequadratic(the2-adicexpansionofthemhaveweight2)sincer2isnotaquadraticdecimation.

Theremainderofthispaperisorganizedasfollows.InSection2,weintroducesomepreliminaries.InSection3,wegivetheconstructionofthesequencefamilyandderiveitscorrelationdistribution.TheconcludingremarksaregiveninSection4.

2Preliminaries

Fortwobinarysequences{u(t)}and{v(t)}oflengthN,theirperiodiccorrelationfunctionisdefinedas:

where 0≤τ≤N-1,t+τis computed by moduloN. Two sequences {u(t)} and {v(t)}are said to be cyclically equivalent if there exists an integerτsuch thatu(t+τ)=v(t) for allt. Otherwise, they are said to be cyclically distinct.

For a sequence familySof periodN, its maximum correlationCmaxis defined by:

where|x|denotesthemodulusvalueofacomplexnumberx.Clearly,Cmaxisthemaximummagnitudeofallnontrivialauto-andcross-correlationsofpairsofsequencesinS.IfScontainsMcycliclydistinctsequences,thenSwillbecalledan(N,M,Cmax)sequencefamily.

wherex∈F2mandlis a divisor ofm. Letf(x) be a function fromF2mtoF2. The trace transform off(x) is defined by:

wherebi,j∈F2. The rank of a quadratic formf(x) is determined by the number ofz∈F2msuch that:

f(x)+f(z)+f(x+z)=0 for allx∈F2m.

(2)

It is well known that the rank off(x) must be even, and if there are 2m-2hz′sinF2msatisfying Eq.(2), then the rank off(x) is equal to 2h[2,15].

LetCbe a linear code overF2with lengthnand

dimensionl. Then, we callCis an [n,l] linear code overF2. The Hamming weight of a vector c∈Cis the number of its nonzero entries and is denoted WH(c). LetAibe the number of codewords inCwith Hamming weighti,0≤i≤n. The sequence {A0,A1,A2,…,An} is called the weight distribution ofC. The dual code of c, denotedC⊥, is defined by:

where x·c denotes the dot product. According to MacWilliams identity[15], if the weight distribution ofCis known, then the weight distribution ofC⊥will be uniquely determined, and vice versa.

Lemma2LetCbethecycliccodedefinedinEq.(3).ItsweightdistributionisgiveninTable1.

Tab.1　Weight distribution of C

3New sequence family with large size

From now on, we will fix the following notations:

(i)mis an odd integer andm≥5;

(iii) αisaprimitiveelementofF2m.

Sequencefamilyconstruction:Set

Δ0={(1,0,0)},Δ1={(x0,1,0)|x0∈F2m},

Δ2={(x0,x1,0)|x0,x1∈F2m},Δ=Δ0∪Δ1∪Δ2.

The new sequence familySis defined by:

(4)

where

(5)

In order to study the correlation properties of the sequence familyS, we need to investigate some exponential sums.

(6)

whereS0(a,b)=2mif and only if (a,b)=(0,0).

From the above analysis, Eq.(6) is obtained.

Lemma 4Let:

(7)

S1(a,b,c)=2m-2WH(c),

(8)

Theorem1LetSbethesequencefamilydefinedinEq.(4).Then, Scontains22m+2m+1cycliclydistinctsequencesanditscorrelationdistributionisgiveninTab.2.

Tab.2　Correlation distribution of S

Proof Let

where (ai,bi,ci)∈Δ,i=1,2 . Then, the correlation function betweens1ands2is given by:

Cs1,s2(τ)=

(9)

where 0≤τ<2m-1. In what follows, we will determine the values taken byCs1,s2(τ) and the times they occur when (a1,b1,c1) and (a2,b2,c2) run throughΔ, respectively, andτruns through {0,1,2,…,2m-2}. We consider the following cases.

Case 1: (a1,b1,c1) and (a2,b2,c2) run throughΔ0, respectively. In this case, Eq.(9) becomes:

Obviously, in this case,-1 occurs 2m-2 times and 2m-1 occurs once.

Case 2: (a1,b1,c1) runs throughΔ0and (a2,b2,c2) runs throughΔ1. Then,

Whena2runs throughF2mandτruns through {0,1,2,…,2m-2}, by the proof of Lemma 3, one has:

Cs1,s2(τ)=

Case 3: (a1,b1,c1) runs throughΔ0and (a2,b2,c2) runs throughΔ2. Then,

Case 4:(a1,b1,c1) runs throughΔ1and (a2,b2,c2) runs throughΔ0. Then,

Whena1runs throughF2mandτruns through {0,1,2,…,2m-2}, by the proof of Lemma 3, we have:

Cs1,s2(τ)=

Case 5:(a1,b1,c1) runs throughΔ1and (a2,b2,c2) runs throughΔ1. Then,

By Lemma 3 and its proof, in this case we have：

Cs1,s2(τ)=

Note that in this caseCs1,s2(τ)=2m-1 if and only if (a1,b1,c1)=(a2,b2,c2) andτ=0.

Case 6:(a1,b1,c1) runs throughΔ1and (a2,b2,c2) runs throughΔ2. Then,

Case 7:(a1,b1,c1) runs throughΔ2and (a2,b2,c2) runs throughΔ0. Then,

Case 8:(a1,b1,c1) runs throughΔ2and (a2,b2,c2) runs throughΔ1. Then,

Case 9:(a1,b1,c1) runs throughΔ2and (a2,b2,c2) runs throughΔ2. Then,

Ifτ=0, by Lemma 3 and its proof, when (a1,b1,c1) runs throughΔ2and (a2,b2,c2) runs throughΔ2, the value distribution ofCs1,s2(τ) is as follows:

Summing the value distributions in Cases 1-9, the desired distribution in Tab.2 is obtained. From the above discussion, it is easily seen thatCs1,s2(τ)=2m-1 if and only if (a1,b1,c1)=(a2,b2,c2) andτ=0. By counting the number of elements inΔ, the family size ofSis obtained.

Tab.3　Known exponent pairs {d1,d2} such that C1,d1,d2 and

4Conclusion

Attheendofthispaper,weprovideanexampletoverifyTheorem1.

Example1Letm=5,r=9,r2=81≡19mod(2m-1)andαbeaprimitiveelementofF25.Then,thesequencefamilySisgivenasfollows:

By computer experiment, the correlation distribution ofSis given by:

The numerical result coincides with Theorem 1.

References

[1]Golomb S W, Gong G. Signal design for good correlation for wireless communication, cryptography and radar[M]. Cambridge(U.K.): Cambridge Univ Press, 2005:401-421.

[2]Helleseth T, Kumar P V. Sequences with low correlation[M]//Pless V,Huffman C. Handbook of Coding Theory. New York: Elsevier Science, 1998: 1767-1853.

[3]Gold R. Maximal recursive sequences with 3-valued recursive crosscorrelation functions[J]. IEEE Trans Inf Theory, 1968, 14(1): 154-156.

[4]Sarwate D V, Pursley M B. Crosscorrelation properties of pseudorandom and related sequences[J]. Proc IEEE, 1980, 68:593-619.

[5]Boztas S, Kumar P V. Binary sequences with Gold-like correlation but larger linear span[J]. IEEE Trans Inf Theory, 1994, 40(2): 532-537.

[6]Rothaus O S. Modified Gold codes[J]. IEEE Trans Inf Theory,1993, 39(2): 654-656.

[7]Kasami T. Weight distribution of Bose-Chaudhuri-Hocquenghem codes[C]//Bose R C, Dowling T A. Combinatorial Mathematics and Its Applications. Chapel Hill(NC): Univ North Carolina Press, 1969:335-357.

[8]Zeng X, John Liu Q, Hu L. Generalized Kasami sequences: the large set[J]. IEEE Trans Inf Theory, 2007, 53(7): 2587-2598.

[9]Yu N Y, Gong G. A new binary sequence family with low correlation and large size[J]. IEEE Trans Inf Theory, 2006, 52: 1624-1636.

[10]Zhou Z C, Tang X H. Generalized modified Gold sequences[J]. Des Codes Crypt, 2011, 60(3): 241-253.

[11]Sidelnikov V M. On mutual correlation of sequences[J]. Sovi Math-Dokl, 1971, 12: 197-201.

[12]Welch L R. Lower bounds on the maximum cross correlation of the signals[J]. IEEE Trans Inf Theory, 1974, 20(3): 397-399.

[13]Levenshtein V I. Bounds for codes as solutions of extremum problems for system of orthogonal polynomials[M]//San Juan de Puerto Rico. Proceedings of AAECC′93, LNCS, vol. 673. Berlin: Springer-Verlag, 1993: 25-42.

[14]Lidl R, Niederreiter H. Finite fields[M]. Second edition.Cambridge(U.K.): Cambridge Univ Press, 1997 : 54-63.

[15]MacWilliams F J, Sloane N J. The theory of error-correcting codes[M]. Amsterdam: North-Holland, 1977: 698-700.

[16]Bose R, Ray-Chaudhuri D. On a class of error correcting binary group codes[J]. Info and Control, 1960, 3: 68-79.

[17]Hocquenghem A. Codes correcteurs d′erreurs[J]. Chiffres(Paris), 1959, 2: 147-156.

[18]Chang A, Gaal P, Golomb S W, et al. On a conjectured ideal autocorrelation sequence and a related triple-error correcting cyclic code[J]. IEEE Trans Inf Theory, 2000, 46(2): 680-687.

[19]Kasami T. Weight enumerators for several classes of subcodes of the 2nd order Reed-Muller codes[J]. Inf Contr, 1971, 18: 369-394.

[20]Zeng X, Shan J, Hu L. A triple-error-correcting cyclic code from the Gold and Kasami-Welch APN power functions[J]. Finite Fields Appl, 2012, 18(1): 70-92.

一類新的二元序列集及其相關(guān)分布

夏永波, 上官曉天

(中南民族大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)學(xué)院, 武漢 430074)

摘要對(duì)于奇整數(shù)m≥5, 構(gòu)造了一類新的周期為2m-1的二元序列集, 并完全確定了衡量新序列集性能的一個(gè)重要指標(biāo)——相關(guān)分布. 新序列集的最大相關(guān)值為+1, 集合容量為2(2m)+2m+1, 和著名的Rothaus序列具有類似的相關(guān)性質(zhì), 能適用于無線通信系統(tǒng)如CDMA通信系統(tǒng).

關(guān)鍵詞Rothaus序列；序列族；相關(guān)函數(shù)；相關(guān)分布；BCH碼

中圖分類號(hào)O157

文獻(xiàn)標(biāo)識(shí)碼A

文章編號(hào)1672-4321(2016)01-0145-06