Cours Codage binaire - yalamaths.free.fryalamaths.free.fr/documents/isn/RepresentationInformation/TleS_ISN... · Cours de Mr JULES v1.0 Classe de Terminale S spécialité ISN Page

Cours de Mr JULES v1.0 Classe de Terminale S spécialité ISN Page 1 sur 19

NOM et prénom : …………………………………………… Terminale S spécialité ISN

CODAGE BINAIRE

I. Un peu de Théorie de l’Information. ___________________________________________________ 2

II. Codage de l’Information. ____________________________________________________________ 4

III. Le codage binaire. ________________________________________________________________ 6

IV. L’Octet. _________________________________________________________________________ 7

V. Codage binaire des nombres : Décodage - encodage. _____________________________________ 10

VI. Bilan des acquisitions. ____________________________________________________________ 19

Matériel :

Pré-requis pour prendre un bon départ :

Puissances de 2

Division euclidienne (entière)


I. UN PEU DE THEORIE DE L’INFORMATION.

« L'informatique est un domaine d'activité scientifique, technique et industriel concernant le traitement

automatique de l'Information par l'exécution de programmes informatiques par des machines. » (Wikipédia)

On a déjà vu le traitement automatique (partie Algorithmique) et l’exécution de programmes (partie

Langages et Programmation). Intéressons-nous plus en détail à l’Information.

A. L’Information, c’est quoi ?

C’est une question très difficile et la littérature est abondante sur ce sujet, donc je ne m’hasarderai pas à

donner une définition catégorique. Essayons quand même :

« L’Information est contenue dans toutes choses matérielles ou immatérielles (situations, évènements) :

c’est tout ce qui permet de caractériser cette chose ou cet évènement. »

Plusieurs remarques se dégagent :

l’Information est immatérielle : ce ne peut être une masse ou une énergie.

L’Information n’est pas la chose mais elle lui donne ses caractéristiques, son sens, son essence ?

L’Information n’a d’intérêt que parce qu’elle peut être communiquée.

B. Représentations de l’Information :

Intéressons-nous à la dernière remarque ci-dessus.

Pour pouvoir être communiquée, cette Information pure doit être inscrite dans le monde réel en étant

associée à un objet concret appelé support. Ce support va subir une modification physique.

C’est cette modification physique du support qui va représenter l’Information.

Exemples : dans une représentation de l’Information sous forme de texte : le support sera le papier et les

modifications physiques seront les traces d’encre qui y sont déposées ; dans une représentation de la même

Information sous forme de chanson, le support est l’air ambiant et les modifications physiques sont les

vibrations sonores provoquées par les mots et la musique.

Bien sûr, il faut que ces modifications physiques (traits de stylo, paroles prononcées) obéissent à

certaines règles pour que ces représentations de l’Information conservent du sens : on parle de codage de

l’Information.

Toute représentation de l’Information est l’association d’un support et d’un codage.

Les modifications physiques du support forment des signes ou signaux constituant un message.

L’Information pure est la signification de ce message.

Le codage est la correspondance entre les signes constituant le message et la signification du message.

Les ordinateurs manipulent les signes des représentations sans comprendre le sens du message. C’est là

leur force : ils traitent les signes à toute vitesse sans être arrêtés par les significations, sans états d’âme !


C. Problématique des représentations :

Souvent, on confond l’Information (le contenu informatif de la chose) et les représentations qu’on peut en

faire afin de communiquer cette Information. Par exemple : l’évènement « Seconde Guerre Mondiale »

contient une grande quantité d’informations. Un film, un livre ou un site internet ne peuvent en être que des

représentations partielles.

1. Il est impossible de représenter parfaitement toute l’Information :

Une représentation est forcément partielle, subjective et imparfaite :

partielle : l’Information contenue étant quasi infinie, celui qui veut la communiquer doit opérer des

choix restrictifs dans sa représentation.

subjective : qui dit choix dit forcément subjectivité de ce choix. Une représentation ne peut donc être

totalement objective malgré toute l’honnêteté qu’on peut y mettre.

imparfaite : même la partie retranscrite ne peut être parfaite ! En effet, la transcription de

l’Information sur un support selon un certain codage fait plus ou moins perdre de l’Information,

donc de la signification.

Exemples : Un tableau est une représentation en 2D d’une réalité en 3D ; …………….......................

