f degree 5, and, furthermore, a portion of the sequence contains 1011101100011 (5.41) where the sequence index is increasing from left to right. Applying (5.6) sep- arately to overlapping blocks of six consecutive symbols from the sequence gives the following set of equations: 0=a1ta2a3+a5 1 =a2a3a4 1=a + a3 + a4 + a5 (5.42) 0 = a1 + a2 + a4 + a5 + a5. In constructing these L (in this case five) linearly independent equations, we used L + 1 specified sequence elements for the first equation plus one additional (previously unused) element for each additional equation. Hence, knowledge of 2L bits from the given sequence was used in the construction of (5.42). In the special case where the element field is GF(2) as it is here, the fact that the degree of the recursion is L and aL is non-zero implies that aL must be 1, the only non-zero field element. Therefore, only L - 1 equa- tions are needed in the GF(2) case, in this example the first four in (5.42), which can be rewritten as (5.43) 1 = a1 + c Memory-Efficient Linear Generators Since addition in GF(2) is modulo 2, adding the first three equations directly gives a3 = 0, and adding the last three gives a4 = 0. Substitution of these val- ues gives a2 = 1 and a1 = 0, and, hence, the resulting linear recursion is (5.44) When K symbols from the sequence are known but the linear span L is not, one can always guess L and follow the above procedure. If the guess is less than the true linear span, additional data will not be consistent with the deduced (incorrectly) linear generator. On the other hand, if the guess is greater than the true linear span, then multiple solutions will appear in the above procedure, all leading to correct, but usually non-minimal, generators of the complete sequence. Lacking knowledge of L, a more organized approach uses techniques for constructing rational approximations to the sequence's formal power series B(z), when only the first K terms are known. These techniques, suggested by Massey for use in the Berlekamp-Massey decoding algorithm [7