Research on linear complexities of modified de Bruijn sequences

doi:10.3778/j.issn.1002-8331.2009.15.017

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (15): 58-60.DOI: 10.3778/j.issn.1002-8331.2009.15.017

• 研究、探讨 • Previous Articles Next Articles

Research on linear complexities of modified de Bruijn sequences

FU Sai-hong,YOU lin

Department of Telecommunication Engineering，Hangzhou Dianzi University，Hangzhou 310018，China

Received:2008-03-31 Revised:2008-06-16 Online:2009-05-21 Published:2009-05-21
Contact: FU Sai-hong

修正de Bruijn序列的线性复杂度研究

傅赛虹,游林

杭州电子科技大学通信工程学院，杭州 310018

通讯作者: 傅赛虹

Abstract

Abstract: Ordern de Bruijn-0/1 sequences，with the period of 2ⁿ-1，are created by removing a single zero from the all-zero state（denoted de Bruijn-0） or a single one from the all-one state（denoted de Bruijn-1） in period 2ⁿ de Bruijn sequences.The complexities properties of de Bruijn-0/1 sequences are studied.Some theorems are given and proved on the linear complexities of de Bruijn-0/1 sequences and detail data are presented for 4≤n≤6.

Key words: de Bruijn sequences, feedback shift register, linear complexity

摘要： n级de Bruijn-0/1序列，就是从de Bruijn序列2ⁿ个状态中去除一个全0状态（记为de Bruijn-0）或全1状态（记为de Bruijn-1）而得到的周期为2ⁿ-1的序列。研究了de Bruijn-0和de Bruijn-1（记为de Bruijn-0/1）序列的线性复杂度特性，提出了相关的定理并给出了证明，同时给出了4~6级de Bruijn-0/1序列线性复杂度的统计数据。

关键词: de Bruijn序列, 反馈移位寄存器, 线性复杂度

FU Sai-hong,YOU lin. Research on linear complexities of modified de Bruijn sequences[J]. Computer Engineering and Applications, 2009, 45(15): 58-60.

傅赛虹,游林. 修正de Bruijn序列的线性复杂度研究[J]. 计算机工程与应用, 2009, 45(15): 58-60.

[1]	HAN Rui, ZHANG Xuefeng. Pseudo-random sequence generating method based on high dimensional cat map [J]. Computer Engineering and Applications, 2016, 52(10): 91-99.
[2]	WANG Jinling， ZOU Huixian. Self-shrinking sequence with modular addition on [m-]sequence [J]. Computer Engineering and Applications, 2015, 51(19): 110-113.
[3]	GAO Shujing. Hash function based on multiple input signature analysis registers [J]. Computer Engineering and Applications, 2013, 49(21): 95-97.
[4]	MA Lingyong¹，WEI Shimin². Fast algorithm for determining k-error linear complexity profile of special period sequence [J]. Computer Engineering and Applications, 2011, 47(5): 80-82.
[5]	ZHOU Jianqin1，2，SHANGGUAN Cheng2，ZHAO Zemao1. Tight error linear complexity of periodic binary sequences [J]. Computer Engineering and Applications, 2011, 47(10): 49-53.
[6]	ZHANG Xue-feng^1，2，FAN Jiu-lun¹. Pseudo-random sequence generating method based on chaotic systems [J]. Computer Engineering and Applications, 2010, 46(29): 80-82.
[7]	WANG Jin-ling，CHEN Ya-hua，LAN Juan-li. New model and studying of self-shrinking sequence developed on GF（3） [J]. Computer Engineering and Applications, 2009, 45(35): 114-119.
[8]	DUANMU Qing-feng¹，WANG Yan-bo¹，ZHANG Kai-ze¹，WANG Xi² . Blind signature scheme based on GH-PKC [J]. Computer Engineering and Applications, 2009, 45(21): 71-73.
[9]	LIANG Wei¹,XU Jian-bo¹,TANG Ming-dong^1,2,LIU Hui-ya¹. Improved LFSR cryptographic algorithm and FPGA implementation [J]. Computer Engineering and Applications, 2009, 45(16): 80-82.

Research on linear complexities of modified de Bruijn sequences

修正de Bruijn序列的线性复杂度研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 9

Recommended Articles

Metrics