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

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

通信学报 ›› 2022, Vol. 43 ›› Issue (7): 126-133.doi: 10.11959/j.issn.1000-436x.2022108

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

周琮伟, 胡斌, 关杰

信息工程大学密码工程学院，河南郑州 450001

修回日期:2022-04-15 出版日期:2022-07-25 发布日期:2022-06-01
作者简介:周琮伟（1994- ），男，四川眉山人，信息工程大学博士生，主要研究方向为移位寄存器中的数学理论
胡斌（1972- ），男，河南信阳人，博士，信息工程大学教授、博士生导师，主要研究方向为密码设计与分析
关杰（1974- ），女，河南郑州人，博士，信息工程大学教授、博士生导师，主要研究方向为密码设计与分析
基金资助:
国家自然科学基金资助项目(61572516);国家自然科学基金资助项目(61802437)

Construction de Bruijn sequence based on whole LFSR with 4 cycles

Congwei ZHOU, Bin HU, Jie GUAN

Department of Cryptogram Engineering, Information Engineering University, Zhengzhou 450001, China

Revised:2022-04-15 Online:2022-07-25 Published:2022-06-01
Supported by:
The National Natural Science Foundation of China(61572516);The National Natural Science Foundation of China(61802437)

摘要/Abstract

摘要：

为了提高并圈法的构造效率，拓宽并圈法的应用深度，从圈结构中圈个数的角度，提出了基于全体圈个数为4的LFSR构造de Bruijn序列的方法。基于LFSR的级联特征，确定了一类级联型的反馈移位寄存器的圈结构，并据此给出了圈个数为4的n级LFSR的精确个数，以及基于全体圈个数为4的n级LFSR构造n级de Bruijn序列的全部数目。

关键词: 线性反馈移位寄存器, deBruijn序列, 级联, 圈结构

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

中图分类号:

TN918.6

周琮伟, 胡斌, 关杰. 基于全体圈个数为4的LFSR构造de Bruijn序列的研究[J]. 通信学报, 2022, 43(7): 126-133.

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.

图/表 2

参考文献 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.

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

Construction de Bruijn sequence based on whole LFSR with 4 cycles

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 35

相关文章 13

Metrics

推荐阅读 0

[1]	符小东,李泳成,沈纲祥. 面向弹性光网络的新型光节点升级策略研究[J]. 通信学报, 2018, 39(9): 76-83.
[2]	王春华,蔺海荣,李毅,金杰,夏赞明. 基于单个CDCTA的低压电控调谐电流模式多相位正弦振荡器的设计[J]. 通信学报, 2015, 36(8): 8-12.
[3]	侯成郭,罗柏文,李地. 基于级联随机共振的窄带信号宽带化接收[J]. 通信学报, 2015, 36(7): 138-143.
[4]	吴晓平，王甲生，秦艳琳，叶清. 非线性负载容量模型的小世界网络级联抗毁性研究[J]. 通信学报, 2014, 35(6): 1-7.
[5]	吴晓平,王甲生,秦艳琳,叶清. 非线性负载容量模型的小世界网络级联抗毁性研究[J]. 通信学报, 2014, 35(6): 1-7.
[6]	魏浩1,2，郑宝玉1,3，侯晓赟1,2，朱艳1,3. 基于压缩感知的放大转发双向中继信道估计[J]. 通信学报, 2013, 34(10): 20-182.
[7]	魏浩,郑宝玉,侯晓赟,朱艳. 基于压缩感知的放大转发双向中继信道估计[J]. 通信学报, 2013, 34(10): 174-182.
[8]	杨友福,刘建伟,张其善,修春娣. 基于多符号分组的CPM软输出非相干检测算法[J]. 通信学报, 2012, 33(8): 113-118.
[9]	杨阳,曾光. 序列密码算法RAKAPOSHI的动态移存器构造[J]. 通信学报, 2011, 32(11A): 178-183.
[10]	曾光,杨阳,韩文报,范淑琴. 本原多项式与基于字的线性反馈寄存器[J]. 通信学报, 2009, 30(11A): 111-116.
[11]	刘青格,邵定蓉,李署坚. 从素数码到级联素数码[J]. 通信学报, 2007, 28(4): 123-127.
[12]	王浩畅,赵铁军,郑德权,于浩. 基于元学习策略的分类器融合方法及应用[J]. 通信学报, 2007, 28(10): 7-13.
[13]	李晋,滑翰,华惊字,尤肖虎. 并行级联LDPC码泽码迭代终止准则研究[J]. 通信学报, 2006, 27(4): 95-100.