--> Cours ISN n°1
Introduction au codage binaire 1Codage binaire 1.1Le 0 et le 1 Un ordinateur est une machine complexe qui dans son fonctionnement et dans tous ses composants utilise simplement le fait qu'un courant électrique circule ou non.
Il n'y a donc que deux états qui nous intéressent : le courant ne passe pas, on note 0, et le courant passe, on note 1.
On parle alors de système binaire.
Definition 1
Chaque information binaire (0 ou 1) est appelée bit. On appelle mot un sussession de bit. Un mot de huit bits est appelé octet.
Dans un mot, on parle de bit de poids fort pour le bit le plus à gauche et de bit de poids faible pour le bit le plus à droite. Exemple 1 10101010 est un octet dont le bit de poids fort est 1 est le bit de poids faible est 0.
1011100101010100 est un mot de 16 bits, ou encore un doublet. Remark 1 On parlera d'écriture en base 2 et on pourra à cette occasion ajouter l'indice ₂ en bas du mot afin d'éviter toute confusion. Exemple 2 00101010₂ = 42₁₀ Exemple 3 Voici un arbre permettant d'obtenir tous les mots de trois bits.

0,0

0 : 000

1 : 001

0 : 010

1 : 011

0 : 100

1 : 101

0 : 110

1 : 111

Property 1
Une succession de

n

bits permet d'écrire

2^n

mots différents. Exemple 4 Un octet permet de coder

2^8

=

256

mots différents. 1.2Codage d'un entier Nous avons l'habitude de n'utiliser pour écrire les nombres que le système décimal, aussi appelé base

10

.
Par exemple le nombre 1397 s'écrit :

7\times10^0+9\times10^1+3\times10^2+1\times10^3

.
Un ordinateur, en langage machine, ne peut travailler par contre qu'avec des mots écrits avec des 0 et 1. Il n'utilisera pas le nombre 1397, mais plutôt 10101110101 qui lui correspond.
En effet, en multipliant chaque bit par la puissance de

2

associée à sa position (en partant de la droite et en comptant à partir de

0

), on obtient :

$10101110101$	$=$	$1\times2^0$ $+$ $0\times2^1$ $+$ $1\times2^2$ $+$ $0\times2^3$ $+$ $1\times2^4$ $+$ $1\times2^5$ $+$ $1\times2^6$ $+$ $0\times2^7$ $+$ $1\times2^8$ $+$ $0\times2^9$ $+$ $1\times2^{10}$
	$=$	$1+4+16+32+64+256+1024$
	$=$	$1397$ .

Remark 2 Il est donc important de connaître les puissances de 2 :

1

2

4

8

16

32

64

128

256

512

1024

2048

4096

8192

16384

32768

65536

, etc. Property 2
Pour passer d'une écriture binaire à une écriture décimale, il suffira de lire le mot de droite à gauche, de multiplier chaque bit par la puissance de 2 associée et d'additionner le tout. Exemple 5

1011 correspond au nombre 11
010011 correspond au nombre 19
11111111 correspond au nombre 255
00000000 correspond au nombre 0

Remark 3 On peut utiliser un tableau de la forme :

128	64	32	16	8	4	2	1

Avec un octet on peut donc obtenir 256 nombres différents. Exemple 6 Voici un code en langage Python permettant d'automatiser la conversion.

xxxxxxxxxx
 
t = input()
​
s = 0
n = len(t)
​
for i in range(0,n):
     s = s + int(t[i])*pow(2,n-i-1)
​
print s
​

Exécuter

Property 3
Pour passer d'une écriture décimale à une écriture binaire, il suffit de réaliser des divisions euclidiennes successives par 2, jusqu'à obtenir un quotient nul, et de lire les restes obtenus dans le sens contraire. Exemple 7 Écrivons le nombre 157 en écriture binaire.

$157$	$=$	$78\times2$	$+$	$1$
$78$	$=$	$39\times2$	$+$	$0$
$39$	$=$	$19\times2$	$+$	$1$
$19$	$=$	$9\times2$	$+$	$1$
$9$	$=$	$4\times2$	$+$	$1$
$4$	$=$	$2\times2$	$+$	$0$
$2$	$=$	$2\times1$	$+$	$0$
$1$	$=$	$2\times0$	$+$	$1$

