section 2_5 rewrite later dumped REVD

New Section 2.5 PhL 7.18.13 This "new" stuff got thrown out and all the probability stuff went into the last FT appendix. Section 2.5 was rewritten many times and here is one of those times, now dumped. 2.5 Basic Probability Theory, MLS Spectral Power Density, and Autocorrelation 1 (a) Basic Probability Theory 1 (b) Application to Sequences 4 (c) A Plan for Finding the Spectral Power Density of an MLS Sequence 7 (d) Case 1: The Spectral Power Density of an MLS Sequence with symbols in {1,0}. 8 (e) Case 2: The Spectral Power Density of an MLS Sequence with symbols in {1,-1} 11 (f) Statistics Summary Table for an MLS sequence for Both Cases 12 (g) The Autocorrelation Sequence 13 (h) MLS spectrum for symbols in {1,0} 16 (i) MLS spectrum for symbols in {1,-1} 19 (j) The Z-Transform Wiener-Khintchine Theorem 20 (k) Using Wiener-Khintchine to compute the MLS Spectrum 22 2.5 Basic Probability Theory, MLS Spectral Power Density, and Autocorrelation (a) Basic Probability Theory 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.1) If events A and B are statistically independent in second order, one gets: P(A,B) = P(AB) = P(A) P(B) P(A|B) = P(A), P(B|A) = P(B) . (2.5.2) 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.3) A possible "event" is that a "random variable" X takes some value x. In this case, instead of writing things like P(A) = P(X = x), we abbreviate and say P(X=x) = p(x). Similarly P(X=x, Y=y) = p(x,y), so the position of the argument of p(....) indicates which random variable one is talking about. This concept applies for the values x being either continuous (such as the reals) or discrete (such as GF(p) ). The joint pdfs are now written p(x,y) and p(x,y,z) and so on. If the random variables X and Y are statistically independent, then all the pdf's must completely "factor". For example, p(x,y,z) = p(x)p(y)p(z). Any pdf is normalized to 1 since the probability of all possible events is 1. Thus, ∫∫.... p(x,y....) dx dy... = 1 or Σij.... p(xi,yj....) = 1 . (2.5.4) An example is that ∫p(x)dx = 1 or Σip(xi) = 1. If f(X,Y...) is some arbitrary function of some random variables X.Y..., one can define the expectation value of f as follows: E(f(X,Y,...)) = ∫∫.... f(x,y...) p(x,y....) dx dy.... or Σij.... f(xi,yj...) p(xi,yj....) . (2.5.5) Cases of interest to us will be the following E(X) = ∫ x p(x) dx or Σixi p(xi) = "the mean", often written μx (2.5.6) E((X-μx)(Y-μy)) = ∫∫ (x-μx) (y-μy) p(x,y) dx dy or Σi,j (xi-μx) (yj - μy) p(xi,xj) = "the covariance of X and Y" = cov(X,Y) . (2.5.7) If the joint second-order pdf factors, so that p(x,y) = p(x)p(y), or equivalently p(xi,xj) = p(xi)p(yj), then one says that the random variables X and Y are uncorrelated. Since the higher joint pdf's might not factor, this does not imply statistical independence. Thus we have only one direction here: Fact: X and Y statistically independent X and Y are uncorrelated (2.5.8) We can now identify three different statements: Fact: X and Y are uncorrelated E(XY) = E(X)E(Y) cov(X,Y) = 0 . (2.5.9) Proof: We show this in the continuous notation but everything applies also in the discrete notation. X and Y uncorrelated means p(x,y) = p(x)p(y) which at once means E(XY) = E(X)E(Y) from the definitions shown above: E(XY) = ∫∫ x y p(x,y) dx dy = ∫∫ x y p(x)p(y) dx dy = [∫x p(x) dx] [∫y p(y) dy] = E(X)E(Y) . The covariance is cov(X,Y) = ∫∫ (x-μx) (y-μy) p(x,y) dx dy = ∫∫ (x-μx) (y-μy) p(x)p(y) dx dy = [ ∫ (x-μx) p(x) dx ] [ ∫ (y-μy) p(y) dy ] . But each factor vanishes for the reason shown below, and thus cov(X,Y) = 0 : [ ∫ (x-μX) p(x) dx ] = ∫x p(x) dx - μx ∫ p(x) dx = μx - μx * 1 = 0 . QED Now suppose X and Y are the same random variable. Then we have, for example, p(x,y) = p(x)δ(x-y) or p(xi,yj) = p(xi)δi,j . (2.5.10) The reason is that if X and Y are the same random variable, they cannot take different values. If X,Y and Z are all the same variable, then we would have p(x,y,z) = p(x)δ(x-y)δ(x-z) or p(xi,yj,zk) = p(xi) δi,j δi,k (2.5.11) Note that δ(x-y)δ(x-z) = δ(x-y)δ(y-z) = δ(x-z)δ(y-z) and δi,j δi,k = δi,j δj,k = δi,k δj,k . The main application of this concept relates to the variance and standard deviation of X: cov(X,X) = ∫∫ (x-μx) (y-μx) p(x,y) dx dy = ∫∫ (x-μx) (y-μx) p(x)δ(x-y) dx dy = ∫ (x-μx)2 p(x) dx or Σi (xi -μx)2 p(xi) ≡ var(X) = "the variance of X" = [σ(X)]2 = "the standard deviation squared" . (2.5.12) Notice that this quantity could in theory vanish if p(x) = δ(x - x1) so that the entire pdf is concentrated at a single value. var(X) = ∫ (x-μx)2 p(x) dx = ∫ (x-μx)2 δ(x - x1) dx = (x1-μx)2 = (x1- x1)2 = 0 = σ(X) . A pdf of this form is not very interesting and normally one has σ(X) > 0. Fact: var(X) = σ2(X) = E(X2) - {E(X)}2 (2.5.13) Proof: E(X2) - {E(X)}2 = ∫x 2p(x) dx - {∫x p(x) dx} 2 = ∫x 2p(x) dx - μx2 var(X) = ∫ (x-μx)2 p(x) dx = ∫x 2p(x) dx -2μx∫x p(x) dx + μx2∫ p(x) dx = ∫x 2p(x) dx - 2μx μx + μx2 1 = ∫x 2p(x) dx - μx2 . QED There is one more object of interest which is the correlation function of X and Y corr(X,Y) ≡ cov(X,Y) / [σ(X) σ(Y) ] . (2.5.14) This is just a rescaled version of the covariance. We may now extend our fact above : Fact: X and Y are uncorrelated E(XY) = E(X)E(Y) cov(X,Y) = 0 corr(X,Y) = 0 (2.5.15) To be consistent with notation in other documents, we shall use this alternate <...> notation for expectation values, < f(x,y...)> ≡ E(f(X,Y,...)) . (2.5.16) Normally the notation <...> means an average of something, and expectation values are averages. (b) Application to Sequences We shall now apply these probability concepts to the simple case of a sequence {ai} . We think of each position in the sequence as corresponding to a random variable Ai which can take values in some set of values, and the value that Ai takes is called ai. Then, for example, <an> ≡ E(An) = Σnan p(an) (2.5.17) <an2> ≡ E(An2) = Σn,m an2 p(an) <anam> ≡ E(AnAm) = Σn,m an am p(an,am) <anam> = <an><am> = <an>2 // from (2.5.15), only if An and Am are uncorrelated where all sums are over the entire sequence. And Fact (2.5.13) says var(An) = σ2(An) = E(X2) - {E(X)}2 = <an2> – <an>2 ≡ σn2 (2.5.18) Question: Does <an> or <an2> depend on n ? Recall that p(an) = P(An = an) so in theory we could have P(A3= an) ≠ P(A5= an), say. In our treatment of sequences we assume that there is nothing distinguishing about a particular symbol position other than its value, so we would have P(A3= an) = P(A5= an) for positions 3 and 5 in any sequence. So the answer is no, <an> and <an2> do not depend on n, they are just averages over the sequence. On the other hand, when we write <anam> = <anan+k>, this could depend on the distance k between two symbol positions, as it does in the AMI line code (see FT Section 37), but <anan+k> does not depend on n. When the An and Am variables are uncorrelated, then <anam> = <an><am> = <an>2 and in this case we find that <anam> depends on neither n nor m, and <anan+k> depends on neither n nor k. Case 1: Symbols in {1,0} We first calculate <an> , μ = <an> = Σnan p(an) = 1 p(1) + 0 p(0) = p(1) = p . We have defined a local symbol p ≡ p(1) = the probability that an takes the value +1. This symbol p has nothing to do with the p appearing in GF(pk) ! Now we do some other expectation values. First, <an2> = Σnan2 p(an) = 1 p(1) + 0 p(0) = p(1) = <an> ≡ μ . // the mean Then from (2.5.18), σn2 = <an2> – <an>2 = μ - μ2 = μ(1-μ) . Next we consider <anam>. For m = n the result is as above, while for m ≠ n we get <anam> = Σnanam p(an,am) = 1*1*p(1,1) + three zero terms = p(1,1) = P(an= 1, am = 1) . If An and Am were uncorrelated, then according to (2.5.17) we would have <anam> = <an><am> = <an>2 = μ2 . // uncorrelated Case 2: Symbols in {1,-1} Here we mimic the previous section, making changes as needed. We first calculate <an> , μ = <an> = Σnan p(an) = 1 p(1) + (-1) p(-1) = 1 p(1) + (-1) [1-p(1)] = 2p(1) - 1 ≡ 2p-1 . Again we have defined a local symbol p ≡ p(1) = the probability that an takes the value +1. Now we do some other expectation values. First, <an2> = Σnan2 p(an) = (1)2 p(1) + (-1)2 p(-1) = p(1) + p(-1) = 1 . Then from (2.5.18), σn2 = <an2> – <an>2 = 1 - μ2 = 1 - (2p-1)2 = 4p(1-p) . Next we consider <anam>. For m = n the result is as above, while for m ≠ n we get <anam> = Σnanam p(an,am) = 1*1*p(1,1) + 1*(-1)p(1,-1) + (-1)*1 p(-1,1) + (-1)2 p(-1,-1) = p(1,1) - p(1,-1) - p(-1,1) + p(-1,-1) . If An and Am were uncorrelated, then according to to (2.5.17) we would have <anam> = <an><am> = <an>2 = μ2 = (2p-1)2 // uncorrelated The results of both cases are summarized in this table: General Sequence Probability Characteristics (2.5.19) Case 1: symbols in {1,0} Case 2: symbols in {1,-1} P(an = 1) p p <an> = μ p (2p-1) <an2> μ = p 1 σn2 μ-μ2 = p-p2 1-μ2 = 4p(1-p) <anam> m≠n p(1,1) = P(an= 1,am= 1) p(1,1) - p(1,-1) - p(-1,1) + p(-1,-1) <anam> m≠n μ2 = p2 μ2 = (2p-1)2 uncorrelated (c) A Plan for Finding the Spectral Power Density of an MLS Sequence Our FT document studies the energy and power spectra of amplitude-modulated pulse trains. The pulse shape from which the pulse train is made is called xpulse(t) and is often taken to be some kind of square pulse, but we leave it unspecified for the moment. We take our sequence {ai} to be the pulse train amplitudes, called {yi} in FT. Each sequence element ai applies to one pulse of the pulse train, and that one pulse has duration T1. This could be, for example, the clock period of our shift register generator and the pulse train could be the output of the generator. Here are some sample pulse train segments for what we will call Case 1 and Case 2 below, made from a generic pulse xpulse(t): Case 1: {1,0} FT Fig 2.6.1: Encoding of 1101 using arbitrary pulse shape, singled ended drive. Case 2: {1,-1} Ft Fig 2.6.2: Encoding of 1101 using arbitrary pulse shape, differential drive. It is shown in FT Appendix F that the spectral power density of an infinite pulse train composed of a repeating sequence of period P is : ( Q"(z) is the normalized Z transform of the repeated sequence ) P(ω) = Ppulse(ω) ω1 !Syntax Error, I | Q"(z) |2 δ(ω - ω1m/P) FT (F.12) (2.5.20) Q"(z) = !Syntax Error, I an e-iωnT | Q"(z) |2 = !Syntax Error, I !Syntax Error, I am*an eiω(m-n)T For an ensemble of pulse trains, all of which have a repeated sequence of period P, and for which it happens that <am*an>e is independent of indices m and n, FT Appendix F gives this expression for the ensemble's spectral power density <P(ω)>e : <P(ω)>e = Ppulse(ω) ω1 [(β-α) { !Syntax Error, Iδ(ω - ω1m/P)} + α !Syntax Error, Iδ(ω - ω1m) ] where FT (F.22b) (2.5.21) α ≡ <am*an>e for m ≠ n β ≡ <am*an>e for m = n The spectrum is entirely discrete as we expect for the average of a set of sequences each of which is periodic with period P. The notation <....>e refers the ensemble average of some quantity. Notice that in the first term of (2.5.21) the line frequencies are ωm = m(ω1/P) and are spaced by Δω = ω1/P. As P increases, this spacing gets smaller and smaller. In the limit P→∞, the discrete lines coalesce into a continuous spectrum. It is shown in FT that limP→∞ { !Syntax Error, Iδ(ω - ω1m/P)} = 1/ω1 FT (F.27) resulting in this limit of (2.5.21) <P(ω)>e = Ppulse(ω) ω1 [(β-α) {1/ω1} + α !Syntax Error, Iδ(ω - ω1m) ] P→∞ (2.5.22) which we know from FT (35.11) is the spectrum of a random ensemble of infinite pulse trains. We shall return to this limit below for our two specific Cases. An alternate form of (2.5.21) is obtained by isolating the m = 0 contributions into a third term, <P(ω)>e = Ppulse(ω) ω1 [ (β-α) !Syntax Error, Iδ(ω - ω1m/P) + α !Syntax Error, Iδ(ω - ω1m) + { α + (β-α) /P } δ(ω) ] FT(F.22d) (2.5.23) Our goal is to somehow apply the above result (2.5.21) or (2.5.23) to an MLS sequence. To apply (2.5.20) directly to an MLS sequence, we would have to compute the double sum shown which would likely be quite involved. Instead, we carry out this set of steps: 1. Construct an ensemble of P MLS sequences as follows: We start with our given MLS sequence, and then construct P-1 other sequences by doing all possible shifts 0 < Δt < P of the original sequence. 2. For this ensemble of sequences, we figure out how to compute <aman>e and we show that this quantity does not depend on the labels n and m. 3. We then use (2.5.23) to find <P(ω)>e for the ensemble. 4. Since all the infinite sequences in our ensemble are really the same sequence, the power spectrum of any sequence is the same as the average of all of them, so P(ω) = <P(ω)>e and thus we arrive at P(ω) for a specific MLS sequence. (d) Case 1: The Spectral Power Density of an MLS Sequence with symbols in {1,0}. Our starting point for carrying out the steps above is to consider once again our "compressed" chart which collected facts about the product of a specific MLS sequence and a shifted version of itself, 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 (2.4.8) where P = 2k-1. If the shifted version of our MLS sequence is shifted by s bits, then for s ≠ 0, <anan+s> = 1 * 1 * Prob(1,1) + 1*0* Prob(1,0) + etc = Prob(1,1) = n4/P = 2k-2/ P. Only facing bits of the pattern (1,1) contribute to <anan+s>, and the count of those is n4 = 2k-2 as shown in the chart above (Shifted n's column), while the total number of bit pairs is P. Now 2k-2/ P = (1/4)2k/P = (1/4)(P+1)/P = (1/4)(1 + 1/P) so we have just shown that <anan+s> = (1/4)(1 + 1/P) for s ≠ 0 . For s = 0, there is no shift and, since there are 2k-1 one's in any MLS sequence, this is also the number of (1,1) matching pairs and n4 = 2k-1 as shown in the last column of the chart, bottom row. Thus <anan+0> = 1 * 1 * Prob(1,1) + etc = Prob(1,1) = 2k-1/P = 2 [2k-2/ P] = (1/2)(1 + 1/P) . We have now established that <anan+s> = (1/4)(1 + 1/P) for s ≠ 0 <anan+0> = (1/2)(1 + 1/P) which we rewrite as <anam> = (1/4)(1 + 1/P) for m ≠ n <an2> = (1/2)(1 + 1/P) (2.5.24) As a graphic aid to understanding the averages <...> appearing here, consider: Fig 2.8 The top line shows our specific MLS sequence, and the bottom line the same sequence shifted by s bits, where here s = 2. To compute the average <anan+s>, we move the pair of arrows to all P = 7 positions and add the pairwise products, and then we divide by P = 7. This is the 2k-2/ P ratio shown above. Here is another way to think of the same average <anan+s> , Fig 2.9 Here we draw only the original MLS sequence and we have an arrow pair where the arrows are locked at a spacing of s bits. To compute the average <anan+s> we compute a sum and divide by P. The sum is formed from those P = 7 terms of products aiaj pointed at by the arrow tips as the rigid arrow pair is slid sideways to all P = 7 positions. Again, we get <anan+s> = 2k-2/ P . Now we come up with yet another way to compute <anan+s>. Consider this picture where we have drawn a whole set of P = 7 shifted MLS sequences: Fig 2.10 To compute the very same <anan+s>, we now keep our rigid arrow pair fixed so the left end is at some an, which here is a2. This time we add the pairwise products aiaj to which the arrows point in each of the P = 7 rows. Since each row is shifted one position from the previous row, this sum is exactly the same sum computed using the previous figure by sliding the rigid arrow pair sideways. But using this new picture, we may regard this average as an ensemble average! Thus, for this particular ensemble of sequences associated with our specific starting MLS sequence, we have <anan+s>e = <anan+s> . (2.5.25) In particular, then, we have <anan+s>e = (1/4)(1 + 1/P) for s ≠ 0 <anan+0>e = (1/2)(1 + 1/P) which we rewrite once again as <anam>e = (1/4)(1 + 1/P) ≡ α m ≠n <an2>e = (1/2)(1 + 1/P) ≡ β (2.5.26) Thus, we have carried out the first two steps of our program outlined at the end of section (c) above. Notice that the ensemble averages do not depend on indices m or n. We then carry out the last two steps of the plan to arrive at the following spectral power density for our specific MLS sequence of length P with symbols in {1,0} which is used to form an infinite pulse train by repetitions. The result is this restatement of (2.5.23) with the step #4 understanding that <P(ω)>e is the same as P(ω), P(ω) = Ppulse(ω) ω1 [ (β-α) !Syntax Error, Iδ(ω - ω1m/P) + α !Syntax Error, Iδ(ω - ω1m) + { α + (β-α) /P } δ(ω) ] where (2.5.27) <aman>e = α = (1/4)(1 + 1/P) for m ≠ n Note: (β-α) = α <aman>e = β = (1/2)(1 + 1/P) for m = n This is an exact result valid for even small values of P = 2k-1. It applies to a specific MLS sequence. Although the above equation applies to the infinitely long MLS sequence in which the P-length subsequence is repeated, the equations concerning α and β only concern am over one period P, so |m-n| < P as far as <aman>e is concerned. (e) Case 2: The Spectral Power Density of an MLS Sequence with symbols in {1,-1} Our starting point to carry out this program is to consider once again our "compressed" chart which collected facts about the product of a specific MLS sequence and a shifted version of itself. However, we now draw the chart for our new choice of symbols: (the right two columns are unchanged) 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 (2.5.28) Our new computation of goes like this, assuming s ≠ 0, <anan+s> = 1*1*Prob(1,1) + 1*(-1)*Prob(1,-1) + (-1)*1* Prob(-1, 1) + (-1)*(-1)Prob(-1,-1) . For s ≠ 0, the "shifted n's" column tells us that Prob(1,1) = Prob(-1,1) = Prob(1,-1) = 2k-2/P Prob(-1.-1) = [(2k - 1) - 3•2k-2]/P Then for s ≠ 0, <anan+s> = 2k-2/P – 2k-2/P - 2k-2/P + [(2k - 1) - 3•2k-2]/P = - 2k-2/P + [(2k - 1) - 3•2k-2]/P = [(2k - 1) - 4•2k-2]/P = [P - (4/4)•2k]/P = [P - (P+1)]/P = -1/P . For s = 0 we get instead <anan+0> = 1*1*Prob(1,1) + 1*(-1)*Prob(1,-1) + (-1)*1* Prob(-1, 1) + (-1)*(-1)Prob(-1,-1) = Prob(1,1) + Prob(-1,-1) = 2k-1/P + (2k-1-1)/P = (2k-1)/P = P/P = 1 . This result is fairly obvious since <an2> = 1 for both an in {1,-1} . Skipping all the intermediate steps detailed in the previous section, we then arrive at <anam>e = -1/P ≡ α m ≠n <an2>e = 1 ≡ β (2.5.29) and this statement of the MLS spectrum for symbols in {1,-1}, P(ω) = Ppulse(ω) ω1 [ (β-α) !Syntax Error, Iδ(ω - ω1m/P) + α !Syntax Error, Iδ(ω - ω1m) + { α + (β-α) /P } δ(ω) ] where (2.5.30) <aman>e = α = -1/P for m ≠ n <aman>e = β = 1 for m = n (f) Statistics Summary Table for an MLS sequence for Both Cases In an MLS sequence, the probability of a bit being a 1 is p = 2k-1/P = (1/2)2k/P = (1/2)(P+1)/P = (1/2)(1 + 1/P) and this applies for both Cases. Our table of (2.5.19) is then Probability Characteristics of an MLS Sequence of Length P (2.5.31) Case 1: symbols in {1,0} Case 2: symbols in {1,-1} P(an = 1) p = (1/2)(1 + 1/P) p = (1/2)(1 + 1/P) <an> = μ p = (1/2)(1 + 1/P) (2p-1) = 1/P <an2> = β μ = (1/2)(1 + 1/P) 1 σn2 μ-μ2 = p-p2 = (1/4)(1-1/P2) 1-μ2 = 4p(1-p) = 1 - 1/P2 <anam> = α (1/4)(1 + 1/P) -1/P m≠n We can make a similar table for a "white sequence" which is a completely random sequence of symbols. For Case 1, certainly <an> = p = 1/2 = μ. <an2> = (1/2)12 + (1/2)02 = 1/2 <anam> = (1/4)12 + (1/4)0*1 etc = 1/4 = <an><am> = 1/4 σn2 = <an2>- <an>2 = 1/2 - (1/2)2 = 1/4 For Case 2, <an> = 0 = μ <an2> = (1/2)12 + (1/2)(-1)2 = 1 <anam> = <an><am> = μ2 = 0 σn2 = <an2>- <an>2 = 1 - 02 = 1 Therefore: Probability Characteristics of an White Sequence (2.5.32) Case 1: symbols in {1,0} Case 2: symbols in {1,-1} P(an = 1) p = (1/2) p = (1/2) <an> = μ p = (1/2) (2p-1) = 0 <an2> = β μ = (1/2) 1 σn2 μ-μ2 = p-p2 = (1/4) 1-μ2 = 4p(1-p) = 1 <anam> = α (1/4) 0 m≠n We are not surprised to see that, for the MLS sequence as P→∞, the two tables above are the same. (g) The Autocorrelation Sequence For all purposes of our current document, there is no need to even mention the autocorrelation function. Nothing depends upon it in any way. As is shown below, the autocorrelation sequences of interest to us contain only two parameters r0 and r1, and these are the same as our parameters β and α. Nevertheless, it is useful to tie in the autocorrelation function to our analysis and then display some standard plots that are seen often in texts. Comment: See FT 32 (e) for the relationship between autocorrelation, cross-correlation and convolution. For a real function b(t), the autocorrelation function is both the cross-correlation ⋆ of b(t) with itself, and the convolution ∗ of b(t) with itself, so rb = b⋆b = b∗b . 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) by doing t" = t'+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" (discrete) autocorrelation function having the following form: rs ≡ . // = r-s by doing n' = n+s 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. We should call this an autocorrelation sequence, but the more normal terminology is autocorrelation function. It certainly is a function over a discrete domain. 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 MLS sequence: rs ≡ (1/P) s = any integer (2.5.33) P is the period of the periodic sequence and for an MLS sequence P = 2k - 1. Here it is implied that if an+s takes us off the end of any length-P subsequence, we encounter the starting bits of the next length-P subsequence, so in effect we wrap to values at the start of the subsequence. Remember that the MLS sequence really is an infinite sequence formed by repeats of the length-P subsequence. We use the term MLS ambiguously for both the finite subsequence and the infinite sequence it generates. The wrap around rule (periodicity of the infinite MLS sequence) can be stated this way an+NP = an or an+s = a(n+s)modP Without further ado, we see that rs is something we have been using all along, rs = <anan+s> s = any integer (2.5.34) so that, rs = <an2> s = NP N = any integer rs = <anan+s> s ≠ NP which we can rewrite as r0 = rNP = <an2> = β rn-m = <anam> = rm-n m-n ≠ NP = α (2.5.35) Here is a table summarizing results above where we limit our interest to m-n < P: Case 1 {1,0) uncorrelated μ μ μ2 0 ≤ μ ≤ 1 MLS (1/2)(1+1/P) (1/2)(1+1/P) (1/4)(1+1/P) white 1/2 1/2 1/4 Case 2 {1,-1) uncorrelated μ 1 μ2 -1 ≤ μ ≤ 1 MLS 1/P 1 -1/P white 0 1 0 (2.5.36) Comments: 1. If a sequence is uncorrelated, it must have α = <anam> = <an><am> = <an>2 = μ2. Although α = <anam> and β = <an2> for an MLS sequence are independent of indices m and n (for |n-m| < P), the MLS sequence is not uncorrelated. In Case 1, we have μ = (1/2)(1+1/P) but α = (1/4)(1+1/P) ≠ μ2. Similarly in Case 2 we have μ = 1/P but α = -1/P ≠ μ2. As P→∞, we do get μ = μ2 in both Cases and in that limit the MLS sequence becomes uncorrelated. 2. It seems clear that the autocorrelation sequence is associated only with the second-order statistics of a sequence, since rs = <anan+s>. One could define a fancier "autocorrelation function" such as rk,k' ≡ (1/P) = <an an+k an+k'> which would involve third-order statistics. We shall not pursue such objects beyond observing that if the sequence were uncorrelated one would have rk,k' = <an>3 = μ3. We now plot the six autocorrelation sequences implied by (2.5.36). The sequence values are shown as black dots, and the values are linearly interpolated by a red line as a cosmetic guide. In these drawings it is assumed that P > 4 so we don't see the autocorrelation sequences peaking every P integers, but one should keep in mind that they do just that. In the process of acquiring and tracking a spread spectrum signal, where one seeks to align the receiving clock with the transmitting clock, one reverts to a continuous (analog) autocorrelation function and then these red lines are more than cosmetic. See Comments at the start of Section 3.5 below. Case 1 Case 2 Fig 2.11 (h) MLS spectrum for symbols in {1,0} For a square pulse shape of unit amplitude and width T1 we have (see FT Sec 9 with τ = T1 and A = 1) xpulse(t) = [ θ(t + T1/2) - θ(t - T1/2) ] // time domain FT (9.1) Xpulse(ω) = T1 sinc(ωT1/2) . // Fourier Integral Transform FT (9.2) Ppulse(ω) ≡ = (1/ω1) sinc2(ωT1/2) // ω1 ≡ 2π/T1 FT (34.4) (2.5.37) Recall now (2.5.27) P(ω) = Ppulse(ω) ω1 [ (β-α) !Syntax Error, Iδ(ω - ω1m/P) + α !Syntax Error, Iδ(ω - ω1m) + { α + (β-α) /P } δ(ω) ] From below (2.5.27) we have α = (1/4)(1+1/P) and β = (1/2)(1+1/P) so (β-α) = α. Thus we can factor out an overall factor of α to get = Ppulse(ω) ω1 α [!Syntax Error, Iδ(ω - ω1m/P) + !Syntax Error, Iδ(ω - ω1m) + { 1+ 1 /P } δ(ω) ] = sinc2(ωT1/2) (1/4)(1 + 1/P) [ !Syntax Error, Iδ(ω - ω1m/P) + !Syntax Error, Iδ(ω - ω1m) + { 1+ 1/P } δ(ω) ] . The next step is move the sinc factor inside the two m sums and evaluate ω at the δ hit values = (1/4)(1 + 1/P) [ !Syntax Error, Iδ(ω - ω1m/P) sinc2(πm/P) + !Syntax Error, Iδ(ω - ω1m) sinc2(πm) + { 1+ 1/P } δ(ω) sinc2(0) ] = (1/4)(1 + 1/P) [ !Syntax Error, Iδ(ω - ω1m/P) sinc2(πm/P) + { 1+ 1 /P } δ(ω) ] so the MLS spectrum is then given by (remember that sum is on m = ±1, ±2 etc) P(ω) = (1/4)(1 + 1/P) !Syntax Error, Iδ(ω - ω1m/P) sinc2(πm/P) + (1/4)(1 + 1/P)2 δ(ω) . = (1/4)(1 + 1/P) sinc2(πω/ω1) !Syntax Error, Iδ(ω - ω1m/P) + (1/4)(1 + 1/P)2 δ(ω) = (1/4)(1 + 1/P) sinc2(πω/ω1) !Syntax Error, Iδ(ω - ω1m/P) + [ (1/2)(1 + 1/P)]2 δ(ω) = (β/2) sinc2(πω/ω1) !Syntax Error, Iδ(ω - ω1m/P) + β2 δ(ω) , β = (1/2)(1 + 1/P) (2.5.38) Here is a graphical representation of P(ω) drawn for P = 4 : Spectrum of an MLS sequence with symbols in {1,0} and a box pulse shape. Fig 2.12 Each vertical arrow represents a spectral δ line. The height of the arrow is the value of the red envelope curve times the quantity shown. The little arrows are drawn too long so they can be seen. As P gets larger, the density of arrows on the left increases, but the height of the arrows (β/2) sinc2(πm/P) decreases. Remember that each arrow represents a delta function which is infinite in "height", so this infinite height is being scaled down by 1/P as P increases. In the limit P→∞, FT (F.27) shows that limP→∞ [ !Syntax Error, Iδ(ω - ω1m/P)] = 1. FT (F.27) so the spectrum (2.5.38) becomes P(ω) = (1/4) sinc2(πω/ω1) + (1/4) δ(ω) β = (1/2) (2.5.39) Thus, as the arrows get denser in the left image in Fig 2.12, in the limit we get a continuous spectrum which is the red curve times (1/4) . The height of the DC arrow on the right is then β2 = 1/4. As P→∞, the spectrum has become that of a white sequence with symbols in {1,0}. To verify this claim, we can start with our known spectrum of an ensemble of infinite pulse trains which ensemble is characterized by α = <anam> and β = <an2>, <P(ω)> = Ppulse(ω) [(β-α) + ω1 α !Syntax Error, Iδ(ω - ω1m) ] FT (35.11) or FT (F.28) From (2.5.36) we have α = 1/4 and β = 1/2 so (β-α) = 1/4. Then, inserting the box Ppulse(ω) , <P(ω)> = (1/ω1) sinc2(ωT1/2) [1/4 + ω1 1/4 !Syntax Error, Iδ(ω - ω1m) ] = (1/ω1) [1/4 sinc2(ωT1/2)+ ω1 1/4 !Syntax Error, Iδ(ω - ω1m) sinc2(πm) ] = (1/4) (1/ω1) sinc2(πω/ω1) + (1/4) δ(ω) . An infinite random ensemble of uncorrelated pulse trains can be regarded as the infinite ensemble obtained by starting with a particular infinite white sequence and shifting it by all bit positions. Either ensemble must exhaust the infinite set of all possible random pulse trains, though we are not claiming a formal proof. As in our 4 step program earlier, we then argue that <P(ω)> = P(ω) for a white sequence, so then P(ω) = (1/4) (1/ω1) sinc2(πω/ω1) + (1/4) δ(ω) in agreement with (2.5.39). (i) MLS spectrum for symbols in {1,-1} It is assumed the reader has read the previous section. Here we show only things that differ. Recall now (2.5.30) P(ω) = Ppulse(ω) ω1 [ (β-α) !Syntax Error, Iδ(ω - ω1m/P) + α !Syntax Error, Iδ(ω - ω1m) + { α + (β-α) /P } δ(ω) ] . From below (2.5.30) we have α = -1/P and β = 1 so (β-α) = (1+1/P), and { α + (β-α) /P } = 1/P2, so P(ω) = Ppulse(ω) ω1 [(1+1/P) !Syntax Error, Iδ(ω - ω1m/P) - (1/P) !Syntax Error, Iδ(ω - ω1m) + (1/P2) δ(ω) ] = sinc2(ωT1/2) [(1+1/P) !Syntax Error, Iδ(ω - ω1m/P) - (1/P) !Syntax Error, Iδ(ω - ω1m) + (1/P2) δ(ω) ] . The next step is move the sinc factor inside the two m sums and evaluate ω at the δ hit values = [(1+1/P) !Syntax Error, Iδ(ω - ω1m/P) sinc2(πm/P) - (1/P) !Syntax Error, Iδ(ω - ω1m) sinc2(πm) + (1/P2) δ(ω) sinc2(0) ] = [(1+1/P) !Syntax Error, Iδ(ω - ω1m/P) sinc2(πm/P) + (1/P2) δ(ω) ] , so the MLS spectrum is then given by (remember that sum is on m = ±1, ±2 etc) P(ω) = (1+1/P) !Syntax Error, Iδ(ω - ω1m/P) sinc2(πm/P) + (1/P2) δ(ω) = (1+1/P) sinc2(πω/ω1)!Syntax Error, Iδ(ω - ω1m/P) + (1/P2) δ(ω) . (2.5.40) Here is a graphical representation of P(ω) drawn for P = 4 : Spectrum of an MLS sequence with symbols in {1,-1} and a box pulse shape. Fig 2.13 In the limit P→∞, FT (F.27) shows that limP→∞ [ !Syntax Error, Iδ(ω - ω1m/P)] = 1. FT (F.27) so the spectrum (2.5.40) becomes (the DC line goes away) P(ω) = sinc2(πω/ω1) . (2.5.41) Thus, as the arrows get denser in the left image in Fig 2.13, in the limit we get a continuous spectrum which is the red curve times . As P→∞, the spectrum has become that of a white sequence with symbols in {1,0}. To verify this claim, we can start with our known spectrum of an ensemble of infinite pulse trains which ensemble is characterized by α = <anam> and β = <an2>, <P(ω)> = Ppulse(ω) [(β-α) + ω1 α !Syntax Error, Iδ(ω - ω1m) ] FT (35.11) or FT (F.28) From (2.5.36) we have α = 0 and β = 1 so (β-α) = 1. Then, inserting the box Ppulse(ω) , <P(ω)> = (1/ω1) sinc2(ωT1/2) [1 + ω1 0 !Syntax Error, Iδ(ω - ω1m) ] = (1/ω1) sinc2(πω/ω1) . Using the argument of the previous section, we associate this <P(ω)> with the P(ω) of a white sequence and then we have arrived at (2.5.41). (j) The Z-Transform Wiener-Khintchine Theorem In FT Section 32 (c) we derive the continuum version of the Wiener-Khintchine theorem as follows, making use of the Convolution Theorem FT (3.6), rx(t)  !Syntax Error, Idt"x(t - t") x(-t") . // energy units FT (32.7) a(t) = !Syntax Error, I dt" b(t-t") c(t") A(ω) = B(ω) C(ω) . FT (3.6) b(t) = x(t) ↔ B(ω) = X(ω) c(t) = x(-t) ↔ C(ω) = X(ω) = X(ω)* // from FT (7.1) and (7.2) Thus, the diagonalized frequency-domain form A(ω) = B(ω) C(ω) is Rx(ω) = |X(ω)|2 . FT (32.8) Since P(ω) ≡ = FT (33.23) where T is the duration of a pulse train, we find that P(ω) = 2πT Rx(ω) . FT (34. 3) (2.5.42) This says that the spectral power density of a pulse train can be obtained by computing the Fourier Integral Transform of the autocorrelation function and multiplying by 2πT. We can regard this as the Wiener-Khintchine theorem, although strictly the theorem is that Rx(ω) = |X(ω)|2. We shall now obtain a similar Wiener-Khintchine theorem for an infinite pulse train expressed in terms of R"(z) which is the Z Transform of the autocorrelation sequence rs of the pulse train amplitudes yn. for an infinite sequence which contains repeated P-length subsequences. Before doing this, however, we shall write several different expressions for our autocorrelation sequence rs all of which are equivalent. In (2.5.33) we defined the autocorrelation sequence as rs ≡ (1/P) !Syntax Error, Iyn yn+s = !Syntax Error, Iyn yn+s = <yn yn+s> (2.5.33) where <yn yn+s> is an expectation value over the P-length subsequence. We can rewrite rs by averaging over 2M+1 copies of the repeated subsequence, rs = !Syntax Error, I yn yn+s ≈ !Syntax Error, I yn yn+s (2.5.43) where on the right we assume M is very large. Defining large N = MP this can be written rs ≈ !Syntax Error, I yn yn+s ≈ !Syntax Error, I yn yn+s . (2.5.44) For an infinite sequence we take N→∞ so that rs = limN→∞ [!Syntax Error, I yn yn+s ] = <yn yn+s> (2.5.45) where now <yn yn+s> is an expectation value over the infinite sequence. This last form of rs can serve as a definition of rs for any infinite sequence, not just to one which periodic with period P. As a shorthand notation, knowing what the intent is, we write (2.5.44) instead as rs = !Syntax Error, Iyn yn+s = !Syntax Error, Iyn yn+s (2.5.46) where T = (2N+1)T1 is the duration of the pulse train. We know that this infinite T is going to cancel another T so we allow it to exist temporarily. Finally, we take n→-n in the sum and then swap factors to get rs = !Syntax Error, Iy-n y-n+s = !Syntax Error, I ys-n y-n (2.5.47) We can then construct a Z Transform version of the Wiener-Khintchine theorem as follows: rs = !Syntax Error, I ys-n y-n as = !Syntax Error, I∆t bs-n cn A"(z) = ∆t B"(z) C"(z) FT (24.5) as = rs ↔ A"(z) = R"(z) bk = yk ↔ B"(z) = Y"(z) ck = y-k ↔ C"(z) = Y"(z-1) = Y"(z)* // if the ck are real Δt ↔ (T1/T) Thus, the diagonalized z-domain form A"(z) = ∆t B"(z) C"(z) is R"(z) = (T1/T) Y"(z) Y"(z)* = (T1/T) | Y"(z) |2 . (2.5.48) It is shown in FT (34.14) that P(ω) = T1 Ppulse(ω) (1/T) !Syntax Error, I !Syntax Error, I ym* yn eiω(m-n)T FT (34.14) which we easily rewrite as P(ω) = Ppulse(ω) (T1/T) | Y"(z) |2 . (2.5.49) Using (2.5.42) we get, P(ω) = Ppulse(ω) R"(z) . (2.5.50) This says that the spectral power density of any infinite pulse train can be obtained by computing the Z Transform of the autocorrelation sequence and multiplying by Ppulse(ω). This then is our Z Transform version of the Wiener-Khintchine theorem. (k) Using Wiener-Khintchine to compute the MLS Spectrum We shall compute R"(z) and then use the Z transform Wiener-Khintchine theorem (2.5.44) to get P(ω). Recall that rs = <an2> s = NP = β rs = <anan+s> s ≠ NP = α . (2.5.35) Therefore R"(z) = !Syntax Error, Irn z-n = β !Syntax Error, Iz-n + α !Syntax Error, Iz-n = β !Syntax Error, Iz-n + α ( !Syntax Error, I z-n – !Syntax Error, Iz-n ) = (β-α) !Syntax Error, Iz-n + α !Syntax Error, I z-n . (2.5.45) The first sum is over n = 0, ±P, ±2P and so on. We can replace summation index n by index N, !Syntax Error, Iz-n = !Syntax Error, I z-NP = !Syntax Error, I z-nP . (2.5.46) From FT (24.1) we know that z lies on the unit circle in the z-plane and is related to ω by z = eiωT FT (24.1) where T1 is the duration of a pulse of the pulse train. We then have !Syntax Error, Iz-n = !Syntax Error, I (eiωT)-nP = !Syntax Error, I e-iωTnP . (2.5.47) According to FT (13.2) we know how to compute this sum, !Syntax Error, Ieink = !Syntax Error, I2πδ(k - 2πm) -∞ < k < ∞ . FT (13.2) so setting k = -ωT1P we get !Syntax Error, Iz-n = !Syntax Error, I2πδ(-ωT1P - 2πm) = !Syntax Error, I2πδ(ωT1P + 2πm) = !Syntax Error, I2πδ(ωT1P - 2πm) (2.5.48) where we use δ(x) = δ(-x) and in the last step take m→ -m. Meanwhile, our other sum of interest in (2.5.45) is this one, !Syntax Error, I z-n = !Syntax Error, I (eiωT)-n = !Syntax Error, I e-iωTn which is just the previous sum without the P. Thus, !Syntax Error, I z-n = !Syntax Error, I2πδ(ωT1 - 2πm) . (2.5.49) Inserting (2.5.49) and (2.5.48) into (2.5.45) gives R"(z) = (β-α) !Syntax Error, Iz-n + α !Syntax Error, I z-n = (β-α) !Syntax Error, I2πδ(ωT1P - 2πm) + α !Syntax Error, I2πδ(ωT1 - 2πm) = (β-α) (T1P)-1 !Syntax Error, I2πδ(ω - 2πm/[T1P]) + α(T1)-1 !Syntax Error, I2πδ(ω - 2πm/T1) = (2π/T1) { (β-α) (1/P) !Syntax Error, Iδ(ω - 2πm/[T1P]) + α !Syntax Error, Iδ(ω - 2πm/T1) } = ω1 { (β-α) (1/P) !Syntax Error, Iδ(ω - mω1/P) + α !Syntax Error, Iδ(ω - mω1) } (2.5.50) and this concludes our calculation of the Z Transform of the autocorrelation sequence rn. It only remains to install this into the Z Transform Wiener-Khintchine theorem (2.5.44) P(ω) = Ppulse(ω) R"(z) = Ppulse(ω) ω1 { (β-α) (1/P) !Syntax Error, Iδ(ω - mω1/P) + α !Syntax Error, Iδ(ω - mω1) } . (2.5.51) This is in agreement with (2.5.21) which we stole from FT (F.22b) and upon which we based all our MLS spectral results in sections (h) and (i). Comment: Our initial computation of the MLS spectrum including the work of FT Appendix F made no use whatsoever of the autocorrelation sequence, much less its Z transform or the Wiener-Khintchine theorem. For an MLS spectrum these concepts just provide an alternate pathway to computing the spectrum, and of course it is gratifying to see the result come out the same by either method. Deep down, and perhaps not really that deep down, both methods are the same method with a different order of calculation, and the intermediate objects have different names or in some cases no names at all.