电子学报 ›› 2018, Vol. 46 ›› Issue (1): 48-54.DOI: 10.3969/j.issn.0372-2112.2018.01.007

• 学术论文 • 上一篇    下一篇

一种基于“编织法”的de Bruijn序列构造算法

高杨, 刘松华, 王中孝   

  1. 洛阳外国语学院, 河南洛阳 471003
  • 收稿日期:2016-07-13 修回日期:2017-01-08 出版日期:2018-01-25
    • 通讯作者:
    • 高杨
    • 作者简介:
    • 刘松华,男,1979年生于吉林安图,现为洛阳外国语学院研究生,主要研究方向为密码学.E-mail:liusonghua0519@163.com
    • 基金资助:
    • 国家自然科学基金 (No.61502524)

A de Bruijn Sequence Construction Algorithm Based on ‘Interleaving’ Construction Method

GAO Yang, LIU Song-hua, WANG Zhong-xiao   

  1. Luoyang University of Foreign Languages, Luoyang, Henan 471003, China
  • Received:2016-07-13 Revised:2017-01-08 Online:2018-01-25 Published:2018-01-25

摘要: 文章首先给出n级de Bruijn序列通过"编织法"所产生序列的周期,并证明其中所有2n长状态两两不同.之后,论证出平移等价意义下一条n级de Bruijn序列仅能编织出两条序列.最后针对每一条序列,补全其缺失的四个2n长状态即可构造出2n级de Bruijn序列.由于增添比特的方式有两种,因此由一条n级de Bruijn序列可构造出四条2n级de Bruijn序列.

关键词: 序列密码, de Bruijn序列, 编织法, 平移等价

Abstract: Firstly, this paper determines the period of ‘Interleaving’ sequences from de Bruijn sequences of n-stage and proves all 2n-tuple states are different from each other. Secondly, in the view of shift equivalence, the paper demonstrates that one can only construct two sequences from de Bruijn sequences of n-stage. For each one, the completion of its missing four 2n-tuple states can construct de Bruijn sequences of 2n-stage. Since there are two different ways to complete the missing bits, we can finally get four de Bruijn sequences of 2n-stage from one de Bruijn sequence of n-stage.

Key words: stream cipher, de Bruijn sequence, interleaving method, shift equivalence

中图分类号: