On the computation of the Möbius transform - GREYC monebiom Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2019

On the computation of the Möbius transform

Morgan Barbier
Hayat Cheballah
  • Fonction : Auteur

Résumé

The Möbius transform is a crucial transformation into the Boolean world; it allows to change the Boolean representation between the True Table and Algebraic Normal Form. In this work, we introduce a new algebraic point of view of this transformation based on the polynomial form of Boolean functions. It appears that we can perform a new notion: the Möbius computation variable by variable and new computation properties. As a consequence, we propose new algorithms which can produce a huge speed up of the Möbius computation for sub-families of Boolean function. Furthermore we compute directly the Möbius transformation of some particular Boolean functions. Finally, we show that for some of them the Hamming weight is directly related to the algebraic degree of specific factors.
Fichier principal
Vignette du fichier
article.pdf (286.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01178356 , version 1 (19-07-2015)
hal-01178356 , version 2 (08-07-2019)
hal-01178356 , version 3 (15-04-2020)

Licence

Paternité

Identifiants

Citer

Morgan Barbier, Hayat Cheballah, Jean-Marie Le Bars. On the computation of the Möbius transform. Theoretical Computer Science, 2019, Theoretical Computer Science, 809, pp.171-188. ⟨hal-01178356v3⟩
245 Consultations
791 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More