Cours : Une machine à calculer : le bit

Mathématiques et mécanique

Algorithmes et système décimal

Dès le primaire, on apprend des algorithmes mathématiques : ce sont des méthodes automatiques pour « calculer » des additions, des soustractions, des multiplications et des divisions entières en les posant. On trouve en réalité des algorithmes depuis les débuts de l’histoire des mathématiques, comme l’algorithme d’Euclide, que nous apprenions au collège, pour calculer le plus grand diviseur commun (PGCD) de deux entiers.

Définition

Algorithme :

Un algorithme est une séquence d’instructions décrivant de manière précise les étapes de la résolution d’un problème mathématique.

Le mot « algorithme » vient du mathématicien perse Muhammad Al-Khwarizmi, membre de la Maison de la sagesse de Bagdad (IX^e siècle), considéré comme le fondateur de l’algèbre. C’est grâce aux travaux d’Al-Khwarizmi qu’ont été popularisés en Europe les chiffres arabes et le système décimal, qui permettent de réaliser les calculs arithmétiques (additions, soustractions, multiplication, divisions entières) vus en primaire.

Définition

Système décimal : Le système décimal ou système en base $10$ est un système de numération (c’est-à-dire un système pour représenter les nombres) utilisant dix chiffres : $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$.

Exemple

Observons la représentation d’un nombre en base $10$ : $$7518$$ Chaque chiffre, en fonction de sa position, indique le nombre d’unités, de dizaines, de centaines, de milliers :
$$7518 = 7000 + 500 + 10 + 8$$ Ainsi, la position de chaque chiffre correspond à une puissance de dix précise : $$7518 = 7\times10^3 + 5\times10^2 + 1\times10^1 + 8\times10^0$$

Pour rappel : $a^0=1$ et $a^1=a$

Comme nous allons le voir, on peut bâtir sur ce principe des systèmes de numération utilisant n’importe quelle autre valeur entière comme base. Nous verrons plus loin le système binaire (en base $2$) et, dans le prochain cours, le système hexadécimal (en base $16$).

Calculs mécaniques

Pendant des siècles, les algorithmes, permettant les opérations mathématiques de base, étaient exécutés à la main par des scribes ou des comptables, parfois avec l’aide d’outils intermédiaires (comme des bouliers) que l’on appelle les abaques.

Au XVII^e siècle, avec les progrès de la mécanique et de l’horlogerie, les premières machines à calculer mécaniques apparaissent, permettant un gain de temps et réduisant les risques d’erreur par rapport au calcul manuel.

Exemple

• La première machine à réaliser mécaniquement des calculs est inventée par le philosophe français Blaise Pascal en 1642. La pascaline permet de réaliser automatiquement additions et soustractions en faisant tourner des roues crantées.
• Au XVII^e siècle, le mathématicien britannique Charles Babbage conçoit la machine à différences. Cette gigantesque machine, actionnée par une manivelle, réalise une série d’additions spécifiques permettant de résoudre certaines formes d’équations. La machine à différence n’a jamais été construite du vivant de Babbage, mais un exemplaire en a été construit en 2002.

Programmer des machines

La première machine mécanique programmable n’est pas une machine à calculer, mais un métier à tisser. Les métiers Jacquard, inventés en 1801, lisent des instructions sur des cartons perforés pour réaliser automatiquement les motifs des tapisseries.
C’est à partir de la machine à différence, et en s’inspirant des métiers Jacquard, que Charles Babbage et la mathématicienne Ada Lovelace vont inventer la machine analytique, la toute première machine à calculer programmable, l’ancêtre de l’ordinateur.

Les machines que nous avons vues jusqu’à présent réalisent une certaine séquence d’opérations sur les nombres qu’on leur donne : les additionner, les soustraire, etc. On appelle ces nombres des données.

À retenir

Ada Lovelace est l’autrice du premier programme informatique : une suite d’instructions destinée à être exécutée sur des données par une machine.

La machine analytique reçoit à la fois des données et des instructions (sur cartes perforées) indiquant quelles opérations doivent être faites sur les données.

Attention

Ne pas confondre algorithme et programme, même si ces deux idées sont très proches (ce sont tous les deux des suites d’instructions pour résoudre un problème) :

• Un algorithme est destiné à être compris par un être humain.
• Un programme est destiné à être exécuté par une machine. C’est la traduction de l’algorithme en langage machine.

Le double usage du bit

Les instructions et les données devaient être passées à la machine analytique sous la forme de cartes perforées, comme pour les métiers Jacquard. Les cartes perforées ont été utilisées dans de nombreux contextes depuis pour coder de l’information par la présence ou l’absence de trous (0 ou 1).

Définition

Bit :

Un bit (binary digit) est une unité d’information binaire, ne pouvant prendre que $2$ valeurs : $0$ ou $1$.

Les cartes perforées seront très utilisées pour stocker de l’information jusque dans les années 1970. Elles sont encore utilisées aujourd’hui pour certains usages spécifiques (machines à voter, péages autoroutiers, etc.).

À retenir

