OU Exclusif

OU Exclusif

Fonction OU exclusif

La fonction OU exclusif, souvent appelée XOR (eXclusive OR), est un opérateur logique de l'algèbre de Boole. À deux opérandes, qui peuvent avoir chacun la valeur VRAI ou FAUX, il associe un résultat qui a lui-même la valeur VRAI seulement si les deux opérandes ont des valeurs distinctes.

Cet opérateur est très utilisé en électronique, en informatique, et aussi en cryptographie du fait de ses propriétés intéressantes. Son symbole est traditionnellement un signe "PLUS" dans un cercle : « ⊕ ».

Sommaire

Définition

Appelons A et B les deux opérandes considérés. Convenons de représenter leur valeur ainsi :

1 = VRAI
0 = FAUX

L'opérateur XOR est défini par sa table de vérité, qui indique pour toutes les valeurs possibles de A et B la valeur du résultat R :

Table de vérité de XOR
A B R = A ⊕ B
0 0 0
0 1 1
1 0 1
1 1 0


Comme on peut le voir, l'opérateur logique XOR, ou OU exclusif, peut se définir par la phrase suivante :

Le résultat est VRAI si un et un seul des opérandes A et B est VRAI

ou

Le résultat est VRAI si les deux opérandes A et B ont des valeurs distinctes

ou

Le résultat est VRAI si un nombre impair d'entrées est vrai (ceci est surtout applicable lorsque deux ou plusieurs opérateurs logiques XOR se cascadent (générateurs de bit de parité )

Il se différencie de l'opérateur OU inclusif, car il donne un résultat FAUX lorsque A et B ont simultanément la valeur VRAI. Son symbole se différencie aussi de l'opérateur OU inclusif dont le symbole est simplement un "PLUS": « + ».

En informatique, cet opérateur peut s'utiliser pour combiner deux bits, valant chacun 0 ou 1, en appliquant les règles définies par la table précédente, le résultat étant lui-même la valeur d'un bit.

Avec des portes logiques ET/OU, A XOR B = (A ET non B) OU (non A ET B).

