and w2 are identical, (5.250) reduces to [A,(y)](1 (5.253) weGF(2e) by (5.125). Since Tr(y+1) is zero for 2L-e values of y by trace property [A,(y)] = 2L+e for 2L-e values of y. (5.254) When Tr2(y+1) is non-zero, the outer trace in (5.253) is zero and one equally as often as W scans through GF(2) and, therefore, (5.255) Lemma 5.2 provides the mathematical background for computing the peri- odic cross-correlation between an m-sequence and its r-th decimation, when r is of the form 2k + 1. The application of this result to the cross-correlation of m-sequences requires the following lemma to determine when the r-th decimation of an m-sequence is itself an m-sequence. LEMMA 5.3. For all integers m and n, gcd(2m-1,2n-1) 28d(m,)-1 = - (5.256) gcd(2m + 1, 2nd 1) = 1 n/gcd(m, n) is odd. (5.257) Proof. By Euclidean division, m = an + r, Osr< n, (5.258) and, using binary representations of 2m - 1 and 2n - 1 as m- and n-tuples Pseudonoise Generators of ones, Euclidean division of 2m - 1 by 2n - 1 gives (2m 1) = b(2n - 1) + (2' - 1), 0 2 2 - 1 < 2n - 1, (5.259) for some integer b. Hence, there is a correspondence between terms in Euclid's algorithm (see Appendix 5A.2) for determining gcd(m,n) and that for finding gcd(2m - 1,2n-1), which easily yields a proof of (5.256). A proof of (5.257) begins by applying (5.256) to give - - = - (5.260) and noting that (5.261) since these numbers differ by two and are odd. Therefore, gcd(2" + 1,2" - 1) - = 1 gcd(2m,n) / n/gcd(m,n)is odd. (5.262) When the decimation coefficient r is relatively prime to 2L - 1, Theorem 5.8 indicates that the resulting decimation of an m-sequence is also an m- sequence. Placing Lemma 5.2 in correlation terms and restricting the deci- mation by r to produce an m-sequence, gives the following theorem. THEOREM 5.17. Let {an} be a roots-of-unity m-sequence with period 2L - 1, and let Paa(T) be the periodic cross-correlation of {an} with {an}, its deci- mation by r. Let r and e be defined by (5.248), with L/gcd(k, L) odd. Then or2L-2-e-1values of - T, 2(L+e)/2 for