Fiche de révision : Arithmétique et codage binaire

📋 Plan du Cours

1. Repères historiques de l’informatique
2. Architecture de Von Neumann
3. Machine de Turing
4. Information et codage binaire
5. Bases et conversions numériques
6. Codes BCD et Gray
7. Codes décimaux et codes spécialisés
8. Opérations arithmétiques binaires
9. Représentation des nombres signés
10. Arithmétique en complément à 1
11. Arithmétique en complément à 2
12. Extension de signe et débordement
13. Représentation des nombres réels
14. Codage des caractères
15. Codages internes des données
16. Exemples de décodage
17. Codage et cryptage

📅 Repères chronologiques

1. -3000Le symbole chinois de Fou-Hi représente les huit premiers nombres par des traits continus ou interrompus, préfigurant le codage binaire.
2. 1936Alan M. Turing publie un document sur les nombres calculables et propose la machine de Turing, modèle formel de calculateur.
3. 1941Konrad Zuse met au point le Z3, présenté comme le premier calculateur binaire programmable entièrement automatique et le premier véritable ordinateur.
4. 1945John Von Neumann décrit l’EDVAC (Electronic Discrete Variable Automatic Computer).
5. 1947Le transistor est inventé.
6. 1971Intel met en vente le premier microprocesseur.

📖 1. Repères historiques de l’informatique

★ À maîtriser

• Créé en 1946 par P. Eckert et J. Mauchly, l’ENIAC comporte 19 000 tubes à vide, pèse 30 tonnes, occupe 172 m², consomme 140 kilowatts, fonctionne à 100 KHz et réalise environ 330 multiplications par seconde.

Compléments

• La Pascaline, mise au point par Pascal en 1642 pour aider son père collecteur d’impôts, effectue des additions et des soustractions et est souvent considérée comme l’ancêtre de l’ordinateur.

• En 1991, Tim Berners-Lee crée le protocole Internet HTTP (World Wide Web www) et le noyau Linux 0.01 apparaît.

📖 2. Architecture de Von Neumann

🔑 Notions clés & Définitions

• Mémoire centrale : Une suite de cases numérotées contenant chacune une instruction, un morceau d’instruction ou une donnée ; le numéro d’une case est son adresse.

★ À maîtriser

• L’architecture de Von Neumann, définie en 1944, comprend l’unité centrale de traitement, l’unité de stockage et l’unité d’entrées/sorties.

• L’unité centrale de traitement comprend l’unité arithmétique et logique (UAL) et l’unité de contrôle (UC).

• L’UAL effectue les calculs arithmétiques, les opérations logiques, les comparaisons et, parfois, les rotations et décalages de valeurs.

• L’UC contrôle le déroulement du programme en prenant les instructions en mémoire, en les décodant et en donnant ses ordres à l’UAL ; les résultats peuvent modifier le choix de l’instruction suivante.

• Avec des adresses sur $k$ bits, on peut adresser $2^k$ mots ; si chaque mot vaut un octet, la capacité correspondante est $2^k$ octets.

• L’exécution d’un programme suit les étapes suivantes.

Compléments

• Les instructions du programme et les données occupent des zones différentes d’une même mémoire physique, dont l’UC contrôle l’accès.

💡 Astuce mémo

Instruction lue, décodée, exécutée, puis résultat rangé

📖 3. Machine de Turing

🔑 Notions clés & Définitions

• Machine de Turing : Un dispositif abstrait proposé par Alan Turing en 1936 pour formaliser la notion d’algorithme ; elle transforme des données inscrites sur un ruban et s’arrête lorsqu’elle atteint un état final F.

★ À maîtriser

• Une machine de Turing comprend : un ruban théoriquement infini à droite portant des symboles, un scanner-marqueur capable de lire et d’écrire, un mécanisme possédant un nombre fini d’états internes

Compléments

• À chaque étape, la machine peut réécrire ou non un symbole, déplacer ou non le ruban d’une case vers la droite ou la gauche, et modifier ou non son état interne.

• Au départ, le mot est cadré à gauche sur le ruban, précédé d’un blanc et suivi d’une suite infinie de blancs, la tête pointe sur son extrémité gauche et le mécanisme est dans son état initial.

📖 4. Information et codage binaire

🔑 Notions clés & Définitions

• Bit : Le plus petit élément manipulable par l’ordinateur et ne peut prendre que la valeur 0 ou 1.

• Codage de l’information : Associer à chaque élément à coder une représentation binaire appelée mot code ; l’ensemble des mots codes constitue le code.

★ À maîtriser

• Les circuits informatiques reposent sur des transistors à deux états, passant et bloquant, conventionnellement représentés par 1 et 0 ; toute information est représentée par une chaîne binaire de bits.

📌 Les données discrètes assemblent des éléments indépendants et dénombrables, tandis que les données continues ou analogiques résultent de la variation continue d’un phénomène physique comme la température, la voix ou l’image.

Compléments

• Une chaîne de 4 bits est un quartet et une chaîne de 8 bits est un octet ; dans une chaîne binaire, le bit le plus à droite est de poids faible et celui le plus à gauche de poids fort.

📐 Formule - Les multiples binaires de l’octet sont $1\,\mathrm{Ko}=2^{10}\,\mathrm{octets}=1024\,\mathrm{octets}$, $1\,\mathrm{Mo}=2^{20}\,\mathrm{octets}=1024\,\mathrm{Ko}$, $1\,\mathrm{Go}=2^{30}\,\mathrm{octets}=1024\,\mathrm{Mo}$, $1\,\mathrm{To}=2^{40}\,\mathrm{octets}=1024\,\mathrm{Go}$, $1\,\mathrm{Po}=2^{50}\,\mathrm{octets}=1024\,\mathrm{To}$, $1\,\mathrm{Eo}=2^{60}\,\mathrm{octets}=1024\,\mathrm{Po}$, $1\,\mathrm{Zo}=2^{70}\,\mathrm{octets}=1024\,\mathrm{Eo}$ et $1\,\mathrm{Yo}=2^{80}\,\mathrm{octets}=1024\,\mathrm{Zo}$.

💡 Astuce mémo

Le discret se dénombre ; l’analogique varie continûment

📖 5. Bases et conversions numériques

★ À maîtriser

📐 Formule - Un nombre naturel écrit avec les chiffres $x_{n-1},\ldots,x_0$ en base $\beta$ vaut $X=\sum_{i=0}^{n-1}x_i\beta^i$.

• Les chiffres autorisés dépendent de la base :

  • base 2 : 0 et 1
  • base 8 : 0 à 7
  • base 16 : 0 à 9 et A à F, avec A=10, B=11, C=12, D=13, E=14 et F=15 en décimal

• La conversion d’un entier décimal en base 2, 8 ou 16 peut s’effectuer par divisions successives : on divise itérativement par la base jusqu’à obtenir un quotient nul, puis on lit les restes de la dernière division à la première.

• Pour convertir une fraction décimale en base β, on multiplie sa partie fractionnaire successivement par β et on relève les parties entières obtenues dans l’ordre ; on s’arrête à la précision voulue ou lorsqu’une séquence se répète.

• Pour convertir un nombre de base β en base 10, on multiplie chaque chiffre par la puissance de β correspondant à sa position et on additionne les produits.

• Pour passer de la base 8 à la base 2, on remplace chaque chiffre octal par son équivalent binaire sur 3 bits ; pour passer de la base 16 à la base 2, on remplace chaque chiffre hexadécimal par son équivalent binaire sur 4 bits.

Compléments

• Avec n chiffres en base $\beta$, le plus grand nombre représentable est $\beta^n-1$, et les nombres représentables vont de 0 à cette valeur.

• La conversion d’un entier décimal en base β peut aussi s’effectuer par soustractions successives : on retire à répétition la plus grande puissance de β inférieure ou égale au reste, puis on lit le nombre de retraits de chaque puissance dans l’ordre décroissant.

