 all zero, such that (5.146) then the polynomial P(z) has qM - 1 roots and degree at most qM - 2, - a contradiction. The linear span L of a sequence (i.e., the degree of its characteristic poly- nomial) is related to the sequence's powers-of-a representation in the fol- lowing result. THEOREM 5.9. Let {bn} be a sequence over GF(q), and let a be a primitive element of GF(qM). Let {bn} be represented as (5.147) for all n, where A is the set of indices of non-zero coefficients in the expan- sion. Then the linear span L of {bn} is equal to the number of terms in the representation (5.147), i.e., L=A. = (5.148) Proof. Since bn is in GF(q) and all elements of that field have multiplica- tive order dividing q - 1, it follows that bn bq (5.149) for all n, by Theorem 5A.7.1 of Appendix 5A. Since the representation (5.147) is unique, it must be identical to (5.149). Therefore, (5.150) This implies that A can be decomposed into cyclotomic cosets (see Appendix 5A.8), the terms of (5.147) with indices in the same coset summing to a trace function. Let A' be composed of the coset leaders (single representative elements) of the cyclotomic cosets present in the decomposition of A. Then (5.160) Note that the trace function for the 8-th term is calculated from the small- est field GF(qd(8)) containing Q s down to GF(q). In the form (5.160), {bn} can be viewed as the sum of A' sequences, each over GF(q). Furthermore, the number of terms d(8) of (5.147) which are combined to produce the sequence {Tr(asa8n)} is identical to the degree of the minimum polynomial Tr(an+3) Tr(an+2, Tr(an+1) Tr(an ) Tr(an+5, Tr ((an+4) Figure 5.10(a). The LFSR with NLFFL used in Example 5.10. Arithmetic/logic operations are GF(2)/EXCLUSIVE OR and Pseudonoise Generators ma(z), , which by Theorem 5.6 is the characteristic polynomial of that sequence. Therefore, the characteristic polynomial Q(z) of {bn} is given by Q(2)=IIma(z), (5.161) and has degree L given by (5.162) Thus, the linear span of a sequence can be evaluated simply by counting terms in its pow