| 产生 M 序列的一个递推算法 |
| |
| 引用本文： | 章照止(),罗乔林(). 产生 M 序列的一个递推算法[J]. 系统科学与数学, 1987, 7(4): 335-343 |
| |
| 作者姓名： | 章照止() 罗乔林() |
| |
| 作者单位： | 中国科学院系统科学研究所(章照止)，中国科学院系统科学研究所(罗乔林) |
| |
| 摘 要： | §1.引言M 序列又称 de Bruijn 序列,是一类具有最长周期的非线性移位寄存器序列。本文研究产生 M 序列的算法。早在70年代万哲先等对构造 M 序列的方法已有系统的研究。此后有一系列的文章研究 M 序列的构造问题。最近 Fredricksen 对这方面的工作给出了一个很好的综述。产生 M 序列的一个常用方法是先由一个较简单的移位寄存器产生许多短圈,再用并圈法将这些短圈合并起来构成 M 序列。如在[1,6]中就已给出过一些将 n 级纯轮换移位寄存器(简记为 PCK_n)和 n 级补轮换移位寄存器(简记为 CCR_n)产生的圈合并为 M 序列的方法。与[1—7]不同,Fredricksen 给出一个将 PCR_n 产生的圈合并为 M 序列的递推算法。最近 Etzion 和 Lempe 在 Fredricksen 算法的基础
|
A RECURSIVE ALGORITHM FOR THE GENERATION OF DE BRUIJN SEQUENCES |
| |
| ZHANG ZHAO-ZHI,LUO QIAO-LIN. A RECURSIVE ALGORITHM FOR THE GENERATION OF DE BRUIJN SEQUENCES[J]. Journal of Systems Science and Mathematical Sciences, 1987, 7(4): 335-343 |
| |
| Authors: | ZHANG ZHAO-ZHI LUO QIAO-LIN |
| |
| Affiliation: | (1)Institute of Systems Science,Academia Sinica;(2)Institute of Systems Science,Academia Sinica |
| |
| Abstract: | A recursive algorithm is presented for the generation of de Bruijn sequences.The algo-rithm is based on a method of joining the CCR_n cycles together to form a full cycle.It generates2~(g(n))de Bruijin sequences of span n,using about 3n+g(n) bits of strorage for each sequence.Thetime required for producing the next bit from the last n bits is close to 2n units. |
| |
| Keywords: | |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《系统科学与数学》浏览原始摘要信息 |
|
点击此处可从《系统科学与数学》下载全文 |