• Les équivalences données sont $35_{10}=100011_2=43_8=23_{16}$ et $235_{10}=353_8$.

📖 6. Codes BCD et Gray

🔑 Notions clés & Définitions

• Code DCB : Le code DCB (Binary Coded Decimal) représente chaque chiffre décimal par son équivalent binaire sur 4 bits ; il réécrit les chiffres et ne constitue pas un codage binaire pondéré par les puissances de 2.
• Code de Gray : Un codage dans lequel deux mots consécutifs ne diffèrent que par un seul bit.

★ À maîtriser

📌 En DCB, lorsque la somme de deux chiffres décimaux dépasse 9, on ajoute 6 à la somme pour effectuer l’ajustement décimal.

Compléments

📌 Le DCB facilite le codage et le décodage et n’impose pas de limitation aux grandeurs représentées, mais il consomme davantage de mémoire, ralentit les opérations arithmétiques, ne représente pas les entiers négatifs et laisse 6 combinaisons inutilisées par chiffre.

• Un code de Gray d’ordre n est une permutation des $2^n$ mots de n bits telle que deux mots consécutifs diffèrent d’un seul bit ; l’exemple sur 3 bits est 000, 001, 011, 010, 110, 111, 101, 100.

💡 Astuce mémo

Le BCD réécrit chaque chiffre décimal ; Gray ne change qu’un bit entre voisins

📖 7. Codes décimaux et codes spécialisés

🔑 Notions clés & Définitions

• Code plus 3 : Code obtenu en ajoutant 3 à chaque chiffre décimal avant de le traduire en binaire.

📝 Points essentiels

• Le code biquinaire est un mot de 7 bits contenant exactement deux bits à 1, l’un parmi les deux premiers bits et l’autre parmi les cinq derniers.

📖 8. Opérations arithmétiques binaires

★ À maîtriser

• L’addition, la multiplication, la soustraction et la division binaires se réalisent selon les mêmes principes qu’en décimal.

• L’addition binaire s’effectue de droite à gauche, bit à bit, en reportant les retenues.

• La multiplication binaire s’effectue en additionnant les produits partiels obtenus en multipliant successivement par chaque bit du multiplicateur : multiplier par 0 donne 0 et multiplier par 1 recopie le multiplicande décalé selon la position du bit.

Compléments

• En addition binaire, 0 + 0 donne un résultat 0 et une retenue 0, tandis que 0 + 1 et 1 + 0 donnent chacun un résultat 1 et une retenue 0.

• En soustraction binaire, 0 − 0 et 1 − 1 donnent chacun un résultat 0 et une retenue de report 0.

• En soustraction binaire, 0 − 1 donne un résultat 1 et une retenue de report 1, tandis que 1 − 0 donne un résultat 1 et une retenue 0.

📖 9. Représentation des nombres signés

🔑 Notions clés & Définitions

• Représentation des nombres signés : Codage d’un nombre dans une chaîne binaire de longueur fixée à n bits.
• Convention de la valeur signée : Dans la convention de la valeur signée, le bit de poids fort indique le signe et les n − 1 autres bits codent la valeur absolue.

★ À maîtriser

📌 La convention de la valeur signée permet de représenter les entiers négatifs, mais elle possède deux représentations du zéro, −0 et +0.

Compléments

• Sur 8 bits, +77 s’écrit 01001101 et −77 s’écrit 11001101 en convention de la valeur signée.

• En représentation non signée, les intervalles sur 8, 16 et 32 bits sont respectivement [0, 255], [0, 65 535] et [0, 4 294 967 295].

• En représentation non signée sur p bits, l’intervalle représentable est $[0, 2^p - 1]$.

• En convention de la valeur signée, les intervalles sur 8, 16 et 32 bits sont respectivement [−127, 127], [−32 767, 32 767] et [−2 147 483 647, 2 147 483 647].

• En convention de la valeur signée sur p bits, l’intervalle représentable est $[-(2^{p-1}-1), 2^{p-1}-1]$.