…………………………………………………………………………………………………………..

2. Il n’y a pas unicité des représentations :

Variété des supports (disques durs, livres, …………………………………………).

D’un côté, cette variété produit une richesse tant patrimoniale que culturelle ou pédagogique.

Mais d’un autre côté, cela oblige les citoyens à maîtriser les langages liés à ces supports.

Variété des codages pour un même support : ………………………………………………………

3. Quelle problématique se dégage concernant les représentations ?

Nous laisserons à d’autres champs d’étude les problèmes d’ordre philosophique (partialité et

subjectivité des représentations) et éducationnel (maîtrise des différentes formes de communication liées

aux différents supports) pour nous concentrer sur le problème technique du codage de l’Information sur un

support.

Une foule de questions se posent alors :

o S’il existe plusieurs codages de l’Information pour un même support, par quels critères les

différencie-t-on ?

o Peut-on décider qu’un codage est meilleur qu’un autre et selon quel critère ?

o L’Information contient forcément des données. Quelles données sont représentables ?

o Existe-t-il un codage qui peut « unifier » des supports a priori différents ?


II. CODAGE DE L’INFORMATION.

A. Choix du codage :

Un codage fait la correspondance entre les signes ou signaux constituant le message et le sens de ce

message.

Les critères vous semblent importants pour le choix d’un bon codage ?

…………………………………………………………………………………………………………………..

Parmi les 9 codages suivants quel est celui qui vous semble le mieux correspondre à ces critères :

codage à base de signes inventés codage à base d’odeurs codages à base de phrases

codage à base de mots codage à base de sons codages à base de mimiques du visage

codage à base de nombres codage à base de signaux lumineux codage à bases A, T, C, G.

Donc, du fait de leur universalité, de leur caractère simple et pratique, de leur non ambiguïté, de leurs

propriétés structurelles et calculatoires, on choisit évidemment un codage à base de ………………………

B. Données représentables avec un codage numérique :

Toutes les données numériques évidemment !

Les textes ?

Les sons ?

Les images ? Les couleurs ?

Les odeurs ?

Les sensations ? Les sentiments ? L’Intelligence ?

Le Monde est-il nombre ? On peut se poser la question…

C. Quel codage numérique ?

On va donc utiliser de nombres pour transcrire foultitude d’informations.

Mais comment ces nombres eux même seront-ils écrits ? Se pose donc la question de combien de

………………………… on va utiliser pour écrire ces nombres.

1. Nombre minimum de chiffres nécessaires au codage numérique :

Il faut évidemment au moins 1 chiffre pour écrire des nombres. 1 chiffre est-il suffisant ?

Supposons donc qu’il n’y ait qu’un seul chiffre pour coder l’Information, le chiffre 1 par exemple.

Par exemple une vache serait codée 1, une poule : 11, une image : 111, une autre image : ……..

Comme il n’y a qu’un seul chiffre, la seule façon de différencier les choses est de jouer sur la

………………………………. du nombre.

Donc toute chose serait représentée par une suite plus ou moins longue de chiffres 1 !

Quel problème cela pose-t-il concrètement ? …………………………………………………………………

Donc le nombre minimum de chiffres pour coder l’Information n’est pas 1 mais ….. au minimum.

Mais peut-être est-ce 3, 4, 10 chiffres voire plus !! Voyons cela dans ce qui suit.


2. Pas 1, pas 10 mais … :

L’idée la plus naturelle serait de choisir …… chiffres pour le codage numérique de l’Information

comme on a choisi pour base de notre numération.

Mais est-ce un bon choix ? Dans un monde abstrait et parfait comme celui des Maths : ………… ! Mais

qu’en serait-il dans la monde concret, réel des humains et des machines en particulier ?

Les ordinateurs, et par extension toute machine dédiée au traitement de l’Information : systèmes

embarqués, robots, smartphones, automates etc., fonctionnent à l’électricité.

Donc chaque chiffre permettant de coder l’Information va être représenté par un état électrique, la tension

électrique en l’occurrence.

Si on choisit 10 chiffres pour coder l’Information, alors il faut qu’il y ait 10 tensions significatives

différentes qui leur correspondent. Plus exactement vu que la tension est continue : les 10 chiffres doivent

correspondre chacun à 10 intervalles significatif de tensions.