Ainsi, nous avons que

157_{10}

=

10011101_{2}

. Exemple 8 Voici un programme Python permettant de faire la conversion décimale/binaire.

xxxxxxxxxx
 
​
x = input()
x = int(x)
​
result = ""
if x < 2:
  result = str(x)
else:
  quotient = x
  while quotient != 0:
    reste = quotient % 2
    result=''.join([str(reste), result])
    quotient = quotient/2
​
print(result)
​

Exécuter

2Du bit au boolean L’idée naturelle juste aprés avoir codé en binaire un nombre entier afin que l’ordinateur puisse le comprendre, est de s’intéresser aux premières opérations que l’on pourrait effectuer dessus. La toute première qui puisse venir à l’esprit est l'addition.
On retiendra que :

$0+0$ $=$ $0$
$0+1$ $=$ $1$
$1+0$ $=$ $1$
$1+1$ $=$ $10$ , ou encore $1+1$ vaut $0$ avec une retenue qui vaut $1$ .

Exemple 9

111+101

=

1100

101101+10001

=

111110

					1
	1	0	1	1	0	1
+		1	0	0	0	1
	1	1	1	1	1	0

2.1Opérations logiques Depuis les premiers ordinateurs, pour réaliser des opérations telle que l'addition il a fallu utiliser des composants physiques avec deux entrées et une sortie par lesquelles passe ou non un courant électrique.
Ces composants physiques s'appellent des portes logiques car quelques soient les combinaisons possibles des courants électriques en entrée, la réponse en sortie est toujours définie et prévisible.
Mais pour pouvoir aborder les questions de logique dans un ordinateur ou en électronique nous avons besoin auparavant d'établir un vocabulaire précis. Definition 2
On appelle booléen une variable qui ne peut prendre que deux valeurs : "VRAI" ou "FAUX", ce qui se traduit en langage de programmation par true ou false.
Ces deux valeurs correspondent respectivement en binaire aux valeurs 0 et 1. Voici un tableau des principales portes logiques qui permettent de manipuler les booléens, et qui seront à la base de la construction des composants physiques d'un ordinateur.

Porte logique

Schéma

Écritures

Table de vérité

0,0

Logique : A ∧ B
Python : A and B
Javascript : A || B
Booléen : A×B

Entrées		Sortie
A	B	A ET B
0	0	0
0	1	0
1	0	0
1	1	1

0,0

Logique : A ∨ B
Python : A or B
Javascript : A && B
Booléen : A+B

Entrées		Sortie
A	B	A ET B
0	0	0
0	1	1
1	0	1
1	1	1

NON

0,0

Logique : ¬A
Python : not A
Javascript : !A
Booléen : $\overline{\text{A}}$

Entrées	Sortie
A	NON A
0	1
1	0

OU exclusif

0,0

Logique : A ⊕ B
Python : A ^ B
Javascript : A ^ B
Booléen : A ⊕ B

Entrées		Sortie
A	B	A OUX B
0	0	0
0	1	1
1	0	1
1	1	0

Exercice 1 Construire la table de vérité de (¬A)∨B.

Correction

A	B	¬A	(¬A)∨B
0	0	1	1
0	1	1	1
1	0	0	0
1	1	0	1

Remark 4 La proposition (¬A)∨B correspond à "A implique B", notée également

\text{A}\Rightarrow\text{B}

. 2.2Portes logiques de l'addition Le circuit logique suivant permet d'obtenir la somme de deux bits avec l'éventuelle retenue.

0,0

Et voici sa table de vérité :

Entrées		Sorties
A	B	Retenue R	Somme S
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	0

