Characterization of the Third Descent Points for the k-error Linear Complexity of \(2^n\)-periodic Binary Sequences

The linear complexity of a sequence s, denoted as L(s), is defined as the length of the shortest linear feedback shift register (LFSR) that can generate s. As a measure on the linear complexity stability of sequences, the weight complexity and sphere complexity were defined in the monograph by Ding, Xiao and Shan in 1991 [1]. Similarly, Stamp and Martin [7] introduced the k-error linear complexity, which is in essence the same as the sphere complexity. Specifically, suppose that s is a sequence with period N. For any \(k(0\le k\le N)\), the k-error linear complexity of s, denoted as \(L_k(s)\), is defined as the smallest linear complexity that can be obtained when any k or fewer elements of the sequence are changed within one period.

The CELCS (critical error linear complexity spectrum) is first studied by Etzion et al. [2]. The CELCS of a sequence s consists of the ordered set of points \((k,L_k(s))\) satisfying \(L_k(s)> L_{k'}(s)\), for \(k'>k\). In fact, they are the points where a decrease occurs for the k-error linear complexity, and thus are called critical points in [2], hence are called descent points here. In previous research, investigators mainly focus on the first descent points of the k-error linear complexity. There are some results on the second descent points [2, 11].

In another research direction, Rueppel [6] derived the number of \(2^n\)-periodic binary sequences with given linear complexity \(L, 0\le L \le 2^n\). For \(k=1,2\), Meidl [5] characterized the complete counting functions on the k-error linear complexity of \(2^n\)-periodic binary sequences with linear complexity \(2^n\). For \(k=2,3\), Zhu and Qi [12] further gave the complete counting functions on the k-error linear complexity of \(2^n\)-periodic binary sequences with linear complexity \(2^n-1\). The distribution of 1-error linear complexity of binary sequences with arbitrary prime period was studied by Tan et al. [8]. By using algebraic and combinatorial methods, Fu et al. [4] characterized the \(2^n\)-periodic binary sequences with the 1-error linear complexity and derived the counting function completely for the 1-error linear complexity of \(2^n\)-periodic binary sequences. The complete counting functions for the number of \(2^n\)-periodic binary sequences with the 3-error linear complexity are characterized recently in [9].

In this paper, we present a structural approach for determining CELCS for \(2^n\)-periodic binary sequences based on the idea reported in [9]. Accordingly, the third descent point (critical point) distribution of the k-error linear complexity for \(2^n\)-periodic binary sequences is characterized. As a consequence, we obtain the complete counting functions on the 5-error linear complexity when it is the third descent point of the k-error linear complexity for \(2^n\)-periodic binary sequences. We expect that with the structural approach proposed here, one can further characterize other third and fourth descent points of the k-error linear complexity for \(2^n\)-periodic binary sequences.

In [9], all \(2^n\)-periodic binary sequences with the prescribed 3-error linear complexity are investigated. In contrast, in [11] we only investigated the \(2^n\)-periodic binary sequence with the given 1 and 3-error linear complexity as the first and the second descent points separately. Further in this paper, we will investigate the \(2^n\)-periodic binary sequence with the given 1, 3 and 5-error linear complexity as the first, the second and the third descent points, respectively. In fact, we intend to characterize the \(2^n\)-periodic binary sequence via CELCS and the obtained result here is more accurate.

The rest of this paper is organized as follows. In Sect. 2, we first give an outline about our main approach for determining CELCS for \(2^n\)-periodic binary sequences. Also some preliminary results are presented. In Sect. 3, the third descent point (critical point) distribution of the 5-error linear complexity for \(2^n\)-periodic binary sequences is characterized and also the complete counting functions on the 5-error linear complexity as the third descent point is presented. Concluding remarks are given in Sect. 4.

In this section we first give some preliminary results which will be used in the sequel. At the same time an outline about the proposed structural approach is presented for determining CELCS for the k-error linear complexity distribution of \(2^n\)-periodic binary sequences.

Let \(x=(x_1,x_2,\cdots ,x_n)\) and \(y=(y_1,y_2,\cdots ,y_n)\) be vectors over GF(q). Then define \(x+y=(x_1+y_1,x_2+y_2,\cdots ,x_n+y_n)\). When \(n=2m\), we define \(Left(x)=(x_1,x_2,\cdots ,x_m)\) and \(Right(x)=(x_{m+1},x_{m+2},\cdots ,x_{2m})\).

The Hamming weight of an N-periodic sequence s is defined as the number of nonzero elements per period of s, denoted by \(W_H(s)\). Let \(s^N\) be one period of s. If \(N=2^n\), \(s^N\) is also denoted as \(s^{(n)}\). The distance of two elements is defined as the difference of their indexes. Specifically, for an N-periodic sequence \(s=\{s_0, s_1, s_2, s_3, \cdots , \}\), the distance of \(s_i,s_j\) is \(j-i\), where \(0\le i\le j\le N\).

The linear complexity of a \(2^n\)-periodic binary sequence s can be recursively computed by the Games-Chan algorithm [3] as follows.

The following two lemmas are well known results on \(2^n\)-periodic binary sequences. Please refer to [5, 9, 12] for details.

Lemma 2.1

Suppose that s is a binary sequence with period \(N=2^n\). Then \(L(s)=N\) if and only if the Hamming weight of a period of the sequence is odd.

Lemma 2.2

Let \(s_1\) and \(s_2\) be two binary sequences with period \(2^n\). If \(L(s_1)\ne L(s_2)\), then \(L(s_1+s_2)=\max \{L(s_1),L(s_2)\} \); otherwise if \(L(s_1)= L(s_2)\), then \(L(s_1+s_2)<L(s_1)\).

Suppose that the linear complexity of s can decrease when at least k elements of s are changed. By Lemma 2.2, the linear complexity of the binary sequence, in which elements at exactly those k positions are all nonzero, must be L(s). Therefore, for the computation of the k-error linear complexity, we only need to find the binary sequence whose Hamming weight is minimum and its linear complexity is L(s).

Based on Games-Chan algorithm, the following lemma is given in [5].

Lemma 2.3

Suppose that s is a binary sequence with one period \(s^{(n)}=\{s_0,s_1,s_2,\cdots , s_{2^n-1}\}\), a mapping \(\varphi _n\) from \(F^{2^n}_2\) to \(F^{2^{n-1}}_2\) is defined as

Let \(W_H(\mathbf {\upsilon })\) denote the Hamming weight of a vector \(\mathbf {\upsilon }\). Then the mapping \(\varphi _n\) has the following properties.

1. (1)

   \(W_H(\varphi _n(s^{(n)}))\le W_H(s^{(n)})\);

2. (2)

   If \(n\ge 2\), then \(W_H(\varphi _n(s^{(n)}))\) and \(W_H(s^{(n)})\) are either both odd or both even;

3. (3)

   The set

   $$\varphi ^{-1}_{n+1}(s^{(n)})=\{v\in F^{2^{n+1}}_2|\varphi _{n+1}(v)=s^{(n)} \}$$

   of the preimage of \(s^{(n)}\) has cardinality \(2^{2^n}\).

Rueppel [6] presented the following result on the number of sequences with a given linear complexity.

Lemma 2.4

The number N(L) of \(2^n\)-periodic binary sequences with linear complexity \(L, 0\le L \le 2^n\), is given by \(N(L)=\left\{ \begin{array}{l} 1, \ \ \ \ \ L=0\ \ \\ 2^{L-1}, \ 1\le L\le 2^n \end{array}\right. \)

Based on algebraic and combinatorial methods, Fu, Niederreiter and Su [4] characterized the \(2^n\)-periodic binary sequences with the 1-error linear complexity and derived the counting function completely for the 1-error linear complexity of \(2^n\)-periodic binary sequences. Meidl [5] characterized the complete counting functions on the 1-error linear complexity of \(2^n\)-periodic binary sequences with linear complexity \(2^n\). Zhu and Qi [12] gave the complete counting functions on the 2-error linear complexity of \(2^n\)-periodic binary sequences with linear complexity \(2^n-1\).

In this paper, we will study the k-error linear complexity of \(2^n\)-periodic binary sequences by using the sieve approach and Games-Chan algorithm. The adopted approach is similar to [9] but different from those in [4, 5, 12]. The proposed structural approach in this paper is based on the following framework. Let \(S=\{s | L(s)=c\}, E=\{e | W_H(e)=k\}, SE=\{s+e | s\in S, e\in E\}\), where s is a sequence with linear complexity c and e is sequence with \(W_H(e)=k\). With the following sieve method, we aim to sieve sequences \(s+e\) with \(L_{k}(s+e)=c\) from SE.

For given linear complexity c, it remains to investigate two cases. One is that \(s+u\in SE\), but \(L_{k}(s+u) <c\). This is equivalent to checking if there exists a sequence v such that \(L(u+v)=c\). The other is the case that \(s+u, t+v\in SE\) and \(L_{k}(s+u) =L_{k}(t+v) =c\) with \(s\ne t\), \(u\ne v\), but \(s+u= t+v\). It is equivalent to checking if there exists a sequence v such that \(L(u+v)=L(s+t)<c\) and if so, check the number of such sequence v, where \(W_H(u)= W_H(v)=k\).

Next we derive the counting formula of \(2^n\)-periodic binary sequences with the prescribed 1-error linear complexity as the first descent point, prescribed 3-error linear complexity as the second descent point and the prescribed 5-error linear complexity as the third descent point. To this end, we will use Cube Theory recently introduced in [10]. Cube theory and some related results are presented next for completeness.

Suppose that the position difference of two non-zero elements of a sequence s is \((2x+1)2^y\), where x and y are non-negative integers. From Algorithm 2.1, only in the \((n-y)\)th step, the sequence length is \(2^{y+1}\), so the two non-zero elements must be in the left and right half of the sequence respectively, thus they can be removed or reduce to one non-zero element in consequence operation. Therefore we have the following definitions.

Definition 3.1

([10]). Suppose that the position difference of two non-zero elements of a sequence s is \((2x+1)2^y\), where both x and y are non-negative integers, then the distance between the two elements is defined as \(2^y\).

Definition 3.2

([10]). Suppose that s is a binary sequence with period \(2^n\), and there are \(2^m\) non-zero elements in s, and \(0\le i_1< i_2<\cdots <i_m<n\). If \(m=1\), then there are 2 non-zero elements in s and the distance between the two elements is \(2^{i_1}\), so it is called as a 1-cube. If \(m = 2\), then s has 4 non-zero elements which form a rectangle, the lengths of 4 sides are \(2^{i_1}\) and \(2^{i_2}\) respectively, so it is called as a 2-cube. In general, s has \(2^{m-1}\) pairs of non-zero elements, in which there are \(2^{m-1}\) non-zero elements which form a \((m-1)\)-cube, the other \(2^{m-1}\) non-zero elements also form a \((m-1)\)-cube, and the distance between each pair of elements are all \(2^{i_m}\), then the sequence s is called as an m-cube, and the linear complexity of s is called as the linear complexity of the cube as well.

Definition 3.3

([10]). A non-zero element of sequence s is called a vertex. Two vertexes can form an edge. If the distance between the two elements (vertices) is \(2^y\), then the length of the edge is defined as \(2^y\).

As demonstrated in [10], the linear complexity of a \(2^n\)-periodic binary sequence with only one cube has the following nice property.

Theorem 3.1

Suppose that s is a binary sequence with period \(2^n\), and non-zero elements of s form a m-cube, if lengths of edges are \( 2^{i_1}, 2^{i_2},\cdots ,2^{i_m}\) \((0\le i_1< i_2<\cdots <i_m<n )\) respectively, then \(L(s)=2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})\).

