非线性过滤序列线性复杂度的估计  

On Linear Complexity of Nonlinear Filtered m-sequences

作　　者：孙中化[1] 戚文峰[1] 

机构地区：[1]郑州信息工程大学信息研究系,郑州450002

出　　处：《计算机工程与应用》2006年第33期31-33,37,共4页Computer Engineering and Applications

基　　金：国家自然科学基金资助项目(60373092)

摘　　要：设_a是F2以上f（x）为极小多项式的n级m-序列，a为f（x）的一个根，布尔函数F（x0,x1,…xm-1）=xi1xi2…xi2＋G（x0,x1…,xm-1）,其中1〈m〈2^n-1,2≤k≤[n/2],deg（G（x0,x1…，xm-1）〈k。论文证明了：若a^i1, a^i2,…a^i1在F2上线性无关，且F2（a^i1,a^i2,…a^i1）=F2≠F2，则非线性过滤序列b=F（L^0_a,L^1a,…L^m-1 _a）（L^i_a=（ai,ai＋1,ai＋2,…）,i≥0）的线性复杂度LC（_b）iakhφ（n^＊）（n/n^＊）^k≤LC（_b）≤i=1∑^k （i^n）-n^＊ ｜a＇｜n∑ （k ^n/d）。Let _a be a binary m-sequence of degree n f（x） the minimal polynomial of _a , and α a root of f（x）; Let 1〈m〈2^n -1, 2≤k≤[n/2] and F（x0,x1…,xm-1）=xi1xi2…xi2＋G（x0,x1…,xm-1）, Where deg （G（x0,x1…,xm-1）〈k. It proved that if a^i1, a^i1, …a^i2 are linera independent over F2 and a^i1, a^i2,…a^i1∈F2^n＋, which is a subfield of F2 , then the Linear Complexity of _b=F（L^0_a, L^1 _a, …, L^m-1 _a） （where L^i _a=（ai,ai＋1,ai＋2,…）,i≥0） satisfies φ（n^＊）（n/n^＊）^k≤LC（_b）≤i=1∑^k （i^n）-n^＊ ｜a＇｜n∑ （k ^n/d）.

关 键 词：M-序列 非践性过滤序列 线性复杂度 

分 类 号：O151.2[理学—数学] O153.4[理学—基础数学]