Binaire & logique booléenne

La suite du cours va mettre en avant la logique binaire, plus généralement appelée algèbre de Boole. Cela peut faire peur au premiers abords mais en réalité ce n’est que de la logique qui manipule des valeurs $0$ ou $1$, FAUX ou VRAI…

La base des raisonnements mathématiques, mais aussi base de l’informatique qui sans l’algèbre de Boole n’existerait pas. En effet l’informatique est basé sur les opérations binaires. La raison principale de l’utilisation de cette théorie pour l’informatique est qu’elle fiable et reproductible par rapport à l’analogique. Cependant la base $2$ (binaire) n’est pas forcément le plus efficace pour traiter l’information, mais c’est la plus facile à obtenir avec des composants. On observe assez facilement que le signal est simplement l’absence de tension ($0$), ou la présence de tension ($1$) . L’avantage est donc que quelque soit la valeur de la tension (qui peut fluctuer selon les conditions) n’est pas si importante : l’info est donc très fiable.

Mais comment faire des calculs avec juste des $0$ et $1$, et avoir de l’information complexe ?

1. Le binaire comme base pour compter :

Binaire non signé

La réponse est dans l’algèbre de Boole et le binaire. En réalité nous comptons en base $10$, c’est à dire que nous séparons l’unité, la dizaine, la centaine… par des facteurs $10$. Le binaire c’est la même chose même avec des unités et des dizaines séparé par des facteurs $2$. Je m’explique : prenons par exemple $152$, qui a pour unité $2$, dizaine $5$ et $1$ pour centaine, ce qui veut concrètement dire que

$$152 = 1 * 10^{2} + 5 * 10^{1} + 2 * 10^{0}.$$

C’est la même chose pour le binaire mais avec des facteurs deux et non pas dix. Par exemple nous avons $10111$ qui vaut : $$10111 = 1 * 2^{4} + 0*2^{3} + 1*2^{2} + 1*2^{1} + 1*2^{0} = 23.$$

Les opérations sont les mêmes mais la retenue se fait différemment : $00101 + 10011 = 11000$, en effet dès qu’on dépasse $1$ il suffit de retenir pour passer la retenue à la colonne suivante : $1 + 1 = 10$. Ici le résultat est le même que l’opération soit faite en base $10$ ou en base $2$. L’exemple ci dessus est valable, $00101_{(2)} + 10011_{(2)} = 5 + 19 = 24$ et $11000_{(2)} = 24$. Tout ces nombres sont les mêmes mais pas dans la même base. La multiplication, la soustraction et la division sont identiques, si on oublie pas la retenue.

L’ordinateur utilise des bits, un bit est une information binaire, c’est-à-dire $0$ ou $1$. Pour aller plus vite, on regroupe les bits en un minimum de huit. Soit huit bits, donne un octet. Cette fameuse unité de mémoire l’octet vient du fait que nous avons huit bits d’information qui peut donner $2^8$ nombres, de $0$ à $2^8 – 1$. Maintenant on parle plutôt de Mo, Go qui sont $10^9$, $10^{12}$ octets. On dit que le binaire est non signé : c’est un binaire simple mais qui ne permet pas de représenter les nombres négatifs. En effet sur un octet les nombres vont de $0$ à $2^8 – 1$ et non pas de $-2^7$ à $2^7 – 1$.

Binaire signé

Maintenant pour compliquer la chose, nous voulons autoriser le binaire négatif. C’est pourquoi non utiliserons ce que nous appelons le binaire signé complément à deux. Pour obtenir un nombre négatif nous allons utiliser le bit de poids fort (ici celui le plus à gauche) pour connaitre le signe du nombre. Ainsi $01100110$ est positif et $10100111$ est négatif. Mais il suffit pas juste de lire le nombre binaire dans l’ordre et regarde le bit de poids fort pour savoir si on met le nombre négatif ou positif. Il faut faire le complément à $2$,

1. il faut en réalité inverser tout les bits.
2. et ajouter $1$.

Exemple simple, pour écrire $\{-4\}$ il faut prendre $4 = 00000100_{(2)}$,

1. inverser tout les bits $11111011_{(2)}$
2. et ajouter $1$ (à cause du zéro) et : $$-4 = 11111100_{(2)}$$

2. Logique booléenne :

Maintenant il faut comprendre la base des opérations faites en binaire. En réalité les variables ne seront que des $0$ ou $1$. Les opérations booléennes sont très pratiques pour faire des opérations bit à bit comme additionner des bits ou faire des décalages, etc… L’algèbre booléenne utilise donc un formalisme logique pour obtenir à peut prêt n’importe quel opérateur.

Pour commencer nous définirons une variable comme un élément qui peut prendre différentes valeurs. Notre variable porte un nom par exemple $a$ ou encore $b$, voire $S$ et une valeur $a = 0$, $b = 1$ et $S = a + b$. Comme nous sommes en logique les seules valeurs possible sont FAUX et VRAI qui seront traduites par $0$ et $1$ et les opérateurs de base $+$ et $\cdot$ ne seront pas l’addition, ni la multiplication mais les opérateurs logique OU et ET.

Nous devons donc poser les tables de vérités des opérateurs logiques OU et ET.

Soit $S = a + b$ autrement $a$ OU $b$. Ici pour faire simple il faut voir $a$ et $b$ comme des entrées et $S$ comme une sortie :

Il faut voir la porte OU comme une boite magique qui fait l’opération OU. On peut mettre du courant dans $a$, dans $b$ et on observe se qu’il se passe en $S$ :

Pour lire le tableau il faut comprendre :

• Première ligne (i) $a$ et $b$ n’ont pas de courant alors $S$ n’aura pas de courant.
• Deuxième ligne (ii) Si $a$ est allumé et $b$ non, $S$ sera allumé.
• Troisième ligne (iii) Si $a$ n’a pas de courant et que $b$ en a alors $S$ est allumé.
• Quatrième ligne (iv) si $a$ et $b$ ont du courant alors $S$ est allumé.

Ici on remarque que le OU n’est pas exclusif comme en français, en effet en français, si je dis : « tu veux $a$ ou $b$ ? » ici pas de possibilité d’avoir $a$ et $b$ en même temps, alors que dans la porte OU logique est inclusive : si $a$ et $b$ sont vrais alors $S$ l’est aussi.

Soit $S = a \cdot b$, autrement dit $a$ ET $b$ a pour table de vérité :

Ici ces deux tables logique sont la base de la logique booléenne. Il existe aussi une opération de négation qui rend négatif la variable. Par exemple si $a = 1$ alors la négation $\overline{a} = 0$. Avec ces éléments il est possible de calculer la réponse des ordinateurs avec des équations et donc de construire les opérateurs classique mathématiques comme l’addition, la soustraction, etc…

C’est donc avec ces deux grands concepts que nous arrivons à faire des ordinateurs qui fonctionnent, nous comptons en base deux, et faisons des opérations bit à bit grâce à l’algèbre de Boole. Cependant comment tout cela est fait ? Comment les séries de $0$ et $1$ sont « transformés » en chansons, en jeu vidéo ? Comment l’information est traitée ? Grâce au petit transistor ! Qui sera tout simplement introduit de le prochain cours.