Based on Algorithm 2.1, we may have a standard cube decomposition for any binary sequence with period \(2^n\).

Obviously, this is a cube decomposition of sequence \(s^{(n)}\), and we define it as the standard cube decomposition. One can observe that cube decomposition of a sequence may not be unique in general and the standard cube decomposition of a sequence described above is unique.

Suppose that \(s^{(n)}\) is a \(2^n\)-periodic binary sequence. We first investigate the relationship among the first descent point, the second descent point and the third descent point of the k-error linear complexity. Second, based on the first descent point, the second descent point and the third descent point, we obtain the complete counting functions of \(2^n\)-periodic binary sequences with given 1-error linear complexity, 3-error linear complexity and 5-error linear complexity as the first descent point, the second descent point and the third descent point separately.

Theorem 3.2

Let \(s^{(n)}\) be a \(2^n\)-periodic binary sequence with linear complexity \(2^n \). Then

1. (i).

   Suppose that \(c_1\), \(c_2\) and \(c_3\) are in the standard cube decomposition of sequence \(s^{(n)}\). \(L_{5}(s^{(n)})<L_{3}(s^{(n)})<L_1(s^{(n)})\) if and only if \(c_1\) is a 0-cube (only one nonzero element), \(c_2\) and \(c_3\) are two 1-cubes or \(c_1\) is a 0-cube and \(c_2\) is a 2-cube;

