DOC

AUTOCORRELATIONS

By Jack Lewis,2014-06-20 05:44
13 views 0
AUTOCORRELATIONS

    AUTOCORRELATIONS

    Vl01.24No.4JOURNALOFELECTRONICSfCHINAJuly2007

    AUTOCORRELATIONSOF/-SEQUENCESWITHCERTAINSHIFTS

    XuHongQiWenfeng

    (DepartmentofAppliedMathematics,ZhengzhouInformationEngineeringUniversity,Zhengzhou450002,China)

    AbstractInthispaper,theautocorrelationsofmaximalperiodFeedbackwithCarryShiftRegister

    sequences(/-sequences)arediscussed.Foran/-sequenceawithconnectionintegerq=Pe2)and

    periodT=pe-1(p1),andforanyintegeri,1ie/2,bycalculatingthenumberofcertainsets,it

    ,where isshownthattheautocorrelationofawithshift7_=kT/2pis(7-)=(-1)T/p~

    12p1,andgcd(k,2p)=1.Thisresultshowstheredoexistsomeshi~ssuchthattheauto

    correlationsof/-sequencesarehighalthoughmostautocorrelationsarelow.Suchresultalsoholdsfor

    thedecimationsof/-sequences.

    KeywordsPseudorandomsequences;/-sequences;FeedbackwithCarryShiftRegister(FCSR)se

    quences;Autocorrelations

    CLCindexO157.4:TN918.1

    DOI10.1007/s1176700502147

    I.Introduction

    Pseudorandomsequencesareimportantin

    manyareasofcommunicationsandcomputingsuch

    ascryptography,spreadspectrumcommunications,

    errorcorrectingcodes,andMonteCarlointegration

    Generally,acryptographicaUy"good"pseudoran

    domsequenceshouldhavelongperiod,highlinear complexity,andsatisfyGolomb'sthreepostulates, thatis,itshouldbebalanced,havefinerunprop. ertyandtwovaluedidea1autOcorre1ations.The correlationpropertiesofpseudorandomsequences arenotonlyanimportantmeasureofrandomness, butalsohavepracticalapplicationsinspread spectrumcommunicationsystems,radarsystems, cryptanalysis,andsoon.

    Inthefollowing,letPbeanoddprimeinteger ande>1suchthat2isaprimitiverootmodulo q=P.Theclassofbinarysequencesknownas fsequencescanbedescribedinsevera1ways[12.An

    /-sequenceistheoutputsequencefromamaximal periodFeedbackwithCarryShiftRegister(FCSR) withconnectionintegerq.Itisthe2adicexpan

    Manuscriptreceiveddate:November10,2005;reviseddate May28,2006.

    Supportedbythe863ProjectofChina

    fNo.2006AA01Z4171andtheNationalNaturalScience FoundationofChinafNo.60673081).

    Communicationauthor:XuHong,bornin1979,female, doctoralcandidate.DepartmentofAppliedMathematics, ZhengzhouInformationEngineeringUniversity,Zheng

    zhou450002,China.

    Emall:xuhong0504@163.com.

    sionsofarationalnumberr/q,wheregcd(r,q)--

    1.and0<r<q.Itisthesequenceoftheform a=A2(roodq)(mod2),wheregcd(A,q)=1.

    ThearchitectureofFCSRwasfirstintroduced

