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

本文定义了k个从k元n级de Bruijn-Good图到k元n-1级de Bruijn-Good图的满同态映射D_a,利用这些同态映射,我们证明了n级非奇反馈函数f(x₁,x₂,…,x_n)与以D_a(G_f)为状态图的n-1级非奇反馈函数g(x₁,x₂,…,x_n-1)的一个关系定理,给出了k元de Bruijn序列的反馈函数的一个升级算法,特别当k=2,a=0时,利用映射D在 Z ₂上运算的简单性,本文给出了一个从2元n-2^r级de Bruijn序列反馈函数直接生成2元n级de Bruijn序列的反馈函数的有效算法.

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

k homomorphic mappings from k-ary n-stage de Bruijn-Good graph onto k-ary(n-1)-stage de Bruijn-Good graph are defined.By using the homomorphic mappings,we prove a relational theorem between n-stage nonsingular feedback function f(x₁,x₂,…,x_n) and (n-1)-stage nonsingular feedback function g(x₁,x₂,…,x_n-1),whose state graph is D_a(G_f),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 a=0,by using the simplicity of mapping D over Z ₂,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.