2. (ii).

   \(L_{5}(s^{(n)})<L_{3}(s^{(n)})<L_1(s^{(n)})\) if and only if \(L_{1}(s^{(n)})=2^n -(2^i+2^j), 0\le i<j<n\), \(L_{3}(s^{(n)})=2^n -(2^p+2^q), 0\le p<q<n, j<q, p\ne i,j\), or \(L_{3}(s^{(n)})=2^n -(2^i+2^j+2^r), 0\le r<n, r\ne i,j\).

Proof

Based on cube theory, sequence \(s^{(n)}\) has a standard cube decomposition. As \(L(s^{(n)})=2^n\), it is obvious that \(c_1\) is a 0-cube.

First, suppose that \(c_2\) and \(c_3\) are two 1-cubes. Then \(L_{1}(s^{(n)})=2^n -(2^i+2^j)\), where \(0\le i<j<n, L(c_2)=2^n-2^j\) and \(L_{3}(s^{(n)})=2^n -(2^p+2^q)\), where \(0\le p<q<n, L(c_3)=2^n-2^q\) or \(L_{3}(s^{(n)})=2^n -(2^i+2^j+2^q)\), where \(0\le q<n, q\ne i,j, L(c_3)=2^n-2^q\). Thus \(j<q\).

In the case that \(L_{3}(s^{(n)})=2^n -(2^p+2^q)\), we now prove that \(p\ne i,j\). Assume that \(p= i\), and the distance (based on Definition 3.1) of nonzero elements \(p_1\) and \(p_4\) is \(2^i\), where \(p_1\) is in \(c_1\) (in the case that \(p_1\) is in \(c_2\), the proof is similar), \(p_4\) is in \(c_3\). As the distance of nonzero elements \(p_1\) and \(p_2\) is also \(2^i\), so the distance of nonzero elements \(p_2\) and \(p_4\) is \(2^{i+1}\), thus \(L_{3}(s^{(n)})=2^n -(2^{i+1}+2^q)\) should be true, which contradicts to the fact that \(L_{3}(s^{(n)})=2^n -(2^{i}+2^q)\).

Assume that \(p= j\), similarly one can prove that \(L_{3}(s^{(n)})=2^n -(2^{j+1}+2^q)\), which is not true, or one can prove that \(L_{3}(s^{(n)})=2^n -(2^i+2^j+2^q)\). In this case, it is obvious that \(q\ne i,j\).

Second, suppose that \(c_2\) is a 2-cube and \(L(c_2)=2^n -(2^i+2^j)\). It is easy to show that \(L_{1}(s^{(n)})=2^n -(2^i+2^j)\) and \(L_{3}(s^{(n)})=2^n -(2^i+2^j+2^r), 0\le r<n, r\ne i,j\).    \(\square \)

Next we investigate the distribution of \(L_{5}(s^{(n)})\).

Theorem 3.3

Let \(s^{(n)}\) be a \(2^n\)-periodic binary sequence with linear complexity \(2^n\) and \(L_{5}(s^{(n)})<L_{3}(s^{(n)})<L_1(s^{(n)})\), \(L_{1}(s^{(n)})=2^n -(2^i+2^j), 0\le i<j<n\).

1. (i).

   If \(L_{3}(s^{(n)})=2^n -(2^p+2^q), 0\le p<q<n, j<q, p\ne i,j\), then \(L_{5}(s^{(n)})\) can be \( 2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})<2^n -(2^p+2^q)\), where \(0\le i_1< i_2<\cdots <i_m<n, m>3\).

   For the case of \(m=3\). If \(j<p\) or \(i<p<j\), \(\{i_1,i_2,i_3\}\ne \{i,p,q\}\); if \(i>p\), \(\{i_1,i_2,i_3\}\ne \{i,p,q\}\) and \(\{j,p,q\}\). For the case of \(m=2\), \(\{i_1,i_2\}\) can not include i, j, p or q.

2. (ii).

   If \(L_{3}(s^{(n)})=2^n -(2^i+2^j+2^r), 0\le r<n, r\ne i,j\), then \(L_{5}(s^{(n)})\) can be \( 2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})<2^n -(2^p+2^q)\), where \(0\le i_1< i_2<\cdots <i_m<n, m>3\).

   For the case of \(m=3\), \(\{i_1,i_2,i_3\}\) can not contain \(\{i,j\}\). For the case of \(m=2\), \(\{i_1,i_2\}\) can not include i, j or r.

Proof

The following proof is based on the framework: \(SE=\{t+e | t\in S, e\in E\}\).

(i). In the case that \(L_{5}(s^{(n)})= 2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})<2^n -(2^i+2^j), m>3\), let \(s^{(n)}\) be a \(2^n\)-periodic binary sequence with linear complexity \(2^n \), \(L_{1}(s^{(n)})=2^n -(2^i+2^j)\) and \(L_{3}(s^{(n)})=2^n -(2^p+2^q)\).

Let \(S=\{t | L(t)=2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})\}, E=\{e | W_H(e)=5\}, SE=\{t+e | t\in S, e\in E\}\), where t is a sequence with linear complexity \(2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})\) and e is sequence with \(W_H(e)=5\). With the sieve method, we aim to sieve sequences \(t+e\) with \(L_{5}(t+e)=2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})\) from SE.

We investigate the case that \(s+u\in SE\), but \(L_{5}(t+u) <2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})\). This is equivalent to checking if there exists a sequence \(v\in E\) such that \(L(u+v)=2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m}), m\ge 4\). As a 4-cube has \(2^4=16\) nonzero elements and \(W_H(u)=W_H(v)=5\), thus it is impossible that \(L(u+v)=2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m}), m\ge 4\). Therefore, \(L_{5}(s^{(n)})\) can be \( 2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})<2^n -(2^p+2^q)\).

Second consider the case that \(m=3\) and \(i>p\).