in1994[3l,

    andsincethen1otsofresearcheshave

    beendoneonthestructureandpropertiesof FCSRsandsequencesgeneratedbythemj.Re- cently,akindoffilteredFCSRwasalsoproposedas anewkeystreamgeneratorIs,91.Uptonow,the /~sequenceshavebeenshowntobebalancedand havefinerunproperty.Astothecorrelation propertyof/~sequences,theirordinaryautocorre

    1ationshavenotbeenstudiedalthoughtheir arithmeticautocorre1ationshavebeenshowntobe zero[.

    Thearithmeticautocorre1ation8aredefined Definition1_4JLeta=(a0,a)bebinaryse-

    quenceswithperiodT.and1et0<T<T.Denote a=abethesequenceformedbyshiftingaby 7-positions.Letandbethe2adicnumbers

    whosecoefficientsaregivenbyaanda,respec

    tively.Thenthesequenceofcoefficientsassociated withniseventuallyperiodic,anditsperiodis dividedbvTheshiftedarithmeticautocorrela

    tion8f)i'o7-ofasthenumberof0sminusthe numberof1'sinacompleteperiodoflengthT of.

    Theusua1autocorre1ationofsuchsequencea withshift7-isdefinedas7-)=?T-o1(1)%".

    Inanearlywork,weevaluatedtheexpectationand varianceoftheautocorre1ationsof/~sequencesand

    JOURNALOFELECTRONICS(CHINA),Vo1.24No.4,July2007

    theirdecimations.Inthispaper,wefurtherprovide theexactvalueoftheautOcOrrelatiOnsof/-se

    quencesandtheirdecimationswhentheshiftTis ofcertainform.

    II.MaiIIResults

    Wefirstgivethedefinitionandexponential representationof1sequences.

    Definition2l12An/-sequenceisaperiodicse

    quence(ofmaximalpossibleperiodT=(g)= pe-1(p1))whichisobtainedfromanFCSRwith connectionintegerq=Pforwhich2isaprimitive root.

    Foranypositiveinteger,letz/(n)={0,1,,

    佗一1)betheringofintegersmoduloand

    (z/())themultiplicativegroupofit.The/-se- quenceshavethefollowingexponentialrepresen- tation:

    Lemma1[112]Let0=(00,0??)bean/-sequence generatedbyanFCSRwithconnectioninteger q=PandperiodT=P(P1).Thenthereis

    anintegerA?(z/(g)),suchthat

    a=A2(modq)(mod2),=0,1,2,

    wherethenotation(modq)(mod2)meansthat firstthenumberA2_..shouldbereducedmoduloa togiveanumberbetween0andq1.andthen

    thatnumbershouldbereducedmodulo2. Remark1Letb=(b0,bl,)bethed-folddeci

    mationofa.Thatis,=a.Forconvenience, alwaysassumedisrelativelyprimetoThusthe sequencebisofthef0rm

=

    A2(modq)(mod2),=0,1,2,

    where2(modq)isalsoaprimitiverootmoduloq.

    Generally,letgbeaprimitiverootmoduloq,and

    setAg(modq)(mod2).Thenb=(b0,,)

    isan/-sequenceoritsdecimation. Beforeshowingthemainresults,wefirstgivea

    lemma.

    Lemma2LetPbeanoddprime.andi>1.Set A0=)?(z/(p))×(z/(p))

    Im+=modp.)(mod2))

    A1--{(m,)?(Z/(p.))×(Z/(p))

    Im+佗?佗m.dp)(mod2))

    then

    1.lll=(p1)

    ProofAslA01+1All=p2~-1(p1),weneedonlyto calculatelA0l,thenumberofelementsinA0.For

    any(m,)?A0,obviouslywehave0<m+<

    2p,andthenumberlA0lcanbecalculatedac

    cordingtotheparityofm.

    (1)Ifmisodd,then

    m+佗一佗(modP)(mod2)

    ifandonlyifm+>P

    Since0<<p.1.thenumberof

    Pm<<P.1ism.

    f2)Ifmiseven,then

    m+=(modP)(mod2)

    ifandonlyif0<m+<

    Since0<<P.1.thenumberof

0<<P.1misP.m.

    Fromaboveweknow

    satisfying

    P

    satisfying

    .l=?m+?(pm)

    me(Z/(p')1me(z/(p')1' 2Im2Im

    =

    ?P.+?m2?m

    m?(z/(F))me(z/(p'))m?(z/(F))

    Thus

    =p2i-1(p1)/2+p(p1)/2

    

    (P+1)(p1)/2

    =p2i-~(p1)/2~(P1)/2

    1.l11=p(p1)2l.1=(p1)Q.E.D Letgbeaprimitiverootmoduloq=P.and

    set=Ag(modq)(mod2)withgcd(A,q)=1.

    FromRemark1weknowthat'b=(,51,)isan1

    sequenceoritsdecimationwithperiodT=

    P(P1).Theautocorrelationofbwithshift7.

    canberepresentedas

    ()l?(1)

    n=0

    NoN

    where?0----(10<_1jand=+)Iis thenumberofsatisfying=andNl= I{10<佗一1,and6n?+)Iisthenumber.f

    satisfying?+.Obviously,No+N1=T. NextwewillcalculateNoandN1.

XUeta1.Autocorrelationsof/-sequenceswithCertainShifts441

    Set

    =

    {?(z/(q))lAg=(m.dq)(m.d2)) --

    --

    {A?(z/(q))IAg?(m.dq)(m.d2))

    obviously,wehaveNo=Il,cb(7)=f-ff.<