生成de Bruijn序列的加元算法

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (2): 38-41.

生成de Bruijn序列的加元算法

谢深泉

湘潭大学信息工程学院，湖南湘潭 411105

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-01-11 发布日期:2008-01-11
通讯作者: 谢深泉

Algorithm for generating de Bruijn sequences by adding elements

XIE Shen-quan

College of Information and Engineering，Xiangtan University，Xiangtan，Hunan 411105，China

Received:1900-01-01 Revised:1900-01-01 Online:2008-01-11 Published:2008-01-11
Contact: XIE Shen-quan

摘要/Abstract

摘要： 提出一种加元算法，通过对给定的一个m+1元的de Buijn序列添加一元来产生m+2元de Bruijn序列。实现的方法是通过由一个m+1元de Bruijn序列找出它的Look-up表标签，并由该Look-up表标签产生多个m+1元Look-up表标签，然后合成这些Look-up表标签产生一个m+2元Look-up表标签，再由它产生m+2元de Bruijn序列。

关键词: de Bruijn序列, Look-up表, Look-up表标签, 节点链, 加元

Abstract: An algorithm by adding elements is presented in this paper，which is to produce m+2-ary de Bruijn sequences by adding an element to a given m+1-ary de Bruijn sequence.The implementing method is by means of finding the Look-up table labels of m+1-ary de Bruijn sequences from a given de Bruijn sequence and producing a group of m+1-ary Look-up table labels from the obtained m+1-ary Look-up table labels，then obtaining m+2-ary Look-up table labels by composing the group of m+1-ary Look-up table labels and generating m+2-ary de Bruijn sequences by using the relative Look-up table.

Key words: de Bruijn sequence, Look-up table, Look-up table label, node chain, adding an element

谢深泉. 生成de Bruijn序列的加元算法[J]. 计算机工程与应用, 2008, 44(2): 38-41.

XIE Shen-quan. Algorithm for generating de Bruijn sequences by adding elements[J]. Computer Engineering and Applications, 2008, 44(2): 38-41.

[1]	傅赛虹,游林. 修正de Bruijn序列的线性复杂度研究[J]. 计算机工程与应用, 2009, 45(15): 58-60.
[2]	谢深泉^1,2. de Bruijn序列查寻表标签的k位修正构造法[J]. 计算机工程与应用, 2008, 44(33): 37-40.
[3]	谢深泉. de Bruijn序列查寻表标签的定值构造法[J]. 计算机工程与应用, 2008, 44(19): 16-19.
[4]	谢深泉. de Bruijn序列间的映射及降级算法[J]. 计算机工程与应用, 2007, 43(28): 21-24.
[5]	谢深泉. de Bruijn序列间的映射及升级算法[J]. 计算机工程与应用, 2007, 43(22): 12-14.