Même avec l’apparition de nouveaux supports (par exemple magnétiques, optiques ou électroniques) utilisés pour le coder, les ordinateurs utilisent encore aujourd’hui le code binaire (à l’insu de l’utilisateur).

Ada Lovelace, la première, réalise que ce codage binaire permet de représenter et manipuler à la fois des nombres (avec un système en base $2$) et des concepts logiques (vrai ou faux). C’est ce que nous allons voir dans la suite de ce cours : la deuxième partie est consacrée à la logique binaire, et la troisième partie au système numérique binaire.

Algèbre booléenne

Le mathématicien britannique George Boole (1815-1864) est considéré comme le fondateur de la logique moderne.

Définition

Algèbre booléenne :

L’algèbre booléenne (ou algèbre de Boole) est une théorie mathématique qui s’intéresse aux opérations sur les valeurs de vérité (vrai et faux).

À retenir

En algèbre booléenne :

• $0$ signifie faux ;
• $1$ signifie vrai.
• On appelle ces valeurs des valeurs booléennes ou des booléens.

Lois de base ($\text{ET}$, $\text{OU}$, $\text{NON}$)

L’algèbre de Boole se fonde sur deux opérations $\text{ET}$ et $\text{OU}$ et une transformation $\text{NON}$.

Propriété

• Soit un booléen $\text{a}$.
  On appelle $\text{non-a}$ (ou $\text{not-a}$ en anglais) la négation de $\text{a}$, autrement dit, $\text{non-vrai} = \text{faux}$ et $\text{non-faux} = \text{vrai}$.
• Soient deux booléens $\text{a}$ et $\text{b}$.
• Le booléen $\text{a ET b}$ est vrai si et seulement si $\text{a}$ est vrai ET $\text{b}$ est vrai.
• Le booléen $\text{a OU b}$ est vrai si et seulement si $\text{a}$ est vrai OU $\text{b}$ est vrai.

On utilise les notations suivantes :

• $\text{not-a}$ est noté $\neg\text{a}$ ou $\bar{\text{a}}$ (« a barre »).
• Selon le contexte, $\text{ET}$ est représenté par l’un de ces trois symboles :
• $\land$
• $\cdot$ (utilisée ici)
• $\&$
• Selon le contexte, $\text{OU}$ est représenté par l’un de ces trois symboles :
• $\lor$
• $+$ (utilisée ici)
• $ \Vert$

Expression booléenne et table de vérité

Définition

Expression booléenne :

Une expression booléenne est une expression qui correspond à une valeur booléenne.

• En d’autres termes, c’est une phrase qui est soit vraie, soit fausse.

Exemple

• « $5 < 3$ » est une expression booléenne qui vaut $\text{faux}$, car $5$ est plus grand que $3$.
• « $7$ est un nombre premier » est une expression booléenne qui vaut $\text{vrai}$.
• Si $\text{a}$, $\text{b}$ et $\text{c}$ sont des booléens, alors « $\text{a}$ OU $\text{b}$ OU $\text{c}$ » est un booléen. Sa valeur dépend de celles de $\text{a}$, $\text{b}$ et $\text{c}$.
• « ($5 < 3$) ou ($7$ est un nombre premier) » est donc un booléen qui vaut $\text{vrai}$.

Définition

Table de vérité :

La table de vérité d’une expression booléenne exprime sa valeur en fonction des valeurs prises par les booléens qui la composent.

Les tables de vérité des opérations de base sont les suivantes :

Exemple

On veut construire la table de vérité de $(\text{a}+\text{b})\cdot\bar{\text{c}}$. Pour s’aider, on peut construire comme intermédiaires la table de vérité de $\text{a}+\text{b}$ et celle de $\bar{\text{c}}$ :

$\text{a}$	$\text{b}$	$\text{c}$	$\text{a}+\text{b}$	$\bar{\text{c}}$	$(\text{a}+\text{b})\cdot\bar{\text{c}}$
$0$	$0$	$0$	$0$	$1$	$0$
$0$	$0$	$1$	$0$	$0$	$0$
$0$	$1$	$0$	$1$	$1$	$1$
$0$	$1$	$1$	$1$	$0$	$0$
$1$	$0$	$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$	$0$	$0$
$1$	$1$	$0$	$1$	$1$	$1$
$1$	$1$	$1$	$1$	$0$	$0$

Égalités

Propriété

Deux expressions booléennes sont égales si elles ont la même table de vérité.

On peut vérifier, en comparant leurs tables de vérités, les égalités suivantes, connues sous le nom du théorème de Morgan :

Propriété

• Première loi de Morgan : $\overline{\text{a}+\text{b}}=\bar{\text{a}}\cdot\bar{\text{b}}$
• Deuxième loi de Morgan : $\overline{\text{a}\cdot\text{b}}=\bar{\text{a}}+\bar{\text{b}}$

Propriété

Il existe d’autres opérateurs booléens, mais ils peuvent tous s’exprimer à partir des trois opérateurs $\text{non}$, $\text{et}$, $\text{ou}$.

Deux autres opérateurs sont particulièrement connus :

