ssing the same characteristic polynomial have the same period. 5.2.3 Galois Generators One consequence of the above development is that the sequence {bn} can be generated alternatively by a logic circuit that performs the division of P(z) by Q(z). The first step in this formal long division is shown below: p1Z-1 + . . . + -11 Pseudonoise Generators Note that the above formal computation is valid, even if P1 = 0. The first cycle (shown above) in this never-ending long-division process produces a remain- der polynomial via the equation P(z) - = (5.21) with the quotient coefficient P1 being the first bit b1 of the formal power series B(z). Each succeeding cycle in the long-division process divides the previous cycle's remainder by Q(z) to produce a quotient corresponding to the next element in {bn}, and a new remainder. Specifically, let the n-th for- mal power series remainder in the division process be represented by (5.22) The long division process imposes the following recursion on these remain- ders: R1()]-11() = (5.23) In summary, the remainder polynomial (no negative powers of z) recursion n = 1,2,..., (5.24) initialized by (5.25) produces the desired output sequence through the series of quotient coef- ficients bn1n1,,.. (5.26) The division of P(z) by Q(z) is embodied in the device, shown in Figure 5.6, which mechanizes the remainder recursion (5.22). This LFSR form is called the Galois configuration because it is related to Galois field multi- plication (more on this in Section 5.5). Example 5.4. A binary sequence of period N = 30 begins with the following thirty bits, indexed from the left: 000001100010010111110011101101 The formal power series representation (5.7) for this sequence begins B(z)671461 (5.27) and reduces by (5.14)-(5.17) to (5.28) The Galois and Fibonacci generators for the above sequence are shown in Figure 5.7. 'L-1 (n) (2(N) Figure 5.6. A minimum-memory LFSR in the Galois configuration for generation {bn}. Pseudonoise Generators 12(n) (a) Galois configuration (b) Fibonacci configuration F