# 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 *s _{0},* si, s

_{2}, • • •; s

^{n}denotes a finite sequence of length

*n*whose terms are so, si, • • • , s

_{n}_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*s*if there is some initial state for which the output sequence of the LFSR has s" as its first^{n}*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.*

- (i) if
- 6.18 Definition The
*linear complexity*of a finite binary sequence*s*denoted^{n},*L(s*is the length of the shortest LFSR that generates a sequence having^{n}),*s*as its first^{n}*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*s*satisfies 0 <^{n}*L(s*^{n}) < n. - (ii)
*L(s*= 0 if and only if^{n})*s*is the zero sequence of length^{n}*n.* - (iii)
*L(s*if and only if^{n}) = n*s*= 0,0,0,... ,0,1.^{n} - (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 Z_{2}[Z>] is irreducible over Z_{2}and has degree L, then each of the*2*non-zero initial states of the non-singular LFSR^{L}-1*(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*s*be chosen uniformly at random from the set of all binary sequences of length^{n}*n,*and let*L(s*be the linear complexity of^{n})*s*Let^{n}.*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
*s*is^{n}

Hence, for moderately large *n, E(L(s ^{n}))* se ^ + | if

*n*is even, and

*E(L(s*ss

^{n}))*^ +*yg if

*n*is odd.

(ii) The variance of the linear complexity of *s ^{n}* is Var(L(.s'

^{!})) =

Hence, Var*(L(s ^{n}))* 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 *s ^{n}.* Then the expected linear complexity of s is

*E(L(s*- 1 +

^{n})) = n*2~*

^{n}.The linear complexity profile of a binary sequence is introduced next.

6.23 Definition Let *s* = s_{0}, si, • • • be a binary sequence, and let L/v denote the linear complexity of the subsequence *s ^{N} *= sq, si, ... , sn-i,

*N*> 0. The sequence

*L*

*i.*L

_{2}.... is called the

*linear complexity’profile of s.*Similarly, if

*s*, s„-i is a finite binary sequence, the sequence

^{n}= so, si,...*L*, L

_{2}, • ■ • • L„ is called the

*linear complexity’profile ofs*

^{n}.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 *s ^{N} = s_{0},si,, *sn-i for each

*N >*1. For any fixed index

*N >*1, the expected smallest

*j*for which

*L*> Z/дг is 2 if L.v <

_{±}_{+}j*Nj*2, or 2 + 2

*L*if L/v >

_{±}- N*N/2.*Moreover, the expected increase in lmear complexity is 2 if

*> N/2,*or

*N - 2*L.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(s ^{N}) =* [(A’ + 1)/2J for all

*N*> 1. However, the sequence s is clearly non-random. □