Let \(s^{(n)}\) be a \(2^n\)-periodic binary sequence with linear complexity \(2^n \). If \(L_{1}(s^{(n)})=2^n -(2^i+2^j)\) and \(L_{3}(s^{(n)})=2^n -(2^p+2^q)\), then \(L_{5}(s^{(n)})\ne 2^n-(2^p+2^i+2^q)\).

We will prove it by a contradiction. Suppose that \(L_{5}(s^{(n)})= 2^n-(2^p+2^i+2^q)\). Let \(S=\{t | L(t)=2^n-(2^p+2^i+2^q)\}, E=\{e | W_H(e)=5\}, SE=\{t+e | t\in S, e\in E\}\), where t is a sequence with linear complexity \(2^n-(2^p+2^i+2^q)\) and e is sequence with \(W_H(e)=5\). With the sieve method, we aim to sieve sequences \(t+e\) with \(L_{5}(t+e)=2^n-(2^p+2^i+2^q)\) from SE.

We now investigate the case that \(s+u\in SE\), but \(L_{5}(t+u) <2^n-(2^p+2^i+2^q)\). This is equivalent to checking if there exists a sequence \(v\in E\) such that \(L(u+v)=2^n-(2^p+2^i+2^q)\).

For any \(u\in E\) such that \(L_{1}(t+u) =2^n-(2^i+2^j)\) and \(L_{3}(t+u)=2^n -(2^p+2^q)\). It is easy to prove that there exists a sequence \(v\in E\) such that \(L_{1}(t+v) =2^n-(2^i+2^j)\), \(L_{3}(t+v)=2^n -(2^p+2^q)\) and \(L(u+v)= 2^n-(2^p+2^i+2^q)\). (Refer to Example 3.1 for the illustration of the proof.) So \(L_{5}(t+u) <2^n-(2^p+2^i+2^q)\). Therefore \(\{i_1,i_2,i_3\}\ne \{i,p,q\}\).

Similarly, let \(L(t)=2^n-(2^p+2^j+2^q)\). There exists a sequence \(v\in E\) such that \(L_{1}(t+v) =2^n-(2^i+2^j)\), \(L_{3}(t+v)=2^n -(2^p+2^q)\) and \(L(u+v)=2^n-(2^p+2^j+2^q)\). So \(L_{5}(t+u) <2^n-(2^p+2^j+2^q)\). Therefore \(\{i_1,i_2,i_3\}\ne \{j,p,q\}\).

In the case that \(m=2\), \(\{i_1,i_2\}\) can not contain i, j, p or q. Suppose that \(\{i_1,i_2\}\) comprises q and \(L=2^n-(2^w+2^q)\). As \(L=2^n-(2^w+2^q)<2^n-(2^p+2^q)\), thus \(w>p\). For any \(u\in E\) such that \(L_{1}(t+u) =2^n-(2^i+2^j)\) and \(L_{3}(t+u)=2^n -(2^p+2^q)\). It is easy to prove that there exists a sequence \(v\in E\) such that \(L_{1}(t+v) =2^n-(2^i+2^j)\), \(L_{3}(t+v)=2^n -(2^p+2^q)\) and \(L(u+v)= 2^n-(2^w+2^q)\). (Refer to Example 3.2 for the illustration of the proof.) So \(L_{5}(t+u) <2^n-(2^w+2^q)\). Therefore \(\{i_1,i_2\}\ne \{w,q\}\).

(ii). In the case that \(m=3\) and \(r>j\), \(\{i_1,i_2,i_3\}\) can not contain \(\{i,j\}\).

In the case that \(L_{3}(s^{(n)})= 2^n-(2^{i}+2^{j}+2^{r})\). Note that \(c_1\) is a 0-cube and \(c_2\) is a 2-cube, \(L(c_2)=L_{1}(s^{(n)})=2^n -(2^i+2^j)\). For any \(u\in E\) such that \(L_{1}(t+u) =2^n-(2^i+2^j)\) and \(L_{3}(t+u)=2^n -(2^{i}+2^{j}+2^{r})\). It is easy to prove that there exists a sequence \(v\in E\) such that \(L_{1}(t+v) =2^n-(2^i+2^j)\), \(L_{3}(t+v)=2^n -(2^{i}+2^{j}+2^{r})\) and \(L(u+v)= 2^n-(2^{i}+2^{j}+2^{w})\). (Refer to Example 3.3 for the illustration of the proof.) So \(L_{5}(t+u) <2^n-(2^{i}+2^{j}+2^{w})\). Therefore \(\{i_1,i_2,i_3\}\) can not contain \(\{i,j\}\).

Similarly, for the case of \(m=2\), it is easy to show that \(\{i_1,i_2\}\) can not include i, j or r.

This completes the proof.   \(\square \)

Example 3.1

Let \(u=\{1101\ 0100\ 1000\ 0000 \}\) with \(L_{1}(u) =2^4-(2+2^2)\) and \(L_{3}(u)=2^4 -(1+2^3)\). There exists a sequence \(v=\{0010\ 0100\ 0111\ 0000 \}\) such that \(L_{1}(v) =2^4-(2+2^2)\), \(L_{3}(v)=2^4 -(1+2^3)\), and \(L(u+v)= 2^4-(2^0+2^1+2^3)\).

Example 3.2

Suppose that \(n=5, i=2,j=3, p=1, q=4, w=2\),

\(u^{(5)}=\{1010\ 0010\ 0010\ 0000\ 1000\ 0000\ 0000\ 0000 \}\).

Then \(L=2^n-(2^w+2^q)=12\). There exists

\(v^{(5)}=\{0010\ 1010\ 0010\ 0000\ 0000\ 1000\ 0000\ 0000 \}\), such that \(L(u^{(5)}+v^{(5)})=2^5-(2^2+2^4)=12\).

Example 3.3

Suppose that \(n=4, i=0,j=1, r=2, w=3\),

\(u^{(4)}=\{1111\ 1000\ 0000\ 0000 \}\). Then there exists \(v^{(4)}=\{0000\ 1000\ 1111\ 0000 \}\), such that \(L(u^{(4)}+v^{(4)})=2^4-(1+2+2^3)\).

We next derive the counting formula of binary sequences with the prescribed 1-error linear complexity, the prescribed 3-error linear complexity and the prescribed 5-error linear complexity.

Theorem 3.4

