<p>A binary de Bruijn sequence of order <i>n</i> can be generated by an <i>n</i>-stage nonlinear feedback shift register with the feedback function of the form <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(x_0\oplus g(x_1,x_2,\ldots ,x_{n-1})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>x</mi> <mn>0</mn> </msub> <mo>⊕</mo> <mi>g</mi> <mrow> <mo stretchy="false">(</mo> <msub> <mi>x</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>x</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>x</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. In this paper, based on the generating function theory for the weights of de Bruijn sequences proposed by Coppersmith et al., it is shown that the expectation and the variance of the weight of <i>g</i> are <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(2^{n-2}+\frac{1}{2} e_{n,1}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <msub> <mi>e</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>1</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(2^{n-3}-\frac{1}{4} e_{n,1}-\frac{1}{2} e_{n,2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>3</mn> </mrow> </msup> <mo>-</mo> <mfrac> <mn>1</mn> <mn>4</mn> </mfrac> <msub> <mi>e</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>1</mn> </mrow> </msub> <mo>-</mo> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> <msub> <mi>e</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>2</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>, respectively, where <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(e_{n,1}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>e</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(e_{n,2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>e</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> denote the number of cycles of the <i>n</i>-stage pure circulating register with weight 1 and 2, respectively. The expectation and the variance are close to <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(2^{n-2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </msup> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(2^{n-3}\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mrow> <mi>n</mi> <mo>-</mo> <mn>3</mn> </mrow> </msup> </math></EquationSource> </InlineEquation> when <i>n</i> is large enough, respectively, which shows that the weight distribution of <i>g</i> is very dispersed.</p>

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

The expectation and the variance of the weights of de Bruijn sequences

  • Xiao-Xin Zhao,
  • Zhong-Xiao Wang,
  • Deng Tang,
  • Qun-Xiong Zheng

摘要

A binary de Bruijn sequence of order n can be generated by an n-stage nonlinear feedback shift register with the feedback function of the form \(x_0\oplus g(x_1,x_2,\ldots ,x_{n-1})\) x 0 g ( x 1 , x 2 , , x n - 1 ) . In this paper, based on the generating function theory for the weights of de Bruijn sequences proposed by Coppersmith et al., it is shown that the expectation and the variance of the weight of g are \(2^{n-2}+\frac{1}{2} e_{n,1}\) 2 n - 2 + 1 2 e n , 1 and \(2^{n-3}-\frac{1}{4} e_{n,1}-\frac{1}{2} e_{n,2}\) 2 n - 3 - 1 4 e n , 1 - 1 2 e n , 2 , respectively, where \(e_{n,1}\) e n , 1 and \(e_{n,2}\) e n , 2 denote the number of cycles of the n-stage pure circulating register with weight 1 and 2, respectively. The expectation and the variance are close to \(2^{n-2}\) 2 n - 2 and \(2^{n-3}\) 2 n - 3 when n is large enough, respectively, which shows that the weight distribution of g is very dispersed.