3Les signes et les virgules Nous avons précédemment vu comment additionner des entiers naturels. Il nous faut maintenant voir les principes d'écritures concernant les autres nombres. Ceux-ci ont été mis en place dès les premiers ordinateurs et n'ont peu évolué depuis. 3.1Codage des entiers relatifs On s'intéresse maintenat au codage des entiers relatifs. On considère que nous avons un octet pour écrire nos nombres. La première idée serait de réserver un bit, celui de poids fort par exemple, pour le signe (0 pour les positifs et 1 pour les négatifs), et les sept autres bits pour la valeur absolue du nombre. Par exemple :

coderait le nombre

+127

, et :

pour

-127

.
Malheureusement, plusieurs problèmes se posent alors, dont notamment :

on a deux écritures pour le nombre zéro (gaspillage d'une configuration) :

0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0
il est nécessaire d'avoir un circuit physique spécifique pour la soustraction.

Pour éviter ces problèmes, il a fallut mettre en place un codage des nombres négatifs tel que :

le bit de signe soit à 1,
il n'y ait qu'une seule écriture pour le nombre zéro,
on puisse utiliser la méthode d'addition standard pour calculer les sommes de nombres positifs et négatifs.

Exercice 2 Déterminer les bits manquants pour que l'opération soit correcte.

Correction

La seule solution possible est :

Elle génére d'ailleurs une retenue "perdue" car elle ne peut être stockée sur un octet.

Definition 3
Pour représenter l'opposé d'un nombre entier, on prend son complément bit à bit, auquel on ajoute 1.
Cette notation est appelée complément à deux. Exemple 10 Le nombre

+5

s'écrit :

Son complément bit à bit est :

Auquel nous ajoutons 1 :

On peut vérifier que la somme entre ce dernier nombre et le premier donne bien 0, car la retenue obtenue en additionnant les bits de poids faibles se "propage" jusqu'au bit de poids forts et ne donne que des 0. Cette retenue se "perd" alors. Remark 5 À l'aide de la notation en complément à deux, nous pouvons alors écrire les entiers naturels de

-128

jusqu'à

128

.
Les sept derniers bits de :

donne le nombre 123. Ce qui nous donne bien

123-128

=

-5

. Property 4
Pour trouver la représentation binaire sur

n

bits d'un entier relatifs

x

donné en décimal, il suffit :

de coder le nombre $x$ en binaire si il est positif ou nul.
de coder en binaire le nombre $2^n+x$ , si $x$ est strictement négatif.

Exemple 11 Sur un 11 bits, on aura les codages suivants :

Pour le nombre 117 :

0 0 0 1 1 1 1 0 1 0 1
Pour le nombre -531 :

1 0 1 1 1 1 0 1 1 0 1

Exercice 3 Donner l'écriture décimale des nombres suivants codés en complément à deux sur un octet :

00011001
11100111

Correction

Le nombre 00011001 est un entier positif, il correspond en écriture décimale à

1+8+16

=

25

.
Le nombre 11100111 est un entier négatif, prenons donc son complément 00011000 et ajoutons 1 : 00011001 qui est en décimale le nombre 25. Ainsi 11100111 correspond en décimale à

-25

.
On peut vérifier ce résultat en additionnant les deux écritures binaires.

Exercice 4 Additionner les nombres suivants, écrits en complément à deux : 00101110 et 11111001. On donnera le résultat en écriture binaire en complément à deux, puis en base 10.

Correction

Le nombre 00101110 correspond en base 10 à 46.
Le nombre 11111001 a pour complément 00000110, auquel en ajoutant 1 on obtient 00000111 ce qui correspond en base 10 à

7

. Ainsi le nombre 11111001 correspond à

-7

.
Or,

46+(-7)

=

39

, et le nombre 00100111 correspond bien à 39 en décimale.

3.2Codage d'un flottant Nous ne pouvons pas coder sur un ordinateur tous les nombres réels. En effet, ceux qui possèdent une infinité de chiffres dans leur écriture ne peuvent être stockés sur un support fini. Il existe cependant un type de variable pour gérer les nombres possédant des chiffres après la virgule. Ce type s'appelle flottant ou float en anglais.
Le principe est le même que celui suivi par les calculatratices en mode scientifique, la seule différence étant qu'à la fin de l'écriture ce n'est pas l'exposant de 10 qui est donné, mais celui de 2.
Nous n'avons pas dans ce cours à comprendre tous les détails mais tout a été établi dans une norme internationale appelée IEEE-754 qui décrit le codage d’un flottant (≃nombre réel) sur 32 bits :

le bit de poids fort correspond au signe,
les 8 bits suivants correspondent à l'exposant de 2, avec un décalage de 127 (pour éviter des exposants négatifs) : "codage sur 8 bits" = "exposant" + 127,
les 23 derniers bits permettent de coder la mantisse, c'est-à-dire les chiffres significatifs, sans complément à deux, où le premier bit significatif qui vaut nécessairement 1 est "caché" pour gagner de la place en mémoire (comme dans l'écriture scientifique où le premier chiffre n'est jamais 0 et en binaire, si le premier chiffre n'est pas 0, il vaut forcément 1).

