Leeper 1973

Copyright @1973American Telephone nodTelegraph Company TilEBELLSYSTEM TECIiNICAL JOUHSAL Vol.52,No.10,December, \073 PrintedinU.S.A. AUniversal DigitalDataScrambler ByDAVID G.LEEPER (Manuscript received Ma.y22,1973) Analyses intheliterature ofdigitalcommunications oftenpresuppose thatthedigitalsourceisHwhite, IIthatis,thatitproduces stochastically independent eguiprobable symbols. I'llthispaperweshowthatitispossible to"whiten" toanydegreeallthefirst-andsecond-order statistics ofany binarysourceatthecostofanarbitrarily smallcontrollable errorrate. Specifically, weprovethattheself-synchronizing digitaldatascrambler, alreadyshowneffectiveatscrambling strictlyperiodic datasources,will scram.ble anybinarysourcetoanarbitrarily smallfirst-andsecond-order probability densityimbalance 6if(i)thesourceisfirstpassedthroughthe equivalent ofasymmetric memoryless channelwithanarbitrarily small butnonzeroerrorprobability" and(ii)thescrambler contains Mstages where M~I+log,[(ln26)/ln(I-2,)]. Someinterpretations andapplications ofthisresultareincluded. I.INTRODUCTION ANDSUMMARY Digitaltransmission systems oftenhaveimpairments whichvary withthestatistics ofthedigitalsource.Timing,crosstalk, andequaliza­ tionproblems usuallyinvolvesourcestatistics insomeway.While redundan ttransmission codesmaybeusedtohelpisolatesystem performance fromsourcestatistics, theisolation isnotalwayscomplete, andsuchcodesgenerate additional problems byincreasing therequired symbolrateortbenumberoflevelspersymbolwhichmustbetrans­ mitted.Inaddition, withorwithout transmission codes,itisalways easiesttoanalyzeorpredictsystemimpairments ifweassumethatthe sourcesymbols arestochastically independent andequiprobable. We shallrefertosuchasourceasHwhite" becauseoftheobviousanalogy towhiteGaussian noise.Methods forHwhitening" thestatistics of digitalsourceswithoutusingredundant codinggenerally comeunder theheadingofscrambling. 1851 1852 THEBELLSYSTEM TECHNICAL JOURNAL, DECEMBER 1973 Wedescribe hereanonredundant scrambling/dcscrambling method whichinprinciple willsatisfactorily whitenthestatistics ofanybinary source.Thetechnique isbasedupontheself-synchronizing digitaldata scrambler. Savagebasshown Ithatthisdeviceisveryeffective at scrambling strictlyperiodic digitalsources.Inthispaperitisproven thattbesamedevicewillscramble anybinarydigitalsourcetoan arbitrarily smallfirst-andsecond-order probability densityimbalance oif(i)thesourceisfirstpasscdthrough theequivalent ofabinary symmetric memoryles", channelwitbanarbitrarily smallbutnonzero errorprobability E,and(ii)thescrambler contains Mstageswhere M;;;:;1+log,[(In26)/ln(1-2,)].Inotherwords,atthecostofan arbitrarily smallc01ltrollable errorrale,onecan"whiten" loanydegree allthefirsl-andsecondrorder slatislics ofanybinarysource.Thisrelaxes therestriction frequently foundintheliterature inwhichthesourceis assumcd aprioritoproduceonlyindependent equiprobable symbols. Anauxiliary resultisthatthcaboverelationforMisusefulwhen designing astandard self-synchronizing scrambler foragivenapplica­ tion.Heuristically speaking, therelationexpresses thelfpower" ofthe scrambler bylinkingthc"randomness" oftheinputandoutputtothe scrambler length,M. InSectionsIIandIIIofthispaperweexamine someproperties of scramblers, maximal lengthsequence.s, andmod-2sumsofbinary randomvariables. Withthesediscussions asbackground, weprovethe maintheorem inSectionIV.InSectionVwederiveboundsforthe autocorrelation ofthescrambled sequence. SectionVIcontains some practical considerations involved inapplying thetheorem ofSection IV.Beacuse theyaddinsight,wegivesimplcdirectproofsforthe lemmasandtheoremofScctionsIIIandIV. II.SCRAMBLERS ANDMAxnUL LENGTH SEQUENCES Figure1showsafiv",stage self-synchronizing scrambler andd", scrambler. IAsseen,botharelinearsequential filters,thescrambler utilizing feedback pathsandthedescrambler feedforwardpaths.Each cellrepresents aunitdelay.Werestrictourattention tothebinary caseandusethesymbols (j)andEtodenotemod-2addition. Repr", sentingthedataasshown,wehave b,=a,(j)b'_3(j)b,_, and c,=b,(j)b'_3(j)b,_,=a" whichshowsthatthedescrambled sequence isidentically equaltothe AUNIVERSAL DIGITAL DATASCRAMBLER 1853 '.INPUT b. INPUT.... OUTPUT (a) '"OUTPUT(b) Fig.1-(a)Five-stage scrambler. (b)Five-stnge descrnmbler. originaldatasequence. Thedescrambler isself-synchronizing because theeffectofachannelerror,insertion, ordeletionlastsonlyaslongas thetotaldelayoftheregister, fivebit-intervals inthisexample. Letusconsider thegeneralscrambler ofFig.2awiththeinput streamdisconnected. Undersuchacondition, thescramhler hecomes asequence generator whoseoutputmustultimately hecomeperiodic because (i)futurestatesoftheregisterarecompletely determined hy thepresentstate(thestateoftheregisteristhecontents ofitsstages) and(i.)onlythefinitenumber2Mstatesarepossible, whereMequals thenumherofstages.Oneofthese,theall-zeros state,simplyleadsto anall-zeros output.Discounting thisstate,weseethatthelongest possibleperiodfromthegenerator mustbe2M-1bits.Itisprovenin theliterature'·' thatwiththeproperchoiceoffeedback tapsweean generate suchamaximal lengthsequence foranyM. Registers whichgenerate maximal lengthsequences makevery effective scramblers becauseoftheirability to dissociate onescrambler outputbitfromanother. Thisproperty willenableustoshowthattwo arbitrarily chosenoutputbitstendtobeveryweaklycorrelated. We statethisessential property hereintheformofalemma. Lemma1:FromFig.2aitisevidentthateach"b"bitisequaltoalengthy mod.-llsummation ofselected"allbits.Choosetwobits,b",andbn,m>n, anddefi.neJ"Intobethenumberof/fa"bitswhichenterthesummation for bmbutnotthes"mmation forb,.Thatis,bmisdissociated froll'b,bythe mod-2sumofJ1ft""a"bits. Then,ifn>2M+1(thatis,thescrambler hasprocessed atleast2MH 1854 THEBELLSYSTEM TECHNICAL JOURNAL, DECEMBER 1973 .-------(+ ....,..,---<+ >-....-< INPUT (a) b, INPUT +)----{ " OUTPUT (b) Fig.2-(a)M-atagescrambler. (b)M..stagedescrambler. CIa"bits), (1) m•• InotherwordiJ,afterasettlingtimeof2'1+'bits,anychosenpairof autputbitswilldiffel'bythemod-2sumofatleast2"-'inputbits. Proof:Seeappendix. III.MOD-2 SUMSOFBINARY RANDOM VARIABLES Throughout thispaperweassumethatadatasequence maybe modeled asasequence ofbinaryrandomvariables definedonasuitable probability space.Inthissectionwestateaslemmastwoessential properties ofmod-2sumsofbinaryrandom variables. Sincethe scrambler outputisformedfrommod-2sumsofinputbits,these properties playakeyroleindetermining thescrambler outputcharac­ teristics. Weincludetheproofsinthetextbecause theequations involved willbeusefullateron. Lemma2:Consider twoindep""dent binaryrandomvariables r1andr,. Athirdbinaryrandomvariabler,=r,Ellr,.Let p;=Per;=1)=1 -Per;=0),i=1,2,3. ThenAUNIVERSAL DIGITAL DATASCRAMBLER Ip,-tI~min[Ip,-tI.IP,-tIJ1855 withequalityifandonlyifPIorp,=t,0,or1.Inotherwords,r.is ascloseorclosertobeingequiprobable thaneitherT,orTI. Proof:Sincerlandr,areindependent, p.=p,(1-PI)+PI(l-p,). Let(2) d;=p;-t Thenbysubstitutioni=1,2,3. Butsince wehave Id.1~min[Idd,1d,IJ withequality ifandonlyifIdllorId,I=0ort. Corollary toLemma2:IfPI=t,thenp,=tandT.isindependent ofT2. Proof:SinceT,=TlG)T"P(T.=1fro=1)=1 -PI=t.Butbyeq. (2),p.=t.Thus,Ph=1h=1)=P(T.=1)=t.whichimplies rJand r~areindependent. Lemma 8:Consider nowasequence ofindependent binaryrandom vaTiables IT.,k=1,2,···1with P(T.=1)=1-P(T.=0)=,forallk. Weformthemod-2sum •R.=ET.'-1 andletp.=P(R.=1).Then p.=tel-(1-2')'J; n?;1.(3) (4) Notethat,asn-"Xl,p.converges totforall0< , <1.However, weshallbeconcerned onlywithfinitevaluesforn. PTOOf:Byapplying eq.(2)repeatedly, itiseasilyshownthatthe sequencep.satisfies n~2, and 1856 THEBELLSYSTEM TECHNICAL 10URNAL, DECEMBER 1973 Thesolution tothisfirst-order lineardifference equation isgivenby eq.(4). IV.AUNIVERSAL DIGITAL DATASCRAMBLER Withthehelpofthelemmas, wemaynowderivethemainresult. Wemodelthesourceasadevicewhichgenerates asequence ofbinary randomvariablesIs.),,~thcompletely unknown statistics. Ourgoalis tofindascrambling/descrambling method suchthatthescrambled sequenceIb,Iwillhavestatistics whichapproach thoseoftheinde­ pendent equiprobable ("white") sequence fw.}.Ifweattempt to scramble fs.}directlyasinFig.2,wearefacedwithadilemma. The scrambler simplyprovides aone-to-one mapping between itsinputand output.Aslongaswehavenoknowledge orcontrolofthestatistics of (s.},thestatistics of[b.1mustlikewise remainunknown anduncon­ trolled. Hence,theself-synchronizing scrambler alonecannotbe universal. Insteadofscrambling directly, weproceedasshowninFig.3.The sourceoutputisfirstpassedthrough theequivalent ofabinarysym­ metricmemoryless channel (BSC)withcrossover probability, >o. Remarkably, nomatterhowsmall,maybe,thismodification ofthe sourcesequence issufficient toguarantee thatthefirst-andsecond­ orderprobability densities for(b.}willapproach thoseofIw.1to withinanarbitrarily smalldifference 8.Theonlyrequirement isthat M,thelengthofthescrambler, bedependent uponthechoiceof,and o.Thisistheessenceofthetheorem whichwederivebelow.(Wenote inpassingthatthedescrambled sequence willnowdifferfromthe originalsourcesequence bytheerrorrate"butsince,maybechosen arbitrarily small,weassumefornowthatthisisofnoconsequence.) Tobegin,weobservethatbecauseoftheBSCthescrambler input sequence maybewritten wherek=0,1,2,..., (5) P(r.=1)=1 -P(r.=0)=,. FromLemma1wehaveseenthattheactionoftheM-stage scrambler istodissociate anychosenpairofbits(bm,b.)bythemod-2sumofat least2"-1"a"bits.Letusassumethatbmandb.aredissociated by exactly2"-1"a"bitsandthattheyarerelatedby 2J/-l bm=b.®Ea,. I_I(6) AUNIVERSAL DIGITAL DATASCRAMBLER 1857 r-------------, I 11-" IlIZ' I sk to ikas,.e'k bk o 0I 11-<1 IL --J (a) _ _",:b""__ L__M_-S_T_AG_E__1~k·SklBrk DESCRAMBlER , (b) Fig.3-(11)Universal scrambler. (b)Descrambler. (Herethesubscript lisunrelated totheoriginalposition ofa,inthe scrambler inputstream.) InwhatfollowsweshowthatP(bm=1)~t andthatbmandb.arenearlyindependent. Forthesepurposes theuse ofeq.(6)represents aworst-case analysis. Bysubstitution fromeq. (5)wemaywrite bm=[b.®2i.'s,]®[2i.'T']I-I 1_1 " A ®R(7) whereAandRequalthefirstandsecondbracketed terms,respectively. Sincethebitscomprising Rareindependent fromthosecomprising A, Risindependent ofA.Furthermore, byLemma 3, Therefore, byLemma 2,nomatterwhatthevalueof 6'"IP(bm=1)-tI~t[(1-2.)'"-'J"6.(8) P(A=1), (9) Itfollowsthatsolongas•>0wemayforce6and6'tobearbitrarily smallbychoosing alargeenoughM.Specifically, foragiven6, (10) 0<.<t. [In26]M~1+log,In(1_2.); Since6maybemadearbitrarily small,thedensityfunction p(bm)may bemadenearlywhite,anditfollowsthatallfirst-order statistics ofthe scrambled sequence maybemadenearlywhite. OurhavingshownP(bm=1)~tdoesnotbyitselfshowthatthe sourcehasbeeneffectively scrambled. Forexample, consider asequence 1858 THEBELLSYSTEM TECHNIC.o\.L JOURNAL, DECEMBER 1973 Ix.}whichconsistsofconsecutive blocksof100symbols each.Allthe symbols ineachblockarealikc;withprobability1theyareallones, andwithprobability 1theyareallzeros.HereP(x.=1)=1foralln, yetthesequence hasavery"nonrandom" nature.Theimplication is thattodetermine theeffectiveness ofthescrambler, wemustalso evaluate thestatistical dependence between scrambler ontputbits. Bydefinition, thevariables bmandb.areindependent if Accordingly, wedcfinethefunction d(bm,b.)'"p(bm,b.)-p(bm)p(b.) =p(bmIb.)p(b.) -p(bm)p(b.) (11) andshowthattheuniversal scrambler (Fig.3)boundsthemaximum valueof1d(bm,b.)I. Wedoaworst-case analysisbyassuming thatbmandb.arerelated byeq.(7).Further, wcignorethe"s"bitsappearing ineq.(7)because, beingindependent ofR,theycanonlyweakenthedependence between bmandb•.Hence,wemaycompute themaximum valueofId(bm,b.)I byassuming bm=b.®R. (12) Fromeqs.(8)and(9)wenotepeR=1)=1-6andforcon­ venience wetemporarily letPCb.=1)=b.Substituting theserela­ tionsandeq.(12)intoeq.(11),wefindthat Id(bm,b.)I~26[b(1-b)]; for Hence,forb=1weobtainthegeneralresult Id(bm,b.)Im..=6/2. Since0maybeforcedarbitrarily smallifMisgivenbyeq.(10),it followsthatanypairofoutputbitsmaybemadenearlyindependent, andwemaywhitentoanydegreealltbesecond-order statistics ofthe sourcesequence. Wemayalsosbowthatthejoint(second-order) density p(bm,b.) approaches thatforthewhitesequence. Thederivation ofeqs.(6)to (9)showsthatboththedensity pCb,)andtheconditional density p(bilb;)musthavevaluesontheinterval[(1-0),ct+0)]forall AUNIVERSAL DIGI'fAL DATASCRAMBLER 1859 >0 10 10' >0' >0'1011 10-130 ~~0 '"~8~10-10 I 0 N ~~\ il·1(Jl 0"-~0 ~ ~~ 0-,,Dw ~ 5aw4 ~5 1015~ ~ ~ ~ ~3 w "m ~< ~ ~2 1; ~wm ~1z Fig.4--8crambler stagesrequired asafunction offando. possiblevaluesofb;andbj•Hence, or where Forthewhitesequence {Wk11weknowp(wm1wn)=-lforWm,'Wn=0,1. Thusthejointdensity p(bm,b,)maybewhitened toanydegreeby choiceofOJfJandJIi!. Thediscussion aboveconstitutes aproofofthefollowing theorem. Universal Scrambler Theorem: Abinarysourcewithunknown output statistics isconnected toabinarysymmetric memoryless channel andan M-stage self-synchronizing scrambler asshowninFig.3.Thechannel has errorprobability fwhere0<E<!.Thescrambler outputisrepresented byasequence ofrandom variables Ibn,n=0,I,...Iandwedefine pCb,)tobethefirst-order andp(bm,b,)thesecond-order densityfunctions forIb,}.Thenforall0>0;111>n>2M+1,andbm,bn=0,1, andIpCb,)-tI;>0, (13) (14) 1860 THEBELLSYSTEM TECHNICAL JOURNAL, DECEMBER 1973 provided that >[In20]M=1+log,In(12.)'(15) Figure4showstherelation betweenM,E,ando.Asseen,Mis primarily dependent upon•.Thismaybeclarified byrewriting eq. (15)forsmallvaluesof•.Wethenobtain M~log,(1/.)+log,[In(I/20)J; E«t. Theprimary importance ofthistheorem isconceptual. Toavoid inordinate difficulties, manyanalyses intheliterature ofdigitaltrans­ missionmustassumeapriorithatthedigitalsourceiswhite.The theorem relaxesthisrestriction byshowing thatinconceptthefirst­ andsecond-order statistics ofanysourcemaybemadeasymptotically white.Thepractical application ofthistheorem isdiscussed in SectionVI. V.AUTOCORRELATION OFTHESCRAMBLED SEQUENCE Animportant second-order statisticofthescrambled sequence isits autocorrelation. Wedefinetheautocorrelation astheexpectation andforconvenience weletthevalueofb.be+1or-1.Clearly, R(O)=1.Fork'"0,wecompute aboundonIE[b.b.HJI.Following theargument whichledtoeq.(12),wehave IE[b.b.+,JI ~IE[b.(b. (1)R)JI; Bydefinition, E[b.bmJ =LLijP(bm=ilb.=j)P(b.=j). ., Weletbm=b.~Randforconvenience P(b.=1)=b=1 -P(b.=-1). Substituting, thedependency onbvanishes, leavinguswith Hence,E[b.(b. (1)R)J =20. R(k)=1fork=0, IR(k)I~20fork'"O.(16) Notethat,byforcing0toasmallvaluewithproperchoiceofMand E,thisautocorrelation approaches thatfora"white"digitalsource AUNIVERSAL DIGITAL DATASCRAMBLER Rlrl1861 UNITRECTANGULAR PULSESI.-T~:,----.- T TL ~-3T -3T(a) (b)-2T -2TT-T 2T 2T3T ---, ,T I 3T Fig.5-(a)Autocorrelation forwhitesequence Iwot}.(b)Autocorrelation bound forscrambled sequence Ibotl. whichhasR(k)=0,kr'O.Thisisshowngraphically inFig.5which showstheautocorrelation ofHwhite" andscrambled sourcesforunit rectangular pulses. VI.PRAC1'ICAL CONSIDERATIONS Inpractice, thebinarysymmetric channelrequired bythetheorem mightbeimplemented asshowninFig.6.Thebitr,isalogic"one" onlywhenthelevelfromthenoisegenerator cxceedssomethreshold. Thethreshold issetsuchthatper,=1)=E.Thenoisesourceneed notbewhite,butvalucsof11(t)separated bythcbaudintervalshould Fig.6-Onepossibleimplementation oftheBSC. 1862 THEBELLSYSTEM TECHNICAL JOURNAL, DECEMBER 1973 beindependent. Inprinciple, thecombination ofthissimulated BSC andanM-stage self-synchronizing scrambler willformauniversal scrambler capable ofsatisfactorily whitening thestatistics ofany binarysource.Suchascrambling structure couldbeusedwherever randomized bitstatistics areessential andasmallerrorratecanbe tolerated (orperhapscorrected byanerror-correcting code). Thereare,ofcourse,goodreasonstoavoidactualimplementation of theBSC.First,itmaybedifficulttogenerate ther,sequence accu­ ratelyif•isverysmall.Second,thedeliberate generation oferrors,if notimpractical, isatleastunpalatable. Third,andmostimportant, manycommonly encountered sourcesdonotneedit.Self-synchronizing scramblers havebeenusedsuccessfully withoutanypriorrandomiza­ tionofthesouree.·Inthissectionweconsider theoperation ofthe scrambler \\~thouttheBSCandshowhowadesigner mayuseeq.(15) toestimate therequired scrambler lengthforagivenapplication. Fromeqs.(2)and(5)wededucethattheneteffectofthebinary symmetric channelinFig.3is •<p(a,lao,a"...,a,_,)<1 -.; (17) forallk.Inotherwords,becauseoftheBSCthereremainsasmall uncertainty astothevalueofany"a"bit,eventhoughalltheother "a"bitsmightbeknown.Asshowninthetheorem, thisandthe dissociation property aresufficient toguarantee effective scrambling. Hence,ifthedesigner knewtobeginwiththatthesourceitselfhadthe characteristic •<p(8,180,8"...,8,_,)<1 -.; (18) thennoBSCwouldbenecessary, andeq.(15)couldbeapplieddirectly. Forexample, bitstreams encoded fromanalogwaveforms (suchas frequency-division multiplexed speech)oftenhavesuchaproperty, and avaluefor.couldbeobtained fromthecodingruleandtheamplitude distribution oftheanalogsignal. ForthosecasesinwhichavalueforEcannotbecomputed, letus assumethatthedesigner hasatleastsomeknowledge ofthesource pulsedensity.Hecouldthenproceedbyestimating anominalvaluefor Eandthendecreasing thevaluetoallowsomemargin.Forexample, a sourcewhiehproduces bitstreamsknowntovaryfrom10to90percent Hones"overshortperiods(say,severalhundred bits)wouldhavea nominal •=0.1.Itseemsreasonable toallowatleastoneorderof magnitude Itmargin" intheestimate, resultingint==0.01.Thenfrom Fig.4weseethataneight-stage scrambler shouldbesufficient. AUNIVERSAL DIGITAL DATASCRAMBLER 1863 Ofcourse,estimating Efromthesourcepulsedensity docsnot guarantee thateq.(18)reallyholds,butifthesourcesequence isnot strictlyperiodic (thecasecoveredcomprehensively bySavage), itisa reasonable procedure. Thepointhereisthatevenwhenweareun­ willingtocommitdeliberate errorstoguarantee fixedsourcestatistics, wemaystilluseeq.(15)toestimate howlargeascrambler isrequired. Heuristically speaking, eq.(15)isanexpression forthe"power" of thescrambler, relating theHrandomness" oftheinputandoutputto thenumberofscrambler stages. VlI.CONCLUSIONS Wehaveshownthatatthecostofanarbitrarily smallerrorrateitis possible to"whiten" toanydegreeallthefirst-andsecond-order statistics ofanybinarydigitalsource.Thisrelaxestherestriction frequently foundintheliterature inwhichthedigitalsourceisassumed aprioritoproduce onlyindependent equiprobable symbols. Thekey equation inourresultCeq.(15)Jisusefulwhendesigning astandard self-synchronizing scrambler foragivenapplication. Weleaveunsolved theproblem ofwhether universal scramblers exist fortheM-arysource. VIII. ACKNOWLEDGMENTS IwishtothankM.B.Romeiser foreditorial suggestions andMiss J.M.Michelforassistance incomputer programming. Ialsohadthe benefitofstimulating discussions onthesubjectofscrambling with T.M.ChienandR.J.Deaton. APPENDIX ProofofLemmaI' Forconvenience, weassumethatinFig.2athescrambler initially contains allzeros.Sinceeachscrambler outputbitisultimately a mod~2summation ofselected inputbits,wemaywrite •bll=EhJ;an_/q'-0(19) wherethebinarysequence It,performs theselection. Wenotethatif ao=1anda;=0foralli>0,thenlb.}=11t.1.Butunderthese •Independently ort.heauUlOr, U.Henriksson hasdeveloped5aproofofasimilar lemma. 1864 THEBELLSYSTEM TECHNICAL JOURNAL, DECEMBER 1973 conditions, asdescribed inSectionII,Ib.1willbeamaximal lengtb sequence. Hence,{h.lmustitseUbeamaximallengtb sequence. Nowweconsider thetwooutputbitsb.andbm•Wewishtocount thenumber of"a"bitswhichenteredthesummation forbmbutnot b•.Wehave Since 111>11"(a) (b)(20) m-II-1 mEhiram_I; E!)Ehl;am_1; .1:-0 .I:_m_1I m-n-I nEhka"'_k E!)Ehm_n+l.:a,,_k .1:-0 .1:-0(21) Examination ofthesubscript rangeshowsthataUthe"aubits selected bythefirstsummation ineq.(21)areuniquetobm•Bycom­ paringthesecondsummation witheq.(2Oa)weseethattheadditional "allbitswhichenterb",butnotb"arethoseforwhich Hence, m-n_1 ,. L:h,+L:[hm_.+,-hm_'+kh,], .1:-0 .1:-0 or Jmn=m-n_1 n nLItk+LItm_n+k-Lhm_n+kh k, k_O k-O k_O(22) whereaddition isnowintheusualsense. Weexamine thisexpression indetail,recalling thatthesequence Ih,1hasperiodp~(2Af-1)andthegivenconditionn>2M+I. Case(1):If11l-n=Kp,K=1,2,"',then foraUvaluesofk.Hencethesecondandthirdsummations cancel.But thenthefirstsummation contains Kperiodsofamaximal length sequence. Sinceeachperiodcontains exactly 2(M-1)ones, ISthefirst summation totalsatleast2(Af-o. Case(2):If11l-n'"Kp,thenitiseasilyshown'thatthesequence formedbytheterm-by-term product hm_.+,h, hasperiodpandcon- AUNIVERSAL DIGITAL DATASCRAMBLER 1865 tams2(iLf-2)onesperperiod.Thesequence Ihrn-"+k} contains 2CiLf-1) onesperperiod.Hencethenetcontrihution ofthesecondandthird summations is2(Af-2lonesperperiod.Sincen>2M+1>2p,the summations coveratleasttwoperiods.Thustheirnettotalisatleast 2(M-I). Thusforeithercase, Jomin[Jm.]=2M-I• m,">ZJI+I REFERENCES 1.Savagel... J.E.,IlSomeSimpleSelf-Synchronizing DigitalDataScramblers," B.S.T.J., 4-6,No.2(February 1967),pp.449-487. 2.Gallager, R.G.,InjQnnation TheoryandRel'iable Commum"cation, NewYork: JohnWileyandSons,1968,pp.225-238. 3.Peterson, W.W.,ErrorCorrecting Codes,Cambridge: M.LT.Press,1961,pp. 251-270. 4.Fracassi, R.0.,andTammaru, T.,"Megabit DataServicewiththe306AData Set,"BellLaboratories Record, 49,No.10(November 1971),pp.310-315. 5.Henriksson, D.,"On0.Scrambling Property ofFeedback ShiftRegi8ters," IEEE Trans.onCommun. eo,No.5(October 1972),pp.998-1001. 6.Golomb, S.W.,ShiftRegisterSequences, SanFrancisco: Holden-Day, 1967,pp. 23-59,88.