Linear complexity

This subsection summarizes selected results about the linear complexity of sequences. All sequences are assumed to be binary sequences. Notation: s denotes an infinite sequence whose terms are s0, si, s2, • • •; sn denotes a finite sequence of length n whose terms are so, si, • • • , sn_i (see Definition 5.24).

• 6.16 Definition An LFSR is said to generate a sequence s if there is some initial state for which the output sequence of the LFSR is s. Similarly, an LFSR is said to generate a finite sequence sn if there is some initial state for which the output sequence of the LFSR has s" as its first n terms.
• 6.17 Definition The linear complexity' of an infinite binary sequence s, denoted L(s), is defined as follows:
• (i) if s is the zero sequence s = 0.0. (),..., then L(s) = 0;
• (ii) if no LFSR generates s, then L(s) = oc;
• (iii) otherwise, L(s) is the length of the shortest LFSR that generates s.
• 6.18 Definition The linear complexity of a finite binary sequence sn, denoted L(sn), is the length of the shortest LFSR that generates a sequence having sn as its first n terms.

Facts 6.19 - 6.22 summarize some basic results about linear complexity.

• 6.19 Fact (properties of linear complexity>) Let s and t be binary sequences.
• (i) For any n > 1, the linear complexity of the subsequence sn satisfies 0 < L(sn) < n.
• (ii) L(sn) = 0 if and only if sn is the zero sequence of length n.
• (iii) L(sn) = n if and only if sn = 0,0,0,... ,0,1.
• (iv) If s is periodic with period N, then L(s) < N.
• (v) L(s®t) < L(s) + L(t), where s®t denotes the bitwise XOR of s and t.
• 6.20 Fact If the polynomial C(D) e Z2[Z>] is irreducible over Z2 and has degree L, then each of the 2L -1 non-zero initial states of the non-singular LFSR (L, C(D)) produces an output sequence with linear complexity L.
• 6.21 Fact (expectation and variance of the linear complexity> of a random sequence) Let sn be chosen uniformly at random from the set of all binary sequences of length n, and let L(sn) be the linear complexity of sn. Let B(n) denote the parity function: B(n) = 0 if /г is even; B(n) = 1 if n is odd.
• (i) The expected linear complexity of sn is

Hence, for moderately large n, E(L(sn)) se ^ + | if n is even, and E(L(sn)) ss ^ + yg if n is odd.

(ii) The variance of the linear complexity of sn is Var(L(.s'!)) =

Hence, Var(L(sn)) w || for moderately large n.

6.22 Fact (expectation of the linear complexity’ of a random periodic sequence) Let .s" be chosen uniformly at random from the set of all binary sequences of length n, where n = 2* for some fixed t > 1, and let s be the /(-periodic infinite sequence obtained by repeating the sequence sn. Then the expected linear complexity of s is E(L(sn)) = n - 1 + 2~n.

The linear complexity profile of a binary sequence is introduced next.

6.23 Definition Let s = s0, si, • • • be a binary sequence, and let L/v denote the linear complexity of the subsequence sN = sq, si, ... , sn-i, N > 0. The sequence Li. L2.... is called the linear complexity’profile of s. Similarly, if sn = so, si,... , s„-i is a finite binary sequence, the sequence L, L2, • ■ • • L„ is called the linear complexity’profile ofsn.

The linear complexity profile of a sequence can be computed using the Berlekamp- Massey algorithm (Algorithm 6.30); see also Note 6.31. The following properties of the linear complexity profile can be deduced from Fact 6.29.

• 6.24 Fact (properties of linear complexity’profiIe)Let Li, L-2, ■■ ■ be the Unear complexity profile of a sequence s = so, si,____
• (i) If j > i, then Lj > Li.
• (u) L.v-. i > Ljv is possible only if L.v < N/2.
• (hi) If L.v+i > Ln, then L_n+i + Ln = N + 1.

The linear complexity profile of a sequence s can be graphed by plotting the points (N. Ln), N > 1, in the N x L plane and joining successive points by a horizontal line followed by a vertical line, if necessary (see Figure 6.6). Fact 6.24 can then be interpreted as saying that the graph of a linear complexity profile is non-decreasing. Moreover, a (vertical) jump in the graph can only occur from below the line L = N/2: if a jump occurs, then it is symmetric about this line. Fact 6.25 shows that the expected linear complexity of a random sequence should closely follow the line L = N/2.

6.25 Fact (expected linear complexity’ profile of a random sequence) Let s = so, si,. • • be a random sequence, and let L_- be the linear complexity of the subsequence sN = s0,si,, sn-i for each N > 1. For any fixed index N > 1, the expected smallest j for which L± +j > Z/дг is 2 if L.v < Nj2, or 2 + 2L± - N if L/v > N/2. Moreover, the expected increase in lmear complexity is 2 if > N/2, or N - 2L.v + 2 if L/v < N/2.

6.26 Example (linear complexity’profile) Consider the 20-periodic sequence s with cycle

The linear complexity profile of s is 1,1,1,3,3,3,3,5,5,5,6,6,6,8,8,8,9,9,10,10,11, 11,11.11,14,14,14,14,15,15,15,17,17,17,18,18,19,19,19,19,.... Figure6.6shows the graph of the linear complexity profile of s.

Figure 6.6: Linear complexity profile of the 20 -periodic sequence of Example 6.26.

As is the case with all statistical tests for randomness (cf. §5.4), the condition that a sequence s have a linear complexity profile that closely resembles that of a random sequence is necessary but not sufficient for s to be considered random. This point is illustrated in the following example.

6.27 Example (limitations of the linear complexity profile) The linear complexity profile of the sequence s defined as

follows the hue L = N/2 as closely as possible. That is, L(sN) = [(A’ + 1)/2J for all N > 1. However, the sequence s is clearly non-random. □