Chap3 8

Chapter 3: The Matrix Approach Chapter 3: The Matrix Approach Chapter Contents 3.1 Review of earlier Chapters 3.2 Matrix Solution of Figure 2. The A matrix. 3.3 Matrix Solution of Figure 1. The B matrix. 3.4 Shift Register Generators Revisited Fact 1: The entire state vector of a primitive polynomial shift register generator satisfies the difference equation (2.3.2). Thus, each component of the state vector satisfies (2.3.2) as well, and each component is the state of a particular register. Fact 2 : The state of each individual register in a primitive polynomial shift register generator cycles through the characteristic sequence. 3.5 The Output of a Scrambler Fact 2 : In the presence of an input stream {i n}, and with initial state vector q0 = 0, the state of any register of a primitive polynomial scrambler equals the "dot product" of a characteristic sequence multiplied by the (time reversed) input sequence. A Lemma: Review of Leeper 1973. 3.6 The Spectral Density of a Scrambler Output " Barring anomolous input sequences, the spectral density of the output of an operating scrambler is essentially the same as the spectral density of a random white NRZ signal." Interpretation of the Spectrum; Power Distribution by Hump 3.7 The NRZI Mi ni-Scrambler. Fact 1 : The output of the above mini -scrambler changes state each time a one is encountered in the input data stream, and it holds its state each time a 0 is encountered in the input stream. Definition : An NRZI line code is what emerges from the mini -scrambler when you input a NRZ linecode. Scrambler Summary! 3.8. Matrix analysis of the polynomial multiplier (de -scrambler) of Figure 7 . 3.9 Matrix analysis of the standard polynomial multiplier of Figure 8 . Chapter 3: The Matrix Approach 3.10. Proof that a Descr ambler really descrambles the output of a Scrambler. Figure 3.10.1: Proposed scrambler structure for serial digital communication . Proof in the Z Domain; Proof in the Time Domain; Conclusions (contents continued on next page) Chapter 3: The Matrix Approach 1 3.11 The Kill Sequence Problem and Strings of Zeros Fact 1 : It is possible that a k -stage scrambler will output a string of N+k zeros if a string of N zeros exists in the input stream; the probability is 1/P where P = 2k - 1. Example 1 : Suppose in D1 video. Example 2 : Ancillary data Fact 2 : Assume a scrambler is in some state a. Consider the k -symbol pattern that next shifts in, call this pattern i. After this pattern shifts in, the scrambler is in state b. We claim that, given any patterns a and b, there exists a unique pattern i which causes a to go to b. Corollary 2 : If pattern b is 0, there exists a unique pattern i which takes a to 0. Definition : Such a pattern is called a kill vector . Explicit formula for vector i. Example : k=9 Discussion of the zeros problem. Fact 3 : If a k -stage scrambler has an even number of feedback taps, then if the input stream is set to all 1's, the scrambler behaves exactly as if the input stream were all 0's and there were an inverter on the final output. Some final notes: Appendix 3.1: Proof of Eq. (3.10.15) Chapter 3: The Matrix Approach 2 Chapter 3: The Matrix Approach This Chapter will lean heavily on Galois Chapter 8. There, it was shown that it is possible to construct an explicit matrix representation of any Galois Field. Her e, as we attempt to solve directly for the output sequence (and state vector sequence) of a scrambler, we will find ourselves eyeball -to-eyeball with exactly the matters discussed in Galois Chapter 8. 3.1 Review of earlier Chapters Because this document is so lengthy, we feel it is always worthwhile to review our current status. In Chapter 1 we discussed the polynomial divider circuits of Figure 1 and Figure 2. Figure 1 is what we called "the scrambler style" circuit, whereas Figure 2 is the "standar d circuit". We showed how these circuits both perform the division of polynomials O(z) = I(z)/H(z). An attempt was made to show how each circuit carries out this task in comparison to the way a human being would carry out the long division of polynomials. The Figure 2 circuit was in some ways easier to understand since its registers always contain the current remainder, or current dividend. However, the Figure 1 circuit is intrinsically more interesting to use since we are really studying Scramblers. Polynomial multipliers were also treated in Chapter 1, and again two circuit forms were considered, Figure 7 and Figure 8. We spent less time worrying about the multipliers because they have no feedback, only "feedforward" and are easier to understand. It is a mathematical fact that multiplication is simpler than division. In Section 1.8 of Chapter 1, we gave a summary box which outlines the behavior of dividers and multipliers in both the Z -domain and the time domain. In the Z -domain, the equations are just the statements of polynomial division and multiplication. In the time domain, we get difference equations which relate the output stream symbols to the input stream symbols. In Chapter 2 we attempted to characterize the behavior in time of the polynomial divider circuits with their input streams set to zero. Such circuits are called shift register generators. Of particular interest is the periodicity of the register "state vector", and the periodicity of the output stream. We showed that the u se of a Galois primitive polynomial for the polynomial h(x) [ same as H(z) ] resulted in things having the maximum possible periods. We made no comments as to whether this is good or bad, desirable or undesirable. In Section 2.3 we did a rather thorough analysis of the difference equation which describes the output sequence o n of a shift register generator, namely,  j=0k hj on+j = 0 n = any integer (2.3.2) repeated Chapter 3: The Matrix Approach 3 Here we were dealing with numbers in GF(p), and with a shift regis ter generator having k registers, and hi were the feedback coefficients, also the coefficients of h(x). We showed that there are pk solutions of the difference equation, one of which is all zeros. In the interesting case that h(x) is a primitive polynomial of GF(pk), the remaining pk - 1 solutions turned out to be starting time variations of one characteristic solution of the form { c,c,c,c...}. Here, the sequence c has period pk - 1, and c could be considered any code word of the cyclic code (n=pk - 1, k). The generator of this code, g(x), is a polynomial of degree n -k = pk - 1 - k which is obtained by dividing xn - 1 by h(x). It seemed simplest to consider the sequence c to be the code word consisting of the (pk - 1 - k) + 1 coefficients of g(x), padded with (k -1) zeros. We went on to state various properties of the characteristic sequence, also known as a maximal length sequence. Along the way, various Facts from the Galois notes were quoted and used. In Section 2.2 we used the special polynomi al residue class ring representation of GF(pm ) to show that the behavior of the Figure 2 divider circuit could be described by a Galois Iterator equation, which we duplicate here: s = s 0 + [ s-1 i0 + s-2 i1 + .... +  is-2 + is-11 ] 1 (2.2.10 ) repeated The symbol 0 represented the starting state vector of the registers in Figure 2. Then s gave the state vector after s clockings of the circuit. We identified  with a certain entity {x}. As can be seen in the above, the input sequence i n does of course play a role in the subsequent state vector s. We then turned off the input stream to get the simpler equation s = s 0 which describes the shift register generator. Perhaps the reader noticed on the part of the writer a certain dissatisfaction with the above equation, and how it was not very much pursued, although it was declared to be important. There were several problems. First, we seemed to have the above equation apply to Figure 2, but not to Figure 1. This certain ly is unsatisfying, since both circuits do the same thing, and since Figure 1 is the circuit used for a scrambler. Secondly, the equation above has a certain abstract feel to it. We have these abstract Galois elements  and  floating around, and we have a dim connection that  = {x} where {x} is an element of some polynomial quotient ring business. But the connection to our circuits is just not very clear. On the other hand, we realize and appreciate how the abstract Galois theory has provided us with all of our most powerful claims made so far, such as those about the period of the characteristic output sequence of a shift register generator. In the present Chapter, all these deficiencies will be remedied. 3.2 Matrix Solution of Figure 2. We assume from here on out that h(x) is monic, so that h k = 1. From Section 1.4 we describe the operation of Figure 2 as qj+1(n+1) = d j+1(n) = q j(n) - hj o(n) j = 0,1,2,...k -1 (1.4.1) repeated Chapter 3: The Matrix Approach 4 As earlier, we write f(n) = f, and f(n+1) = f'. Since h k = 1, o = q k . And i = q 0. We now explicitly write out the above k equations: q'1 = i - h0 qk q'2 = q1 - h1 qk q'3 = q2 - h2 qk q'4 = q3 - h3 qkk (3.2.1) ... q'k-1 = qk-2 - hk-2 qk q'k = qk-1 - hk-1 qk These equations can be trivially re -expressed in matrix form as follows. ( we apologize for the vertical bars in place of proper large parentheses) q'1 0 0 0 ... 0 -h0 q1 i q'2 1 0 0 ... 0 -h1 q2 0 q'3 0 1 0 ... 0 -h2 q3 0 q'4 = 0 0 1 ... 0 -h3 q4 + 0 ... .................................................................... ... .. q'k-1 0 0 0 ... 0 -hk-2 qk-1 0 q'k 0 0 0 ... 1 -hk-1 qk 0 (3.2.2) Now we can write this in compact vector/matrix notation as: q' = A q + i 1 (3.2.3) Here q and q' are the obvious column vectors, 1 is a unit column vector, and A is the matrix. Now put back the time indices n which we took out above, and get rid of the primes. Put the time index as a subscript, since this notational slot is again available, qn+1 = A qn + in 1 (3.2.4) This is a vector difference equation for the state vector q n of Figure 2. It is easy to solve (3.2.4) by brute force, and here is the result: qn = An q0 + [ i 0 An-1 + i1 An-2 + .... + i n-2 A + in-1 I ] 1 (3.2.5) Observations: Chapter 3: The Matrix Approach 5 (1) The matrix A has exactly the "companion" form C discussed in Galois Chapter 8, Section 8.5. This means that h(x) is the characteristic polynomial of A. (2) Therefore, from Big Fact 2 of Section 8.1, we kno w that h(A) = 0, which we can rewrite as, Ak = - ho I - h1 A - h2 A2 - ... - hk-1 Ak-1 (3) Since A is a root of h(x), we know that A is some element of a matrix representation of the Galois Field GF(pm). (4) It follows from the Section 8.5 Big Corollary that, if h(x) is a primitive polynomial of GF(pm), then the matrix A can be regarded as an explicit matrix representation of an abstract primitive element  of the Galois Field GF(pm). In this case, all non -zero elements of GF(pm ) can be represented as powers of A. (5) The above solution (3.2.5) is a concrete realization of the abstract Galois Iterator obtained in Chapter 2, Eq. (2.2.10), n = n 0 + [ i 0 n-1 + i1 n-2 + .... + i n-2  + in-1 1 ] 1 (2.2.10 ) repeated In (2.2.10) the quantities 0, n , k, 1 are abstract field elements, and the i k are numbers in GF(p). In Eq. (3.2.5) the quantities 0, n , and the outside 1 are replaced with vectors q0, qn, 1. The quantities k and the inside 1 are replaced w ith matrices Ak and I. Equation (3.2.4) could be put into a computer to generate the state vector sequence, while (3.2.5) gives the result in closed form. Before going on the draw more conclusions, we pause to derive a similar matrix equation for the scrambler circuit of Figure 1. 3.3 Matrix Solution of Figure 1. In notation similar to that of the previous section, we now write the equations of motion for the divider circuit of Figure 1 q'k-1 = i - h0 q0 - h1 q1 - h2 q2 -... - hk-1 qk-1 q'k-2 = qk-1 q'k-3 = qk-2 q'k-4 = qk-3 (3.3.1) ... q'1 = q2 q'0 = q1 These equations can be trivially re -expressed in matrix form as follows, Chapter 3: The Matrix Approach 6 q'k-1 -hk-1 -hk-2 -hk-3 ... -h1 -h0 qk-1 i q'k-2 1 0 0 ... 0 0 qk-2 0 q'k-3 0 1 0 ... 0 0 qk-3 0 q'k-4 = 0 0 1 ... 0 0 qk-4 + 0 ... ............................................................... .. .. q'1 0 0 0 ... 0 0 q1 0 q'0 0 0 0 ... 1 0 q0 0 (3.3.2) As before, we can write this in co mpact vector notation as, q' = B q + i 1 (3.3.3) Notice that the ordering of the registers in the vector q is different here than it was in the previous section. Making the same notational change as before, we get a difference equation and solution: qn+1 = B qn + in 1 (3.3.4) qn = Bn q0 + [ i 0 Bn-1 + i1 Bn-2 + .... + i n-2 B + in-1 I ] 1 (3.3.5) The matrix B above is in one of the standard forms for a companion polynomial (form C 1 of Galois Section 8.5). Thus, all obse rvations made about matrix A in the previous section also apply to matrix B here. This is a step forward from Chapter 2. We now see that the Galois Iterator equation applies to Figure 1 as well as Figure 2. These iterator equations are (3.2.5) and (3.3.5). 3.4 Shift Register Generators Revisited We have learned that, whether implemented as Figure 1 or Figure 2, the "equation of motion" of the state vector of a scrambler has the basic form exemplified in (3.2.5) and (3.3.5). We are now in a posi tion to make more powerful statements about the shift register generator than we were able to make in the previous chapter. Consider such a generator. Setting the input sequence to zero in (3.3.5) we get, qn = Bn q0 n = 0,1,2... (3.4.1) In particular we can wite Bj qn = Bj+n q0 = qn+j (3.4.2) Meanwhile, we know that matrix B is a root of the primitive polynomial h(x), h(B) = 0, so we can write: Chapter 3: The Matrix Approach 7  j=0k hj Bj = 0 (3.4.3) Now apply both sides of (3.4.3) onto the vect or qn, and make use of (3.4.2) to get  j=0k hj qn+j = 0 (3.4.4) Each side of this equation is a k -component vector. We have now proved the following Fact 1 : The entire state vector of a primitive polynomial shift register generator satisfies the difference equation (2.3.2). Thus, each component of the state vector satisfies (2.3.2) as well, and each component is the state of a particular register. In Chapter 2 we learned a lot about sequences which satisfy (2.3.2), for h(x) be ing a primitive polynomial of GF(2k). The main results were stated in Facts 8 and 9 of Section 2.3. The upshot is that any solution of (2.3.2) is a characteristic sequence. Therefore we now know that: Fact 2 : The state of each individual register in a primitive polynomial shift register generator cycles through the characteristic sequence. Notice how this is an improvement over Fact 11 of Section 2.2. Corollary 2 : The output of a shift register generator cycles through the characteristic sequenc e. Proof : This is just because the output happens to be one of the registers. 3.5 The Output of a Scrambler In this section, finally, we consider the output of our polynomial divider circuit of either Figure 1 or Figure 2 when there is an input stream present. Such a device is known as a data scrambler. As above, we assume there are k registers, and that the feedback polynomial h(x) is a primitive polynomial of GF(2k). First, we need one more technical matter dealt with. Take (3.4.3) and multiply both sides by Bn to get,  j=0k hj Bj+n = 0 (3.5.1) This says that difference equation (2.3.2) is also obeyed by the following sequence of matrices : { I, B, B2, ....}. If we examine any particular matrix element of this sequence of matrices, call it the rs element, this sequence of numbers also satisfies (2.3.2), that is, Chapter 3: The Matrix Approach 8  j=0k hj [Bj+n ]rs = 0 (3.5.2) We now just proved: Fact 1 : The sequence of numbers [Bn ]rs for any fixed rs, and for n=0,1,2.... eithe r cycles through the characteristic sequence, or is identically 0. Thus, [Bn ]rs = gn, n = 0,1,2.. where we indicate by {g n} the characteristic sequence. Aside : I feel certain that this second option is not possible ([Bn ]rs identically 0) , but do not know how to prove it. It has little bearing on the following discussion. Example : If you look at the example at the end of Galois Section 8.5, you see that each matrix element of the set of matrices {An} for GF(8) runs through the sequence 0010 111. Don't forget to include the identity matrix, so there is a total set of 7 matrices. Now consider (3.3.5) in the case that the starting vector q0 = 0. In other words, we assume that at some (possibly ancient) time the scrambler was in the zero state, and then some input stream began. We then have: qn = [ i 0 Bn-1 + i1 Bn-2 + .... +i n-2 B + in-1 I ] 1 =  j=0n-1 in-1-j [Bj ] 1 (3.5.3) We can express the sth component of this vector equation (corresponding to the state of som e register s) as follows, [qn ]s = i0 [ Bn-1]s,1 + i1 [Bn-2]s,1 + .... + i n-2 [B]s,1 + in-1 [I]s,1 =  j=0n-1 in-1-j [Bj ]s,1 (3.5.4) According to Fact 1, the sequence of matrix elements in this sum is a characteristic sequence. For convenience, we shall label this sequence as follows: g j+1 + [Bj]s,1 Then we can rewrite (3.5.4) as , [qn ]s = in-1 g1 + in-2 g2 + in-3 g3 + .. i1 gn-1 + i0 gn =  j=1n gj in-j (3.5.5) We have now proved the following: Chapter 3: The Matrix Approach 9 Fact 2 : In the presence of an input stream {i n}, and with initial state vector q0 = 0, the state of any register of a primitive polynomial scrambler equals the "dot product" of a characteristic sequence multiplied by the (time reversed) input sequence. We now wish to make some comment about the statistical nature of [ qn ]s . Remember that one of the registers (some s) in either Figure 1 or Figure 2 represents the output stream of the scrambler, so we are really seeking a st atement about the scrambler output statistics. To this end we need: Lemma : If you add up n terms of a sequence {r i} in GF(2), and if each term in the sequence is an independent random variable with probability  of being 1, then the probability that the sum of the n terms equals 1 is given by Pn = (1/2) [ 1 - (1-2)n ] Notice that, if 0 <   , Pn approaches 1/2 as n keeps increasing. Also, if  = 1/2, P n = 1/2. Proof : Let P n = probability that the sum of n terms is a 1. Then add one more term to get Pn+1 = Pn(1-) + (1-Pn) = P n (1 - 2) +  =  Pn +  where we define  = (1 - 2). Iterate this difference equation starting with P 1 =  to get Pn =  (1 +  + 2 + ... + n-1 ) =  ( 1 - n)/(1-) = (1/2) ( 1 - n). Q.E.D. Now consider the state of any scrambler register as being the (reversed) input sequence dotted with the characteristic sequence, as shown in (3.5.4) above. Consider one particular term in this sequence, for example, g3 in-3 Assume that an input bit ( like i n-3) has a probability p of being a 1. We know (see Section 2.5, Case 1 Analysis,  = p') that the probability of a characteristic sequence bit being 1 is p' =  = (1/2)(1 + 1/P), where P = 2k - 1 = the Period of the characteristic sequence. In other words, for reasonably large k, p' is just slightly larger than 1/2. In order for our term g 3 in-3 to be 1, both factors must be 1, so the probability that this term is 1 is  = pp' p = input sequence prob of 1 p' = (1/2)(1 + 1/P) ≈ 1/2, P = 2k - 1 We c an now use the above Lemma to obtain the probability that the n term sum shown in (3.5.5) is a 1: { Prob that [q n ]s = 1 } = (1/2) [ 1 - (1-2pp')n ] Chapter 3: The Matrix Approach 10 Since p' ≈ 1/2, we have  = pp' < 1/2 unless p is unusually close to 1. Thus, as the scrambler continues to run and n increases, the probability that any register of the scrambler is a 1 gets closer and closer to 1/2, regardless of the value of the p of the input stream, as long as p is not too close to 1. Admittedly, we have not been too rigorous i n our statistical analysis. With this caveat, we claim to have proven the following fact Fact 3 : If we assume that the input stream is characterized by a p in some reasonable range, say 0.1 < p < 0.9, then after some number M of clocks has passed, the p of any register of the scrambler is very close to 1/2. It differs from 1/2 in our example by amount (1/2) (0.9)M. If we let M = 1000 clocks, this difference quantity is on the order of 10-46. Corollary 3 : Barring highly anomolous input streams, a nd assuming the average value of the input stream (with symbols 0,1) lies in some reasonable range like 0.1<p<0.9, and assuming there are at least say 6 registers in a primitive polynomial data scrambler, so that p' ≈ 1/2 , then after the scrambler runs for on the order of 1000 clocks, the average value of the output stream will be so close to 1/2 that the variation from 1/2 will be unmeasureable. Review of Leeper 1973. A Universal Digital Data Scrambler , by David. G. Leeper, BSTJ 52,10, Dec 1973, pp 1851 -1865. This paper considers the scrambler -descrambler combination just as we are used to seeing it. Earlier papers dealt with scramblers having periodic input streams, while this paper deals with an arbitrary input stream. Subject to a certain technical qualification, the paper concludes that, by choosing a sufficiently large number of stages in the scrambler, the output sequence can be made as "white" as one requires. By this, the author means that the "first and second order statistics" of the sc rambler output can be made arbitrarily close to those of white noise. The "first order statistics" is that the probability of an output bit being a 1 can be made as close to 1/2 as required. We have shown in our own discussion above how this comes out, and we have stolen some of Leeper's arguments in our presentation. The "second order statistics" are twofold. First, Leeper shows that the autocorrelation function of the output sequence can be made arbitrarily close to that shown in our Figure 2.5.2 of Chapter 2. Second, he shows that any pair of symbols in the scrambler output sequence can be made as "independent" as required. This means that the "joint second -order density" p(o m, on) = p(o m)p(o n) + , where  can be made as small as required, again by choosing a suitable number of registers k. Here {o n} is the output sequence. Since the first order statistic says that p(o m) ≈ 1/2, he gets p(o m, on) ≈ 1/4. The "technical qualification" of the paper is a bit tricky, and we hope that some later p aper has been able to bring it a little closer to the practical realm. It is my belief that with k=9 stages, a scrambler designed for use with signals which come from a "live" video source will easily meet this technical qualification. The technical qualification is that the input stream cannot be "too perfect" in some sense, and the author is able to make it less perfect by intentionally adding some "error" to the input stream by simulating a binary symmetric channel with some small probability of error. Leeper comments that the inherent Chapter 3: The Matrix Approach 11 noise in a digital signal that derives from an analog source is likely to have a sufficient amount of this "imperfection" so that a scrambler with a small number of registers will meet the conditions of his Universal Scrambler Theorem, which results in the conclusions noted above -- namely, that the output stream has the same first and second order characteristics as white noise. 3.6 The Spectral Density of a Scrambler Output The basic conclusion of the previous sec tion can be summarized as follows: " Barring anomolous input sequences, the spectral density of the output of an operating scrambler is essentially the same as the spectral density of a random white NRZ signal." The interesting fact we learned is that, even if p ≠ 1/2 for the input stream, we end up with p = 1/2 for the output stream. This is what "white" means in our current context. We have already derived the spectral density of such a signal in Spectral Section 6.6(a), and we quote that result he re, setting p = 1/2: <|X()|2> T = V2 T1 [ sinc( T1/2) ]2 { (1/4) + (1/4) 2(T1) } Spectral (6. 6.1) If we integrate the DC line, we get power = (V/2)2 . Our "power" in effect operates on a 1 ohm load, so this is the power going into a cable due to the average voltage being (1/2) V. In a real system this would be blocked by adding a DC offset to the signal, then there would be no DC line at all. This leaves the interesting part of our scrambler output spectral density, <|X()|2> T = (V/2)2 T1 sinc2(T1/2) (3.6.1) Here, T 1 is the width of a NRZ "1" or "0", and V is the peak -to-peak amplitude of the NRZ signal. Interpretation of the Spectrum It might be helpful to look at the Spectral Figure 17.1 plot of sinc(x) , which we repeat here, Chapter 3: The Matrix Approach 12 For a periodic square wave pulse train having half -pulses of width T 1, the spectrum was a line spectrum with the first "fundamental" line occurring at x = /2 of sinc(x = T1/2). This line is at  = / 2T1 f = 1/(2T 1) = (1/2) f 1. If such a signal represented the string 01010101... for a 140 Mbit/sec NRZ signal, one would have f 1 = 140 MHz, and f = 70 MHz. One would normally use a channel with slightly more than 70 MHz bandwidth, and get this line passed through, and ignore the higher lines. Our scrambler output signal is different. The spectrum is entirely continous, and it is the area under the above sinc(x) curve squared. In the pure periodic square wave signal, each "line" was at the peak of one of the abo ve humps. In the scrambled real signal, one can imagine that each such discrete line has been broadened out to encompass the entire hump. The right side of the hump is the "upper sideband", and the left side of the hump is the "lower sideband". There is no residual "carrier" line left at the center of each hump. However, there is amplitude at the hump centers, just as there is everywhere except at the zeros. It is just the amplitude of the continuum sinc2(x) envelope. Fact: If you have a 140 Mbit/s ec scrambled NRZ signal, and you want to pass the entire main hump, you need a system bandwidth of 140 MHz. To pass the left half of the main hump only, you are back to the 70 MHz bandwidth. Power Distribution by Hump It might be interesting to examine the amount of power in various portions of the spectrum. We obtain relative answers by integrating sinc2(x) over various ranges. This is not a handy closed form integral, the easiest thing is to do parts and cast the indefinite integral in terms of the Si(x) (sine integral) function. We will then integrate from 0 to various points of interest:  0b dx sinc2(x) = -sin2(b)/b + Si(2b) Here is a table, Chapter 3: The Matrix Approach 13 b 2b Si(2b) = -sin2(b)/b integral /2  Si() = 1.8519370 -2/ = -.6366198 1.2153172  2 Si(2) = 1.4181516 0 1.4181516 2 4 Si(4) = 1.4921612 0 1.4921612 3 6 Si(6) = 1.5180339 0 1.5180339 4 8 Si(8) = 1.5311313 0 1.5311313 5 10 Si(10 ) = 1.5390291 0 1.5390291 ∞ ∞ Si(∞) = /2 = 1.5707963 0 1.5707963 And here are the contributions of the various humps, as a percent of the total power: % Left Half of Main Hump = 1.2153172/1.5707963 =0.7736950 = 77.4% % Right Half of Main Hump = (1.4181516 - 1.2153172)/1.5707963 =0.1291284 = 12.9% % Main Hump = 1.4181516/1.5707963 = 0.9028234 = 90.2% % Second Hump = (1.4921612 - 1.4181516)/ 1.5707963 = 0.0471160 = 4.7% % Third Hump = (1.5180339 - 1.4921612)/ 1.5707963 =0.0164711 = 1.6% % Fourth Hump = (1.5311313 - 1.5180339)/ 1.5707963 =0.0083381 = 0.8% Fact: If, for a 140 Mbit/sec NRZ signal, you pass only the left half of the main hump by using a 70 MHz bandwidth system, you pass 77.4% of the power spectrum. This seems like a reasonable thing to do. 3.7 The NRZI Mini -Scrambler. Typically, a scrambler circuit is followed by an output stage consisting of this circuit: Figure 3.7.1: The NRZI mini -scrambler. This is a k=1 scrambler (see Figure 1) , and the only possible irreducible polynomial is h(x) = 1 + x, so h 0 = h1 = 1. Thus, the mult iplying x's in the figure can be ignored ( -1 = +1 in GF(2) ). Consider the generator matrix B for this scrambler that we would use in equation (3.3.5). The matrix represents a primitive element of GF(2k) = GF(21) = GF(2) = {0,1}. Thus, the matrix is 1x1 and is simply the number "1". B = 1 h(B) = 0 = the characteristic polynomial = B + 1 Chapter 3: The Matrix Approach 14 The state vector for this scrambler is the state of its one register. Using this fact, and B = 1, we can write down equation (3.3.5) as follows: on = o0 + [ i0 + i1 + i2 + ... + i n-1] (3.7.1) Thus, the output of this "mini -scrambler" is simply the sum of the input stream plus the initial state of the register. Assume that n -1 bits have been input as shown, and that o n has some value, either 0 or 1. Consider the effect of the next input bit i n. If it is a 0, o n does not change, and if it is a 1, o n toggles. We have now proven that Fact 1 : The output of the above mini -scrambler changes state each time a 1 is encountered in the input data stream, and it holds its state each time a 0 is encountered in the input stream. Comment : We have shown this result based on a trivial reduction of our matrix scrambler formalism. The result is of course obvious just looking at the above circuit, since the GF(2) adder is an XOR gate. Definition : An NRZI line code is what emerges from the above circuit when you input a NRZ linecode. NRZ means "non -return -to-zero", the idea being that on a 1 or mark, the signal stays at 1 for the entire state of the mark, whi ch we have usually called T 1. Various other line codes only hold the mark for half the period and are therefore called RZ or "return to zero" type codes. The I in NRZI = NRZ(I) means that one bit value (in our case a 1) is encoded as an Inversion of the level, ie, as an edge. Corollary 1 : In an NRZI signal as output by the above flipflop, a 1 is indicated by a state which begins with an edge, and a 0 is indicated by a state which begins with no edge. The location of the state relative to the edge it u nimportant . The important thing is that a 1 is represented by an edge, and a 0 is represented by the absence of an edge. Observation : Since there is no mention of the polarity of an "edge", we see that the NRZI signal is non - polar. If you have a differential NRZI signal carried on a twisted pair, it does not matter which way you hook up the wires at the receiver. Hooking them up "wrong" just changes the polarity of edges, which does not affect the interpretation of the NRZI signal in terms of 1's and 0's. The desire to have a non - polar signal is the only reason for the use of the mini -scrambler following the main scrambler. Question : What is the effect of the mini -scrambler on the output of the main scrambler in terms of statistics and frequency spectrum? On its own, the mini -scrambler cannot add any statistical whiteness to its incoming data stream. It is too weak to do this. We have seen above how the mini -scrambler produces an output stream that is just a sum of the input stream. This should be compared with Equation (3.5.5) of Section 3.5 which shows what a "real" scrambler does to its input stream. The stream is multiplied term by term with the characteristic sequence of the scrambler. For reasonable k, this characteristic sequence {g i} is "pseudorandom" and "induces" onto the output stream its random nature. For the mini -scrambler, the length of the characteristic sequence is 21 - 1 = 1, so the charactersitic sequence is simply { 1,1,1,1,1 ...}. You can imagine in Eq. (3.7.1) that the input sequence is multiplied by Chapter 3: The Matrix Approach 15 this light -weight characteristic sequence. Obviously, the sequence { 1,1,1,1,1 ...} does not carry a lot of whitener. It is like a bad detergent. Nevertheless, the mini -scrambler is applied after the action of the main scrambler. Thus, the input to the mini -scrambler is already "white". This means that p = 1/2 and the individual bits emerging from the main scrambler are to a high degree statistically independent. We can therefore use the Lemma of Section 3.5. This Le mma describes exactly the situation we have above. The output sequence of the mini -scrambler is a sum of n terms of the sequence {i} in GF(2), and the input bits are independent. Thus, we get: output stream probability of 1 = P n = (1/2) [ 1 - (1 - 2/2)n ] = 1/2 In other words, white -in gives white -out. If the input stream to the mini -scrambler is slightly off white, perhaps p = 1/2 +  say, then we get output stream probability of 1 = P n = (1/2) [ 1 - (-2)n ] This shows that the P n of the mini -scrambler output oscillates around the P n = 1/2, always getting closer to it as time goes by. So in this sense, the whiteness of the main scrambler is somewhat improved by the mini -scrambler. However, the main issue here is the statistical independence of the bits, ie, the "higher order statistics" that you cannot see just looking at the first order statistical quantity P n. It is the job of the main scrambler to generate this independence. We summarize these remarks as follows: Scrambler Summary: (a) We first assume that the main scrambler does its job of producing a white output sequence. If the output of this scrambler is applied through an output driver to a line, the resulting spectrum is obtained from Eq. (2.6.2) for the single -ended Case 1 signal of Figure 2.6.1, and from Eq. (2.6.4) for the differential Case 2 signal of Figure 2.6.2. In each case, we set P = ∞ since we assume full whiteness. <|X()|2> T = |Xpulse ()|2 T1 (1/4) { 1 +  m=-∞∞ 2(-2m) } (2.6.2) Case 1 <|X()|2> T = |Xpulse ()|2 T1 { 1 } (2.6.4) Case 2 Here, X pulse () is the Fourier Integral transform of the pulse shape used to drive the line at the output of the scrambler. T 1 is the time duration of one state (high or low). The LHS of each of these equations is the "spectral power density" P( ), so that P( )d is measured in watts. Chapter 3: The Matrix Approach 16 (b) If the main scrambler input is set to all zeros -- a highly non -random data stream -- the above formulas are still cor rect with a very small amount of error. The error is in the form of the 1/P corrections appearing in (2.6.2) and (2.6.4), where P = length of main scrambler characteristic sequence. (c) Under the assumption of (a), the insertion of the NRZI mini -scrambler between the main scrambler and the output driver circuit has zero effect on the statistics of the output signal, and zero effect on the above power spectrum of the output signal. (d) If the line driving pulse is selected to be an ideal box of width T1 and height V, and if we add a DC offset to the driven signal as needed to eliminate any DC component (add a capacitor), the Case 1 result above reduces as shown in Eq. (3.6.1), <|X()|2> T = (V/2)2 T1 sinc2(T1/2) The power spectrum is continuous, there are no discrete lines whatsoever. (e) Other pulse shapes can be evaluated using the above formulas and the Fourier Transform discussed in the Spectral notes. (f) One of the main motivations for using a scrambler in the first place is to obtain the above continuous spectrum. Since power is smoothly distributed over a continuum of frequencies and there are no sharp lines, crosstalk between cables and circuits carrying scrambled signals is minimized. RFI emissions are also held in check. (g) Notice that this is true even if the input signal to the main scrambler is all zeros. In this case, the main scrambler simply outputs its characteristic sequence. (h) Another motivation for scrambling is to reduce the frequency of occurrence o f large "edge -less" periods in the signal. Such streams make clock recovery more difficult. Because of the NRZI output circuit, only strings of zeros output by the main scrambler are of concern in this regard. According to our discussion in Section 2.4, the probability distribution of strings of n zeros output by the main scrambler (and also by the mini -scrambler) is independent of the distribution of such strings in the source signal, and is given to a high degree of accuracy by the simple formula P(n) = 2-n. When the source input stream is all zeros, the maximum length of a zero output string is k -1. However, for real input data, arbitrarily long strings of zeros are possible with relative probability 2-n. This subject will be discussed further in Section 3.11 below. 3.8. Matrix analysis of the polynomial multiplier (de -scrambler) of Figure 7 . As noted earlier, the polynomial multiplier circuits are easier to analyze than the corresponding divider circuits mainly because the multipliers have n o feedback. Since this is a Chapter on the Matrix Approach, and since we later want to prove by brute force that the scrambler -descrambler combination really does pass data unaltered, we pause here to analyze our multiplier circuits. Chapter 3: The Matrix Approach 17 For the circuit shown in Figure 7, the equation of motion for the state vector is very simple, and the output is a linear combination of the contents of the registers. That is, the output is a function of the state vector. The data simple flows through the flipflops from l eft to right, so that q 0' = q 1, and q 1' = q 2 , etc. When this is put in our usual matrix form we get, q'k-1 0 0 0 ... 0 0 qk-1 i q'k-2 1 0 0 ... 0 0 qk-2 0 q'k-3 0 1 0 ... 0 0 qk-3 0 q'k-4 = 0 0 1 ... 0 0 qk-4 + 0 ... ............................................................... .. .. q'1 0 0 0 ... 0 0 q1 0 q'0 0 0 0 ... 1 0 q0 0 (3.8.1) The matrix here has the same form as in Eq. (3.3.2) for the scrambler divider circuit of Figure 1, except here all th e feedback entries in the first row are zero. As before, we use matrix/vector notation to rewrite the above as q' = Cq + i1. We then re -install the time index n to get the vector difference equation and its solution: qn+1 = C qn + in1 (3.8.2) qn = Cn q0 + [ i0 Cn-1 + i1 Cn-2 + .... + i n-2 C + in-1I ] 1 (3.8.3) The column vector qn has the following components, where we revert to a former notation of putting the time index as an argument, [ qn ]s = qk-s(n) (3.8.4) For exa mple, with s=1 the first component of the column vector qn equals the register q k-1 of Figure 7 at time n. We have named the above matrix "C", not to be confused with the companion C of Galois Chapter 8. The matrix C has the following matrix elements, as can be seen from (3.8.1), Cij = i,j+1 , [C2] ij = i,j+2 , ... [Cn] ij = i,j+n (3.8.5) The matrix C2 has the ones slid down to the next lower subdiagonal, and so on for higher powers. Finally, the matrix Ck-1 has a single non -vanishing element , a 1 in the lower left corner. All higher powers Cn = 0 for n ≥ k. Thus, in the solution (3.8.3), most terms vanish. Only those terms having powers less than k survive. We therefore rewrite (3.8.3) as, qn = Cn q0 + [ in-k Ck-1 + i n-3 C2 + in-2 C + in-1I ] 1 I = C0 Chapter 3: The Matrix Approach 18 = Cn q0 +  j=1k in-j [Cj-1] 1 (3.8.6) Interpretation : If n≥k, the current state vector of the multiplier is affected only by the most recent k input symbols. If n < k, the first term in (3.8.6) has not yet vanished, so some components of the starting state vector q 0 still have an effect. These comments are of course totally trivial, since the circuit is just a shift register. After the first k clocks of operation, the original contents (the starting state vector) have been shifted out and have no influence on anything that happens in the future. This is in sharp contrast to what happens in the polynomial divider circuit, where the starting state vector has a lingering influence tha t lasts forever. An exercise in notation. This section is included only to demonstrate how to deal with the strange matrix/vector notation used above and in earlier sections of this Chapter. The purpose of this exercise is to use the above matrix/vector notation and to try and recover the time -domain statement of how a polynomial multiplier works. In an upcoming section we will be attempting a rigorous time -domain proof that a descrambler really does recover the source data stream that went into t he scrambler. In other words, we will prove that a self-synchronizing scrambler/descrambler combination really works. In that proof, manipulations of the kind appearing below will be used a lot, so the following "exercise" is a sort of warm up. Consider the sth component of the vector equation (3.8.6), [qn]s =  j=1k [ Cn ]s,j [q0]j +  j=1k in- j [Cj-1]s,1 (3.8.7) According to (3.8.4), we have [ Cn ]s,j = s,n+j and [Cj-1]s,1 = s,j so both sums go away giving [qn]s = [q0]s-n + in-s = [q0]s-n (n<s) + i n-s (n≥s) (3.8.8) Here we have added explicit  functions [ (A) = 1 if A true, 0 if A false ] to show that only one of the two terms can be non -vanishing for a given s. The vector index s -n must be in the range (1,k) so s -n ≥ 1 n<s for the first term. And the input sequence is assumed to begin with i 0 , hence n -s ≥ 0 in the second term. Now use (3.8.4) to rewrite this last result as [qn]s = qk-s(n) = q k-s+n(0) (n<s) + i n-s (n≥s) (3.8.9) Chapter 3: The Matrix Approach 19 This is an elaborate statement of a trivial fact, see Figure 7. Consider register q k-s . If the number of clocks n is less than s, then after n clocks from startup, register q k-s contains the startup contents of the register n to the left. If n > s, register q k-s contains i n-s. If this still seems strange, pick a particular value of s ( try s=1) and stare at Figure 7. The output of the polynomial multiplier can be written in terms of the components of vector q n: on =  s=0k-1 hs [qn ]k-s + hk in (3.8.10) If the vector solution (3.8.9) is inserted into (3.8.10), we can solve for the output sequence o n of our polynomial multiplier: on =  s=0k-n-1 hs qs+n(0) +  s=k-nk hs in+s-k (3.8.11) As a test of this result, lets examine the first two terms in this output sequence, o0 =  s=0k-1 hs qs(0) + hki0 , o1 =  s=0k-2 hs qs+1(0) + hk-1i0 + hk i1 For n ≥ k, the first sum contributes nothing, and the second sum has its full range: on =  s=0k hs in+s-k n≥k (3.8.12) Setting n:= n+k we get on+k =  s=0k hs in+s n≥0 (3.8.13) Finally we have recovered our time domain result appearing in the box at the end of Section 1.8 in Chapter 1. 3.9 Matrix analysis of the standard polynomial multiplier of Figure 8 . Chapter 3: The Matrix Approach 20 Looking at Figure 8, one can write down the following series of equations, q'1 = h 0 i q'2 = q1 + h1 i q'3 = q2 + h2 i ... q'k-1 = qk-2 + hk-2 i (3.9.1) These equations may be com bined into a single matrix equation, q'1 0 0 0 ... 0 0 q1 h0 q'2 1 0 0 ... 0 0 q2 h1 q'3 0 1 0 ... 0 0 q3 h2 q'4 = 0 0 1 ... 0 0 q4 + i x h3 ... .................................................................... ... .. q'k-1 0 0 0 ... 0 0 qk-1 hk-2 q'k 0 0 0 ... 1 0 qk hk-1 (3.9.2) We recognize the matrix above as the same matrix C which appeared in the Figure 7 analysis. Notice that the rightmost vector used to be 1, but here it is a vector consisti ng of the first k components of the feedback polynomial coefficients. We call this vector h. As we have done many times before, we write the above as a vector difference equation and state the solution of this difference equation. We also write out a component of the vector qn: qn+1 = C qn + inh (3.9.3) qn = Cn q0 + [ i0 Cn-1 + i1 Cn-2 + .... + i n-2 C + in-1I ] h (3.9.4) [ qn ]s = qs(n) (3.9.5) The comments made about the matrix C all apply here as well, so we can rewrit e (3.9.4) as, qn = Cn q0 + [ in-k Ck-1 + i n-3 C2 + in-2 C + in-1I ] h I = C0 = Cn q0 +  j=1k in-j [Cj-1] h (3.9.6) In Figure 7, the output o n was a sum of many terms. For Figure 8, the output is the sum of only two terms, Chapter 3: The Matrix Approach 21 on = q k(n) + h k in = [ qn]k + hk in =  j=1k [ Cn ]k,j [q0]j +  j=1k  s=0k-1 in- j [Cj-1]k,s hs + hk in (3.9.7) According to (3.8.4), we have [ Cn ]k,j = k,n+j and [Cj-1]k,s = k,j+s so both j sums go away leaving on = [q0]k-n +  s=k-nk-1 hs in+s-k + hk in = (n<k) [ q k-n(0) + hk in ] + (n≥k)  s=0nk hs in+s-k (3.9.8) The left term controls the output for the first n clocks. For example, o0 = qk(0) + h ki0. o1 = qk-1(0) + h ki1. Notice that this is completely different from the output of the Figure 7 circuit. However, after n clocks have gone by, the second term takes over and we get the same results as for Figure 7, namely, e quations (3.8.12) and (3.8.13). This concludes our matrix exercises for the polynomial multiplier circuits. The obvious conclusion in either case is that nobody cares about the output of these circuits for the first k clocks. After that, the output is given by the fundamental result (3.8.13). 3.10. Proof that a Descrambler really descrambles the output of a Scrambler. The proposed serial digital standard involves the following scrambler - descrambler structure: Chapter 3: The Matrix Approach 22 Figure 3.10.1: Proposed scra mbler structure for serial digital communication . One can think of this as an operation S 1 S2 D2 D1 acting on the signal. We want to prove that a "descrambler" really descrambles the output of a scrambler. In terms of operations, this means that S D = 1, or D = S-1. The "1" means there is no change to the signal after passing through a scrambler followed by a descrambler. We will show this for an arbitrary scrambler. Then, with regard to the above picture, we will have shown that S1 S2 D2 D1 = S1 S2 S2-1 S1-1 = S 1 ( S2 S2-1 ) S1- 1 = S 1 ( 1 ) S1- 1 = S1 S1- 1 = 1 Here subscript 1 refers to the Main scrambler and descrambler, while 2 refers to the mini NRZI operations as described in Section 3.7 above. Proof in the Z Domain Back at the end of Section 1.8 in Chapter 1 we wrote down the z -domain and time -domain equations for polynomial dividers (scramblers) and mulipliers (descramblers). Here they are again: z-domain time -domain Poly Divider (s crambler) O(z) = I(z)/H(z) in =  j=0k hj on+j (3.10.1) (Figure 1 or Figure 2) Chapter 3: The Matrix Approach 23 Poly Multiplier (descrambler) zk O(z) = I(z) H(z) ok+n =  j=0k hj in+j (3.10.2) (Figure 7 or Figure 8) In the z domain, our proof is very simple and goes as follows. Let I(z) represent the source data. Let O(z) be the output of a scrambler with coefficients H(z). Then , O(z) = I(z)/H(z) Now run this O(z) as the input to a descrambler, whose output we will call O'(z): zk O'(z) = { O(z) } H(z) = { I(z)/H(z) } H(z) = I(z) This says that the output O'(z) of the descrambler replicates the input I(z) to the scrambler, apart from a time delay of k clocks. This delay is characteristic of the multiplier circuit. Recall that all these z -transform functions of z are just polynomials. Of course the ones other than H(z) can be arbitrarily long, since their corresponding sequences can be long. The above proof is correct, but somewhat unsatisfying. We would really like to see how this all works out in the time domain. Proof in the Time Domain In Section 3.3 we constructed an explicit formula for the output of a Figure 1 scrambler, using our matrix formalism. Equation (3.3.5) shows the status of the state vector q at time t = n clocks: qn = Bn q0 +  j=0n-1 in-1-j Bj 1 (3.10.3) Here q0 is the starting state vector, 1 is the unit column vector (1,0.0...) , and B is the matrix discussed in Section 3.3. According to Eq. (3.3.2), the state of r egister k -s is given by the sth component of the vector qn. Thus we can write, on = qk-s(n) = [ qn ]s = [Bn q0 ]s +  j=0n-1 in-1-j [ Bj ]s,1 (3.10.4) Notice in Figure 1 that we can take the scrambled output from any of the k flipflops, the only difference is a time delay. So we will therefore regard q k-s(n) as shown above as the output o n of our scrambler. Eq. (3.10.4) is an explicit expression for the scrambler output sequence o n in terms of the scrambler input sequence i n , and the starting state vector q0 . Chapter 3: The Matrix Approach 24 During the first k clocks of operation, we know that the descrambler clocks out whatever k garbage bits happened to be in its k registers. During this time, the first k bits of the above sequence o n move into the descrambler registers. We can use (3.10.2) above to compute the descrambler output after this time, assuming that its input is the output of the scrambler: o'k+n =  r=0k hr on+r n ≥ 0 (3.10.5) Our task is now "simply" to insert (3.10.4) with n  n+r into (3.10.5), and turn the crank. The reader is warned that things are going to get a little tricky as we proceed, but in the end, the desired result will be obtained, and some insight will be gained along the way. Doing the above insertion, we get o'k+n =  r=0k hr { [Br+n q0 ]s +  j=0n+r-1 in+r-1-j [ Bj ]s,1 } (3.10.6 ) Consider the first term above, which can be expanded as ,  r=0k hr [Br+n q0 ]s =  i=0k [q0]i {  r=0k hr [Br+n]s,i } =  i=0k [q0]i {0} = 0 (3.10.7) According to Eq. (3.5.2), the sum over r {...} completely vanishes. This may be traced back to the fact that h(B) = 0. The reason this is true is that the matrix B has the "companion" form C 1 shown in Galois Chapter 8, Section 8.5, with f i = hi. The characteristic polynomial of C 1 is then h(x), and according to Big Fact 2 of Section 8.1, it follows that h(B) = 0. This is the Cayley -Hamilton Theorem. Since the term conta ining q0 completely vanishes in (3.10.6), we conclude that the output sequence o' k+n is completely independent of the starting state vector q0 of the scrambler!! This is the kind of result that is hard to deduce from the z -domain analysis. We are now left with the following double sum: o'k+n =  r=0k hr  j=0n+r-1 in+r-1-j [ Bj ]s,1 (3.10.8) Replace the j summation variable with a new summation variable m = n+r -1-j : Chapter 3: The Matrix Approach 25 o'k+n =  r=0k hr  m=0n+r-1 im [ Br+n-m-1]s,1 (3.10.9) The motivation for this less -than -obvious replacement was to get i m. Consider now the shape of the region of the double summation in (3.10.8). Here is a picture: Figure 3.10.2: Summation domain for Eq. (3.10.9) Consider first the summation over the rectangular region A. Here, r goes 0 to k, and m goes 0 to n -2. The line m=n -1 will be considered part of the upper triangle B. We get, o'k+n (over region A) =  r=0k hr  m=0n-2 im [ Br+n-m-1]s,1 (3.10.10) Because the upper endpoint on the m summation is now independent of r, we can move the r summation to the right where it collides with the B matrix thing to give zero just as happened in (3.10.7): o'k+n (over region A) =  m=0n-2 im {  r=0k hr [ Br+n-m-1]s,1} = 0 (3.10.11 ) Now we have only to worry about the triangular region A. So, o'k+n = o' k+n (over region B) =  r=0k hr  m=n-1n-2 im [ Br+n-m-1]s,1 (3.10.12) The next step is to replace index m with j = m -n+1 which yields, Chapter 3: The Matrix Approach 26 o'k+n =  r=0k hr  j=0r ij+n-1 [ Br-j ]s,1 (3.10.13) This time we cannot move in the r summation and have it die against the matrix because r appears as the upper endpoint of the j summation. The summation domain for (3.10.13) is as follows: Figure 3.10.3: Summation domain for Eq. (3.10.13) Based on this picture, we can rewrite the double summation as follows: o'k+n =  j=0k ij+n-1 {  r=jk hr [ Br-j ]s,1 } (3.10.14 ) In Appendix 3.1 at the end of this Chapter, we prove the following extremely un -obvious fact about the quantity in brackets {..} appearing above, {  r=jk hr [ Br-j ]s,1 } = s, k-j+1 (3.10.15 ) Basically this is a property of the B matrices. Inserting (3.10.15) into (3.10.14) we get our final result: o'k+n =  j=0k ij+n-1 { s, k-j+1 } = i k+n-s (3.10.16) Recall that we took our scrambler output from register q k-s of the scrambler of Figure 1. If we now select s=k, the output comes from register q 0 exactly as shown in Figure 1. In this case, we get the result, o'k+n = in n = 0,1,2... (3.10.17) Conclusions: Chapter 3: The Matrix Approach 27 (a) Eq. (3.10.17) says that if you run a sequence i n through a scrambler, and then through the corresponding descrambler, you get out exactly what you put in, with k clock delays due to the way the multiplier starts up. During this startup phase, k garbage bits are emitted by the descrambler. (b) If you decide to take your scrambler output from an earlier register of Figure 1, then you will lose the first few bits of the input stream during the garbage clock out phase. For example, if (k -s) = 1, so we are taking data from q 1 in Figure 1, we get o' k+n = in+1, so the first non -garbage bit out of the descrambler will be i 1 and i 0 is lost. (c) Conversely, suppose there are N extra latch delays inserted into the "line" of Figure 3.10.1. The N garba ge bits held in these latches will appear right after the k garbage bits are shifted out of the descrambler latches. Then following these N extra garbage bits will come the input sequence starting with the first bit i 0, so nothing is lost. (d) In general, nobody cares whether the first few bits are lost as in (b), or whether there are a few extra startup garbage bits as in (c). The only possible concern is in the overall delay which is N -(k-s). An interesting idea is to consider taking the scrambler ou tput a few latches back from the end (ie, advanced) and attempt to cancel out any line delay N. That is, one could tune so that N - (k-s) = 0. (e) Notice that in the above proof we assumed use of the Figure 1 scrambler with its B matrices, but we made no assumption about whether Figure 7 or Figure 8 was used as the descrambler. 3.11 The Kill Sequence Problem and Strings of Zeros It has been noted that a long string of zeros emerging from the Main Scrambler shown in Figure 3.10.1 can cause a problem at the clock recovery circuit which must exist at the end of the "line". Unlike strings of 1's, strings of 0's pass right through the NRZI mini -scrambler and enter the line. Question : What type of source data can cause the main scrambler to output a long string of zeros? Answer : At any instant of time, the main scrambler contains some state vector q n. As will be shown below, for any such state vector, there is a unique corresponding "kill vector" which, if shifted into the scrambler, will bring it to the all -zero state. Subsequent zeros at the input keep the scrambler in its zero state. This leads us to the following: Fact 1 : It is possible that a k -stage scrambler will output a string of N+k zeros if a string of N zeros exists in the input stream. The probability of this happening, given the input stream of N zeros, and assuming the scrambler is in a random state, is 1/P where P = 2k - 1. That's just because P is the number of states the scambler can be in. For k=9, this probability is 1/51 1, which is is not a very small number in this context. Proof : Imagine that the input data stream has the following form: ....xxxxxxxxx1 00000000000000...00000000001xxxxxx...  Chapter 3: The Matrix Approach 28 Suppose that , at the instant in time indicated by the arrow, the scrambler happens to contain exactly the right k -bit vector a which gets "killed" by the next k bits of the input stream (underlined). Then, when the first 0 of the long string of zeros shown is at the scrambler input, the scrambler will contain k zeros. Suppose the string of zeros shown above has length N. By the time the "1" which ends the string is at the scrambler input, it will have output N zeros. But its state vector is still 0, so there are k more zeros still to come out. Thus, if N zeros are input, it is possible that N+k zeros will be output. Example 1 : Suppose in D1 video there is a sync pattern consisting of the following four 10 -bit words : 3FF, 000, 000, 000 001 Suppose this pattern is followed by a Y or a C sample, with an unknown bi t ordering. In the very worst case (probably a few bits worse than could really happen), this pattern could be in effect a 1, and we have added that above. Thus, we have a string of 39 bits (in 10 -bit video), and with a k=9 scrambler, there could be a string of 48 zeros in the scrambler output. [We address below the question of what vector is killed by the all -ones input vector.] In 8 -bit video, we would lower this estimate from 30+9+9 = 48 to 24 + 7 + 9 = 40. In 8-bit video, the normal blanking pat tern is YC = 0x1080, so the longest zero strings are 10 bits. In 10 -bit video, we presume this extends to 12 bits. Example 2 : Suppose in some video spec, one is allowed to have an entire active scanline of ancillary data that is all zeros. In the 601 world with 10 -bit video, this would represent a string of 720*20 = 14, 400. Zeros. To this we might add 30 + 9 as above, but who is counting? In HDTV we get 1920*20 = 38400 zeros. We now prove some of the claims referred to above. Fact 2 : Assume a s crambler is in some state a. Consider the k -symbol pattern that next shifts in, call this pattern i. After this pattern shifts in, the scrambler is in state b. We claim that, given any patterns a and b, there exists a unique pattern i which causes a to go to b. Corollary 2 : If pattern b is the all -zero pattern 0, there exists a unique pattern i which takes a to 0. Definition : Such a pattern is called a kill vector . Proof of Fact : Our proof makes no assumption about the nature of the symbols c arried on the lines of Figure 1. They could be in GF(2), in GF(p), or in GF(pm). To keep the proof general, we retain the minus signs on the h i coefficients. Stare at Figure 1. Assume that at t=0 pattern a is in the registers. The rightmost bit of pattern a is a0. Assume the the first incoming bit is called i 0. We select i 0 such that the resulting contents of register q k-1 will be the rightmost bit b 0 of pattern b. This is because b 0 sitting in register q k-1 will end up in register q0 after k cloc ks. Chapter 3: The Matrix Approach 29 A clock goes by and we now have some i 1 at the input. The feedback circuit is generating some feedback based on the remaining (shifted) bits of pattern a and our b 0 which is sitting in q k-1. We now select i 1 so that when combined with the feedback, it generates the second -from -the-right bit b 1 of pattern b. We keep going in this fashion, and each bit is in turn fully determined. Here are some equations: i0 - h0 a0 - h1 a1 - ... h k-1ak-1 = b0 solve for i 0 i1 - h0 a1 - h1 a2 - ... h k-2 ak-1 - hk-1 b0 = b1 solve for i 1 i2 - h0 a2 - h1 a3 - ... hk-2 b0 - hk-1 b1 = b2 solve for i 2 etc. We can group all these equations into a matrix solution for the {i n } as follows: i0 a0 a1 a2 a3 .. ak-3 ak-2 ak-1 -h0 b0 i1 a1 a2 a3 a4 .. ak-2 ak-1 b0 -h1 b1 i2 a2 a3 a4 a5 .. ak-1 b0 b1 -h2 b2 i3 = a3 a4 a5 a6 .. b0 b1 b2 -h3 + b3 i4 a4 a5 a6 a7 .. b1 b2 b3 -h4 b4 .. .. .. .. .. .. .. .. .. .. .. ik-2 ak-2 ak-1 b0 b1 .. bk-5 bk-4 bk-3 -hk-2 bk-2 ik-1 ak-1 b0 b1 b2 .. bk-4 bk-3 bk-2 -hk-1 bk-1 Notice that all elements on any / diagonal are the same. We can write this in vector form as: i = -X(a,b) h + b where X is the matrix shown, and we note that it is a function of vectors a and b. Thus, we have explicitly constructed the input vector i which converts state a into state b. If we are looking for a kill vector, we set b = 0, so all elements in X below the diagonal vanish, as does the add -on column vector on the right. Since we have an explicit answer for i, it must be unique, given a and b. Example : For k=9, X is a 9x9 matrix, and for h(x) = 1 + x4 + x9 we have h 0 = h4 = 1, all other h i in the vector h vanish. In this case, each equation has only three terms. Here they are: i0 = a0 + a4 + b0 i5 = a5 + b0 + b5 i1 = a1 + a5 + b1 i6 = a6 + b1 + b6 i2 = a2 + a6 + b2 i7 = a7 + b2 + b7 i3 = a3 + a7 + b3 i8 = a8 + b3 + b8 i4 = a4 + a8 + b4 This is the general result for going from a to b. To find the kill vector , set bi = 0 to get: Chapter 3: The Matrix Approach 30 i0 = a0 + a4 i5 = a5 i1 = a1 + a5 i6 = a6 i2 = a2 + a6 i7 = a7 i3 = a3 + a7 i8 = a8 i4 = a4 + a8 Question : In the above example k = 9, what vector a is killed by an incoming vector consisting of all ones? Answer : Reverse solve the last set of equations above. We quickly get that a 8 = a7 = a6 = a5 = 1. Then from the earlier equations we get a 4 = a3 = a2 = a1 = 0. Finally, the first equation then says a 0 = 1. The answer to the question is therefore: { a8, a7, a5. a4, a3, a2. a1, a0 } = { 1,1,1,1,0,0,0,0,1} = 0x1E1 Discussion of the zeros problem. In general, for each video standard, one must find the spec, and study the longest possible string of zeros that is allowed. Officially illegal values do sometimes occur, and there are all kinds of EAV, SAV codes and ancillary data and various indices to worry about, plus embedded sound. The general principle applies: "If it can happen, it will happen. " If the clock recovery circuit drops out of lock during a lo ng string of zeros, there will be some period of time determined by the PLL system during which data will be lost. If the lock -up time is very short, perhaps only a few bits at the end of an anomolous scan line will be lost, but this sounds unhealthy. It seems that a long time constant would be better than a short one, so you could live through an anomolous event without losing lock. A time constant that is long compared to a scanline but short compared to a field time would be good. In this case, one could survive an anomolous scanline. The following fact does not really belong here, but is was omitted from earlier work. Fact 3 : If a k -stage scrambler has an even number of feedback taps, then if the input stream is set to all 1's, the scrambler behaves exactly as if the input stream were all 0's and there were an inverter on the final output. Thus, a primitive polynomial scrambler with all 1's for input will cycle through an inverted characteristic sequence of the usual length P = 2k - 1. The only pattern that does not appear at the output is then the pattern consisting of k ones. All characteristic sequence theorems quoted earlier then need to be adjusted to account to the effective inversion. Proof : The input feed of all ones at the input XOR gate can be thought of as an inverter at the input of the first flip flop and an input stream of zeros. We can then mentally move this inverter to the right in Figure 1 one step at a time. At the output of a flip flop, the inverter "forks" into a p air of inverters, one moves to the next flipflop, and one moves up the feedback path. The lower inverter eventually ends up on the output signal. If there are an even number of feedback paths, then the feedback forked inverters all cancel out. Each such inverter can be regarded as adding a 1, and if you add a 1 an even number of times, it is like doing nothing. Chapter 3: The Matrix Approach 31 Some final notes: (1) Long strings of zeros might have some bad effect on a dynamic equalizer. (2) For each extra bit that is added to a sc rambler, the probability of an anomolous event is cut in half. Inside a custom chip, having 9 registers or having 19 in a scrambler does not make much difference, but the 19 bit scrambler has the "zeros problem" reduced by a factor of 2-10 = 10-3. (3) There is no data propagation problem to speak of with the descrambler. If a data loss occurs, the descrambler will "resynchronize" in k clock periods. In other words, if any garbage bits get into the descrambler, they do not have any long term affect. Chapter 3: The Matrix Approach 32 Appendix 3.1: Proof of Eq. (3.10.15) First, we state what we want to prove is true: {  r=jk hr [ Br-j ]s,1 } = s, k-j+1 (A.1) The matrix B which goes with the Figure 1 circuit is shown in Eq. (3.3.2). We can write its elements as, Bij = = i, j+1 + i,1 hk-j (A.2) We are always working in the GF(2) binary world where - = +. Also, since we are assuming the h(x) is order k, we must have h k = 1. We will prove (A.1) by induction. (a) To start, we show that (A.1 ) is true for j = k. In this case, the LHS of (A.1) has one term and (A.1) says, hk Is,1 = s, 1 But this is trivially true since h k= 1 and I = identity matrix = B0. So, we are off and running. (b) Now we show that if (A.1) is true for some j, then it is also true for j -1 . Start with (A.1), and apply the operation  s=0k [ B ] n,s to both sides. On the LHS of (A.1), this new B matrix glues onto the Br-j matrix already present to give Br-(j-1). On the RHS the delta picks out the value s = k-j+1 for the second index of B, so we get: {  r=jk hr [ Br-(j-1) ]n,1 } = B n,k-j+1 = n, k-(j-1) +1 + n,1 hj-1 (A.3) where we have used (A.2) to write out the B matrix element. Now, if the sum on the LHS of (A.3) had a term for r = j -1, here is what that term would be: hj-1 [ B0]n,1 = hj-1n,1 But this is the second term on the right of (A.3). So (A.3) now becomes, {  r=j-1k hr [ Br-(j-1) ]n,1 } = n, k-(j-1) +1 (A.4) Chapter 3: The Matrix Approach 33 If we now set n=s, (A.4) is th e same as (A.1) with j replaced by j -1. We have therefore shown that (A.1) implies (A.4), which completes the second part of our induction proof. Q.E.D.