| 产生k元de Bruijn序列的一个递归算法 |
| |
| 引用本文： | 朱士信,吴波.产生k元de Bruijn序列的一个递归算法[J].合肥工业大学学报(自然科学版),2005,28(9):1210-1212. |
| |
| 作者姓名： | 朱士信 吴波 |
| |
| 作者单位： | 合肥工业大学,理学院,安徽,合肥,230009;合肥工业大学,理学院,安徽,合肥,230009 |
| |
| 基金项目： | 安徽省自然科学基金资助项目(03042201) |
| |
| 摘 要： | 通过合并纯轮换移位寄存器状态图中的所有圈,给出了生成k元de Bruijn序列的一个递归算法,不再采用“主圈并一个圈”的经典并圈法,而是利用了“主圈并一组共轭圈”的新方法,减少了选择桥状态的次数;同时,给出了新的选择桥状态的规则,简化了判断一个状态是否是桥状态的计算,从而加快了并圈的速度。
|
| 关 键 词： | 移位寄存器 状态图 桥状态 de Bruijn序列 |
| 文章编号： | 1003-5060(2005)09-1210-03 |
| 修稿时间： | 2005年7月4日 |
A recursive algorithm for generating k-ary de Bruijn sequences |
| |
| ZHU Shi-xin,WU Bo.A recursive algorithm for generating k-ary de Bruijn sequences[J].Journal of Hefei University of Technology(Natural Science),2005,28(9):1210-1212. |
| |
| Authors: | ZHU Shi-xin WU Bo |
| |
| Abstract: | 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. |
| |
| Keywords: | shift register state graph bridging state de Bruijn sequence |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