Quelques propriétés mathématiques

  • A \oplus A = 0 (on le vérifie facilement sur la table pour les 2 valeurs possibles de A)
  • A \oplus 0 = A
  • A \oplus 1 = \bar{A}
  • A \oplus \bar{A} = 1
  • Commutativité A \oplus B = B \oplus A
  • Associativité A \oplus (B \oplus C) = (A \oplus B) \oplus C
  • A \oplus B = (A +B) \oplus A.B
  • A \oplus B = 0 si et seulement si A = B (dans un sens, c'est immédiat, dans l'autre, utilisation de la propriété d'associativité et de la propriété: A \oplus 0 = A)
  • A \oplus B = \bar{A}.B + A.\bar{B} On déduit de cette propriété : \overline{A \oplus B} = A.B + \bar{A}.\bar{B}
  • A \oplus B = C alors C \oplus B = A et A \oplus C = B
  • (A \oplus B) \oplus B = A (Conséquence des deux premières propriétés et de l'associativité - utile en cryptographie (voir ci-dessous))
  • L'ensemble {0;1} muni des deux lois de composition interne OU exclusif et ET possède une structure de corps commutatif fini.

Exemple d'utilisation en cryptographie

Considérons un document numérique à chiffrer, il consiste en une suite de bits. Dans la méthode de chiffrement par flot, on doit disposer par ailleurs une suite de bits de même longueur, totalement aléatoire, que l'on appelle clé de chiffrement. On traite un à un les bits du document en clair, en le combinant avec le bit de même rang de la clé de chiffrement.

Appelons A un bit en clair et B le bit de même rang de la suite aléatoire.

Le chiffrement consiste à calculer le bit C par : C = AB . C est le chiffré de A.

Pour déchiffrer C on utilise à nouveau le bit B de la suite aléatoire et on calcule : CB.

Le résultat donne A, le bit de clair, car CB = ABB = A0 = A, en utilisant les deux premières propriétés ci-dessus .

Cette méthode est l'une des manières d'effectuer un chiffrement symétrique, où la même clé sert à chiffrer et déchiffrer.

Ce système, bien que très simple dans son principe, peut s'avérer inviolable si la suite de bits de la clé est vraiment aléatoire. Cette dernière ne doit en outre être utilisée qu'une seule fois (on parle de masque jetable, ou encore de «one-time pad»). Dans cette phrase, c'est surtout le mot «aléatoire» qui s'avère être le plus difficile à mettre en œuvre. Mais lorsque la clé est vraiment aléatoire --- techniquement, qu'elle est tirée selon la distribution uniforme parmi toutes les suites possibles de cette longueur --- ce système est parfaitement sûr, en un sens rigoureusement défini par Claude Shannon, en 1949, dans un article fondateur «Communications theory of secrecy systems». Il convient d'ajouter que c'est le seul chiffrement aboutissant à une sécurité absolue, en théorie.

Voir aussi l'article : masque jetable

Illustration

Voici un exemple numérique de la méthode précédente :

M = 0110101011010100 (message en clair)

K = 0101011011100110 (la clé ; à garder secrète bien évidemment)

Convenons que le symbole ⊕ représente ici l'application de l'opérateur XOR à chacun des bits :

Chiffrement : C = MK = 0011110000110010 (message chiffré)

Déchiffrement : M = CK = 0110101011010100 (message déchiffré)

Histoire

Ce système de chiffrement a été utilisé pour le téléphone rouge, en fait un télex, reliant directement le Kremlin à la Maison Blanche, les clés transitant alors par valises diplomatiques. Le système de masque jetable était également employé par les espions soviétiques. Certains masques furent utilisés plus d'une fois (parfois avec des années d'intervalle) ce qui permit aux services du chiffre anglais de déchiffrer certains messages.

Autres applications en cryptographie

La totalité des chiffreurs symétriques utilise l'opérateur XOR. Le nouvel algorithme de cryptographie haute sécurité symétrique AES ( Rijndael ) en particulier, en utilise un très grand nombre.

Application en électronique

Exemple d'utilisation : Le Circuit intégré 7486 TTL ou le circuit intégré CMOS 4070 intègre quatre portes logiques du type OU exclusif. Illustration : Exemple : La lampe s'allume si l'on appuie sur « a » ou « b » seulement, mais pas si l'on appuie sur « a » et « b » simultanément.

Schéma
Fonctions logiques(5-a).png
Équation
L = a \oplus b
L = (\bar{a}.b)+(a.\bar{b})
Chronogramme
Fonctions logiques(5-d).png
Symbole
Fonctions logiques(5-e).png
Symbole ANSI (appelé aussi militaire)
XOR ANSI.svg

Application en informatique

Outre les utilisations liées à la cryptographie, la fonction OU exclusif permet de remettre rapidement la valeur d'une variable (souvent un registre) à zéro. Prenons par exemple le code en assembleur qui utilise le OU exclusif pour remettre la valeur du registre eax à zéro :

xor eax, eax

Celui-ci s'exécute plus rapidement que le code intuitif suivant :

mov eax, 0

Application en électricité domestique

Une application utilisée de l'opérateur logique OU exclusif en électricité domestique est dans les salles ou une ampoule peut être allumée ou éteinte par deux interrupteurs placés près de deux entrées. Chacun des deux interrupteurs peut soit allumer ou éteindre l'ampoule quelle que soit la position de l'autre interrupteur. Pour obtenir une telle fonctionalité, on doit brancher les deux interrupteurs afin de former un opérateur XOR.

Voir aussi

  • Portail de la logique Portail de la logique
  • Portail de la cryptologie Portail de la cryptologie
  • Portail de l’électricité et de l’électronique Portail de l’électricité et de l’électronique
Ce document provient de « Fonction OU exclusif ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article OU Exclusif de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • exclusif — exclusif, ive [ ɛksklyzif, iv ] adj. • 1453; lat. médiév. exclusivus, du supin de excludere → exclure 1 ♦ Anc. dr. Qui a force d exclure. Avoir voix exclusive : avoir le droit d exclure un candidat proposé. 2 ♦ (fin XVIIe) Qui exclut de tout… …   Encyclopédie Universelle

  • exclusif — exclusif, ive (èk sklu zif, zi v ) adj. 1°   Qui a force d exclure. Un droit exclusif de tout autre. •   Le vice roi de Goa accordait à des particuliers des priviléges exclusifs, MONTESQ. Esp. XX, 20. •   Faut il de tous les champs qu exclusifs… …   Dictionnaire de la Langue Française d'Émile Littré

  • exclusif — Exclusif, [exclus]ive adj. v. Qui a force d exclurre. Il a voix exclusive. c est une raison exclusive de sa demande. cela est exclusif. un droit exclusif de tout autre …   Dictionnaire de l'Académie française

  • Exclusif — ce soir Genre magazine Présentation Emmanuelle Gaume et Thierry Clopeau (1998) Emmanuelle Gaume et Frédéric Joly (1998 2000) Flavie Flament et Frédéric Joly (2000 2001) Valérie Bénaïm et Frédéric Joly (2001 2002) Pays …   Wikipédia en Français

  • Exclusif — Als Exclusif (frz.) bezeichnet man die Forderung nach einer ausschließlichen Nutzung der eigenen überseeischen Besitzungen (Kolonien) zum Vorteil des französischen Mutterlandes im Zeitalter des Merkantilismus. Inhaltsverzeichnis 1 Grundlagen 2… …   Deutsch Wikipedia

  • EXCLUSIF — IVE. adj. Qui a force d exclure. C est une raison exclusive. Cela est exclusif. Un droit exclusif, exclusif de tout autre. Privilége exclusif.   Avoir voix exclusive dans une élection, Avoir le droit d exclure le candidat présenté. Il y a des… …   Dictionnaire de l'Academie Francaise, 7eme edition (1835)

  • EXCLUSIF, IVE — adj. Qui a force d’exclure. C’est une raison exclusive. Cela est exclusif. Un droit exclusif, exclusif de tout autre. Privilège exclusif. Avoir voix exclusive dans une élection, Avoir le droit d’exclure le candidat présenté. On dit aussi comme… …   Dictionnaire de l'Academie Francaise, 8eme edition (1935)

  • exclusif — См. esclusivo …   Пятиязычный словарь лингвистических терминов

  • exclusif — adj. èskluzifo, ifa / îva, e (Albanais) …   Dictionnaire Français-Savoyard

  • Nous exclusif — « nous » exclusif et inclusif Le nous inclusif et le nous exclusif En linguistique, un nous inclusif est un pronom ou une conjugaison de verbe qui indique l’inclusion du locuteur, des auditeurs, et peut être encore d’autres personnes, par… …   Wikipédia en Français

  • « nous » exclusif et inclusif — Le nous inclusif et le nous exclusif En linguistique, un nous inclusif est un pronom ou une conjugaison de verbe qui indique l’inclusion du locuteur, des auditeurs, et peut être encore d’autres personnes, par opposition au nous exclusif qui lui… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”