Scholarlink

<p>A <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(2^n\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mi>n</mi> </msup> </math></EquationSource> </InlineEquation>-periodic binary sequence is a binary de Bruijn sequence of order <i>n</i> if every binary <i>n</i>-tuple occurs exactly once within each period. We put forward new classes of successor rules derived from the pure cycling register (PCR) that generate binary de Bruijn sequences. We define a transitive relation on its cycles, based on their weights. We also extend the choices of conjugate states by using new shift operations. Each class generates a number, exponential in <i>n</i>, of binary de Bruijn sequences. Producing the next bit in each such sequence takes <i>O</i>(<i>n</i>) memory and <i>O</i>(<i>n</i>) time. We explicitly determine the feedback functions of special de Bruijn sequences in this paper.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

New successor rules to efficiently produce exponentially many binary de Bruijn sequences

  • 期刊论文

  • 发表日期：

    2025年6月30日

查看全文
  • Zuling Chang,
  • Martianus Frederic Ezerman,
  • Pinhui Ke,
  • Qiang Wang

摘要

A \(2^n\) 2 n -periodic binary sequence is a binary de Bruijn sequence of order n if every binary n-tuple occurs exactly once within each period. We put forward new classes of successor rules derived from the pure cycling register (PCR) that generate binary de Bruijn sequences. We define a transitive relation on its cycles, based on their weights. We also extend the choices of conjugate states by using new shift operations. Each class generates a number, exponential in n, of binary de Bruijn sequences. Producing the next bit in each such sequence takes O(n) memory and O(n) time. We explicitly determine the feedback functions of special de Bruijn sequences in this paper.