Par exemple la plage [0 volt ; 1 volt[ correspondrait au chiffre 1, la plage [1,1 volts ; 3 volts[ correspondrait

au chiffre 2, etc.

Et donc, si l’ordinateur « mesure » 0,95 volts, il « lit » théoriquement le chiffre ……

Seulement voilà, nous sommes dans le monde réel et dans le monde réel, qui dit « mesure », dit

imprécisions liées aux parasites électriques, à la précision du mesureur de la machine etc.

Supposons que cette incertitude soit de 0,2 volts. En reprenant l’exemple précédent, l’ordinateur « lit »

toujours le chiffre 1, mais peut-être était-ce en réalité le chiffre ……. que l’ordinateur devait lire !

Il y a donc ambiguïté de la lecture ! Impardonnable, cela entraînerait bug sur bug dans les programmes !

Il n’y a que 2 façons possibles de remédier à ce problème de mesure lié à l’incertitude :

o soit diminuer l’incertitude de la mesure de la tension :

Impossible car cela dépendrait de chaque machine !

o soit augmenter la distance entre les intervalles significatifs de tension.

Ce qui revient forcément à diminuer le nombre de chiffres codant l’Information !

La distance entre les intervalles significatifs de tension est maximum lorsqu’il n’y a que …… chiffres

codant l’Information !

Ces 2 seuls chiffres codant numériquement l’Information seront donc :

o le chiffre ....... qui correspondra à la tension 0 (pas de courant).

o le chiffre ....... qui correspondra à la tension d’alimentation (il y a du courant).

Voilà donc pourquoi les ordinateurs fonctionnent en binaire.


III. LE CODAGE BINAIRE.

A. Définitions et vocabulaire :

1. Le codage numérique ayant pour base les deux chiffres ..... et ..... s’appelle le codage binaire ou

langage machine.

2. Toute information est représentée dans la machine par une suite de 0 et/ou de 1.

3. Cette suite quelconque de 0 et/ou de 1 s’appelle un nombre binaire ou mot binaire1.

4. Chaque chiffre de ce nombre binaire s’appelle un bit (binary digit).

Le bit est donc la plus petite quantité d’information manipulable par une machine.

Le bit est l’Unité élémentaire de quantité d’Information.

Le bit ne peut prendre que deux valeurs : 0 ou 1.

5. Le bit commençant un nombre binaire (écrit le plus à gauche) s’appelle le bit de poids le plus fort.

6. Le bit terminant un nombre binaire (écrit le plus à droite) s’appelle le bit de poids le plus faible.

Cette dualité du bit peut correspondre à plusieurs types de situations :

o nombres 0 ou 1 (numérique)

o faux ou vrai (logique)

o ouvert ou fermé (interrupteur)

o nord ou sud (magnétique)

o noir ou blanc (optique)

o absence ou présence de trou (carte perforée)

B. Nombre maximum d’états distincts codables avec N bits :

La mémoire des ordinateurs est constituée d’une multitude de petits circuits électroniques ne pouvant être

chacun que dans deux états représentés par 0 (absence de tension électrique) ou 1 (présence d’une tension

électrique). Un tel circuit à deux états s’appelle circuit mémoire un bit ou commutateur.

L'assemblage de ces commutateurs permet de réaliser les opérateurs logiques de base qui permettront à leur

tour de concevoir des systèmes complexes.

Soit donc une mémoire d’ordinateur composé de plusieurs commutateurs (circuits mémoire un bit). L’état

de cette mémoire se traduit par une suite finie de 0 et de 1. Par exemple, le mot binaire 100 décrit l’état

d’une mémoire composé de trois commutateurs, respectivement dans les états 1, 0 et 0.

Un circuit mémoire est constitué de 6 commutateurs, un autre de 10 commutateurs.

Quel est le nombre d’états possibles de la mémoire dans chaque cas ? ……................................

Plus généralement pour un ordinateur dont la mémoire est constituée de N commutateurs. …….

1 Mot binaire fait ici référence au langage binaire. Mot binaire se comprend comme motif composé de 0 et de 1, séquence de 0 et de 1 etc.


C. Nombre de bits nécessaires au codage de k valeurs distinctes.

La Nature a choisi une autre base pour le codage de l'ADN. Laquelle ? ..........................................

Si l’on devait recoder en langage machine ce codage en base 4, combien de bits faudrait-il ? …….

Un circuit mémoire doit être capable de manipuler les représentations binaires d’un jeu de 52 cartes.

De combien de commutateurs minimum doit être composée cette mémoire ? …………

Plus généralement, calculer le nombre minimum N de bits pour coder k états distincts ?

Les performances du tableur Excel de Microsoft ont augmenté avec la montée en gamme des processeurs.

Voici quelques spécifications pour Excel 2003 et Excel 2016 :

Excel 2003 Excel 2016

spécification codée sur ... bits spécification codée sur ... bits

Nb de lignes 65 536 1 048 576

Nb de colonnes 256 16 384

Nb max de caractères

par cellule 32 767 32 767

Nb max de caractères

par formule 1024 8 192

Le codage en binaire explique pourquoi on n’a pas de nombres « ronds » comme spécifications.

IV. L’OCTET.

A. Regroupement des bits par paquets :

On rappelle qu’un mot binaire est une suite plus ou moins longue de 0 et de 1.

Voici un motif binaire (c-à-d un mot binaire, un nombre en langage machine) : 1000111111000000

Sur combien de bits est-il codé ? Dit autrement combien de chiffres binaires a-t-il ? …….

Est-il facile à lire et à écrire ? ……

De même que pour écrire plus lisiblement 123456789 en écriture décimale, on écrit 123 456 789, on va

regrouper par paquets les bits. Mais par paquets de combien ?

La réponse à cette question est liée intimement à l’histoire des processeurs des ordinateurs. Comme le

codage binaire est un système à base 2, les processeurs (et les systèmes d’exploitation associés) ont traité

d’abord des paquets de 1 bit, puis 2 bits, puis 4 bits, puis …. bits, puis ….. bits etc.

Historiquement, le choix a été fait d’écrire les nombres binaires par paquets de ……. bits.

Un regroupement de 8 bits s’appelle un Octet.

L’écriture en octets rend l’écriture binaire plus lisible.


Applications :

1. Réécrire le nombre précédent en faisant apparaître les octets : ……………………………..

2. Réécrire le mot binaire 1110001011 sur 2 octets quitte à compléter son écriture à gauche (par des 0

supplémentaires : …………………………………………

3. Les systèmes modernes d’exploitation (Windows 64 bits par exemple) manipulent des mots codés sur 64

bits. Combien cela fait-il d’octets ? …….

B. Une nouvelle unité d’Information :

1. Définition de l’Octet :

Rappel : d’après la p.6, la plus petite Unité de quantité d’Information est le ……

L’octet, outre son caractère pratique, permet de définir une nouvelle unité de quantité d’Information :

L’Octet est une autre Unité de quantité d’Information : celle formée à partir de 8 bits.

L’Octet est l’unité qui a été choisie pour représenter les capacités mémoire.

Attention : En anglais un octet s’écrit byte (parfois Byte avec une Majuscule), ce qui ressemble à bit !

2. Multiples de l’Octet :

Depuis Décembre 1998, l’International Electrotechnical Commission (IEC) a grandement simplifié les

conversions entre les multiples de l’Octet : celles-ci doivent suivre les mêmes principes que les conversions

en système décimal (multiplication ou division par 10 pour passer d’une colonne à une colonne adjacente).

Giga

octet

(Go)

Méga

octet

(Mo)

kilo

octet

(ko)

octet

D’après ce tableau de conversion (attention aux majuscules) :

1 ko = 1 …………… octet = 10 3

octets = mille octets.

1 Mo = 1 ……………. octet = 10…

octets =

1 Go = 1 …………….. octet = 10…

octets =

1 To = 1 ……………... octet = 10…

octets =

Attention !

Avant la standardisation simplificatrice de 1998, 1 kilo octet valait 1 024 octets, 1 Mo valait 1 024 ko,

1 Go valait 1 024 Mo, 1 To valait 1 024 Go etc.


3. Exercices sur les octets :

Un circuit mémoire est composé 32 milliards de commutateurs.

Quelle est la capacité en Mo de cette mémoire ?

Est-ce beaucoup pour un ordinateur actuel ?

Certains fabricants de disques durs entretiennent la confusion entre les Mo ou Go ancienne version et les

Mo ou Go nouvelle version ! Quel pourcentage de tromperie est-il fait en faisant passer des Mo nouvelle

version pour des Mo ancienne version ?

Poids en Mo d’une image.

On verra plus tard que les images sont

constituées de points. L’œil humain ne

distingue plus les points d’une image lorsque

leur densité atteint au minimum 600 points

par pouce (600 dpi) soit environ 560 points

par mm².

Soit donc une image format A4 (21 cm

29,7 cm) dont on ne distingue plus les points.

1. Combien de points au minimum contient cette image ?

2. Chaque point a une couleur codée sur 32 bits. Quel est le poids minimum en Mo du fichier image

correspondant ?

Nous avons maintenant toutes les armes nécessaires pour commencer à numériser nos données.

Evidemment, on commence toujours par le plus simple : les ………………………………

Exemple de densités de points sur une image. On parle aussi de résolution.


V. CODAGE BINAIRE DES NOMBRES : DECODAGE - ENCODAGE.

Nos nombres sont usuellement écrits en base …….. Le codage binaire est lui en base ……

Les 2 questions complémentaires qui se posent sont donc :

Comment convertir de la base 2 vers la base 10 ? Ou, ce qui revient au même,

Comment calculer la valeur d’un nombre écrit en binaire ?

C’est la question du décodage (decoding en anglais).

Inversement, comment convertir de la base 10 vers la base 2 ?

C’est la question de l’encodage (encoding en anglais).

Cette double conversion, décodage-encodage dans une certaine base, s’appuie sur la décomposition

d’un nombre selon les puissances décroissantes de cette base.

Exemple pour le nombre 123 écrit en base 10 qu’on décompose selon les puissances décroissantes de 10 :

123 = 1 100 + 2 10 + 3 1

= 1 10² + 2 101 + 3 10

0

Les chiffres de l’écriture en base 10 sont donnés par les facteurs devant chaque puissance de 10.

La valeur du nombre se trouve en terminant le calcul de cette somme de puissances de 10.

De la même manière :

Les chiffres de l’écriture en base 2 seront donnés par les facteurs devant chaque puissance de 2.

La valeur du nombre écrit en base 2 se trouvera en terminant le calcul de cette somme de puissances de 2.

Voilà donc pour le principe général (valable pour n’importe quelle base d’ailleurs !).

Commençons par le type de nombres le plus simple : les entiers naturels.

A. Décodage - Encodage des nombres entiers naturels :

Les nombres entiers naturels sont codés par une suite de 0 et de 1.

Les chiffres des nombres binaires s’appellent le bit des unités, le bit des deuxaines, le bit des

quatraines, le bit des huitaines, le bit des ………………………. etc.

Il est toujours plus simple d’étudier d’abord le décodage, c-à-d la conversion Base ..... Base .....

1. Base 2 Base 10 : Calcul de la valeur d’un entier naturel binaire.

On part donc d’un entier naturel écrit en binaire, on veut trouver sa valeur.

Calcul de la valeur d’un nombre binaire par somme des puissances de 2 : exemple.

1001 = 1 23 + 0 2

2 + 0 2

1 + 1 2

0 On décompose selon les puissances décroissantes de 2.

= 8 + 0 + 0 + 1 On calcule comme d’habitude en n’oubliant pas que 20 = 1.

= 9

(1001)2 = (9)10 Dit autrement 1001 en base 2 vaut 9 en base 10.


Décodage Base 2 Base 10 : Calcul de la valeur d’un nombre binaire par somme de puissances.

Calculer la valeur de (1011)2 :

(1011)2 =

R= 11

(101101)2 =

Convertir en base 10 les octets suivants :

(1100 1010)2 =

R = 202

(1111 1111)2 =

Vérifier vos résultats avec votre calculette ou la calculette de l’ordinateur en mode programmeur.

Ecrire une méthode permettant de calculer la valeur d’un nb binaire, puis l’algorithme en pseudo-code

« Les Grandes Lignes »

Algorithme en pseudo-code

Comment reconnaît-on l’écriture binaire d’un entier pair ? D’un entier impair ?

Rajouter un chiffre à droite de l’écriture d’un nombre binaire.

En écriture décimale, lorsqu’on rajoute un 0 à droite de l’écriture d’un entier, on multiplie sa valeur par .....

En écriture binaire, rajouter un 0 à droite de l’écriture revient à multiplier la valeur par ……

En écriture binaire, rajouter 00 à droite de l’écriture revient à multiplier la valeur par …….. etc.

En écriture binaire, rajouter un 1 à droite de l’écriture revient à ……………………..


a) Une machine traite les nombres entiers positifs sur 2 bits puis sur 3 bits, puis sur 4 bits, puis sur 5 bits.

Ecrire alors dans chaque cas la plage de nombres entiers potentiellement manipulables :

Codage sur 2 bits 3 bits 4 bits 5 bits

Plage des entiers

représentables de 0 à 3 de 0 à

Que constate-t-on à chaque fois sur la plus grande valeur représentable ?

b) Plus généralement, une machine code les entiers positifs sur n bits.

Montrer que la plus grande valeur représentable est 2n 1.

(aide : somme des n premiers termes d’une suite ………………………………..)

c) Les processeurs manipulent les données binaires selon une taille en bits standard.

Plus cette taille est longue, plus la plage d’entiers représentables est grande.

Plus cette taille est longue, plus le processeur est rapide car les données qu’il peut traiter à chaque cycle

d’horloge sont plus nombreuses.

Calculer la plage d’entiers manipulables pour les processeurs « historiques » suivants :

Processeur 8 bits 16 bits 32 bits 64 bits

Plage d’entiers

représentables de 0 à de 0 à


2. Base 10 Base 2 : Encodage des entiers naturels.

Plutôt qu’un long discours théorique, le mieux est de voir comment faire sur un exemple :

On veut convertir l’entier naturel 53 en base 2.

Il s’agit donc de trouver les facteurs devant les puissances de 2 dans la décomposition de 53 en base 2.

53 = etc. + c 22 + b 2

1 + a 2

0

Il s’agit donc de trouver son bit « a » des unités, son bit « b » des deuxaines, son bit « c » des quatraines etc.

Pour trouver tous ces chiffres binaires, 2 méthodes existent :

1ère

méthode : Par une suite de questions (par une suite de soustractions successives).

Quelle est la plus haute puissance de 2 que je peux mettre dans 53 ? 25 car 2

5 = 32 53 mais 2

6 = 64 > 53.

Est-ce que je peux mettre 24 = 16 dans le reste 21 (= 53 32) ? Oui.

Est-ce que je peux mettre 23 = 8 dans le reste 5 (= 21 16) ? Non.


Est-ce que je peux mettre 21 = 2 dans le reste 1 (= 5 4) ? Non.


Et il reste 0. Donc la série de questions s’arrête.

On a 53 = 1 25 + 1 2

4 + 0 2

3 + 1 2

2 + 0 2

1 + 1 2

0

L’écriture binaire de 53 est : (53)2 = 11 0101 = 0011 0101 (sur 8 bits)

Dans quel ordre obtient-t-on les bits ?

Par cette méthode par questionnement, trouver l’écriture binaire sur un octet de 47 : (47)2 =

Retranscrire les grandes étapes de cette méthode puis écrire l’algorithme correspondant en pseudo-code :

«Les Grandes Lignes »


Soit N un entier qu’on veut encoder en binaire grâce à cet algorithme. En considérant le nombre de

comparaisons effectuées lors du traitement, évaluer en fonction de N la complexité de cet algorithme :


2ème

méthode : Par une suite de divisions entières successives.

On garde notre exemple 53 comme nombre de départ.

La méthode précédente renvoyait les bits cherchés dans l’ordre naturel d’écriture (« de la gauche vers la

droite ») : du bit de poids le plus fort jusqu’au bit de poids le plus faible.

On veut une méthode qui trouve les bits dans l’ordre inverse (« de la droite vers la gauche ») : du bit de

poids le plus faible jusqu’au bit de poids le plus fort.

On commence donc d’abord à chercher le bit de poids le plus faible c-à-d le chiffre des unités.

Le chiffre des unités est ce qu’il reste après avoir formé le maximum de paquets de 2 dans 53. Le chiffre des

unités est donc le reste dans la division euclidienne par 2 de 53.

Le chiffre des deuxaines est ce qu’il reste après avoir reformé le maximum de gros paquets de 2 avec les

précédents petits paquets de 2. Le chiffre des deuxaines est donc le reste dans la division euclidienne par 2

du quotient trouvé à l’étape précédente.

Et ainsi de suite jusqu’à ce qu’on ne puisse plus reformer de gros gros ... paquets de paquets de paquets etc.

La méthode apparaît donc comme une …………………… de …………………………. successives :

o Que va-t-on diviser successivement ? Les …………………………..

o Par combien divisera-t-on successivement ces quotients ? Toujours par …….

o Quand arrête-t-on le processus ? ………………………………………………………………………

o Les bits cherchés sont les ………………………………………………………………………………

Concrètement voici ce que cette méthode donne pour 53 :

Par cette méthode par divisions successives, trouver les écritures binaires sur 8 bits de 25 puis 70 :

Stop

(53)10 = (0011 0101)2 sur 8 bits

Attention à l’ordre d’écriture inversé ! bit des unités

bit des deuxaines

(25)10 =

bit des ……………

1 26

0 13

2

2

1 6

2

0 3

2

1 1

2

1 0

2

53

25 2

70 2


Ecrire les grandes étapes de cette méthode puis écrire l’algorithme correspondant en pseudo-code :

« Grandes Lignes »


Soit N un entier qu’on veut encoder en binaire grâce à cet algorithme. En considérant le nombre de

comparaisons effectuées lors du traitement, évaluer en fonction de N la complexité de cet algorithme :

Comparaison des 2 méthodes :

Par questions successives

(ou soustractions successives) Par divisions successives

Avantages

Inconvénients

Ordre de sortie

des chiffres

Complexité de

l’algorithme


B. Encodage des nombres entiers relatifs (dits signés) :

Un entier relatif a un signe + ou un signe devant sa …………………………................... Exemple : ......

En binaire, on ne peut pas ajouter bêtement un signe devant l’écriture binaire !

Donc l’un des bits doit jouer le rôle de signe : le bit de poids le plus …………….. évidemment.

1. Plage d’entiers relatifs représentables :

Ce bit de signe a pour conséquence d’enlever un bit pour le codage de la valeur absolue.

Par exemple, pour le codage des nombres relatifs sur 8 bits, il y aura le bit le plus à gauche pour le signe

(soit 0 pour le signe +, soit 1 pour le signe ) et il ne restera que 7 bits pour la valeur absolue.

Le plus petit nombre positif sur 8 bits s’écrit en binaire …………………....… et vaut évidemment + 0 !

Le plus grand nombre positif sur 8 bits s’écrit en binaire …………………..… et vaut +127.

Donc les nombres entiers positifs codables sur 8 bits vont de 0 à +127 inclus soit 128 entiers positifs.

Par symétrie, il y aura aussi 128 entiers négatifs codables en 8 bits : 1 ; 2 ; etc. jusqu’à ….….. et non …..

Processeur 8 bits 16 bits 32 bits

Plage d’entiers

naturels

représentables

de 0 à 255 de 0 à 65 535 de 0 à 4 294 967 295

Plage d’entiers

relatifs

représentables de 128 à +127

de

à de −2 147 483 648 à +2 147 483 647

2. Encodage des entiers positifs :

Leur écriture commence par 0. Puis leur valeur absolue s’écrit comme pour les entiers naturels sans signe.

3. Encodage des entiers négatifs :

Pour l’instant, on sait juste que l’écriture des entiers négatifs commence par ….. pour indiquer le signe ….

Mettons-nous sur 3 bits pour simplifier les exemples :

1er

essai : Prendre l’écriture des entiers positifs et changer juste leur bit de signe ? Essayons :

+2 s’écrit 010 donc 2 s’écrirait 110. +1 s’écrit 001 donc 1 s’écrirait 101

La moindre des choses est que la somme de 2 nombres opposés fasse 0 ! Vérifions donc si la somme en

binaire de ces paires de nombres opposés donne 000 (c-à-d 0).

Les additions posées en binaire se calculent de la même façon qu’en décimal. Sauf pour les retenues qui

apparaissent dès qu’on obtient 2 (3). On pose alors 0 (1) et on retient 1 dans la colonne gauche suivante.

Si une retenue déborde tout à gauche de la représentation, elle est tout simplement ignorée !

On a bien +2 + (2) qui vaut 000 (la petite retenue 1 étant tout simple ignorée car elle sort tout à gauche de

la représentation sur 3 bits) mais hélas, +1 + (1) ne vaut pas 000 !

Donc dans l’encodage des entiers négatifs, un changement du bit de signe ne suffit pas !

0 1 0 (+2)

+ 1 1 0 (2)

1 0 0 0

0 0 1 (+1)

+ 1 0 1 (1)

1 1 0


2ème

essai :

La question qui se pose est donc la suivante :

Quand on fait la somme d’un nombre et de son opposé, comment être sûr d’obtenir à chaque fois 000 (ou ce

qui revient au même 1 000 sur 3 bits avec un petit 1 en retenue qui déborde tout à gauche) ?

On sait en tous cas à coup sûr obtenir 111 ! En effet, en partant de n’importe quelle écriture sur 3 bits, si on

lui ajoute son écriture complémentaire (chaque 0 est changé en 1 et vice versa), on obtient forcément 111 !

Maintenant, pour obtenir 000, il faut 1 de plus ! En effet 111 + 001 donne 1 000 soit 000.

Donc l’opposé doit être le complémentaire + 1. Vérifions dans nos 2 exemples :

Technique du complémentaire à 2

L’écriture binaire de l’opposé d’un entier positif s’obtient de la façon suivante :

1) Ecrire l’entier positif en binaire signé.

2) Prendre son complémentaire.

