产生二进制德·布鲁因序列的两个算法

TWO ALGORITHMS FOR THE GENERATION OF BINARY DE BRUIJIN SEQUENCES

Huang首次利用n元组相邻位的相异数为索引,生成德·布鲁因序列.由前几位产生下一位需4n 位存贮单元,4n 个时间单元.本文,首先改进Huang 的算法,使产生一位需4n 位存贮单元,2n 个时间单元;然后给出一个利用n 元组相异数为索引,生成德·布鲁因序列的新算法,由前n 位产生下一位需4n 位存贮单元,n 个时间单元.新算法与原算法同样具备可从任意n 元组开始计算的特点.

Huang first proposes an algorithm which uses the adjacent bit differences of the n tuplesas index to produce Binary de Bruijin sequences.It takes 4n bits of storage arid 4n units oftime to produce the next bit from the last n bits.In this paper,the original algorithm byHuang is first improved to one which takes 4n bits of storage and 2n units of time to producea bit.Then a new algorithm also using the adjacent bit differences of the n tuples as index isproposed,which takes 4n bits of storage and n units of time to produce the next bit from thelast n bits.The new algorithm has the same characteristic that can begin with any n tuple asthe original one.