(n-1) - LL - : L L 2 (5.36a) B=00...01. (5.36b) The A matrices in (5.33) and (5.36a), which are transposes of each other, are referred to as companion matrices of the monic characteristic polynomial Q(z), where (5.37) Other linear sequential circuits, which generate the same output sequence {bn}, can be constructed from transformations of the state space. Let T be a nonsingular matrix over the sequence element field F and define a new state vector S'n, 'n=Tsn. (5.38) Then the linear sequential circuit of the new state sequence {s'}} has a state equation governed by the transition matrix A' = TAT-1, (5.39) and an output equation (5.40) There is no significant difference between these generators when the out- put sequence is a linear function of the state sequence, as shown in (5.30), and (5.31). Certainly, the memory requirements are identical in each case, although some realizations may use fewer adders than others [50]. On the Pseudonoise Generators other hand, when the output bn is a non-linear function of the circuit state Sn, i.e., non-linear feedforward logic is employed, then attempts to deduce the structure of the generator from a short segment from the output sequence may be compliced by the insertion of T. 5.2.5 Determination of Linear Recursions from Sequence Segments When given a segment b1, b2, bk, of K symbols from a sequence {bn}, is impossible to determine with absolute certainty the remainder of the sequence. However, if one proceeds on the assumption that K is at least twice the linear span of the sequence, and if that assumption is in fact correct, then a linear generator of the complete sequence can be determined. For the moment, consider the possibility of knowing the linear span L of the sequence a priori, in addition to 2L consecutive sequence elements. In this case, the fact that (5.6) also is linear in the L unknown coefficients ai, i = 1, , L, can be used to determine the recursion. Example 5.5. Suppose that a binary sequence of elements from GF(2) is known to satisfy a linear recursion o