• DocumentCode
    3202644
  • Title

    Cumulative distribution function for order 7 de Bruijn weight classes

  • Author

    Mayhew, Gregory L.

  • Author_Institution
    Dept. of Electr. & Syst. Eng., Washington Univ. St. Louis, St. Louis, MO
  • fYear
    2009
  • fDate
    7-14 March 2009
  • Firstpage
    1
  • Lastpage
    9
  • Abstract
    Order n de Bruijn sequences are the period 2n binary sequences from n-stage feedback shift registers. The de Bruijn sequences have good randomness and complexity properties. The quantity of de Bruijn sequences in a weight class of the order n generating functions is an unsolved NP complete problem. Weight class distributions for small n have been obtained by exhaustive searches. This paper uses cumulative distribution function to obtain a high resolution projection of the quantity of de Bruijn sequences in each order 7 weight class. The weight class probability mass function is a shifted Binomial probability mass function which in the limit is accurately represented as a Normal probability density function scaled by a Beta probability density function. The order 7 weight class cumulative distribution function can be modeled as a weighted sum of two Normal cumulative distribution functions.
  • Keywords
    binary sequences; binomial distribution; computational complexity; normal distribution; probability; shift registers; NP complete problem; beta probability density function; binary sequences; n-stage feedback shift registers; normal cumulative distribution functions; order 7 de Bruijn weight classes; shifted binomial probability mass function; weight class probability mass function; Binary sequences; Biographies; Distributed computing; Distribution functions; Drives; Feedback; Hamming weight; Probability density function; Shift registers; Systems engineering and theory;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Aerospace conference, 2009 IEEE
  • Conference_Location
    Big Sky, MT
  • Print_ISBN
    978-1-4244-2621-8
  • Electronic_ISBN
    978-1-4244-2622-5
  • Type

    conf

  • DOI
    10.1109/AERO.2009.4839405
  • Filename
    4839405