On the k-Error Linear Complexities of De Bruijn Sequences

摘要

We study the fc-error linear complexities of de Bruijn sequences. Let n be a positive integer and k be an integer less than 「2~(n-1)/n」. We show that the fc-error linear complexity of a de Bruijn sequence of order n is greater than or equal to 2~(n-1) + 1, which implies that de Bruijn sequences have good randomness property with respect to the fc-error linear complexity. We also study the compactness of some related bounds, and prove that in the case that n ≥ 4 and n is a power of 2, there always exists a de Bruijn of order n such that the Hamming weight of L(s)⊕ R(s) is 2~(n-1)/n, where L(s) and R(s) denote respectively the left half and right half of one period of this de Bruijn sequence. Besides, some experimental results are provided for the case that n is not a power of 2.