💡 Astuce mémo

Signe et valeur absolue sépare le signe ; le complément à 2 l’intègre au calcul.

📖 10. Arithmétique en complément à 1

📝 Points essentiels

• En complément à 1 sur n bits, un nombre négatif s’obtient en soustrayant sa valeur positive de $2^n - 1$, ce qui revient à inverser tous les bits de sa représentation positive.

📌 Le complément à 1 possède deux représentations du zéro et rend les opérations arithmétiques peu commodes.

📖 11. Arithmétique en complément à 2

🔑 Notions clés & Définitions

• Complément à 2 : Le complément à 2 est la représentation standard des entiers négatifs sur ordinateur ; sur n bits, un nombre négatif −X s’obtient en inversant les bits de +X puis en ajoutant 1.

★ À maîtriser

• En complément à 2 sur n bits, l’intervalle représentable est $[-2^{n-1}, 2^{n-1}-1]$.

• Pour soustraire X à Y en complément à 2, on additionne à Y le complément à 2 de X.

Compléments

• Sur 8 bits, +77 s’écrit 01001101 et −77 s’écrit 10110011 en complément à 2.

• Pour obtenir le complément à 2 de X sur n bits, on calcule $C_2(X)=2^n-X$ ; appliquer deux fois cette opération redonne X.

📌 Le complément à 2 possède une seule représentation du zéro et facilite les opérations arithmétiques, mais l’intervalle représentable reste limité.

• Pour multiplier deux nombres en complément à 2, on multiplie leurs valeurs absolues puis on prend l’opposé du résultat si les nombres ont des signes contraires.

📌 En complément à 2, deux nombres de signes opposés ne provoquent pas de débordement lors de leur addition.

📖 12. Extension de signe et débordement

★ À maîtriser

• Pour étendre un nombre positif en complément à 2, on ajoute des zéros à gauche ; pour étendre un nombre négatif, on recopie son bit de signe dans les nouveaux bits de gauche.

📌 En représentation non signée sur n bits, une somme qui dépasse $2^n-1$ déborde, ce qui correspond à la présence d’une retenue finale.

• En complément à 2, une retenue finale peut apparaître sans débordement, et son absence ne garantit pas l’absence de débordement.

📌 En complément à 2, il y a débordement si les deux retenues associées aux bits de poids fort sont différentes ; si elles sont identiques, il n’y a pas débordement.

Compléments

• Sur 8 bits non signés, 156 + 168 = 324 n’est pas représentable.

📌 En arithmétique non signée, le bit de débordement est pris en compte dans le résultat, tandis qu’en complément à 2 il est écarté du résultat sur la taille fixée.

📖 13. Représentation des nombres réels

🔑 Notions clés & Définitions

• Bit caché : Le bit 1 précédant la virgule dans la mantisse normalisée est implicite et n’est pas codé en machine.

★ À maîtriser

📌 La représentation en virgule fixe place la virgule à une position définie dans le nombre, tandis que la virgule flottante représente les nombres sous forme scientifique avec un exposant.

📐 Formule - En binaire, un nombre flottant normalisé s’écrit sous la forme $\pm 1,M \times 2^{\pm c}$, où M est la mantisse et c l’exposant.

• La norme IEEE 754 définit un format simple précision sur 32 bits et un format double précision sur 64 bits.

• Le format IEEE 754 simple précision répartit ses 32 bits entre 1 bit de signe, 8 bits d’exposant et 23 bits de mantisse.

• Pour additionner des nombres flottants, on aligne les exposants en décalant une mantisse, on additionne les mantisses, on renormalise si nécessaire puis on arrondit la mantisse.

Compléments

• En virgule fixe, les bits à gauche de la virgule représentent les puissances positives de 2 et ceux à droite les puissances négatives de 2.

📌 La virgule fixe offre une plage de nombres représentables limitée et peu de précision après la virgule.

• Le format IEEE 754 double précision répartit ses 64 bits entre 1 bit de signe, 11 bits d’exposant et 52 bits de mantisse.