paginationLet \(s^{(n)}\) be a \(2^n\)-periodic binary sequence with linear complexity \(2^n \).

(1) Suppose that \(L_{5}(s^{(n)})<L_{3}(s^{(n)})<L_1(s^{(n)})\) and \(L_{1}(s^{(n)})=2^n -(2^i+2^j), 0\le i<j<n\), \(L_{3}(s^{(n)})=2^n -(2^p+2^q), 0\le p<q<n, j<q, p\ne i,j\), and \(L_{5}(s^{(n)})= 2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})<L_{3}(s^{(n)})\), where \(0\le i_1< i_2<\cdots <i_m<n, m>1\). Then the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) can be given by

where \(\theta \) is defined in (1) of the following proof, \(\delta , \mu \) and \(\epsilon \) are defined in the following proof according to \(j<p\), \(i<p<j\) and \(p<i<j\).

If \(L_{5}(s^{(n)})=0\), then the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) can be given by

where if \(j<p\) then \(\gamma =3\), if \(j>p>i\) then \(\gamma =2\) else \(\gamma =1\).

(2) Suppose that \(L_{5}(s^{(n)})<L_{3}(s^{(n)})<L_1(s^{(n)})\) and \(L_{1}(s^{(n)})=2^n -(2^i+2^j), 0\le i<j<n\), \(L_{3}(s^{(n)})=2^n -(2^i+2^j+2^r), 0\le r<n, r\ne i,j\), and \(L_{5}(s^{(n)})= 2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})<L_{3}(s^{(n)})\), where \(0\le i_1< i_2<\cdots <i_m<n, m>1\). Then the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) can be given by

where \(\delta , \theta \) and \(\epsilon \) are defined in the following proof according to \(j<r\), \(i<r<j\) and \(r<i<j\).

If \(L_{5}(s^{(n)})=0\), then the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) can be given by

where if \(r<i\) then \(\gamma =1/2\) else \(\gamma =1\).

Proof

(1) Let \(S=\{t | L(t)=L\}, E=\{e | W_H(e)=5\}, SE=\{t+e | t\in S, e\in E\}\), where t is a sequence with linear complexity \(L=2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m}), m>2\) and e is sequence with \(W_H(e)=5\), \(L_{1}(e) =2^n-(2^i+2^j)\) and \(L_{3}(e)=2^n -(2^p+2^q)\). With the sieve method, we aim to sieve sequences \(t+e\) with \(L_{5}(t+e)=L\) from SE.

By Lemma 2.4, we know that the number of \(2^n\)-periodic binary sequences t with \(L(t)=L\) is \(2^{L-1}\). Now we will compute the number of sequences e with \(W_H(e)=5\), \(L_{1}(e) =2^n-(2^i+2^j)\) and \(L_{3}(e)=2^n -(2^p+2^q), j<q\).

In the case of \( i<j<p<q\). The number of \(2^{j+1}\)-periodic binary sequences \(e^{(j+1)}\) with linear complexity \(2^{j+1}-2^{j}=2^{j}\) and \(W_H(e^{(j+1)})=2\) is \(2^{j}\). First one nonzero element is added so that \(L_1(e^{(j+1)})=2^{j+1}-(2^i+2^j)\). The number of \(e^{(j+1)}\) becomes \(2^{j}\times 2^{j-i}\).

Second one 1-cube with linear complexity \(2^{q+1}-2^q\) is added so that \(L_3(e^{(q+1)})=2^{q+1}-(2^p+2^q)\). Note that for \(i=0, j=1, p=2, q=3\), sequence \(\{1110\ 0100\}\) is from both \(\{1110\ 0000\}\) and \(\{1010\ 0100\}\). At the same time from sequence \(\{1110\ 0100\}\), we have both \(\{1110\ 0100\ 0100\ 0000\}\) and \(\{1110\ 0100\ 0000\ 0100\}\) with \(L_3(e^{(q+1)})=2^{q+1}-(2^p+2^q)\). So the number of \(e^{(q+1)}\) becomes \(2^{2j-i}\times (2^3)^{p-j}\times 3\times (2^4)^{q-p-1}\times 2^3=3\times 2^{4q-p-j-i-1}\).

Finally the number of sequences \(e^{(n)}\) with \(W_H(e^{(n)})=5\), \(L_{1}(e^{(n)})=2^n-(2^i+2^j)\) and \(L_{3}(e^{(n)}) =2^n-(2^p+2^q)\) can be given by

In the case of \( i<p<j<q\). One 1-cube with linear complexity \(2^{q+1}-2^q\) is added so that \(L_3(e^{(q+1)})=2^{q+1}-(2^p+2^q)\). The number of \(e^{(q+1)}\) becomes \(2^{2j-i}\times 2\times 2^{j-p}\times (2^4)^{q-j-1}\times 2^3=2\times 2^{4q-p-j-i-1}\).

Thus the number of sequences \(e^{(n)}\) can be given by

In the case of \( p<i<j<q\). One 1-cube with linear complexity \(2^{q+1}-2^q\) is added so that \(L_3(e^{(q+1)})=2^{q+1}-(2^p+2^q)\). The number of \(e^{(q+1)}\) becomes \(2^{2j-i}\times 2^{j-p}\times (2^4)^{q-j-1}\times 2^3=2^{4q-p-j-i-1}\).

Thus the number of sequences \(e^{(n)}\) can be given by

In general, the number of these \(e^{(n)}\) can be given by

where if \(j<p\) then \(\gamma =3\), if \(j>p>i\) then \(\gamma =2\) else \(\gamma =1\).

We investigate the case that \(s+u, t+v\in SE\) and \(L_{5}(s+u) =L_{5}(t+v) =L\) with \(s\ne t\), \(u\ne v\), but \(s+u= t+v\). It is equivalent to checking if there exists a sequence v such that \(L(u+v)=L(s+t)<L\) and if so, check the number of such sequence v, where \(W_H(u)= W_H(v)=5\). We need to consider the following two cases.

The first case is related to the minimum \(i_0< q\) such that \(2^n-(2^{i_0}+2^q)<L= 2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})\), where \(q=i_m\). If \(p<i,j\), then \(i_0\) can be i or j.

For any \(u\in E\), it is easy to show that there exist \(2^{q-i_0}-1\) sequences v, such that \(L(u+v)<L\).

Second we consider the case of \(i_m<w<n\).

