Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (2): 38-41.

• 学术探讨 • Previous Articles     Next Articles

Algorithm for generating de Bruijn sequences by adding elements

XIE Shen-quan   

  1. 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

生成de Bruijn序列的加元算法

谢深泉   

  1. 湘潭大学 信息工程学院,湖南 湘潭 411105
  • 通讯作者: 谢深泉

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

摘要: 提出一种加元算法,通过对给定的一个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表标签, 节点链, 加元