3) Rajouter 1.

Quelques remarques :

1. Pourquoi parle-t-on de complémentaire à 2 ?

Parce que d’abord on complémente à 1 (le complémentaire) puis qu’on rajoute 1.

2. Avec la complémentation à 2, on obtient toutes les écritures des entiers négatifs qui ont un symétrique

positif (de 3 à 1 dans notre cas). Mais comment obtient-t-on la représentation du plus petit entier

négatif 2n 1

(4 dans notre cas) qui n’a pas de symétrique positif dans la représentation ?

On prend la représentation de l’avant dernier négatif (3 dans notre exemple) et on enlève 1.

On trouve toujours une écriture de type 100 etc.00 (100 dans notre cas pour 4).

3. On remarque d’ailleurs que l’écriture binaire du plus petit entier négatif représentable est celle du

premier entier positif hors de la plage représentable (l’écriture de 4 est 100 qui la même que celle

de 4 qui est en dehors de l’intervalle représentable des entiers de 4 à 3 sur 3 bits), que l’écriture binaire

du 2ème

entier négatif représentable est le 2ème

entier positif hors de la plage représentable etc.

Application : Un processeur travaille sur 4 bits.

1) Quelle est la plage d’entiers signés manipulables par le processeur ?

2) Donner les écritures sur 4 bits de 5 et 5 ; de 7 et 7 ; de 8.