Suppose that \(j<p\). For \(i_m<w<n\), there exist \(31\times 32^{w-i_m-1}\) sequences v, such that \(L(u+v)=2^n-(2^{q}+2^{w})<L\) or \(L(u+v)=2^n-(2^{p}+2^{w})<L\) or \(L(u+v)=2^n-(2^{j}+2^{w})<L\) or \(L(u+v)=2^n-(2^{i}+2^{w})<L\) or \(L(u+v)=2^n-2^{w}<L\).

Note that for any sequence v with 5 nonzero elements, if we double the period of sequence v, then \(2^5\) new sequences will be generated. Therefore there exist

sequences v, such that \(L(u+v)<L\).

On the other hand, if \(q<i_m\) and only \(2^n-(2^{q}+2^{i_m})<L\) then the number of v will be increased by \(32^{n-i_m-1}\).

If \(2^n-(2^{p}+2^{i_m})<L\) and \(2^n-(2^{j}+2^{i_m})>L\) then the number of v will be increased by \(3\times 32^{n-i_m-1}\).

If \(2^n-(2^{j}+2^{i_m})<L\) and \(2^n-(2^{i}+2^{i_m})>L\) then the number of v will be increased by \(7\times 32^{n-i_m-1}\).

If \(2^n-(2^{i}+2^{i_m})<L\) then the number of v will be increased by \(15\times 32^{n-i_m-1}\).

It follows that the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) with \(L(s^{(n)})=2^n \), \(L_{1}(s^{(n)})=2^n -(2^i+2^j)\), \(L_{3}(s^{(n)})=2^n -(2^p+2^q)\) and \(L_{5}(s^{(n)})= L\) can be given by

where

For the case of \(j<p\). If \(L=2^n-(2^j+2^p+2^q)\) then \(\delta =1\), if \(L=2^n-(2^i+2^p+2^q)\) then \(\delta =0\) else \(\delta =3\); if \(L>2^n-(2^i+2^p+2^q)\) then \(\mu =2\) else \(\mu =1\); if \(q<i_m\) and only \(2^n-(2^{q}+2^{i_m})<L\) then \(\epsilon =1\), if \(2^n-(2^{p}+2^{i_m})<L\) and \(2^n-(2^{j}+2^{i_m})>L\) then \(\epsilon =2\), if \(2^n-(2^{j}+2^{i_m})<L\) and \(2^n-(2^{i}+2^{i_m})>L\) then \(\epsilon =3\), if \(2^n-(2^{i}+2^{i_m})<L\) then \(\epsilon =4\).

For the case of \(j>p>i\). If \(L=2^n-(2^j+2^p+2^q)\) then \(\delta =1\), if \(L=2^n-(2^i+2^j+2^q)\) then \(\delta =1/2\), if \(L=2^n-(2^i+2^p+2^q)\) then \(\delta =0\) else \(\delta =2\); if \(L>2^n-(2^i+2^p+2^q)\) then \(\mu =2\) else \(\mu =1\); if \(q<i_m\) and only \(2^n-(2^{q}+2^{i_m})<L\) then \(\epsilon =1\), if \(2^n-(2^{j}+2^{i_m})<L\) and \(2^n-(2^{p}+2^{i_m})>L\) then \(\epsilon =2\), if \(2^n-(2^{p}+2^{i_m})<L\) and \(2^n-(2^{i}+2^{i_m})>L\) then \(\epsilon =3\), if \(2^n-(2^{i}+2^{i_m})<L\) then \(\epsilon =4\).

For the case of \(j>i>p\). If \(L=2^n-(2^j+2^p+2^q)\) or \(L=2^n-(2^i+2^p+2^q)\) then \(\delta =0\) else \(\delta =1\); if \(L>2^n-(2^i+2^p+2^q)\) and \(L>2^n-(2^j+2^p+2^q)\) then \(\mu =4\), if only \(L>2^n-(2^j+2^p+2^q)\) then \(\mu =2\) else \(\mu =1\); if \(q<i_m\) and only \(2^n-(2^{q}+2^{i_m})<L\) then \(\epsilon =1\), if \(2^n-(2^{j}+2^{i_m})<L\) and \(2^n-(2^{i}+2^{i_m})>L\) then \(\epsilon =2\), if \(2^n-(2^{i}+2^{i_m})<L\) and \(2^n-(2^{p}+2^{i_m})>L\) then \(\epsilon =3\), if \(2^n-(2^{p}+2^{i_m})<L\) then \(\epsilon =4\).

(2) First consider the case of \(i<j<r\). Suppose that \(s^{(i)}\) is a \(2^{i}\)-periodic binary sequence with linear complexity \(2^{i}\) and \(W_H(s^{(i)})=1\), then the number of these \(s^{(i)}\) is \(2^{i}\).

So the number of \(2^{i+1}\)-periodic binary sequences \(s^{(i+1)}\) with linear complexity \(2^{i+1}-2^{i}=2^{i}\) and \(W_H(s^{(i+1)})=2\) is also \(2^{i}\).

For \(j>i\), if \(2^{j}\)-periodic binary sequences \(s^{(j)}\) with linear complexity \(2^{j}-2^{i}\) and \(W_H(s^{(j)})=2\), then \(2^{j}-2^{i}-(2^{i+1}-2^{i})=2^{j-1}+2^{j-2}+\cdots +2^{i+1}\).

Based on Algorithm 2.1, the number of these \(s^{(j)}\) can be given by \((2^2)^{j-i-1}\times 2^{i}=2^{2j-i-2}\).

So the number of \(2^{j+1}\)-periodic binary sequences \(s^{(j+1)}\) with linear complexity \(2^{j+1}-(2^{j}+2^{i})\) and \(W_H(s^{(j+1)})=4\) is also \(2^{2j-i-2}\).

Thus the number of \(2^{r+1}\)-periodic binary sequences \(s^{(r+1)}\) with linear complexity \(2^{r+1}-(2^r+2^{j}+2^{i})\) and \(W_H(s^{(r+1)})=8\) is \((2^4)^{r-j-1}\times 2^{2j-i-2}=2^{4r-2j-i-6}\).

There exist \(2^4\) 2-cubes with linear complexity \(2^{r+1}-(2^{j}+2^{i})\) from one 3-cube with linear complexity \(2^{r+1}-(2^r+2^{j}+2^{i})\). Any pair of one 2-cube with linear complexity \(2^{r+1}-(2^{j}+2^{i})\) and one vertex from the 3-cube comes from exactly two different 2-cubes.

