Secure Communications ontheBattlefield?GaryKrahnHistoryFor two days in June 1942, the fate of the U.S.Fleet (rebuilt since Pearl Harbor)hungonthemeaningoftwoletters-AF.BetweenDecember1941andJune1942,theJapaneseNavyunderthecommandofAdmiralYamamotohadsweptfromonevictorytoanother.Yamamotoknewit was essentialtoachievevictoriesinrapidsuccession.Giventime,Americacould starveJapanoffuel.At Midway he would deal the U.S.Fleet a crushing defeatthat would put itpermanently out of action.OnMay20,1942Yamamotobroadcasthisplansforthefinal destructionof theU.S.Fleet in a series of orders to his own fleet.At the same time the U.S.Combat IntelligenceUnit atPearlHarbor startedtobreak intothestreamoffive-digitcodegroupsthatconcealedtheadmiral'sintentions.Theprojectedbattlebegan to emerge, however, the when and where remained hidden in mysteriouslettergroups that defied analysis.Thekey location was coded:AF.TheU.S.cryptounitemployed oneof theoldesttricks inthebook.Usinga codethattheyknewthe Japanesehad alreadybroken,theyarranged fortheU.sGarrison on Midwayto broadcast the news that they wereshortoffresh water.Two days later, Yamamoto broadcasts to his fleet,"AF is short of freshwater.AdmiralNimitzwasnowabletogethisfleettoMidwayand surprisetheJapanese.TheAmericans destroyed all fourofthebig JapaneseaircraftcarriersthathadattackedPearlHarbor.AsAdmiralNimitzlaterobserved"Midwaywasa victory of intelligence."IntroductionOnthebattlefield wemusthavetheabilitytotransmitinformationquicklyandsecurely.Information managementis acombat multiplier that is critical toimplementingtheprincipalsofmaneuversurprise,andinitiativeonthemodernbattlefield.Successfulmilitaryunitsmustbeableto sendinformation ina disguisedform sothat only the intended recipientscanremovethedisguiseandreadthemessage.Whetherpositioning units,215
215 Secure Communications on the Battlefield? Gary Krahn History For two days in June 1942, the fate of the U.S. Fleet (rebuilt since Pearl Harbor) hung on the meaning of two letters - AF. Between December 1941 and June 1942, the Japanese Navy under the command of Admiral Yamamoto had swept from one victory to another. Yamamoto knew it was essential to achieve victories in rapid succession. Given time, America could starve Japan of fuel. At Midway he would deal the U.S. Fleet a crushing defeat that would put it permanently out of action. On May 20, 1942 Yamamoto broadcast his plans for the final destruction of the U.S. Fleet in a series of orders to his own fleet. At the same time the U.S. Combat Intelligence Unit at Pearl Harbor started to break into the stream of fivedigit code groups that concealed the admiral’s intentions. The projected battle began to emerge, however, the when and where remained hidden in mysterious letter groups that defied analysis. The key location was coded: AF. The U.S. crypto unit employed one of the oldest tricks in the book. Using a code that they knew the Japanese had already broken, they arranged for the U.S. Garrison on Midway to broadcast the news that they were short of fresh water. Two days later, Yamamoto broadcasts to his fleet, “AF is short of freshwater.” Admiral Nimitz was now able to get his fleet to Midway and surprise the Japanese. The Americans destroyed all four of the big Japanese aircraft carriers that had attacked Pearl Harbor. As Admiral Nimitz later observed: “Midway was a victory of intelligence.” Introduction On the battlefield we must have the ability to transmit information quickly and securely. Information management is a combat multiplier that is critical to implementing the principals of maneuver, surprise, and initiative on the modern battlefield. Successful military units must be able to send information in a disguised form so that only the intended recipients can remove the disguise and read the message. Whether positioning units
disseminatinglogistics,or coordinatingan attack,secure information isvital formilitaryoperations.TheWord Cryptographyis fromthe Greek‘kryptos(hidden)and'graphein'(towrite).Thetraditionalgoalofcryptographyhasbeentoensureprivacyincommunication by transforming data to render it unintelligible to all but theintended recipient.This can be achieved through the use of an encodingschemethatreliesona secretkeyknownonlybythe senderand intendedrecipient.Themessagewewanttosendiscalledtheplaintextandthedisguisedmessage iscalledtheciphertext.Themessagemaybeformedbyusing onlythefamiliarsymbolsA-Z.If wedon't includeblanks,however,thenall of the words are run together and the messages are harderto read.Theprocess of converting a plaintext to a ciphertextis called enciphering orencryption,andthereverseprocess is calleddeciphering.Supposetheinformationwearetotransmitcomesfromthesetofsymbols(A,B,C,...,Z)Usingbinarycommunicationswecanassociatea sequenceof O'sand1'switheachofthesesymbols.Forexample,A→00000B→ 10100C→00001D→ 01010E→10011G→ 11111.Hence,a101000000001011sequencerepresentsthemessage"BAD."Inthehostile environment of thebattlefieldwe want informationto remainsecret.Furthermore,wewanttodisguisethemessagetotheenemy;however,wewantour friendly units to beable to convert the disguised message into its originalform. We can represent this process by the following simple model:PlainTextChannelCipher TextPlainTextencoderdecoderPlainTextTMMCCAn enciphering transformation is a function that takes aplaintext message andgivesusaciphertextmessage.Inotherwords,itisamappingf fromthesetMofall possibleplaintext messages tothe set c of all possible ciphertextmessages.We can representthistransformation schematicallybythe diagram:Mc→M,where f-1 is the map for deciphering.Exercise O: If the map (f)is nota one-to-onemapping (or function),whatdifficulties may the receiver encounter when using the map f-1 duringdeciphering.216
216 disseminating logistics, or coordinating an attack, secure information is vital for military operations. The Word Cryptography is from the Greek ‘kryptos’ (hidden) and ‘graphein’ (to write). The traditional goal of cryptography has been to ensure privacy in communication by transforming data to render it unintelligible to all but the intended recipient. This can be achieved through the use of an encoding scheme that relies on a secret key known only by the sender and intended recipient. The message we want to send is called the plaintext and the disguised message is called the ciphertext. The message may be formed by using only the familiar symbols A – Z. If we don’t include blanks, however, then all of the words are run together and the messages are harder to read. The process of converting a plaintext to a ciphertext is called enciphering or encryption, and the reverse process is called deciphering. Suppose the information we are to transmit comes from the set of symbols {A, B, C, . . . , Z}. Using binary communications we can associate a sequence of 0’s and 1’s with each of these symbols. For example, A ’ 00000 B ’ 10100 C ’ 00001 D ’ 01010 E ’ 10011 G ’ 11111. Hence, a 10100 00000 01011 sequence represents the message “BAD.” In the hostile environment of the battlefield we want information to remain secret. Furthermore, we want to disguise the message to the enemy; however, we want our friendly units to be able to convert the disguised message into its original form. We can represent this process by the following simple model: Plain Text Channel Cipher Text Plain Text encoder decoder Plain Text M C f ¾¾ ® C M f ¾ ¾ ® - 1 An enciphering transformation is a function that takes a plaintext message and gives us a ciphertext message. In other words, it is a mapping f from the set M of all possible plaintext messages to the set C of all possible ciphertext messages. We can represent this transformation schematically by the diagram: M ¾¾ ® C ¾ ¾ ® M - 1 f f , where f –1 is the map for deciphering. Exercise 0: If the map (f) is not a one-to-one mapping (or function), what difficulties may the receiver encounter when using the map f –1 during deciphering
Solution: Since the map (f) is not one-to-one then f-1is not a functionanditispossibleduringdecipheringthatanencipheredletterismappedtomorethanoneplaintext letter.Therefore,thereceivermaynotbeabletodeterminewithabsolutecertaintytheactual plaintextmessage.Modernhigh-speed communication systems handleinformation inbinaryform.Todisguiseorencipherabinarymessageduringtransmissiononecouldrandomlychangethebitsofthemessage.Anefficienttechnique to encipher is to add, bit by bit modulo 2, arandom binary sequence,S, to themessage,M,generating a ciphertext. The receiver,also knowingS, can then add S to the ciphertext bit by bit modulo 2toretrievetheoriginalmessage,M.This randombinarysequenceScannotbetrulyrandom.It should,however,possesspropertiesassociatedwitharandomprocess.Note:Modulo2additionisdefinedasfollows:1@1=0:1@0=1:0 01 =1; and 0 0 = 0.Example1:Supp0seMisthemessage101000000001011(representingtheword BAD).We definea functionf fromthemessagesettothe ciphersetbyf(M)=M101010101101011.Inotherwords,f addsthesequence(orkey)S=101010101101011bitbybitmodulo2toMtoformC(M)101000000001011(s)④101010101101011(c)000010101100000ThereceiverdecipherstheciphertextCbyaddingthekey Smodulo2to ctorecreatethemessageM.(c)000010101100000(s)④101010101101011101000000001011(M)If the key, S, is random-looking then the resulting ciphertext, C, tend to berandom-like.Wemayapplythekeytomanymessagesthroughout someperiodofoperations.Therefore,there isa need forhigh-speed techniques togeneraterandom-likesequences.Oneof thesimplestandmostefficientdevicesforgenerating or modeling deterministic,randomlooking sequencesof o0's and 1'sis the shift-register.Theusefulnessofsequencesgeneratedbyashift-registerdepends inlargepartontheir randomness properties.In a sense,no finitesequence istrulyrandom.217
217 Solution: Since the map (f) is not one-to-one then f –1 is not a function and it is possible during deciphering that an enciphered letter is mapped to more than one plaintext letter. Therefore, the receiver may not be able to determine with absolute certainty the actual plaintext message. Modern high-speed communication systems handle information in binary form. To disguise or encipher a binary message during transmission one could randomly change the bits of the message. An efficient technique to encipher is to add, bit by bit modulo 2, a random binary sequence, S, to the message, M, generating a ciphertext. The receiver, also knowing S, can then add S to the ciphertext bit by bit modulo 2 to retrieve the original message, M. This random binary sequence S can not be truly random. It should, however, possess properties associated with a random process. Note: Modulo 2 addition is defined as follows: 1 Å 1 = 0; 1 Å 0 = 1; 0 Å 1 = 1; and 0 Å 0 = 0. Example 1: Suppose M is the message 10100 00000 01011 (representing the word BAD). We define a function f from the message set to the cipher set by f (M) = M Å 10101 01011 01011. In other words, f adds the sequence (or key) S =10101 01011 01011 bit by bit modulo 2 to M to form C. 10100 00000 01011 ( M ) Å 10101 01011 01011 ( S ) 00001 01011 00000 ( C ) The receiver deciphers the ciphertext C by adding the key S modulo 2 to C to recreate the message M. 00001 01011 00000 ( C ) Å 10101 01011 01011 ( S ) 10100 00000 01011 ( M ) If the key, S, is random-looking then the resulting ciphertext, C, tend to be random-like. We may apply the key to many messages throughout some period of operations. Therefore, there is a need for high-speed techniques to generate random-like sequences. One of the simplest and most efficient devices for generating or modeling deterministic, random looking sequences of 0’s and 1’s is the shift-register. The usefulness of sequences generated by a shift-register depends in large part on their randomness properties. In a sense, no finite sequence is truly random
In particular, no sequence that depends on a few parameters, such as thefeedbackconnectionsofa linearfeedbackshift-register,canbeconsideredtrulyrandom.SolomonW.Golombintroducedthenamepseudo-randomforperiodicbinarysequencesbecausetheysatisfythethreerandomnesspropertiesofbalance,runs,andcorrelation.Wewilldiscussthesepropertieslater.FeedbackShift-RegisterDesignAbinaryshift-registerof spann isa collection(w():i=o,1,...,n-1)ofn-storageregisters eachcapableof holding a valuefromthe set(0,1).Thecontentsofthen-storage registers, the n-tuple (s, Sj+1, .:, Sj+n-1), is denoted as the state of theregister at time j for each j≥ 0. An example is shown in Figure 1.WiWo02Figurel:nStorageDevicesThereisafeedbackrulecomputedfromthecontentsofthen-storageregisterscalledthefeedbackfunction(Figure2).If thefeedbackfunction isf(Sj, Sj+1, .., Sj+n-1) = Sj+n= CoS,@ CiSj+1@... Cn-1 Sj+n-1=Zesat,O≤j,k=0where the coefficients co, C1, .,and c n-1 are 1's or O's, and the summation ismodulo2additionthe shift registeris called linear.WiWoW2W3Wn-2Wnr-10：00工1Ic3coIciIc2ICn-2Cn-1f(s, Sj+1 .++, S+n-1)Figure2:FeedbackShift-RegisterModelAtthepulseofanexternal clockthecontentofthestorageregisterWi+isshiftedintowifori=0,1,..:,n-2andthevalueofthecomputedfeedbackfunctionf (sj, Sj+1, :..,Sj+n-1) is shifted into storage register Wn-1.Example2:Usingtheabovenotation,letn=4,Co=C=1,C2=C3=0.Thus,S+4=s, Sj+1 modulo 2.The wiring of this linear feedback shift-register (LFSR) isWoWW2W[sjS卜H Sj+2 I Sj+3S-4= s,@ S+1218
218 In particular, no sequence that depends on a few parameters, such as the feedback connections of a linear feedback shift-register, can be considered truly random. Solomon W. Golomb introduced the name pseudo-random for periodic binary sequences because they satisfy the three randomness properties of balance, runs, and correlation. We will discuss these properties later. Feedback Shift-Register Design A binary shift-register of span n is a collection {w(i): i = 0,1, . . . , n-1} of nstorage registers each capable of holding a value from the set {0,1}. The contents of the n-storage registers, the n-tuple (sj, sj+1, . . . , sj+n-1), is denoted as the state of the register at time j for each j ³ 0. An example is shown in Figure 1. w0 w1 w2 w3 wn-2 wn-1 1 0 0 1 . . . 1 0 Figure 1: n Storage Devices There is a feedback rule computed from the contents of the n-storage registers called the feedback function (Figure 2). If the feedback function is f (sj, sj + 1, . . . , sj + n - 1) = sj + n = c0sj Å c1sj + 1 Å . . . Å c n – 1 sj + n – 1 = , 0 , 1 0 c s j j k n k k + £ - = å where the coefficients c0, c1, . . . , and c n -1 are 1’s or 0’s, and the summation is modulo 2 addition the shift register is called linear. w0 w1 w2 w3 wn-2 wn-1 1 0 0 1 . . . 1 0 c0 c1 c2 c3 cn-2 cn-1 f (sj, sj + 1, . . . , sj + n - 1) Figure 2: Feedback Shift-Register Model At the pulse of an external clock the content of the storage register wi + 1 is shifted into wi for i =0, 1,. . . , n-2 and the value of the computed feedback function f (sj, sj + 1, . . . , sj + n - 1) is shifted into storage register wn-1. Example 2: Using the above notation, let n = 4, c0 = c1 = 1, c2 = c3 = 0. Thus, sj+4 = sj Å sj+1 modulo 2. The wiring of this linear feedback shift-register (LFSR) is w0 w1 w2 w3 sj sj+1 sj+2 sj+3 sj+4 = sjÅ sj+1
Figure3:ALinearFeedbackShift-RegisterModelNote:theconnectionsfromSi+2andSi+3areopensinceC,=0andC=0.Successiveiterations fromthe initial configuration inFigure3look like:WoW1W3W2SoS1S2S3TICKOFTHECLOCKWoWiW2W3S2S1S3S4TICKOFTHECLOCKwoWiW2W3S2S3S4SsThesuccessoroftheregisterfillvectorSo,S1,...,Sn-1isthevector.S,S2,..,Sn,wherethevalueSnisthecomputedfeedbackfunctionf(so,S1,..:,Sn-1).TogeneratesuccessivestatesweiteratethisprocedureWitheachtickoftheclock,theregistercompletesanotherstepthroughasequence of states.If we set the initial fll of the register to be 0001,such thatSo=0, si=0, S2=0, and s3= 1, then the successive states of the register are:00010I010100l10011001001111011010001110110111111110I11101000100001Forthisexample,thestatesequenceofregisterfillsrepeatswithaperiodof15The history ofstage w3,whichis underlined, is the sequence(100110101111000),periodicallyrepeated.IfthecontentsoftheregisterareinitiallynotallO's,thelinearshift-registerwillcyclethroughall15differentstatesbefore repeating itself. Ingeneral, it is possibleto constructa span n linear219
219 Figure 3: A Linear Feedback Shift-Register Model Note: the connections from sj+2 and sj+3 are open since c2 = 0 and c3 = 0. Successive iterations from the initial configuration in Figure 3 look like: w0 w1 w2 w3 s0 s1 s2 s3 TICK OF THE CLOCK w0 w1 w2 w3 s1 s2 s3 s4 TICK OF THE CLOCK w0 w1 w2 w3 s2 s3 s4 s5 The successor of the register fill vector s0, s1, . . . , sn-1 is the vector s1, s2, . . . , sn, where the value sn is the computed feedback function f (s0, s1, . . . , sn-1). To generate successive states we iterate this procedure. With each tick of the clock, the register completes another step through a sequence of states. If we set the initial fill of the register to be 0001, such that s0 = 0, s1= 0, s2 = 0, and s3 = 1, then the successive states of the register are: 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 0 0 0 1 For this example, the state sequence of register fills repeats with a period of 15. The history of stage w3, which is underlined, is the sequence {100110101111000}, periodically repeated. If the contents of the register are initially not all 0’s, the linear shift-register will cycle through all 15 different states before repeating itself. In general, it is possible to construct a span n linear
shift-register of the form in Figure 2that will cycle through all 2"-1 different statesbeforerepeatingitselfforeveryn≥1.Associatedwitheachlinearfeedbackshift-register(LFSR)isthecharacteristicpolynomialC(x)= f(x)= x"Cj=0InExample2thecharacteristicpolynomialisx+x+1.Exercise1:Explainwhyanylinearshift-registerofspannwill generateasequencethatis ultimately periodic witha period p≤2"-1.(Sequencesbeingthehistoryofa selected storageregister.)Solution:Each state of theshift register is completelydetermined bytheprevious state andthefeedbackfunction.Sincethereare only afinitenumberofstates,somestatemusteventuallyrepeat.Workingwithn-stage shift registerswith O's and 1's,the size of the possible statesetis2"The linearityof thefeedback function guaranteesthatthe all zerostate is always its own successor.Therefore,thelongest possible shiftregister cyclecontainsall ofthenonzero states,andisperiodicofperiod2"-1.Asequencegenerated by a linear feedback shift-register of span nhaving aperiod2"-1iscalled a maximumlength linearshift registersequenceormoresimplyanm-sequence.Exercise2:ConstructtheLFSRwiththecharacteristicpolynomialx3+1Furthermore,if the initial state of this shift-register is 001,write the periodicsequence that it generates.Solution: : Using the above notation, let n = 3, Co= 1, C2=0Thus, Sj+3 = s, modulo 2. The wiring of this LFSR is as follows:WoWiW2S3Sj43= SjThe sequence is 100 of period 3. This LFSR does not generate anm-sequenceoflength7220
220 shift-register of the form in Figure 2 that will cycle through all 2n -1 different states before repeating itself for every n ³ 1. Associated with each linear feedback shift-register (LFSR) is the characteristic polynomial j n j j n C x f x x å c x - = = = + 1 0 ( ) ( ) . In Example 2 the characteristic polynomial is 1. 4 x + x + Exercise 1: Explain why any linear shift-register of span n will generate a sequence that is ultimately periodic with a period p £ 2n -1. (Sequences being the history of a selected storage register.) Solution: Each state of the shift register is completely determined by the previous state and the feedback function. Since there are only a finite number of states, some state must eventually repeat. Working with n-stage shift registers with 0’s and 1’s, the size of the possible state set is 2n . The linearity of the feedback function guarantees that the all zero state is always its own successor. Therefore, the longest possible shift register cycle contains all of the nonzero states, and is periodic of period 2 n –1. A sequence generated by a linear feedback shift-register of span n having a period 2 n –1 is called a maximum length linear shift register sequence or more simply an m-sequence. Exercise 2: Construct the LFSR with the characteristic polynomial 1. 3 x + Furthermore, if the initial state of this shift-register is 001, write the periodic sequence that it generates. Solution: : Using the above notation, let n = 3, c0 = 1, c2 = 0. Thus, sj+3 = sj modulo 2. The wiring of this LFSR is as follows: w0 w1 w2 sj sj+1 sj+2 sj+3 = sj The sequence is 100 of period 3. This LFSR does not generate an m-sequence of length 7
Exercise 3: Construct the LFSR with the characteristic polynomial x + x +1.Furthermore,ifthe initial state of theshift-registeris 001,write the periodicsequencethatis generatedSolution: Using the above notation, let n = 3, Co =1, C2 = 1. Thus,Sj+3= s, @ Sj+1 modulo 2. The wiring of this LFSR is as follows:WiW2WoS+1Sj+2rSiSj+3= s,@ Sj+1Thesequenceis1011100ofperiod7.ThisLFSRdoesgenerateanm-sequenceoflength7.RandomnessPropertiesofm-sequencesThe usefulness ofm-sequences depends inlargeparton theirhavingnearlyideal randomness properties.The randomness properties that we would likeasequence to have are given below.TheBalance Property:Ina sequence thenumber of ONEs is the same as thenumberofZEROs.The Run Property: Among the runs of ONEs and ZEROs in a sequence, one-halfthe runs are of length one, one-fourth are of length two, one-eighth are of lengththree, and so on, as long as these fractions give meaningful number ofruns.TheCorrelationProperty:Whenasequenceiscomparedterm-by-termwithacyclicallyshiftedversionofthesame sequence,thenumberofagreementsequalsthenumberofdisagreements.Wewill discoverthatm-sequences satisfytheaboverandomnesspropertiesascloselyaspossibleforeachperiodofthesequence.Exercise 3: Given that every non-zero n-tuple is seen as a state within a LFSRexactlyonce during thegeneration ofan m-sequence,explainwhythebalancepropertyholdsfor everym-sequence.In particular, there are 2-1ONEs and2-1-1 ZEROs in an m-sequence of length 2"-1.Solution:Annstageshift-registergeneratinganm-sequencecyclesthrough all2"-1 states before it repeats.Indecimal notation,eachstatecan be thought of representing an integer from1 to2"-1.From1to2" -1 there are 2n-1 odd integers and 2n-1 even integers. Thus, an221
221 Exercise 3: Construct the LFSR with the characteristic polynomial 1. 3 x + x + Furthermore, if the initial state of the shift-register is 001, write the periodic sequence that is generated. Solution: Using the above notation, let n = 3, c0 = 1, c2 = 1. Thus, sj+3 = sj Å sj+1 modulo 2. The wiring of this LFSR is as follows: w0 w1 w2 sj sj+1 sj+2 sj+3 = sjÅ sj+1 The sequence is 1011100 of period 7. This LFSR does generate an m-sequence of length 7. Randomness Properties of m-sequences The usefulness of m-sequences depends in large part on their having nearly ideal randomness properties. The randomness properties that we would like a sequence to have are given below. The Balance Property: In a sequence the number of ONEs is the same as the number of ZEROs. The Run Property: Among the runs of ONEs and ZEROs in a sequence, one-half the runs are of length one, one-fourth are of length two, one-eighth are of length three, and so on, as long as these fractions give meaningful number of runs. The Correlation Property: When a sequence is compared term–by–term with a cyclically shifted version of the same sequence, the number of agreements equals the number of disagreements. We will discover that m-sequences satisfy the above randomness properties as closely as possible for each period of the sequence. Exercise 3: Given that every non-zero n-tuple is seen as a state within a LFSR exactly once during the generation of an m-sequence, explain why the balance property holds for every m-sequence. In particular, there are 2n-1 ONEs and 2 n-1 –1 ZEROs in an m-sequence of length 2n –1. Solution: An n stage shift-register generating an m-sequence cycles through all 2n –1 states before it repeats. In decimal notation, each state can be thought of representing an integer from 1 to 2n –1. From 1 to 2 n –1 there are 2n-1 odd integers and 2n-1 even integers. Thus, an
m-sequencecontains2n-1ONEsand2-1-1ZEROsandwill thereforealwayspossessthebalanceproperty.Example3:Givenbelowisanm-sequenceoflength63generatedfromaspann=6LFsR.Markedonthesequencearetherunsoflengthgreaterthan2.10100100111000101111001010001100001000001111110100110011022Exercise4:InExample3there area total of32 runs,includingthesingletonruns.Onehalfoftheruns(16)areoflengthone,onefourth (8)areof lengthtwo,oneeighth (4)areof length three,and one sixteenth (2)are of lengthfour.ForeachoftheselengthsthereareequallymanyrunsofZEROsandONEs.Finally,there is onerun offive consecutiveZEROs andone of six consecutive ONEsExplainwhytherunpropertyholdsforall m-sequences.Solution:In an m-sequence of period 2"_1, every non-zeron-tupleoccurs exactlyonce.Ifthen-tuple oo0...0occurs,thesequencewillremain forever in the state 000...0.Therefore,the n-tuple, 000...0,neversoccursinanm-sequence.Sinceeverynon-zeron-tupleoccurs,the n-tuple 111...1 must occur exactly once witha zero preceding andfollowing this all ONE n-tuple. The (n+2)-tuple, 011...10, contains then-tuples [011...1]10 and 01[1...110]. These n-tuples are not repeatedelsewhere inthesequence.Hence,there canbeno runofn-1ONEs inthesequence.However,thereisexactlyonerunoflengthn-1ofZEROs,representedinthe consecutiven-tuple 10...00and 00...01NowconsidertherunsofONEsandlengthrwhere0<r≤n-2.Eachsuchruncanbemadeto correspondton-tuplesof thetype011...10xx...x.n-r-where the x's are arbitrary bits.The number of such n-tuples of runlength ris 2n-2.A similar argument gives the same number of runs ofZEROsoflengthr.Thiscompletelydeterminestherunstructureofm-sequences.Experiment: Compare an m-sequence (si) with a cyclic shift of itself. Thiscomparisonis called autocorrelation.Supposeanm-sequenceisaddedtoitselfbit bybitusingmodulo2addition.Whenthe sequenceis added in phasewithitself, weget the null sequence.When the sequenceis added to each out ofphaseshift ofthe sequenceamiracleoccurs.Whatisthismiracle?Explain.Dom-sequenceshavethecorrelationproperty?Explain.222
222 m-sequence contains 2n-1 ONEs and 2n-1 –1 ZEROs and will therefore always possess the balance property. Example 3: Given below is an m-sequence of length 63 generated from a span n = 6 LFSR. Marked on the sequence are the runs of length greater than 2. 4 5 2 2 3 4 3 3 2 2 2 3 2 2 6 2 111111010101100110111011010010011100010111100101000110000100000 Exercise 4: In Example 3 there are a total of 32 runs, including the singleton runs. One half of the runs (16) are of length one, one fourth (8) are of length two, one eighth (4) are of length three, and one sixteenth (2) are of length four. For each of these lengths there are equally many runs of ZEROs and ONEs. Finally, there is one run of five consecutive ZEROs and one of six consecutive ONEs. Explain why the run property holds for all m-sequences. Solution: In an m-sequence of period 2n –1, every non-zero n-tuple occurs exactly once. If the n-tuple 000. 0 occurs, the sequence will remain forever in the state 000. 0 . Therefore, the n-tuple, 000. 0, nevers occurs in an m-sequence. Since every non-zero n-tuple occurs, the n-tuple 111. 1 must occur exactly once with a zero preceding and following this all ONE n-tuple. The (n+2)-tuple, 011. 10, contains the n-tuples [011. 1]10 and 01[1. 110]. These n-tuples are not repeated elsewhere in the sequence. Hence, there can be no run of n-1 ONEs in the sequence. However, there is exactly one run of length n-1 of ZEROs, represented in the consecutive n-tuple 10. 00 and 00. 01. Now consider the runs of ONEs and length r where 0 < r £n - 2 . Each such run can be made to correspond to n-tuples of the type 2 011.10 . r n- rxx x where the x’s are arbitrary bits. The number of such n-tuples of run length r is 2n-r-2 . A similar argument gives the same number of runs of ZEROs of length r. This completely determines the run structure of m-sequences. Experiment: Compare an m-sequence {si} with a cyclic shift of itself. This comparison is called autocorrelation. Suppose an m-sequence is added to itself bit by bit using modulo 2 addition. When the sequence is added in phase with itself, we get the null sequence. When the sequence is added to each out of phase shift of the sequence a miracle occurs. What is this miracle? Explain. Do m-sequences have the correlation property? Explain
Solution:When the sequence is added to each out of phase shift of thesequence,the resulting sequence is a non-zero sequence that is ashiftedversion oftheoriginal sequence.This propertyisknown astheShift-and-Addproperty.Forexample,1011100,denoted by(si,is anm-sequence. Let [si+1) denoted the sequence [si) shifted to the left byone bit. We find that [Si+1} = 0111001. When [Si+1) and [si) are addedmodular 2 (bit by bit) the resulting sequence is 1100101. A (1) in theresulting sequence meansthat (si+t) and (sidisagreed inthatpositionwhile a (O) means that (si+1) and (si) agreed in that position. Since theresultingsequenceisanm-sequenceitfollowsthatthenumberofagreementsand disagreementsbetweenan m-sequenceandashiftedversion ofthe samem-sequence are justabout equal.Hence,m-sequencespossessthecorrelationproperty.Examplesoftheshift-and-addpropertyaregivenbelow:101110010111001011100SoSoSoS1S2S4④0111001④1110010④1001011110010101011100010111S3S6S5We saythat the shift-and-add pairs for the sequence 1011100 are (1,3), (2,6),and (4,5),e.g.,thesequence1011100addedmodulo2toashifted (by3)version of itself produces a shifted (by 1)version of itself.Becausem-sequencessatisfythethreerandomness propertiestheyaresometimes referredtoaspseudo-random orpseudo-noise sequences.Moreover,m-sequences arethe onlydeterministicsequencesthathavetherandomnesspropertiesanddistinctn-tuples ineachperiodoflength2"_1.Exercise5:Let us saya segmentfrom anunknown m-sequence(S)is added toa shifted (by 3) version of itself:(S)101011101100...0111110011Unknownm-sequence(S3)011101100011...1110011010shiftof3shiftof5(Ss)110110001111...1001101001Wecanseethat (3,5)isa shiftandaddpairfor the sequence (S).Furthermore,the sumS@S3@Ss=000...0000, the all zero sequence.(S)101011101100...0111110011Unknownm-sequence(S3)011101100011...1110011010shift of 3shift of 5(Ss) @ 110110001111. : .1001101001SUM000000000000000000000000223
223 Solution: When the sequence is added to each out of phase shift of the sequence, the resulting sequence is a non-zero sequence that is a shifted version of the original sequence. This property is known as the Shift-and-Add property. For example, 1011100, denoted by {si}, is an m-sequence. Let {si+1} denoted the sequence {si} shifted to the left by one bit. We find that {si+1} = 0111001. When {si+1} and {si} are added modular 2 (bit by bit) the resulting sequence is 1100101. A (1) in the resulting sequence means that {si+1} and {si} disagreed in that position while a (0) means that {si+1} and {si} agreed in that position. Since the resulting sequence is an m-sequence it follows that the number of agreements and disagreements between an m-sequence and a shifted version of the same m-sequence are just about equal. Hence, m-sequences possess the correlation property. Examples of the shift-and-add property are given below: s0 1011100 s0 1011100 s0 1011100 s1 Å 0111001 s2 Å 1110010 s4 Å 1001011 s3 1100101 s6 0101110 s5 0010111 We say that the shift-and-add pairs for the sequence 1011100 are (1,3), (2,6), and (4,5), e.g., the sequence 1011100 added modulo 2 to a shifted (by 3) version of itself produces a shifted (by 1) version of itself. Because m-sequences satisfy the three randomness properties they are sometimes referred to as pseudo-random or pseudo-noise sequences. Moreover, m-sequences are the only deterministic sequences that have the randomness properties and distinct n-tuples in each period of length 2n –1. Exercise 5: Let us say a segment from an unknown m-sequence (S) is added to a shifted (by 3) version of itself: (S) 101011101100. . .0111110011 Unknown m-sequence (S3) Å 011101100011. . .1110011010 shift of 3 (S5) 110110001111. . .1001101001 shift of 5 We can see that (3,5) is a shift and add pair for the sequence (S). Furthermore, the sum S Å S3 Å S5 = 000. . . 0000, the all zero sequence. (S) 101011101100. . .0111110011 Unknown m-sequence (S3) 011101100011. . .1110011010 shift of 3 (S5) Å 110110001111. . .1001101001 shift of 5 000000000000000000000000 SUM
What if the unknown m-sequence (S) was copied by a person who on theaverage made 10%errors inthe sequence atrandomas she records thesequence(S')fromadigital communicationnetwork.Themod2sumof(S')andthe sequence of shifts of 3and 5,i.e.,S'@ S'@ S's=Z would no longer be thezero sequence.In fact, it would give us a sequence (2) with some percentage ofones. How would you estimate the density of ones in (2) if (3,5) was truly ashift-and-add pair of (S)?Solution:The sequence (S)is subjected torandomerrors at arate of10%.That is,the probability that each bit inthe original sequence (S),and in the shifted sequences, is in error is (.10). If the shifts of 3 and 5constituteavalidshiftandaddpairthenS@S3@Ssisthezerosequence. The rows ofthematrix [A] beloware composed of S, S,andS5.101011101100...0111110011011101100011...1110011010110110001111...1001101001The probability that column (i) in matrixA contains :1.One error is=.243(.1)(.9)(.9) C(3,1)2. Two errors is=.027(.1)(.1)(.9) C(3,2)= .0013.Threeerrorsis(.1)(.1)(.1)4. Zero errors is(.9)(.9)(.9)=.729Note: C(n,r) = (n !) / r !(n-r)! is the number of different ways of selecting (r)elementsfromasetwith(n)elements.Sincethesummationismod2,oneorthreeerrorsincolumn(willgenerateaoneinthesequence (2).Therefore,thedensityofones in (2)is approximately24.4%.Exercise 6: Given that someone has injected 20% errors in an m-sequence (S)how would you verify that (a,b)is a shift-and-add pair for (S)?Solution: Using the same analysis as above, if (a,b) is a shift-and-addpair for the sequence S,we would findthatSS@Ss would have39.2% errors, since (.2)(.8)(.8)C(3,1) + (.2)(.2)(.2)=.392. If (a,b) is nota shift-and-add pair S @ S @ Ss would have nearly 50% errors.Aswehaveseen,m-sequenceshavesomeveryinterestingproperties.Fornearlyfourdecades the ideaof using shift registers to generatesequences of1'and 0's has been explored, developed, and refined.There are, however, manymorepropertiestobediscovered.Bonappetite!224
224 What if the unknown m-sequence (S) was copied by a person who on the average made 10% errors in the sequence at random as she records the sequence (S’) from a digital communication network. The mod 2 sum of (S’) and the sequence of shifts of 3 and 5, i.e., S’Å S’3 Å S’5 = S would no longer be the zero sequence. In fact, it would give us a sequence (S) with some percentage of ones. How would you estimate the density of ones in (S) if (3,5) was truly a shift-and-add pair of (S)? Solution: The sequence (S) is subjected to random errors at a rate of 10%. That is, the probability that each bit in the original sequence (S), and in the shifted sequences, is in error is (.10). If the shifts of 3 and 5 constitute a valid shift and add pair then S Å S3 Å S5 is the zero sequence. The rows of the matrix [A] below are composed of S, S3, and S5. The probability that column (i) in matrix A contains : 1. One error is (.1)(.9)(.9) C(3,1) = .243 2. Two errors is (.1)(.1)(.9) C(3,2) = .027 3. Three errors is (.1)(.1)(.1) = .001 4. Zero errors is (.9)(.9)(.9) = .729 Note: C(n,r) = (n !) / r !(n-r)! is the number of different ways of selecting (r) elements from a set with (n) elements. Since the summation is mod 2, one or three errors in column (i) will generate a one in the sequence (S). Therefore, the density of ones in (S) is approximately 24.4%. Exercise 6: Given that someone has injected 20% errors in an m-sequence (S), how would you verify that (a,b) is a shift-and-add pair for (S)? Solution: Using the same analysis as above, if (a,b) is a shift-and-add pair for the sequence S, we would find that S Å S3 Å S5 would have 39.2% errors, since (.2)(.8)(.8)C(3,1) + (.2)(.2)(.2) = .392. If (a,b) is not a shift-and-add pair S Å S3 Å S5 would have nearly 50% errors. As we have seen, m-sequences have some very interesting properties. For nearly four decades the idea of using shift registers to generate sequences of 1’and 0’s has been explored, developed, and refined. There are, however, many more properties to be discovered. Bon appetite! ú ú ú û ù ê ê ê ë é = 110110001111.1001101001 011101100011.1110011010 101011101100.0111110011 A