able that the characteristic polynomial of Q(z) of {bn} is Q(z) = md(z)m.a(z) (5.213) This can be verified directly as specifying the recursion satisfied by the out- put sequence. The k-tuple statistics of the output sequence in this example are shown in Table 5.14. As indicated by this data, the k-tuple statistics of a GMW Non-Linear Feed-Forward Logic Table 5.13 Time coefficients c(k,3) of the sequence [Tr64(a")]. Time Coefficients base-2 base-10 110000 100010 010100 000110 sequence are not uniformly distributed for all k less than the number of memory elements used, as they are for m-sequences by Property R-2 (5.61). A uniform distribution on k-tuple occurrences is achieved in GMW sequences for a restricted range of k, as stated in the following theorem. THEOREM 5.14. Let {bn} be the GMW sequence defined by (5.200). Then the number Na of positions within one period of {bn} at which the k-tuple A1a2 ak occurs, is given by 1sks M a # 0, (5.214) for a = 0, 1sksM Proof. The intermediate field sequence Tr2(a") is an m-sequence with linear span MIJ, and thence k-tuples a' a'k from this sequence occur N'a' times in one period according to the count specified in (5.61): (5.215) Since r is relatively prime to 2 - 1, the r-th power mapping of the inter- mediate field onto itself is one-to-one, and the above count N'a also applies to the sequence {[Tr2"(a")]"}. Table 5.14 K-tuple statistics for the GMW sequence of length 63. (k-tuple: Occurrences per period) (0:31), (1:32) (00:15), (01:16), (10:16), (11:16) (000:6), (100:9), (010:9), (001:9) (110:7), (101:7), (011:7), (111:9) (0000:4), (1000:2), (0100:5), (0010:5) (0001:2), (1100:4), (0110:1), (0011:4) (1001:7), (1010:4), (0101:4), (1110:6) (0111:6), (1011:3), (1101:3), (1111:3) Pseudonoise Generators Let Aa be the set of k-tuples a' over GF(2) which map into a under the trace mapping a==Tr2(a) for i = 1,...,k. (5.216) Note that the all-zeros k-tuple maps into itself. Then the number of occur- rences of a in one period of {bn} is given by (5.217) Since the number of elem