Exemple 12 Considèrons le nombre codé en IEEE-754 :

Il est négatif car le bit de poids fort vaut 1.
Le codage pour l'exposant de 2 est : 10100111, ce qui correspond à 167 en décimale. L'exposant vaut donc $167-127$ $=$ $40$
la mantisse code : 1,01011.

Notre nombre correspond donc à :

-1,01011\times2^{40}

=

$- \left(2^{40}+2^{38}+2^{36}+2^{35}\right)$

\simeq

-1.47746875\times10^{12}

. Exemple 13 Essayons maintenant de donner le codage dans la norme IEEE-754 du nombre 13,6₁₀.
Le bit de poids fort sera 0 car le nombre est positif.
Pour la mantisse déterminons tout d'abord l'écriture binaire de 13,6.
Tout d'abord nous avons que : 13₁₀ = 1101₂.
Il nous reste à déterminer l'écriture binaire de 0,6. Les choses sérieuses commencent ici. Nous allons procéder de manière algorithmique en retirant les puissances de 2 négatives de 0,6. Dès que le résultat est positif on retient cette puissance et on continue avec le reste obtenu, jusqu'à arriver à 20 chiffres après la virgule (la partie entière étant déjà composée de 4 chiffres et que nous codons la mantisse sur 23 chiffres, sachant que le premier bit est caché).

$0,6-2^{-1}$ $=$ $0,1$ $>0$ donc nous sommes à 1101,1.
$0,1-2^{-2}$ $<0$ , le codage est alors : 1101,10.
$0,1-2^{-3}$ $<0$ , le codage est alors : 1101,100.
$0,1-2^{-4}$ $=$ $0,0375$ $>0$ , le codage est alors : 1101,1001.
$0,0375-2^{-5}$ $=$ $0,00625$ $>0$ , le codage est alors : 1101,10011.
$0,00625-2^{-6}$ $<0$ , le codage est alors : 1101,100110.
$0,00625-2^{-7}$ $<0$ , le codage est alors : 1101,1001100.
$0,00625-2^{-8}$ $=$ $0,00234375$ $>0$ , le codage est alors : 1101,10011001.
$0,00234375-2^{-9}$ $=$ $3,90625\times10^{-4}$ $>0$ , le codage est alors : 1101,100110011.

En poursuivant de la sorte on finit par obtenir le codage : 1101,10011001100110011001
Ainsi, il nous faut coder 101,1001100110011001100 (avec le bit caché). On doit donc décaler la virgule de trois rangs vers la gauche c'est-à-dire avoir un exposant égale à 3. Avec le décalage de 127, l'exposant sera codé à 130₁₀ ce qui correspond à 10000010₂.
Le nombre 13,6₁₀ s'écrit dans la norme IEEE-754 :

Exemple 14 Voici un algorithme Python faisant la conversion nombre en base 10 / écriture en IEEE-754.

xxxxxxxxxx
 
import math
​
x = input()
x = float(x)
​
​
​
def entB(n):
    result = ""
    if n < 2:
      result = str(n)
    else:
      quotient = n
      while quotient != 0:
        reste = quotient % 2
        result=''.join([str(reste), result])
        quotient = quotient/2

Exécuter