Une machine à calculer : le bit

information-icon

Les premières épreuves du bac de français édition 2024 sont pour bientôt ! Consulte les dates du bac de français, notre programme de révision accompagné de toutes nos fiches de révisions pour te préparer au mieux à ton examen 💪

Introduction :

Dans cette première partie, nous répondons à une question qui pourrait paraître simple, mais qui ne l’est pas : qu’est-ce qu’au juste un ordinateur ? Pour le comprendre, nous allons voir les ancêtres successifs des ordinateurs d’aujourd’hui.

Dans ce premier cours, nous remontons aux premières machines à calculer mécaniques, pour comprendre les concepts clés d’algorithme, de donnée et d’instruction. Nous découvrons aussi, avec le concept de bit, les bases de l’algèbre booléenne et du système de numération binaire.

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.

bannière definition

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 (IXe 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.

bannière definition

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$.

bannière exemple

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.

Gregor Reisch, Margarita Philosophica Mathématiciens en plein calcul. Celui de droite utilise un abaque, celui de gauche pose le calcul à la façon arabe. « Gregor Reisch : Margarita Philosophica, Gregor Reish », 1508, domaine public.

Au XVIIe 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.

bannière exemple

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 XVIIe 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.

bannière à retenir

À 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.

bannière attention

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).

cartes perforées, machine analytique Des cartes perforées pour la machine analytique. Devant : les cartes d’instructions, der-rière : les données. « Punched cards for programming the Analytical Engine », Karoly Loren-tey, 1834-71, Science Museum, London, CC-BY 2.0.

cartes perforées « Archivage de cartons de cartes perforées, archivés au service du NARA en 1959. Chaque carton peut contenir 2 000 cartes d'une ligne de 80 colonnes chacune », NARA, 1959, domaine public.

bannière definition

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.).

bannière à retenir

À 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.

bannière definition

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).

bannière à retenir

À 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}$.

bannière propriete

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é

bannière definition

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.
bannière exemple

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}$.
bannière definition

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 :

$\text{a}$ $\bar{\text{a}}$
$0$ $1$
$1$ $0$

$\text{a}$ $\text{b}$ $\text{a}\cdot\text{b}$ $\text{a}+\text{b}$
$0$ $0$ $0$ $0$
$0$ $1$ $0$ $1$
$1$ $0$ $0$ $1$
$1$ $1$ $1$ $1$
bannière exemple

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

bannière propriete

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 :

bannière propriete

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}}$

$\text{a}$ $\text{b}$ $\text{a}+\text{b}$ $\overline{\text{a}+\text{b}}$ $\bar{\text{a}}\cdot\bar{\text{b}}$ $\text{a}\cdot\text{b}$ $\overline{\text{a}\cdot\text{b}}$ $\bar{\text{a}}+\bar{\text{b}}$
$0$ $0$ $0$ $1$ $1$ $0$ $1$ $1$
$0$ $1$ $1$ $0$ $0$ $0$ $1$ $1$
$1$ $0$ $1$ $0$ $0$ $0$ $1$ $1$
$1$ $1$ $1$ $0$ $0$ $1$ $0$ $0$
bannière propriete

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}$$

$\text{a}$ $\text{b}$ $\text{a IMPLIQUE b}$
$0$ $0$ $1$
$0$ $1$ $1$
$1$ $0$ $0$
$1$ $1$ $1$

Coder des nombres en binaire

Entiers en base $2$

bannière definition

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$.

bannière exemple

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$.
bannière attention

Attention

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

bannière exemple

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.
bannière exemple

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$

Conclusion :

Nous savons maintenant faire la distinction entre algorithme et programmation. Nous avons également vu dans ce cours les principaux usages du bit ($0$ ou $1$) : il peut représenter des concepts logiques, dans le cadre l’algèbre booléenne, ou des nombres entiers dans le cadre du système binaire.

Dans le prochain cours, nous allons voir comment l’on peut représenter en binaire des nombres relatifs ou réels. Puis nous continuerons notre histoire de l’informatique avec l’apparition des premiers ordinateurs électroniques.