生成de Bruijn序列的降级算法  

Algorithms for Generating de Bruijn Sequences by Reducing a Stage

作　　者：谢深泉[1] 

机构地区：[1]湘潭大学信息工程学院,湖南湘潭411105

出　　处：《小型微型计算机系统》2009年第1期148-151,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60673193)资助;湖南省重点学科建设项目资助;湖南省教育厅重点项目(07A067)资助

摘　　要：讨论一种由n级de Bruijn序列产生n-1级de Bruijn序列的降级算法.方法是由n级de Bruijn序列找出其n级查寻表标签;接着通过删除该查寻表标签的相应节点的首符号,验证n-2级节点链的合法性,发现并删除节点链中的套结,实现查寻表标签的降级,最终成为n-1级查寻表标签;在此基础上建立其相应的n-1级查寻表,从而求得n-1级de Bruijn序列.文章最后给出关于算法的注解.An algorithm for generating de Bruijn sequences by reducing a stage is discussed. The method is finding the n-1 stage Look-up table labels of n-1 stage de Bruijn sequences from an n stage de Bruijn sequence; obtaining the n-1 stage Look-up table labels by deleting the first symbol of corresponding nodes, verifying the validity of the n-2 stage node chain, finding and deleting knots on the node chains; then constructing the relative n-1 stage Look-up table and computing n-1 stage de Bruijn sequences with this Look-up table. Finally, some comments are given.

关 键 词：DE Bruijn序列 查寻表 查寻表标签 节点链 降级 

分 类 号：TP332.11[自动化与计算机技术—计算机系统结构] O141.1[自动化与计算机技术—计算机科学与技术]