• DocumentCode
    805342
  • Title

    Maximum nonlinearity of symmetric Boolean functions on odd number of variables

  • Author

    Maitra, Subhamoy ; Sarkar, Palash

  • Author_Institution
    Comput. & Stat. Service Center, Indian Stat. Inst., Calcutta, India
  • Volume
    48
  • Issue
    9
  • fYear
    2002
  • fDate
    9/1/2002 12:00:00 AM
  • Firstpage
    2626
  • Lastpage
    2630
  • Abstract
    In this correspondence, we establish that for odd n, the maximum nonlinearity achievable by an n-variable symmetric Boolean function is 2n-1-2(n-1)/2 and characterize the set of functions which achieve this value of nonlinearity. In particular, we show that for each odd n≥3, there are exactly four possible symmetric Boolean functions achieving the nonlinearity 2n-1-2(n-1)2/.
  • Keywords
    Boolean functions; combinatorial mathematics; information theory; algebraic normal form; maximum nonlinearity; odd number of variables; symmetric Boolean functions; Boolean functions; Statistics;
  • fLanguage
    English
  • Journal_Title
    Information Theory, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9448
  • Type

    jour

  • DOI
    10.1109/TIT.2002.801482
  • Filename
    1027794