基于全体圈个数为4的LFSR构造de Bruijn序列的研究

doi:10.11959/j.issn.1000-436x.2022108

Abstract

Abstract:

In order to improve the construction efficiency and widen the application depth of cycle-joining method, from the view of the number of cycles in the cycle structure, a method for constructing de Bruijn sequence based on whole LFSR with 4 cycles was proposed.Based on the characteristic of cascade connection of LFSR, the cycle structure of a class of cascaded feedback shift registers was determined.Accordingly, the exact number of whole n-order LFSR with 4 cycles was given, and the total number of n-order de Bruijn sequences constructed from whole n-order LFSR with 4 cycles as well.

Key words: linear feedback shift register, de Bruijn sequence, cascade connection, cycle structure

CLC Number:

TN918.6

Congwei ZHOU, Bin HU, Jie GUAN. Construction de Bruijn sequence based on whole LFSR with 4 cycles[J]. Journal on Communications, 2022, 43(7): 126-133.

Figures/Tables 2

References 35

[1]	丁存生, 肖国镇 . 流密码学及其应用[M]. 北京: 国防工业出版社, 1994.
	DING C S , XIAO G Z . Stream cipher and its applications[M]. Beijing: National Defense Industry Press, 1994.
[2]	SIEGENTHALER T . Decrypting a class of stream ciphers using ciphertext only[J]. IEEE Transactions on Computers, 2006,34(1): 81-85.
[3]	RUEPPEL R A . Analysis and design of stream ciphers[M]. Berlin: Springer, 1986.
[4]	COURTOIS N T , MEIER W . Algebraic attacks on stream ciphers with linear feedback[C]// 2003 International Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT). Berlin:Springer, 2003: 345-359.
[5]	CHAN A H , GAMES R A , KEY E L . On the complexities of de Bruijn sequences[J]. Journal of Combinatorial Theory,Series A, 1982,33(3): 233-246.
[6]	姜春晓, 王佳蔚 . 高动态卫星 DSSS 信号 Turbo 迭代捕获算法[J]. 通信学报, 2021,42(8): 15-24.
	JIANG C X , WANG J W . Turbo iterative acquisition algorithm for satellite high-mobility DSSS signal[J]. Journal on Communications, 2021,42(8): 15-24.
[7]	许饶琪, 彭晓涛, 秦世耀 ,等. 基于M序列的双馈风机变流器参数辨识方法研究[J]. 电网技术, 2022,46(2): 578-586.
	XU R Q , PENG X T , QIN S Y ,et al. Parameter identification of doubly-fed induction generator converter based on M-sequence[J]. Power System Technology, 2022,46(2): 578-586.
[8]	曾理, 成杰峰, 孟金涛 ,等. 使用分布式de Bruijn图遍历基因拼接并行构建和化简[J]. 软件学报, 2013,24(S2): 140-149.
	CENG L , CHENG J F , MENG J T ,et al. Parallelized de Bruijn graph construction and simplification for genome assembly[J]. Journal of Software, 2013,24(S2): 140-149.
[9]	FREDRICKSEN H . A class of nonlinear de Bruijn cycles[J]. Journal of Combinatorial Theory,Series A, 1975,19(2): 192-199.
[10]	ETZION T , LEMPEL A . Algorithms for the generation of full-length shift- register sequences[J]. IEEE Transactions on Information Theory, 1984,30(3): 480-484.
[11]	ANNEXSTEIN F S . Generating de Bruijn sequences:an efficient implementation[J]. IEEE Transactions on Computers, 1997,46(2): 198-200.
[12]	FREDRICKSEN H . A survey of full length nonlinear shift register cycle algorithms[J]. SIAM Review, 1982,24(2): 195-221.
[13]	JANSEN C J A , FRANX W G , BOEKEE D E . An efficient algorithm for the generation of de Bruijn cycles[J]. IEEE Transactions on Information Theory, 1991,37(5): 1475-1478.
[14]	YANG J H , DAI Z D . Construction of m-ary de Bruijn sequences[C]// 1992 International Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT). Berlin:Springer, 1992: 357-363.
[15]	HAUGE E R , MYKKELTVEIT J . On the classification of de Bruijn sequences[J]. Discrete Mathematics, 1996,148(1/2/3): 65-83.
[16]	MYKKELTVEIT J , SZMIDT J . On cross joining de Bruijn sequences[J]. Contemporary Mathematics, 2015,632: 333-344.
[17]	GOLOMB W . Shift register sequences[M]. Los Angeles: Aegean Park Press, 1981.
[18]	关杰, 周琮伟 . M序列反馈函数多项式表示的快速构造方法[J]. 通信学报, 2018,39(4): 84-90.
	GUAN J , ZHOU C W . Method of fast construction of M-sequence feedback functions with polynomial representation[J]. Journal on Communications, 2018,39(4): 84-90.
