k元de Bruijn序列的反馈函数的一个升级算法  

An Algorithm for Generating Feedback Functions of k-ary De Bruijn Sequences by Raising Stage

作　　者：朱士信[1] 孙琳[1] 

机构地区：[1]合肥工业大学应用数学系,安徽合肥230009

出　　处：《电子学报》2006年第6期1066-1068,共3页Acta Electronica Sinica

基　　金：安徽省自然科学基金项目(No.03042203)

摘　　要：本文定义了k个从k元n级de Bruijn-Good图到k元n-1级de Bruijn-Good图的满同态映射Da,利用这些同态映射,我们证明了n级非奇反馈函数f(x1,x2,…,xn)与以Da(Gf)为状态图的n-1级非奇反馈函数g(x1,x2,…,xn-1)的一个关系定理,给出了k元de Bruijn序列的反馈函数的一个升级算法,特别当k=2,a=0时,利用映射D在Z2上运算的简单性,本文给出了一个从2元n-2r级de Bruijn序列反馈函数直接生成2元n级deBruijn序列的反馈函数的有效算法.k homomorphic mappings from k-ary n-stage de Bruijn-Good graph onto k-ary（ n- 1 ）-stage de Bruiin-Good graph are defined. By using the homomorphic mappings, we prove a relational theorem between n-stage nonsingular feedback function f（x1 ,x2 ……, xn ） and （ n - 1 ） -stage nonsingular feedback function g （ x1, x2, ..., xn-1 ）, whose state graph is Dα （ Gf） , and give an algorithm for generating k-ary feedback functions of n-stage de Bruijn sequences from those of （n- 1 ）-stage de Bruijn sequences. In particular, when k=2 and α=0, by using the simplicity of mapping D over Z2, we give an effictive algorithm for generating n-stage feedback functions of de Bruijn sequences from （ n - 2^r） -stage the feedback functions, where r is a nature number.

关 键 词：DE Bruijn—Good图 DE Bruijn序列 同态映射 非奇反馈函数 

分 类 号：TN911[电子电信—通信与信息系统]