save of scrambler old 2_5 REVD

Save of Old Section 2.5 of scrambler PhL 7.21.13 Review this for anything important omitted from its replacement: DONE There is no need to ever look at this doc again. 2.5 Autocorrelation, Probability, and Statistics for a sequence in {0,1} and {-1,1} The Autocorrelation Sequence for a Periodic Sequence The autocorrelation function for a continuous signal a(t) was defined in FT (32.1), where we omitted any kind of normalizing factor, rx(t) ≡ !Syntax Error, I dt' x(t') x(t' + t) // = rx(-t) FT (32.1) Although we did not use this terminology in FT, it should be clear that one can define an exactly corresponding "digital" autocorrelation sequence having the following form: rk ≡ // = r-k (2.5.1) At this point, we still imagine that an = a(tn) is a sample of an analog signal. The sum converges if the sequence tapers off sufficiently in the past and future. For a sequence of numbers which are elements of some finite set, the only way to make something "taper off" is to have it be zero before some time in the past and after some time in the future. For a periodic sequence (such as an MLS sequence) the above definition of rk cannot possible converge, so we replace it with the following definition where the sum is over one period of the periodic sequence: rk ≡ (1/P) . (2.5.2) P is the period of the periodic sequence and for an MLS sequence P = 2k - 1. Here it is implied that if an+k takes us off the end of the sequence, we wrap to the beginning of the sequence, just as if the sequence repeated forever in time. The sum shown above is obviously the average value of the product anan+k for a periodic sequence which we indicate by <anan+k>. So we rewrite the above adding this new notation <anam> = rm-n ≡ (1/P) m ≠n (2.5.3) <an2> = r0 ≡ (1/P) . m = n Quantities like <an> or <an2> don't depend on n since these are averages of some quantity over the sequence, so we can write <an2> = β. A quantity like <anan+k>, however, can possibly depend on the distance k between the two symbol locations n and n+k. This is the case, for example, for the AMI code treated in FT ***. But if there is no correlation between the values of symbols at different locations in the sequence, then <anan+k> is independent of k (as well as n), so we can write it as <anan+k> = α. Thus we can write α = <aman> = rm-n for m ≠ n // uncorrelated β = <an2> = r0 . As we show below, in the uncorrelated case, <aman> = <am><an> = <am>2 = μ2 where μ is the mean value of the symbols ai in the sequence. The variance σ2 of a sequence is σ2 = <an2> - <an>2 = β - μ2, so we can rewrite the above equations to include the mean μ and variance σ2 α = <aman> = μ2 = rm-n for m ≠ n // uncorrelated β = <an2> = (σ2 + μ2) = r0 => σ2 = β - μ2 = (β-α) (2.5.4) For this uncorrelated sequence, we can at once plot the autocorrelation sequence: Here the sequence values ri are at the dots and the red line just interpolates these values. In FT we compute the spectral power density <P(ω)> for an uncorrelated amplitude-modulated pulse train of the form x(t) = !Syntax Error, Ian xpulse(t - nT1). The result is as follows <P(ω)> = Ppulse(ω) [ (β-α) + α !Syntax Error, I2π δ(ωT1- 2πm) ] FT (35.11) where α and β are the quantities shown in (2.5.4). Here Ppulse(ω) is the spectral power density of the underlying pulse xpulse(t) used to make the pulse train. If the pulse train sample spacing is time T1 and if xpulse(t) is square pulse of amplitude 1 and width T1, then Xpulse(ω) = T1 sinc(ωT1/2) Ppulse(ω) = = (T1/2π) sinc2(ωT1/2) FT (36.1) and then we get, for an uncorrelated sequence {an}, <P(ω)> = (T1/2π) sinc2(ωT1/2) [ (β-α) + α !Syntax Error, I2π δ(ωT1- 2πm) ] = (T1/2π) sinc2(ωT1/2) [ (β-α) + α 2π δ(ωT1) ] Apart from a DC line of amplitude α = μ2, the spectrum is entirely continuous. If the amplitudes are selected such that μ = 0, then even the DC line goes away. It turns out that the MLS sequence is not perfectly uncorrelated, so we cannot apply the above theory to get the autocorrelation sequence and the spectral power density. [ this item has been integrated in ] Formula FT (35.11) assumes that the autocorrelation function rk is constant for all non-zero k. If this is not the case, we have to back up to the earlier formula for P(ω), FT (35.2), which is completely general. In fact, this was what we had to do for the AMI line code treated in FT Section 37. We shall soon compute the digital autocorrelation function rk for an MLS sequence, and then use the result in the formulas of FT Chapter 6 to obtain the frequency spectrum of the MLS sequence. But first, we insert the following brief review of "probability and statistics" in relation to <aman> and rk . A few Basics of Probability and Statistics The probability of events A and B both being true is denoted by P(AB), or P(A,B). This is known as the joint second-order probability density function (pdf). A related concept is P(A|B) meaning the conditional probability that A is true given that B is true. Here are the relations: P(A,B) = P(AB) = P(A|B) P(B) = P(B|A) P(A) . (2.5.5) If events A and B are statistically independent, one gets: P(A,B) = P(AB) = P(A) P(B) P(A|B) = P(A), P(B|A) = P(B) . (2.5.6) The result P(A|B) = P(A) means that the probability of A being true is not influenced by whether or not B is true. Similarly one can define joint pdf's of third order and beyond. For example, statistical independence for a third-order pdf is indicated by, P(A,B,C) = P(ABC) = P(A)P(B)P(C) . (2.5.7) Case 1: Symbols in {1,0} The "event" of interest is that an = 1. The sequence {an} has some mean value which we denote by μ. The following shorthand notation is useful: p(an) ≡ P(an=1) = <an> = μ p(an, am) ≡ P(an= 1, am= 1) . (2.5.8) We can now express various mean values in terms of these pdf's: <an> = 1 • P(an=1) + 0 • P(an≠1) = P(an=1) = p(an) = μ (2.5.9a) <an2> = 12 • P(an=1) + 02 • P(an≠1) = P(an=1) = p(an) = μ (2.5.9b) <aman> = 12 • P(am=1,an=1) +3 zero terms = P(am=1,an =1) = p(am, an) . (2.5.9c) If m≠n, it is possible that am and an could be statistically independent. In this case, one would have: <aman> = p(am, an) = p(am) p(an) = <am><an> = μ2 // uncorrelated (2.5.10) For m=n, it is impossible that am and an be statistically independent, and one has: <anan> = p(an, an) = <an2> = p(an) = μ ≠ p(an) p(an) // correlated (2.5.11) In other words, the "diagonal" second-order statistical quantity p(an, an) is really the first-order quantity p(an). We can now write down a few related statistical quantities (we are doing GF(2) symbols here): The moments for N = 0,1,2,3...: m0 = <an0> = <1> = 1 N = 0 mN ≡ <anN> = 1N• P(an=1) + 0N• P(an=1) = p(an) = μ N = 1,2,3.. (2.5.12) The central moments for N = 1,2,3..: μN = < (an - <an>)N> = < (an - μ)N> = < Σj=0N (an)N-j [-μ]j > = Σj=0N (-1)j μj < (an)N-j > = Σj=0N-1 (-1)j μj+1 + (-1)N μN (2.5.13) The N=1,2 central moments μ1 = < (an - <an>)1> = <an> - <an> = μ - μ = 0 μ2 = < (an - <an>)2> = < (an - μ)2> = <an2> - 2μ <an> + μ2 = <an2> - μ2 = μ - μ2 = μ(1-μ) = σ2 = (standard deviation)2 = variance (2.5.14) Thus, in the special case of symbols in GF(2), all moment and central moments are determined by μ. For some different set of symbol values, this might not be the case. In general, a full characterization of a statistical sequence requires specification of the probability density functions of all orders. However, much useful information is contained in the first two orders, and this information is sufficient for many applications. Fact 1: The first and second order statistics are completely determined by the autocorrelation sequence. Proof: Assume that the autocorrelation sequence rk is known. Then, first order: p(an) = <an> = <an2> = r0 // (2.5.9a), (2.5.9b), (2.54) second order: p(an, an) = <an2> = p(an) = r0 // (2.5.9b), (2.54) p(am, an) = <aman> = rm-n m ≠ n // (2.5.4) Corollary 1: Third and higher order statistics are not determined by the autocorrelation sequence. One needs more information to get these higher statistics. Example: Consider the third-order density: p(an, an+k, an+k') = < anan+kan+k'> One could relate this to some kind of fancier 2-variable autocorrelation sequence defined this way, rk,k' ≡ (1/P) Fact 2: For a statistically independent sequence, all higher order statistics are determined by the first order statistics: (p(am) is independent of m ) <aman> = p(am, an) = p(am) p(an) = [p(am)]2 = μ2 m ≠ n <amanak> = p(am, an, ak) = p(am) p(an) p(ak) = [p(am)]3 = μ3 m ≠ n≠ k etc. Proof: This follows from the definition of "statistical independence" given above (= uncorrelated). ok to here Definition: A white sequence over GF(2) is one which is uncorrelated and has p(an) = μ = 1/2. For such a sequence, we have: <an> = p(an) = μ = 1/2 = r0 <aman> = p(am, an) = p(am) p(an) = μ2 = (1/2)2 = 1/4 = rm-n m ≠ n <amanak> = p(am, an, ak) = p(am) p(an) p(ak) = μ3 = (1/2)3 = 1/8 m ≠ n ≠ k etc. (2.5.15) From (2.5.15) here is a plot of the autocorrelation sequence for a white sequence an defined over GF(2): Fig 2.5.1: Autocorrelation function of a white sequence over GF(2) = {0,1}. This fits the general template shown in Fig *** above where α = μ2 = 1/4 and β = σ2+μ2 = μ = 1/2 Case 2: Symbols in {1,-1} It is sometimes convenient to think of the elements of the sequence an as belonging to the set {-1, +1} instead of to the official GF(2) set { 0,1 }. In this case, various statements made above must be modified. For example, P(an = 1) = p(an) ≡ p P(an ≠ 1) = P(an = -1) = 1 - p(an) = 1-p <an> = 1 • p(an) + (-1) • [ 1 - p(an)] = P(an=1) = [ 2 p(an)- 1] = (2p-1) = μ (2.5.9a)' <an2> = 12 • p(an) + (-1)2 • [ 1 - p(an)] = 1 (2.5.9b)' <aman> = 12 • P(am=1,an=1) + 1•(-1) P(am=1,an=-1) + (-1)•1 • P(am=-1,an=1) + (-1)2 P(am=1,an=-1) (2.5.9c)' If m≠n, it is possible that am and an could be statistically independent. In this case, one would have: <aman> = p(am, an) = p(am) p(an) = <am><an> = (2p-1)2 = μ2 // uncorrelated . (2.5.10)' For m=n, it is impossible that am and an be statistically independent, and one has: <anan> = p(an, an) = <an2> = 1 ≠ p(an) p(an) = p2 . (2.5.11)' The moments for N = 0,1,2,3...: m0 = <an0> = <1> = 1 N = 0 mN = <anN> = 1N p(an) + (-1)N [ 1 - p(an)] = p + (-1)N (1-p) N = 1,2,3.. (2.5.12)' = The central moments for N = 1,2,3..: μN = < (an - <an>)N> = < (an - p)N> = < Σj=0N (an)N-j [-p]j > = Σj=0N (-1)j pj < (an)N-j > = Σj=0N (-1)j pj mN-j (2.5.13)' The N=1,2 central moments: μ1 = < (an - <an>)1> = <an> - <an> = 0 μ2 = < (an - <an>)2> = <an2> - 2<an>2 + <an>2 = <an2>- <an>2 = 1 - (2p-1)2 = 4p(1-p) = 1-μ2 = σ2 = (standard deviation)2 = variance (2.5.14)' Fact 1': The first and second order statistics are completely determined by the autocorrelation function. Proof: Assume that the autocorrelation function rk is known. Then, first order: p(an) = <an> = <an2> = r0 // (2.5.9a), (2.5.9b), (2.54) second order: p(an, an) = <an2> = p(an) = r0 // (2.5.9b), (2.54) p(am, an) = <aman> = rm-n m ≠ n // (2.5.4) For a white sequence, we have p = 1/2 so <an> = (2p-1) = 0 = μ <an2> = 1 = r0 // (2.5.4) <aman> = p(am, an) = p(am) p(an) = <an><an> = 0 = rm-n m ≠ n // (2.5.4) <amanak> = p(am, an, ak) = p(am) p(an) p(ak) = 0 m ≠ n ≠ k etc. (2.5.15)' From (2.5.15)' here is a plot of the autocorrelation sequence for a white sequence an defined over {-1, +1} where we set p = 1/2 in the above equations: Fig 2.5.2: Autocorrelation function of a white sequence over {-1,+1}. This fits the general template shown in Fig *** above where now α = μ2 = 0 and β = σ2+μ2 = 1. 2.6 Autocorrelation and Spectral Power Density of an MLS Sequence Consider a shift register generator of k stages having a primitive feedback polynomial h(x). What is the frequency spectrum of the MLS sequence output by this piece of hardware? There are really two different answers to this question, depending on what the output driver looks like. We consider the following two cases: Case 1: (single-ended) On a 1 we make a pulse xpulse(t), and on a 0 we make no pulse. For 1101, Fig 2.6.1: Encoding of 1101 using arbitrary pulse shape, singled ended drive. Case 2: (differential) On a 1 we make a pulse xpulse(t), and on a 0 we make a pulse -xpulse(t) . For 1101, Fig 2.6.2: Encoding of 1101 using arbitrary pulse shape, differential drive. When xpulse(t) is a box of width T1 (as it would be for an ideal NRZ line code), Case 1 and Case 2 are related by a factor of 2 scale change and a DC offset. T1 is the spacing between dotted lines in the above figures. We prefer to deal with an arbitrary pulse shape in the following analysis, so Case 1 and Case 2 are quite different. In either case, our method of analysis will be the same. We compute the two quantities α = <aman> and β = <an2> , and we make use of our general formula given in Spectral Chapter 6, boxed equation (6.4.7). We anticipate that these averages will be independent of the subscripts, and so (6.4.7) applies. If this were not the case, we would have to back up to equation (6.3.9) as we did in the analysis of the AMI line code in Spectral Section 6.6(d). In quantity α = <aman> it is implied that m ≠ n. Case 1: MLS Sequence Statistics for Symbols in {1,0} We replicate our table from Section 2.4 above. Recall that this table describes the product of two MLS sequences, and just such a product sequence is what appears summed in the definition of the autocorrelation function, Equation (2.5.2). The Counts Column 3 Column 4 Shifted n's Unshifted n's n1 = number of (0,0)'s sum = 0 product = 0 (2k - 1) - 3•2k-2 2k-1 - 1 n2 = number of (0,1)'s sum = 1 product = 0 2k-2 0 n3= number of (1,0)'s sum = 1 product = 0 2k-2 0 n4 = number of (1,1)'s sum = 0 product = 1 2k-2 2k-1 The product of two MLS sequences consists of 0's and 1's as shown in Column 4. To get α = <aman>, we use the Shifted column for the values of the ni counts, while for β = <an2> we use the Unshifted counts column. In these sums, the product=0 combinations make no contribution, so we add up only the product=1 combinations. We state the results for general k, and for k = 9 as an example: (P = 2k - 1 ) α = <aman> = n4 / P = = = = (1/4)(1+1/P) = rm-n = 128/511 β = <an2> = n4 / P = = 2 = (1/2)(1+1/P) = r0 = 256/511 (β - α) = 2 - = = (1/4)(1+1/P) = 128/511 (2.6.1) μ = <an> = prob of 1 = = (1/2)(1+1/P) = r0 // see ***** σ2 = <an2> - <an>2 = β - μ2 = r0 - r02 = r0(1-r0) = (1/2)(1+1/P)[ 1 - (1/2)(1+1/P)] = (1/2)(1+1/P) [ (1/2)(1-1/P)] = (1/4)( 1 - [ ]2) Is the MLS sequence correlated or uncorrelated? If it were uncorrelated, we would have <aman> = <an>2, but from the above we see that <aman> = (1/4)(1+1/P) <an> = (1/2)(1+1/P) <an>2 = (1/4)(1+1/P)2 so <aman> – <an>2 = (1/4)[ (1+1/P) - (1+1/P)2] = – ( + ) No, the MLS sequence is not uncorrelated, but it becomes so as P→∞. And in this limit μ = 1/2. From (2.6.1) here is a plot of the autocorrelation function: Fig 2.6.3: Autocorrelation function for Case 1 MLS sequence on {1,0} One can see that as P→∞ this replicates Fig *** for a white sequence in {1,0} Fact 1: Comparison of Fig 2.6.3 with Fig 2.5.1 shows that the MLS sequence has an autocorrelation function that differs only slightly from that of a white sequence. For k = 9, P = 511 so (1 + 1/P) ≈ 1.002. Thus, the first and second order statistics of an MLS sequence are very close to those of a white sequence. Proof: See Fact 1 of Section 2.5 above. The corresponding spectral power density from Spectral (6.4.7) is, [ add FT D.32 reference! ] = { (1/4)(1 + 1/P) + (1/4)(1+ 1/P) } update (2.6.2) Notice that the continuous and discrete spectra have exactly equal strengths, and these strengths are just slightly greater than 1/4. For k=9, we get coefficients 128/511 = .0250489. The above result is in terms of a general pulse shape. If we set P = ∞ in the above formula, we recover the spectral density of a white sequence. If we also specialize to the case of a square wave pulse, we replicate our earlier result for an NRZ line code having p = 1/2. See Spectral equation (6.5.1). Case 2: MLS Sequence Statistics for Symbols in {1,-1} We modify the above table by replacing (0,1) with (+1,-1). We are basically scaling our coefficients by 2 and giving them an offset of -1 unit compared to Case 1. It was already noted that the resulting analog signals are considerably different between Case 2 and Case 1. The Counts Column 3 Column 4 Shifted n's Unshifted n's n1 = number of (-1,-1)'s sum = -2 product = 1 (2k - 1) - 3•2k-2 2k-1 - 1 n2 = number of (-1,1)'s sum = 0 product = -1 2k-2 0 n3 = number of (1,-1)'s sum = 0 product = -1 2k-2 0 n4 = number of (1,1)'s sum = 2 product = 1 2k-2 2k-1 The product of two MLS sequences consists of -1's and 1's as shown in Column 4. To get α = <aman>, we use the Shifted column for the values of the ni counts, while for β = <an2> we use the Unshifted counts column. This time, we get contributions from all four possible combinations. We state the results for general k, and for k = 9 as an example: (recall P = length of sequence = 2k - 1) α = <aman> = (n1 - n2 - n3 + n4) / P = -1/P = rm-n = -1/511 explain β = <an2> = (n1 - n2 - n3 + n4) / P = 1 = r0 = 1 explain (β - α) = (1+1/P) = 1 + 1/511 (2.6.3) μ = <an> = 1 + (-1) // see ***** = – = – = [ 2P+2-P-1 + 2] = = (1 + ) σ2 = <an2> - <an>2 = 1 - μ2 = 1 - ()2 = [ 1 - - ] Here is a plot: Fig 2.6.4: Autocorrelation function for Case 2 MLS sequence Upon comparing Fig 2.6.4 with Fig 2.5.2, one sees again that the autocorrelation function for the MLS sequence (now defined over +1, -1 ) is just slightly different from that of a white sequence. The corresponding Case 2 spectral power density from (6.4.7) is, = { 1+1/P + (-1/P) } (2.6.4) where P = 2k - 1. Now almost all the power is in the continuous spectrum. For a white sequence, we set P = ∞ and find that all power is in the continuous spectrum . For an NRZ signal, Case 1 and Case 2 are essentially the same. They differ only by a factor of 4 due to the factor-of-2 scale change on the height of the pulse. The apparent discrete spectrum in (2.6.2) vanishes due to zeros in the quantity |Xpulse()|2. Therefore: Fact 2: Apart from a possible DC line, the spectrum of the MLS sequence output by a shift register generator is entirely continuous, and it is the envelope of the pulse shape used.