As \(u\in E\) such that \(L_{1}(u) =2^n-(2^i+2^j)\) and \(L_{3}(u)=2^n -(2^i+2^j+2^r)\). So the number of these u can be given by

Second consider the case of \(r<i<j\).

We know that the number of \(2^{n}\)-periodic binary sequences \(s^{(n)}\) with linear complexity \(2^{n}-(2^{j}+2^{i})\) and \(W_H(s^{(n)})=4\) is \((2^4)^{n-j-1}\times 2^{2j-i-2}=2^{4n-2j-i-6}\).

There exit \(\frac{2^n}{2^{r+1}}\) locations with the distance \(2^r\) (Definition 3.1) to every vertex in a 2-cube. As \(u\in E\) such that \(L_{1}(u) =2^n-(2^i+2^j)\) and \(L_{3}(u)=2^n -(2^i+2^j+2^r)\). So the number of these u can be given by

Third consider the case of \(i<r<j\).

We know that the number of \(2^{n}\)-periodic binary sequences \(s^{(n)}\) with linear complexity \(2^{n}-(2^{j}+2^{i})\) and \(W_H(s^{(n)})=4\) is \(2^{4n-2j-i-6}\).

There exit \(\frac{2^n}{2^{r+1}}\) locations with the distance \(2^r\) to every two vertices in a 2-cube. As \(u\in E\) such that \(L_{1}(u) =2^n-(2^i+2^j)\) and \(L_{3}(u)=2^n -(2^i+2^j+2^r)\). So the number of these u can be given by

We now investigate the case that \(s+u, t+v\in SE\) and \(L_{5}(s+u) =L_{5}(t+v) =L\) with \(s\ne t\), \(u\ne v\), but \(s+u= t+v\). We need to consider the following two cases.

The first case is related to the minimum \(i_0< j\) such that \(2^n-(2^{i_0}+2^i+2^j)<L= 2^n-(2^{i_1}+2^{i_2}+\cdots +2^{i_m})\). Suppose that \(j=i_m\) and \(r<i\), \(i_0<i\). For any \(u\in E\), it is easy to show that there exist \(2^{j-i_0-1}-1\) sequences v, such that \(L(u+v)<L\).

(The following example is given to illustrate the above case.

Suppose that \(n=5, i=3,j=4, r=1\), \(i_1=0, i_2=1, i_3=3, i_4=4\). So \(L= 2^n-(2^{i_1}+2^{i_2}+2^{i_3}+2^{i_4})=5\).

If \(u^{(5)}=\{1010\ 0000\ 1000\ 0000\ 1000\ 0000\ 1000\ 0000 \}\), then

\(v^{(5)}=\{0010\ 1000\ 0000\ 1000\ 0000\ 1000\ 0000 \ 1000\}\).

Thus \(L(u^{(5)}+v^{(5)})= 2^5-(2^2+2^3+2^4)=4, i_0=2\).)

Suppose that \(j=i_m\) and \(i<r<j\), \(i<i_0<j\). For any \(u\in E\), it is easy to show that there exist \(2^{j-i_0}-1\) sequences v, such that \(L(u+v)<L\).

The second case is related to \(i_m<w<n\).

Suppose that \(j<r\). For \(i_m<w<n\), there exist \(31\times 32^{w-i_m-1}\) sequences v, such that \(L(u+v)=2^n-(2^{r}+2^{w})<L\) or \(L(u+v)=2^n-(2^i+2^{j}+2^{w})<L\) or \(L(u+v)=2^n-(2^{j}+2^{w})<L\) or \(L(u+v)=2^n-(2^{i}+2^{w})<L\) or \(L(u+v)=2^n-2^{w}<L\).

Note that for any sequence v with 5 nonzero elements, if we double the period of sequence v, then \(2^5\) new sequences will be generated. Therefore there exist

sequences v, such that \(L(u+v)<L\).

On the other hand, if \(r<i_m\) and only \(2^n-(2^{r}+2^{i_m})<L\) then the number of v will be increased by \(32^{n-i_m-1}\).

If \(2^n-(2^i+2^{j}+2^{i_m})<L\) and \(2^n-(2^{j}+2^{i_m})>L\) then the number of v will be increased by \(3\times 32^{n-i_m-1}\).

If \(2^n-(2^{j}+2^{i_m})<L\) and \(2^n-(2^{i}+2^{i_m})>L\) then the number of v will be increased by \(7\times 32^{n-i_m-1}\).

If \(2^n-(2^{i}+2^{i_m})<L\) then the number of v will be increased by \(15\times 32^{n-i_m-1}\).

It follows that the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) with \(L(s^{(n)})=2^n \), \(L_{1}(s^{(n)})=2^n -(2^i+2^j)\), \(L_{3}(s^{(n)})=2^n -(2^i+2^j+2^r)\) and \(L_{5}(s^{(n)})= L\) can be given by

For the case of \(j<r\). \(\delta =1, \theta =1\). If \(r<i_m\) and only \(2^n-(2^{r}+2^{i_m})<L\) then \(\epsilon =1\), if \(2^n-(2^i+2^{j}+2^{i_m})<L\) and \(2^n-(2^{j}+2^{i_m})>L\) then \(\epsilon =2\), if \(2^n-(2^{j}+2^{i_m})<L\) and \(2^n-(2^{i}+2^{i_m})>L\) then \(\epsilon =3\), if \(2^n-(2^{i}+2^{i_m})<L\) then \(\epsilon =4\).

For the case of \(i<r<j\). \(\delta =1\). If \(j=i_m\) and \(i<i_0<j\) then \(\theta =2^{j-i_0}\) else \(\theta =1\). If \(j<i_m\) and only \(2^n-(2^i+2^{j}+2^{i_m})<L\) then \(\epsilon =1\), if \(2^n-(2^{j}+2^{i_m})<L\) and \(2^n-(2^{r}+2^{i_m})>L\) then \(\epsilon =2\), if \(2^n-(2^{r}+2^{i_m})<L\) and \(2^n-(2^{i}+2^{i_m})>L\) then \(\epsilon =3\), if \(2^n-(2^{i}+2^{i_m})<L\) then \(\epsilon =4\).

