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

Abstract

Abstract: The method to construct de Bruijn sequences by join ing all the cycles into one cycle in the cycle structure of linear feedback shift register (LFSR) is called cyclecycle-joining method, which is currently an important and mainstream mainstream. In order to improve the construction efficiency and widen the application depth of cyclecycle-joining method, from the view of the number of c ycle s in the c ycle structurestructure, a method for constructing de Bruijn sequence based on whowhole LFSRLFSRs with 4 cycleycles was proposed for the first time time. Based on the characteristic o f cascade connection of LFSRs, the cycle structure of a class of cascaded feedback shift registers was determineddetermined. AccordinglyAccordingly, the exact number of whole n-order LFSRs with 4 cycles is given, and the total number of n-order de Bruijn sequence s constructed from whole n-order LFSRs with 4 cy-cles as well well.

ZHOU Cong wei, HU Bin, GUAN Jie. Construction of De Bruijn Sequences from Whole LFSRs with 4 Cycles[J]. Journal on Communications.

References

[1] 丁存生, 肖国镇. 流密码学及其应用[M]. 北京: 国防工业出版社,1994.DING C S, XIAO G Z. Stream Cipher and Its Applications[M]. CHN:National Defense Industry Press, Beijing, 1994.
[2] SIEGENTHALER T. Decrypting a Class of Stream Ciphers Using Ciphertext Only[J]. IEEE Transactions on Computers, 2006, C-34(1):81-85.
[3] RUEPPEL R A. Analysis and Design of Stream Ciphers[M]. USA:Springer-Verlag New York, Inc., New York, 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).Springer, Berlin, Heidelberg, 2003: 345-359.
[5] CHAN H A, 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(02): 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(02): 578-586.
[8] 曾理, 成杰峰, 孟金涛, 等. 使用分布式De Bruijn 图遍历基因拼接并行构建和化简. 软件学报, 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 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 In-
《通信学报》第 X 期 ·XX·formati
formation Theory, 1991,heory, 1991, 37(5): 14737(5): 1475-14781478.
[14] YANG JYANG J H, DAI Z DDAI Z D. Construction of mConstruction of m-ary de Bruiary de Bruijn sequenc-jn sequenc-es[C]//es[C]//1992 1992 International Workshop on tInternational Workshop on the Theory and Application he Theory and Application of Cryptographic Techof Cryptographic Techniquesniques (EUROCRYPTEUROCRYPT). Springer, Springer, Berlin, Berlin, Heidelberg, 1992: 357Heidelberg, 1992: 357-363 .
[15] HAU GE GE R, MYK, MYKKE LT VEITVEIT J. On tOn the classifihe classification of de Brucation of de Bruijn sequences[J]sequences[J]. Discrete Mathematics, Discrete Mathematics, 1996, 148(11996, 148(1-3):3): 65 -83 .
[16] MYKKELTVEITMYKKELTVEIT J, SZMIDT J., SZMIDT J. On cross joining n cross joining de Bruijn sequenc-e Bruijn sequenc-es[J]es[J]. ContempContemporary Mathematics,orary Mathematics, 2015, 632:2015, 632: 333 -344344。
[17] GOLOMB GOLOMB W. Shift Shift register egister sequences[M]equences[M]. USA : Aegean ParAegean Park Press,k Press, La guna Hills, guna Hills, 19811981.
[18] 关杰 , 周琮伟周琮伟. M. M序列反馈函数多项式表示的快速构造方法序列反馈函数多项式表示的快速构造方法[J]. [J]. 通信学报通信学报, 2018, , 2018, 39(4): 8439(4): 84-90.90.
GUAN
GUAN J, ZHOUZHOU C WC W. Method of . Method of fast construction of Mfast construction of M-sequence sequence feedback functions with polynomial representation[J]. Journal on feedback functions with polynomial representation[J]. Journal on Communications, 2018, 39(4)Communications, 2018, 39(4): 84 -90.
[19] 高杨 , 刘松华刘松华, 王中孝王中孝. 一种基于一种基于“编织法编织法”的 de Bruijnde Bruijn序列构造列构造算法 [J]. [J]. 电子学报电子学报, 2018, 46(1): 48, 2018, 46(1): 48-54.54.
GAO Y
GAO Y, LI, LIU SU S H, WANG Z, WANG Z X. A de Bruijn Sequence Constr. A de Bruijn Sequence Construction uction Algorithm Based on ‘Interleaving’ Construction Method[J]. Acta Algorithm Based on ‘Interleaving’ Construction Method[J]. Acta Electronica Sinica, 2018, 46(1): 48Electronica Sinica, 2018, 46(1): 48-54.54.
[20] LEMPEL ALEMPEL A. On aOn a homomorphism of the domomorphism of the de Brue Bruijn ijn graph and itraph and its applications to the pplications to the design of esign of feedback eedback shift hift registers[J]egisters[J]. IEEE Com-IEEE Com-puter Soputer Society, 1970ciety, 1970, C-19 19 (12):(12): 12041204-12091209.
[21] SI U KU K, TONG TONG P. Generation of some de Bruijn seGeneration of some de Bruijn sequences[J]quences[J]. Dis-Dis-crete Mathematics, 1980, 31(1):crete Mathematics, 1980, 31(1): 97 -100100.
[22] CHANG Z LANG Z L, GONG GONG G, WANGWANG Q. Cycle Cycle structurestructures of a of a class of lass of cascaded FSRs[J]ascaded FSRs[J]. IEEE Transactions on Information Theory, 2IEEE Transactions on Information Theory, 202 0, 0, 66(6):66(6): 37 66 -3773774.
[23] LI C YC Y, ZENG X Y, HELLESETHZENG X Y, HELLESETH T, et alet al. The properties of a clThe properties of a class ass of lineaof linear FSRs and their applications to the constrr FSRs and their applications to the construc tion tion of nonlinear of nonlinear FSRs [J][J]. IEEE TransactiIEEE Transactions on Information Theoryons on Information Theory, 2014, , 2014, 60(60(5): 30523052-30613061.
[24] LI C YC Y, ZENG X Y,ZENG X Y, LI C L, et alet al. A claA class of ss of de Bruijn seqde Bruijn sequencesuences[J][J]. IEEE Transactions on Information TheoryIEEE Transactions on Information Theory, 2014,, 2014, 60(160(12) : 7955 -79697969.
[25] LI C YC Y, ZENG X Y,ZENG X Y, LI C L, et al. Construction of de BruConstruction of de Bruijn sequijn sequenc-enc-es fres from LFSRs withom LFSRs with reducible characteristic polynomialsreducible characteristic polynomials[J][J]. IEEE IEEE Transactions on ITransactions on Information Tnformation Theoryheory, 2016, 2016, 62(1)62(1): 610610-624 .
[26] LI MLI M, JIANG IANG Y P, LIN D LIN D D. The adjacency The adjacency graphs of sographs of some feedback me feedback shift registersshift registers[J][J]. Designs, CoDesigns, Code s and Cryptos and Cryptogr aphyaphy, 2017, 2017, 82 (3)(3): 695695-713 .
[27] LI MLI M, LIN D DLIN D D. The The adjacency djacency graphs of LFSRs raphs of LFSRs with ith primitiverimitive-like ike characterisharacteristic tic polynomiolynomials[J]als[J]. IEEE Transactions on InformIEEE Transactions on Information ation Theory, 2017, 63(2)Theory, 2017, 63(2): 1325 -13 35 .
[28] CHANG Z CHANG Z L, EZ ERMAN ERMAN M F,M F, LING S, LING S, et alet al. ConstructionConstruction of de f de Bruijn Bruijn sequences from quences from product of roduct of two wo irreducible rreducible polynomials[J]olynomials[J]. Cry ptography and Communications, 2016, 10(3):ptography and Communications, 2016, 10(3): 1-25 .
[29] DONGDONG Y JY J, TIANTIAN T, QI W F,, QI W F, et alet al. The adjacency graphs of FSRs The adjacency graphs of FSRs with a clawith a class ofss of affine charaffine characteristacteristic functions[J]ic functions[J]. Finite Fields and Finite Fields and Th eir Applicatioeir Applications, 2018, 53(SEPns, 2018, 53(SEP.): 21 -35 .
[30] DONG J W, PEI D Y. DONG J W, PEI D Y. Construction for de BrConstruction for de Bruijn sequences with uijn sequences with large stage[J]large stage[J]. Designs, CodDesigns, Codes andes and CryptographyCryptography, 2017, 85(2): , 2017, 85(2): 343343-358 .
[31] 董军武 , 裴定一 . 一类不可约多项式的邻接矩阵一类不可约多项式的邻接矩阵[J] . 数学学报数学学报(中文版 ), 2018, 61(05): 8432018, 61(05): 843-856 .
DONG J W, PEI D Y
DONG J W, PEI D Y. Th e adjacency djacency matrix of trix of some ome class of lass of irre - duciducible ble polynomials.olynomials. Acta Mathematica Sinica, Chinese SeriesActa Mathematica Sinica, Chinese Series, 2018, 2018, 61(5): 84361(5): 843-856856.
[32] 万哲先 , 代宗铎 , 刘木兰, 等. 非线性反馈移位寄存器非线性反馈移位寄存器[M] . 科学出版社 , 北京 , 1978, 1978.
WAN Z X, DAI Z
WAN Z X, DAI Z D, LIU M LD, LIU M L, et al. et al. NonNon-linear feedback shilinear feedback shift regft reg- ister[ister[M]. CHN: HN: Scie nce nce Press,Press, 1978.1978.
[33] ZIERLER ZIERLER N. Linear Linear recurring ecurring sequences[J]equences[J]. Journal of thJournal of the Society e Society for Industrial for Industrial andand Applied MathematiApplied Mathematics, 1959cs, 1959, 7(1):, 7(1): 31 -48 .
[34] MYKKELTVMYKKELTVEITEIT J, S, SIU M KM K, T, TONGONG P. On the cycle structure of . On the cycle structure of some nonlinesome nonlinear shift register sequences[J]. ar shift register sequences[J]. InformationInformation and ControlControl, 1979, 43(2):1979, 43(2): 202 -215.215.
[35] LIDLLIDL R, NIEDERREITER NIEDERREITER H. Finite fields, in encyclopedia of Finite fields, in encyclopedia of mathematics and itsmathematics and its applicapplications[Mations[M]. USA: USA: Ad dison Wesley, MA, dison Wesley, MA, 19831983.

Metrics

Recommended 0

No Suggested Reading articles found!

Construction of De Bruijn Sequences from Whole LFSRs with 4 Cycles

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Metrics

Recommended 0

[1]	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]	Xiaodong FU,Yongcheng LI,Gangxiang SHEN. Novel node upgradation strategy for migration to elastic optical networks [J]. Journal on Communications, 2018, 39(9): 76-83.
[3]	Chun-hua WANG,Hai-rong LIN,Yi LI,Jie JIN,Zan-ming XIA. Design of low-voltage electronically tunable current-mode multiphase sinusoidal oscillator based on single CDCTA [J]. Journal on Communications, 2015, 36(8): 8-12.
[4]	Cheng-guo HOU,Bo-wen LUO,Di LI. Broadband receiver of narrowband signal based on the cascaded stochastic resonance [J]. Journal on Communications, 2015, 36(7): 138-143.
[5]	Xiao-ping WU,Jia-sheng WANG,Yan-lin QIN,Qing YE. Invulnerability of small-world network against cascading failure based on nonlinear load-capacity model [J]. Journal on Communications, 2014, 35(6): 1-7.
[6]	. Invulnerability of small-world network against cascading failure based on nonlinear load-capacity model [J]. Journal on Communications, 2014, 35(6): 1-7.
[7]	. Channel estimation based on compressive sensing in two-way amplify-and-forward relay channel [J]. Journal on Communications, 2013, 34(10): 20-182.
[8]	Hao WEI,Bao-yu ZHENG,Xiao-yun HOU,Yan ZHU. Channel estimation based on compressive sensing in two-way amplify-and-forward relay channel [J]. Journal on Communications, 2013, 34(10): 174-182.
[9]	You-fu YANG,Jian-wei LIU,Qi-shan ZHANG,Chun-di XIU. Multiple symbol soft-output non-coherent detection of serial concatenated CPM [J]. Journal on Communications, 2012, 33(8): 113-118.
[10]	Yang YANG,Guang ZENG. Construction of dynamic linear feedback shift registers in RAKAPOSHI stream cipher [J]. Journal on Communications, 2011, 32(11A): 178-183.
[11]	Guang ZENG,Yang YANG,Wen-bao HAN,Shu-qin FAN. Primitive polynomials and word oriented linear feedback shift registers [J]. Journal on Communications, 2009, 30(11A): 111-116.
[12]	Qing-ge LIU,Ding-rong SHAO,Shu-jian LI. From prime codes to concatenated prime codes [J]. Journal on Communications, 2007, 28(4): 123-127.
[13]	Hao-chang WANG,Tie-jun ZHAO,De-quan ZHENG,Hao YU. Meta-learning based classifier ensemble strategy and its application [J]. Journal on Communications, 2007, 28(10): 7-13.
[14]	Jin LI,Han HUA,Jing-yu HUA,Xiao-hu YOU. Analysis of stop criterions in the decoder of parallel concatenated LDPC codes [J]. Journal on Communications, 2006, 27(4): 95-100.