elation n = 1,2,... (5.116) Pseudonoise Generators where q1 is a coefficient of Q(z) (see (5.20)). Hence, carefully checking ini- tial conditions, (5.117) whence (z) = (z + 91)R (z) - - r0 (5.118) By iterating this computation and substituting (5.115), it can be shown that the formal power series representation for the sequence generated by the k-th memory cell is k=2,3,...,L. (5.119) where L is the number of memory elements (the degree of Q(z)) and also the linear span of {bn}. Since P(z) and Q(z) contain no common factors, the following result is now evident. THEOREM 5.5. Let Q(z) be the characteristic polynomial for the output of a Galois-configured LFSR. Then (with indexing as shown in Figure 5.6) the sequence generated in the k-th memory element, k > 1, has characteristic polynomial given by Q(z) gcd (Q(z), -19izk-1-i). COROLLARY 5.1. Let the minimum polynomial ma(z) over GF(q) be the characteristic polynomial of the output sequence from a Galois-configured LFSR. Then all memory cells in the register produce sequences having char- acteristic polynomial ma(z) and possess identical periods equal to the expo- nent of a. Proof. Since ma(z) is irreducible, all cells have the same characteristic poly- nomial by Theorem 5.5, and all possess identical periods by Theorem 5.1. Example 5.7. As an aside to illustrate what can happen when Q(z) is com- posite, consider a Galois LFSR with output sequence possessing the fol- lowing characteristic polynomial over GF(2). Q(z) 28z7z64 (5.120) Since both (z3 + z + 1) and (z2 + z + 1) are primitive with periods 7 and 3, respectively, Theorem 5.2 indicates that the period of the output sequence for a properly initialized register should be 2 x 3 x 7, i.e., 42. Theorem 5.5 predicts that the characteristic polynomial for the sequences of memory cells 3 and 4 is (z3 + 1)2, while that for the sequence of cell 5 is (z3 + Z + 1) )(z2 + z z 1). Hence, cells 3 and 4 will generate period 14 sequences (see Theorem 5.2), while cell 5 will produce a period 21 sequence. The register Galois Fi