For the case of \(r<i<j\). \(\delta =1/2\). If \(j=i_m\) and \(i_0<i\) then \(\theta =2^{j-i_0-1}\) else \(\theta =1\). If \(j<i_m\) and only \(2^n-(2^i+2^{j}+2^{i_m})<L\) then \(\epsilon =1\), if \(2^n-(2^{j}+2^{i_m})<L\) and \(2^n-(2^{i}+2^{i_m})>L\) then \(\epsilon =2\), if \(2^n-(2^{i}+2^{i_m})<L\) and \(2^n-(2^{r}+2^{i_m})>L\) then \(\epsilon =3\), if \(2^n-(2^{r}+2^{i_m})<L\) then \(\epsilon =4\).

The proof is complete.   \(\square \)

To further illustrate Theorem 3.4, we give the following two examples, which are verified by a computer program as well.

Example 3.4

Suppose that \(n=5, i=0,j=1, p=2, q=4\), \(i_1=0, i_2=1, i_3=2, i_4=4\). So \(L= 2^n-(2^{i_1}+2^{i_2}+2^{i_3}+2^{i_4})=9\). As \(j<p\) and \(q=i_4\), so \(\delta =3\), \(i_0=3\), \(\theta =2^{q-i_0}=2\), \(\epsilon =0\). The number of \(2^5\)-periodic binary sequences \(s^{(5)}\) with \(L(s^{(5)})=32 \), \(L_{1}(s^{(5)})=29\), \(L_{3}(s^{(5)})= 12\) and \(L_{5}(s^{(5)})= 9\) can be given by

Example 3.5

Suppose that \(n=5, i=3,j=4, r=1\), \(i_1=0, i_2=1, i_3=3, i_4=4\). So \(L= 2^n-(2^{i_1}+2^{i_2}+2^{i_3}+2^{i_4})=5\). As \(r<i\) and \(j=i_4\), so \(i_0=2\), \(\delta =1/2\), \(\theta =2^{j-i_0-1}=2\), \(\epsilon =0\). The number of \(2^5\)-periodic binary sequences \(s^{(5)}\) with \(L(s^{(5)})=32 \), \(L_{1}(s^{(5)})=8\), \(L_{3}(s^{(5)})= 6\) and \(L_{5}(s^{(5)})= 5\) can be given by

A new approach to determining CELCS for the k-error linear complexity distribution of \(2^n\)-periodic binary sequences was developed via the sieve method and Games-Chan algorithm. The third descent point distribution of the 5-error linear complexity for \(2^n\)-periodic binary sequences was characterized completely.

Suppose that \(s^{(n)}\) is a \(2^n\)-periodic binary sequence. Let \(N_{k}(L)\) be the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) with linear complexity \(2^n\) and the k-error linear complexity L. The complete counting function \(N_{1}(L)\) is obtained in [5]. The complete counting function \(N_{3}(L)\) is obtained in [9]. With an approach different from [9], we now consider a possible way to obtain the complete counting function \(N_{5}(L)\) based on the results in this paper.

Let \(N_{i,k}(L)\) be the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) with linear complexity \(2^n\), the i-error linear complexity as the last descent point and the k-error linear complexity being L. Then we can have

As the complete counting functions on the 3-error linear complexity of \(2^n\)-periodic binary sequences as the second descent point are obtained in [11]. Combined with the result of Sect. 3, we may have the complete counting function \(N_{5}(L)\). Here we only give two examples to illustrate the counting function.

We further define \(N_{3,5}(C1, L)\) as the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) with linear complexity \(2^n\), the 1-error linear complexity C1, the 3-error linear complexity as the last descent point and the 5-error linear complexity being L. Define \(N_{5,5}(C1, C2, L)\) as the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) with linear complexity \(2^n\), the 1-error linear complexity C1, the 3-error linear complexity C2 and the 5-error linear complexity L as the third descent point. Now we can have the following examples.

Example 4.1

Let \(n=5, L=12\). Note that \(12=32-(2^2+2^4)\). If \(L_1(s^{(n)})=12\), then \(L_5(s^{(n)})<12\).

If \(L_3(s^{(n)})=12\), then \(s^{(n)}\) contains one 0-cube (only one nonzero element) and two 1-cubes, thus \(L_5(s^{(n)})<12\).

In the case of \(N_{5,5}(C1, C2, L)\), from Theorem 3.3, i, j, p, q, r can not be 2 or 4. So

Example 4.2

Let \(n=5, L=21\). Note that \(21=32-(1+2+2^3)\). If \(L_1(s^{(n)})=32-(1+2)\) and \(L_3(s^{(n)})=32-(1+2+2^3)\), then \(s^{(n)}\) contains one 0-cube (only one nonzero element) and one 2-cube, hence \(L_5(s^{(n)})<21\). It is similar for \(s^{(n)}\) with \(L_1(s^{(n)})=32-(1+2^3)\) or \(L_1(s^{(n)})=32-(2+2^3)\).

In the case of \(N_{5,5}(C1, C2, L)\), from Theorem 3.3, \(\{i,j\}\subset \{0,1,3\}\) is impossible, \(\{p,q\}\subset \{0,1,3\}\) does not hold. Thus

The examples above have been verified by a computer program.

Let \(s^{(n)}\) be a \(2^n\)-periodic binary sequence with linear complexity less then \(2^n \). Suppose that \(c_1\), \(c_2\) and \(c_3\) are in the standard cube decomposition of sequence \(s^{(n)}\) and \(L(s^{(n)})=L(c_1)\). \(L_{6}(s^{(n)})<L_{4}(s^{(n)})<L_2(s^{(n)})<L_(s^{(n)})\) if and only if \(c_1\) is one 1-cube and \(c_2\) is one 2-cube or \(c_1\), \(c_2\) and \(c_3\) are three 1-cubes. Similarly, we can compute the number of \(2^n\)-periodic binary sequences \(s^{(n)}\) with given \(L_(s^{(n)})\), \(L_2(s^{(n)})\), \(L_{4}(s^{(n)})\) and \(L_{6}(s^{(n)})\). Accordingly, the solution to the complete counting functions of \(2^n\)-periodic binary sequences with the prescribed 6-error linear complexity can be obtained.

The expected value of the k-error linear complexity of \(2^n\)-periodic binary sequences could also be investigated based on our results. We will continue this work in future due to its importance.