DOC

AUTOCORRELATIONS

By Jack Lewis,2014-06-20 05:44
10 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.?1=II,thus WhentheshiftisoftheformkT/P(1i e1,1kP1,andP,f),usingtheproperty thatgisalsoaprimitiverootmoduloP.~,wecan

    get

    g=1(modP),whereasg?1(roodP卧卜)

    Thuswecanassume

    g=1+p+p++ki1P(modP.)

    where?(z/(p)),and?Z/(p),1Ji1.

    Itiseasytocheckthatwhenkrunsthroughall

    elementsin(z/(p.)),(ko,,,)

    allelementsin(z/(p))×(z/(p)).

    of.thefollowingresultholds: Theorem1Letgbeaprimitive q=p.(e2),A?(z/(q)),andset

    runsthrough

    Forthiskind

    rootmodulo

    =

Ag"m.dq)(m.62),0

    Thenb=(b0,,)isabinaryperiodicsequence withperiodT=P(P1).Foranypositivein- tegeri,1ie/2,theautocorrelationofbwith, shift=kT/pis~

    Cb(kT/P,=T/P..

    where1kP1,andP,k.

    ProofFromtheabovediscussionweknowthatbis anPsequenceoritsdecimationwithperiodT= P(P1).Nextwewillcalculatetheautocorre- lationofbwithshift=kT/p..

    Fromtheaboveanalysis,weknowthatforany =kT/P,1kP1,andP,fk,gisofthe

    form

    g=1+p+p++1P(modP.)

    wherek0?(z/(p)),and?z/(p),1Ji1.

    Next,wewillshowCb()=T/Pforthiskind

    nf

    Usingthesamenotationsasabove,set --

    --

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

    =

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

    thenC()=ll_I1.

    ForanyA?(z/(q)),letA=a0+alP++

    a~_

    lP.~bethep-adicexpansionofA,wherea0?

    (z/(p)),anda,?z/(p),1Je1.Thenwe

    have

Ag(modP.)

    =

    (a0+alP++ae1P)(1+koP +p++ki1P)

    =

    (a0+pa1++pe-i-aa.一一1)+(aoko+ae)p +(00+alko+ae-i+1)p++(aok,1 +aaki

    2

    ++ai_lko+ae_

    1)p

    =

    (a0+pa1++p~-,-aa.一一1)

    +p((+0.一件1p+???+ae1P) +(00+(00+a1ko)P+

    +(aoki1+012++ai_lko)p)) Set

    m=aoko+(00+alko)p+

    +(‰一1+012++ai_ako)p(modP)

    =a.

    +0.+1p++ae1P(modP) Then

    Ag=(+pch++p~-i-1.一一1)

    +(m+n)p(modP.) A=(00+pa1++p~-i-10.一一1) +np(modP.)

    ThusAg=A(modp.)(mod2)ifandonlyifm+

    =(modpi)(mod2). Obviously,when1ie/2,a0,01.,a.1and

ae

    ,

    ae

    +1,,ae

    1areevaluatedindependently.Itis

    easytocheckthatwhena0runsthroughallele mentsin(z/(p)),and throughallelementsin throughallelementsin spectively.

    Set

    01,,ai

    1,ae

    ,,ae

    1run

    A0={(m,)?(z))×(z.))

    lm+=modp)(mod2)) A1=)?(z))×(z))

    Im+礼?礼m.dp)(mod2)) FromLemma2weknowthat m

    a

    Z

    dd{{

    m

    ,L,,,

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

    lollA1l=(p1)

Report this document

For any questions or suggestions please email
cust-service@docsford.com