产生k元de Bruijn序列的一个递归算法  

A recursive algorithm for generating k-ary de Bruijn sequences

作　　者：朱士信[1] 吴波[1] 

机构地区：[1]合肥工业大学理学院,安徽合肥230009

出　　处：《合肥工业大学学报（自然科学版）》2005年第9期1210-1212,共3页Journal of Hefei University of Technology：Natural Science

基　　金：安徽省自然科学基金资助项目(03042201)

摘　　要：通过合并纯轮换移位寄存器状态图中的所有圈,给出了生成k元de Bruijn序列的一个递归算法,不再采用“主圈并一个圈”的经典并圈法,而是利用了“主圈并一组共轭圈”的新方法,减少了选择桥状态的次数;同时,给出了新的选择桥状态的规则,简化了判断一个状态是否是桥状态的计算,从而加快了并圈的速度。By joining all cycles in the state graph of pure cycling register,a recursive algorithm for generating k-ary de Bruijn sequences is given in this paper. Not the classical method that the main cycle is extended by joining to it one cycle but a new method that the main cycle is extended by joining to it a subset of cycles is used in the algorithm. The method reduces the time of choosing bridging states. On the other hand, new regulations of choosing bridging states are given in this paper. The regulations reduce the calculations of judging whether a state is a bridging state or not. The presented recursive algorithm accelerates the speed of joining cycles.

关 键 词：移位寄存器 状态图 桥状态 DE Bruijn序列 

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