ollowing technique can be used to find the linear span and corre- sponding linear recursion for a sequence {bn}, beginning with knowledge of b1,b2,... , bn, and the fact that N is the sequence period. By substituting the periodic sequence structure into (5.8), B(z) is identified as a ratio of polynomials. (5.14) The recursion and initial conditions identified with the denominator and numerator polynomials of (5.14) correspond to the cyclic generator struc- ture of Figure 5.1(b). Cancellation of common factors in the numerator and denominator polynomials in (5.14) will yield lower-degree recursions and, hence, mechanizations with lower memory requirements. Carrying this idea to its logical conclusions, Euclid's algorithm (see Appendix 5A, sections 5A.2 and 5A.3) can be applied to determine the greatest common divisor G(z), (5.15) of the numerator and denominator polynomials in (5.14). After cancellation of this common factor of highest possible degree, B(z) is of the form Linear Recursions (5.16) where gcd(P(z),Q(z)) = = 1. (5.17) It can be assumed without loss of generality that multiplicative constants have been transferred to the numerator in (5.16), SO that the denominator polynomial Q(z) is monic, i.e., the coefficient of the highest power of Z in Q(z) is unity. Clearly, there is no rational representation of B(z) with a denominator polynomial of lesser degree, and, hence, the linear span L of {bn} is given by L = degQ(z), (5.18) and {bn} satisfies the linear recursion (5.19) where qi is the i-th coefficient of Q(z), i.e., (5.20) The monic denominator polynomial Q(z) in (5.16) achieving this linear span is called the characteristic polynomial of the sequence {bn}, and the corre- sponding numerator polynomial P(z) is called the initial condition polyno- mial of {bn}. The following theorem is based on the above derivation. THEOREM 5.1. Let {bn} be a sequence possession characteristic polynomial Q(z). Then the period N of {bn} is the smallest integer N such that Q(z) divides zN - 1. Clearly then, sequences posse