Fonction parité
From Wikipedia, the free encyclopedia
La fonction parité est une fonction booléenne. La sortie vaut 1, si et seulement si, le nombre de 1 dans l'entrée est impair. Un cas particulier est la fonction parité avec deux entrées, qui est connue sous le nom de XOR. Cette fonction est centrale dans l'étude des circuits booléens. Le résultat est parfois appelé bit de parité. Il ne faut pas confondre parité d'un nombre, et le fait qu'il soit pair ou impair (au sens mathématique du terme). Le nombre binaire 00000011 (3 en nombre décimal) est impair (non-divisible par 2) mais de parité paire (nombre pair de bits à 1).
Circuits booléens
La fonction parité un exemple de fonction qui n'est pas dans la classe de complexité nommée AC0. Ceci a été démontré par Furst, Saxe et Sipser[1], et indépendamment à Miklós Ajtai[2].