• En IEEE 754, l’exposant est biaisé par 127 en simple précision et par 1023 en double précision afin de coder une valeur interne positive.

• Pour multiplier des nombres flottants, on multiplie les mantisses, on additionne les exposants, on renormalise si nécessaire, on arrondit la mantisse et on ajuste le signe du résultat.

💡 Astuce mémo

Virgule fixe : position immobile ; virgule flottante : exposant qui déplace l’échelle.

📖 14. Codage des caractères

🔑 Notions clés & Définitions

• Parité paire : La parité paire fixe le bit supplémentaire de façon que le nombre total de bits à 1, bit de parité compris, soit pair.
• Parité impaire : La parité impaire fixe le bit supplémentaire de façon que le nombre total de bits à 1, bit de parité compris, soit impair.

★ À maîtriser

• Le code ASCII représente habituellement les caractères sur 7 bits et permet de coder 128 caractères ; sa première version date de 1963.

• Unicode est un encodage universel visant à représenter les caractères des langues écrites du monde, dans lequel chaque symbole est défini sur 2 octets.

Compléments

• Les 32 premiers codes ASCII sont des caractères de contrôle, les 95 suivants sont des caractères imprimables et le dernier est le caractère de contrôle DEL.

• En ASCII, les codes 65 à 90 représentent les majuscules et les codes 97 à 122 représentent les minuscules.

• Dans la table ASCII, le code numérique d’un caractère s’obtient en combinant le symbole hexadécimal de poids fort donné par la colonne avec celui de poids faible donné par la ligne.

• En ASCII, passer d’une lettre majuscule à la même lettre minuscule s’obtient en ajoutant 32 à son code.

📌 Les tables ASCII étendues propres aux fabricants ont réduit la compatibilité entre ordinateurs, et la norme ISO 8859 a constitué une première tentative de normalisation des alphabets d’Europe occidentale sans éliminer ce problème.

• EBCDIC, utilisé notamment sur les systèmes IBM 370 et 390, code 256 caractères sur 8 bits ; la lettre A y est représentée par 1100 0001, soit C1 en hexadécimal.

📖 15. Codages internes des données

🔑 Notions clés & Définitions

• Codage électrique : Le codage électrique représente les bits par des charges ou niveaux électriques dans les circuits et certains composants d’un ordinateur.
• Codage électromagnétique : Le codage électromagnétique stocke des données sur des supports au moyen d’états d’aimantation, et non de charges électromagnétiques positives ou négatives.
• Codage optique : Le codage optique inscrit l’information sur des supports à sillons en verre, en plastique ou en silicium, lus au moyen de technologies optiques.

📝 Points essentiels

• Le codage électrique permet une transmission à grande vitesse, mais il est volatile et nécessite une alimentation électrique permanente.

• Le codage électromagnétique conserve les données de manière permanente, mais son temps d’accès est substantiellement long.

• Le CD-ROM utilise généralement un rayon laser infrarouge et le DVD-ROM un rayon laser rouge ; le codage optique est permanent mais son accès est lent.

• Le temps d’accès et la capacité de stockage sont deux paramètres importants qui motivent souvent l’utilisation de méthodes de compression.

📖 16. Exemples de décodage

📝 Points essentiels

• Dans l’exemple de stockage électromagnétique, les charges − + − − − − + − − + + − + − − + − + + − − − + + correspondent aux bits 01000010 01101001 01100011 et décodent le nom « Bic » en ASCII.

📖 17. Codage et cryptage

★ À maîtriser

📌 Le cryptage transforme des données afin d’assurer la confidentialité de leur transmission ou de leur stockage, tandis que le codage représente les données dans un format reconnaissable par un système donné.

Compléments

• Un système d’exploitation sert d’interface entre l’utilisateur et le matériel lors des opérations de traitement des données.

💡 Astuce mémo

Le codage rend les données reconnaissables ; le cryptage protège leur confidentialité.

📊 Tableaux de synthèse

Formats IEEE 754