[19]	高杨, 刘松华, 王中孝 . 一种基于“编织法”的de Bruijn序列构造算法[J]. 电子学报, 2018,46(1): 48-54.
	GAO Y , LIU S H , WANG Z X . A de Bruijn sequence construction algorithm based on ‘interleaving’ construction method[J]. Acta Electronica Sinica, 2018,46(1): 48-54.
[20]	LEMPEL A . On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers[J]. IEEE Transactions on Computers, 1970,C-19(12): 1204-1209.
[21]	SIU M K , TONG P . Generation of some de Bruijn sequences[J]. Discrete Mathematics, 1980,31(1): 97-100.
[22]	CHANG Z L , GONG G , WANG Q . Cycle structures of a class of cascaded FSRs[J]. IEEE Transactions on Information Theory, 2020,66(6): 3766-3774.
[23]	LI C Y , ZENG X Y , HELLESETH T ,et al. The properties of a class of linear FSRs and their applications to the construction of nonlinear FSRs[J]. IEEE Transactions on Information Theory, 2014,60(5): 3052-3061.
[24]	LI C Y , ZENG X Y , LI C L ,et al. A class of de Bruijn sequences[J]. IEEE Transactions on Information Theory, 2014,60(12): 7955-7969.
[25]	LI C Y , ZENG X Y , LI C L ,et al. Construction of de Bruijn sequences from LFSRs with reducible characteristic polynomials[J]. IEEE Transactions on Information Theory, 2016,62(1): 610-624.
[26]	LI M , JIANG Y P , LIN D D . The adjacency graphs of some feedback shift registers[J]. Designs,Codes and Cryptography, 2017,82(3): 695-713.
[27]	LI M , LIN D D . The adjacency graphs of LFSRs with primitive-like characteristic polynomials[J]. IEEE Transactions on Information Theory, 2017,63(2): 1325-1335.
[28]	CHANG Z L , EZERMAN M F , LING S ,et al. Construction of de Bruijn sequences from product of two irreducible polynomials[J]. Cryptography and Communications, 2018,10(2): 251-275.
[29]	DONG Y J , TIAN T , QI W F ,et al. The adjacency graphs of FSRs with a class of affine characteristic functions[J]. Finite Fields and Their Applications, 2018,53: 21-35.
[30]	DONG J W , PEI D Y . Construction for de Bruijn sequences with large stage[J]. Designs,Codes and Cryptography, 2017,85(2): 343-358.
[31]	董军武, 裴定一 . 一类不可约多项式的邻接矩阵[J]. 数学学报(中文版), 2018,61(5): 843-856.
	DONG J W , PEI D Y . The adjacency matrix of some class of irreducible polynomials[J]. Acta Mathematica Sinica (Chinese Series), 2018,61(5): 843-856.
[32]	万哲先, 代宗铎, 刘木兰 ,等. 非线性反馈移位寄存器[M]. 北京: 科学出版社, 1978.
	WAN Z X , DAI Z D , LIU M L ,et al. Non-linear feedback shift register[M]. Beijing: Science Press, 1978.
[33]	ZIERLER N . Linear recurring sequences[J]. Journal of the Society for Industrial and Applied Mathematics, 1959,7(1): 31-48.
[34]	MYKKELTVEIT J , SIU M K , TONG P . On the cycle structure of some nonlinear shift register sequences[J]. Information and Control, 1979,43(2): 202-215.
[35]	LIDL R , NIEDERREITER H . Finite fields:encyclopedia of mathematics and its applications[J]. Computers ＆ Mathematics with Applications, 1997,7:136.

Metrics

Recommended 0

No Suggested Reading articles found!

Construction de Bruijn sequence based on whole LFSR with 4 cycles

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 35

Related Articles 1

Metrics

Recommended 0