0 0 1

+ 1 1 0

1 1 1

0 1 0

+ 1 0 1

1 1 1

0 1 0 (+2)

+ 1 1 0 (2)

1 0 0 0

En repartant des

exemples +2 et +1 :

0 0 1 (+1)

+ 1 1 1 (1)

1 0 0 0


C. Encodage des autres types de nombres :

Rechercher des informations sur l’encodage des décimaux, des rationnels et des réels.


VI. BILAN DES ACQUISITIONS.

A la fin de ce livret, je dois savoir :

Représentation et codage en binaire (9 compétences)

Expliquer pourquoi les machines travaillent en binaire.

La définition d’un bit, d’un octet, d’un mot binaire.

Trouver combien de bits il faut pour représenter n états distincts.

Calculer en octets, Mo, Go, To etc. le poids d’une quantité d’information.

Les conversions binaires Base 10 Base 2.

Les conversions hexadécimales Base 10 Base 16.

Les conversions hexadécimales Base 2 Base 16.

Ecrire un algorithme de conversion en binaire d’un nombre entier.

Ecrire la représentation binaire d’un nombre entier signé.

Quelle est la suite logique de ce livret ? « Numérisation des données non …………………………. ».

Perles des hotlines informatiques :

« Secrétaire - J'ai un problème avec Windows.

Hotline - Qu’avez-vous sur l'écran ?

Secrétaire - Euh... un pot de fleur.

Hotline - Non, je veux dire "Qu'est-ce qui est écrit ?".

Secrétaire - Ha d'accord... euh... Sony. »

« Client - Vous me dites "pas de majuscules pour le mot de passe", c'est bien ça ?

Hotline - Exact.

Client - Et, les chiffres, je les mets en minuscule aussi ? »

Documents

Cours Codage binaire - yalamaths.free.fryalamaths.free.fr/documents/isn/RepresentationInformation/TleS_ISN... · Cours de Mr JULES v1.0 Classe de Terminale S spécialité ISN Page