 and n, (5.7) where N is the period of the sequence. For the case m = 1 in (5.7) the Fibonacci-configured LFSR is the cyclic register of Figure 5.1 (b). This obvi- ous recursion often is not the minimum-degree recursion satisfied by the sequence. bn+M-2 Dn+M-1 -OM-1 form. 5.5. An Figure Linear Recursions Table 5.4 Coefficients of linear recursions (5.6) of degree less than 7, satisfied by the period-7 sequence of Example 5.3. 00111 10001 010011 000101 111111 101001 Example 5.3. The binary sequence of period 7, beginning with 0010111, satisfies several recursions of degree less than 7 over GF(2) (see Table 5.4). The minimum number L of memory elements required to build a Fibonacci generator for {bn} is the degree of the minimum-degree recursion which generates {bn}. This key number L is called the linear span of the sequence {bn}, and is often used as an abstract measure of complexity of the sequence structure. In Example 5.3, the linear span L of the period-7 sequence is 3. 5.2.2 Formal Power Series and Characteristic Polynomials The linear span and corresponding linear recursion for a given periodic sequence can be found theoretically by formal power series manipulations. Let B(z) denote the formal power series having sequence elements as coef- ficients, i.e., (5.8) The connection between B(z) and a linear recursion (5.6) satisfied by {bn} can be established in the following manner. Define ao = 1, (5.9) multiply (5.6) by z-n, sum over n, and manipulate to arrive at = A(z)B(z) - D(z), (5.10) and, hence, (5.11) Pseudonoise Generators where (5.12) (5.13a) dn==apn-in n = 1,2,...,M. (5.13b) Thus, the formal power series of every sequence which satisfies a linear recursion can be written as the ratio of two polynomials in Z. (no negative powers of Z are contained in either A(z) or D(z)). The denominator poly- nomial's coefficients are the weights used in the linear recursion, and the numberator polynomial's coefficients are related to the initial elements b1, b2,..., , bm, by the M independent equations (5.13b). The f