• OU exclusif ($\text{XOR}$) : $\text{a XOR b}$ est vrai si et seulement si une seule valeur parmi $\text{a}$ et $\text{b}$ est vraie et que l’autre est fausse. On note :
  $$\text{a XOR b}=(\text{a}+\text{b})\cdot\overline{\text{a}\cdot\text{b}}$$
• implication : $\text{a IMPLIQUE b}$ est vrai si $\text{b}$ est vrai quand $\text{a}$ est vrai (quand $\text{a}$ est faux, $\text{b}$ peut être vrai ou faux). On note :
  $$\text{a IMPLIQUE b}=\bar{\text{a}}+\text{b}$$

Coder des nombres en binaire

Entiers en base $2$

Définition

Système binaire :

Le système binaire ou système en base $2$ est un système de numération utilisant deux chiffres : $0$ ou $1$. Chaque chiffre est donc un bit.

Dans le système binaire, chaque bit représente une puissance de $2$ (celle correspondant à sa position dans le nombre). La valeur du nombre se calcule en additionnant les puissances de $2$ correspondants à chaque bit valant $1$.

Exemple

Coder $1101$ en base 2 :
$=1\times2^3 + 1\times2^2 + 0\times2^1 + 1\times2^0$
$= 8 + 4 + 0 + 1$
$= 13$

À l’inverse, pour calculer l’expression binaire d’un nombre $x$ exprimé en décimal, on suit l’algorithme suivant :

• chercher la plus grande puissance de $2$ plus petite ou égale à $x$ ;
• passer le bit correspondant à $1$ ;
• soustraire cette grandeur à $x$, puis reprendre du début ;
• ainsi de suite, jusqu’à ce que $x = 0$ ;
• tous les bits qui n’ont pas été passés à $1$ sont à $0$.

Attention

Le bit qui correspond à $2n$ n’est pas le $n$ - ième bit mais le $(n+1)$ - ième bit !

Exemple

Exprimer $27$ en binaire en base $2$. Nous utilisons successivement la division euclidienne :

• $\dfrac{27}{2}=13$
• Il nous reste 1
• $\dfrac{13}{2}=6$
• Il nous reste 1
• $\dfrac{6}{2}=3$
• Il nous reste 0
• $\dfrac{3}{2}=1$
• Il nous reste 1
• $\dfrac{1}{2}=0$
• Il nous reste 1
• Le nombre décimal $27$ s’exprime donc par $11\,011$ en binaire.

Addition binaire

L’algorithme d’addition, utilisé en primaire avec le système décimal, fonctionne également pour le système binaire.

• On pose l’addition comme en primaire et on additionne les chiffres colonne par colonne.
• La somme de deux bits vaut toujours $0$, $1$ ou $2$.
• Si la somme vaut $0$ ou $1$, on l’inscrit sous la colonne.
• Si elle vaut $2$, on inscrit $0$ et on met $1$ en retenue.
• Avec une retenue, il se peut que la somme vaille $3$.
• Si c’est le cas, on inscrit $1$ et on met $1$ en retenue.

Exemple

Additionnons $1\,1100$ et $1110$ (soit $28$ et $14$ en décimal).
On pose l’addition :

$\ $	$\ $	$1$	$1$	$1$	$0$	$0$
$+$	$\ $	$\ $	$1$	$1$	$1$	$0$
$=$	$\ $	$\ $	$\ $	$\ $	$\ $	$\ $

• Première colonne :

$\ $	$\ $	$1$	$1$	$1$	$0$	$0$
$+$	$\ $	$\ $	$1$	$1$	$1$	$0$
$=$	$\ $	$\ $	$\ $	$\ $	$\ $	$0$

• Deuxième colonne :

$\ $	$\ $	$1$	$1$	$1$	$0$	$0$
$+$	$\ $	$\ $	$1$	$1$	$1$	$0$
$=$	$\ $	$\ $	$\ $	$\ $	$1$	$0$

• Troisième colonne :

$\ $	$\ $	$1$	$1$ $^{(1)}$	$1$	$0$	$0$
$+$	$\ $	$\ $	$1$	$1$	$1$	$0$
$=$	$\ $	$\ $	$\ $	$0$	$1$	$0$

• Quatrième colonne :

$\ $	$\ $	$1$ $^{(1)}$	$1$ $^{(1)}$	$1$	$0$	$0$
$+$	$\ $	$\ $	$1$	$1$	$1$	$0$
$=$	$\ $	$\ $	$1$	$0$	$1$	$0$

• Cinquième colonne :

$\ $	$^{(1)}$	$1$ $^{(1)}$	$1$ $^{(1)}$	$1$	$0$	$0$
$+$	$\ $	$\ $	$1$	$1$	$1$	$0$
$=$	$1$	$0$	$1$	$0$	$1$	$0$

Le résultat est donc $10\,1010$, ce qui correspond bien à $42$ $(28+14)$ en décimal.
En effet, $1\times{2^5}+0\times{2^4}+1\times{2^3}+1\times{2^1}+0\times{2^0}=42$