The linear complexity of a de Bruijn sequence is the degree of the shortest linear recursion which generates the sequence. It is well known that the complexity of a binary de Bruijn sequence of length 2(n) is bounded ...
详细信息
The linear complexity of a de Bruijn sequence is the degree of the shortest linear recursion which generates the sequence. It is well known that the complexity of a binary de Bruijn sequence of length 2(n) is bounded below by 2(n-1) + n and above by 2(n-1) for n greater than or equal to 3. We briefly survey the known knowledge in this area. Same new results are also presented, in particular, it is shown that for each interval of length 2(right perpendicular log n left perpendicular + 1), in the above range, there exist binary de Bruijn sequences of length 2(n) with linear complexity in the interval.
暂无评论