Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 02 - Les autres codages numériques

PLAN DU CHAPITRE

Il sera présenté dans ce chapitre, les codages :

  1. Hexadécimal

  2. Octal

  3. DCB

OBJECTIF DU CHAPITRE

Ce chapitre va présenter différents codages utiles pour l'architecture des machines. Il est important de savoir lire et interpréter des codages lors d'un travail dans le numérique. Un ordinateur, tout comme bon nombre de machines ont besoin de ces codages pour communiquer et véhiculer de l'information. Le travail du concepteur ou du réparateur est souvent plus efficace, s’il peut vérifier les valeurs numériques sans utiliser d'outils complémentaires.

LE CODAGE HEXADECIMAL

Pourquoi l’hexadécimal ?

Les mémoires des ordinateurs sont accessibles grâce à des adresses. Les adresses sont codées en hexadécimales. Les nombres binaires sont parfois volumineux. Pour éviter les erreurs et pour manipuler des nombres plus petit sans perdre d’informations, ils sont traduits en hexadécimal.

Au-delà des adresses les hexadécimaux sont utiles pour pointer sur des valeurs en mémoire. La notion de pointage et de référence sont très utiles pour certain langage de programmation.

Les algorithmes de traductions en hexadécimal sont étudiés pour manipuler les nombres binaires. De ce fait, les constructions des machines ne sont pas altérées par l’utilisation des traducteurs en hexadécimal et sont mêmes fortement adaptées.

Deux codes hexadécimaux représentent un octet binaire. L’hexadécimale permet de manipuler des nombres en base 16. Nous disposons de :

  • 10 chiffres de 0 à 9

  • 6 lettres de A à F

Conversion de l’hexadécimal entier vers un décimal entier

[Note]

Nom de l’algorithme : Table de conversion

Donnée d’entrée : H un nombre entier hexadécimal quelconque

Donnée produite : N un nombre entier décimal

But : Traduction du nombre entier hexadécimal H en une valeur N entière.

Pour manipuler cet algorithme, il est plus simple de passer par la structure de données qui est une table et de dérouler les correspondances.

Les tables que nous allons prendre se lisent de droite à gauche. Donc l’indice de droite est 0 puis 1 puis 2 …. . Il est important de travailler avec les indices puisqu’ils vont déterminer les valeurs de correspondances.

Voici une table des indices sur 5 cases :

Table 1.1. Table des valeurs des indices

4 3 2 1 0

La base hexadécimale en entier décimale est 16. Entre la base 16 et les indices, nous fabriquons des puissances de 16 pour faire notre transformation d’une base à l’autre.

Table 1.2. Table de la base 16 à la puissance des indices

164 163 162 161 160

Maintenant que nous avons établi les puissances, nous pouvons les transformer en entiers décimaux :

Table 1.3. Table des valeurs des entiers décimaux, valeurs calculées en fonction des puissances de la base 16

65536 4096 256 16 1

La table de correspondance entre le mot hexadécimal et la production de l’entier peut donc se faire :

Table 1.4. Algorithme et résultat décimal en utilisant la table de conversion

Mot hexadécimal 1 4 F 0 A
Correspondance décimale 1 4 15 0 10
Opérateur * * * * *
Valeur décimale calculée 65536 4096 256 16 1
Résultat 65536 16384 3840 0 10
85770 65536 + 16384 + 3840 + 0 + 10

La taille des mots que nous utilisons n’est pas importante pour le moment. Comme nous manipulons des valeurs entières positives, nous pouvons utiliser l’intégralité des cases. Inutile de compléter au début des mots hexadécimal une suite de zéros.

Le seul zéro significatif est le mot d’une case :

Table 1.5. Algorithme et résultat décimal en utilisant la table de conversion pour la plus petite valeur positive

Plus petit mot hexédécimal positif 0
Opérateur *
Valeur décimale du plus petit mot 1 = 160
Résultat 0

Conversion d’un décimal entier vers l’hexadécimal entier

[Note]

Nom de l’algorithme : Division par 16

Donnée d’entrée : N un nombre entier décimal quelconque

Donnée produite : H un nombre entier hexadécimal

But : Traduction du nombre entier N en un nombre entier hexadécimal.

Le principe de l’algorithme est à partir d’un nombre décimal faire la division euclidienne par 16 :

  • Si nous divisons le nombre décimal N par 16, nous avons :

    • Un reste

    • Un quotien

  • La fin de l’algorithme de la division par 16 est lorsque le reste vaut entre 0 et F et qu’il n’est plus possible de constituer le quotient.

  • Après la fin de la division, il y a une reconstitution du nombre hexadécimal produit en lisant et concaténant les restes dans l’ordre inverse de leur fabrication. Ainsi le dernier reste produit devient le bit de poids fort et le premier bit produit devient le bit de poids faible.

Exemple pour trouver l’hexadécimal H à partir du nombre décimal entier N = 18110 :

Figure 1.1. Mise en œuvre graphique d’un déroulement de l’algorithme par division

Mise en œuvre graphique d’un déroulement de l’algorithme par division

A partir de la figure 1.1, si nous lisons les restes produits du dernier au premier, nous avons 1110 et 510 soit en hexadécimal B516.

Conversion d’un hexadécimal entier vers un binaire entier et inversement

Conversion d’un hexadécimal entier vers un binaire entier

[Note]

Nom de l’algorithme : Conversion hexadécimal vers un binaire

Donnée d’entrée : H un nombre entier hexadécimal quelconque

Donnée produite : B un nombre entier binaire

But : Traduction du nombre entier hexadécimal H en un nombre entier binaire B.

Le principe de cet algorithme concise à traiter 1 par 1 les chiffres hexadécimaux du nombre H donné. Il faut d’abord rappeler qu’un chiffre hexadécimal va de 0 à F, soit de 0 à 15 en décimal. Nous avons vu dans la partie des codages binaires qu’il est possible de coder les entiers décimaux de 0 à 15 sur 4 bits. Donc, chaque chiffre hexadécimal sera codé sur 4 bits. Les 0 en bits de poids fort sont significatifs, il faut alors tous les noter pour trouver la conversion des nombres.

Example 1.1. Nous voulons traduire le nombre hexadécimal H = B516 en un nombre binaire B :

H = B 5

B = 1011 0101

Donc, B = 1011 01012


Conversion d’un binaire entier vers un hexadécimal entier

[Note]

Nom de l’algorithme : Conversion binaire vers un hexadécimal

Donnée d’entrée : B un nombre entier binaire quelconque

Donnée produite : H un nombre entier hexadécimal

But : Traduction du nombre entier binaire B en un nombre entier hexadécimal H.

Le principe de cet algorithme est de prendre le nombre binaire B, de le découper par parquet de 4 bits en partant par les bits de poids faible. Si en fonction du découpage, il manque dans le dernier quartet de chiffres des valeurs, il faut le compléter avec des zéros significatifs dans les bits de poids fort.

Example 1.2. Nous voulons traduire 11001101112 en une valeur hexadécimale :

B = 1100110111

En quartets = 11 0011 0111

Complétion de zéros significatifs = 0011 0011 0111

H = 3 3 7

Soit H = 33716


L’arithmétique hexadécimale

L’addition entre hexadécimaux

[Note]

Nom de l’algorithme : Addition entre hexadécimaux

Donnée d’entrée : Deux nombres entiers hexadécimaux H1 et H2

Donnée produite : Un nombre entier hexadécimal avec une retenue potentielle

But : Additionner deux nombres hexadécimaux pour en produire un résultat et une retenue potentielle en fonction de la place disponible pour le résultat.

Les calculs d’additions entre hexadécimaux utilisent les mêmes algorithmes que toutes les autres additions. L’addition se positionne sur les valeurs des chiffres hexadécimaux en fonction du rang d’indice. Et comme tout algorithme d’addition, il faut maintenant considérer les tailles des mots. En effet, si nous avons des mots de taille 1 alors le résultat est de taille 1. Si le résultat ne peut pas tenir sur une case alors nous avons une retenue positive. En informatique, la retenue (positive ou négative) est également nommée dépassement (Carry). Le phénomène de la retenue se propage en fonction de la taille n et s’applique sur le bit d’indice n+1.

Pour illustrer cet algorithme d’addition, nous allons présenter différents calcul entre les chiffres de 0 à F :

Figure 1.2. Table des additions des chiffres hexadécimaux de 0 à F

Table des additions des chiffres hexadécimaux de 0 à F

A partir de la table de la figure 1.2, nous constatons que la mise sous forme du résultat en matrice permet de généraliser les résultats obtenus. En effet, nous constatons qu’une diagonalisation des valeurs est possible. Pour l’algorithme d’addition, il s’agit d’une lecture de cette donnée en utilisant les deux entrées possibles en ligne + colonne ou en colonne + ligne, car l’addition est associative. Il suffit de prendre une valeur de la première ligne puis une valeur de la première colonne et l’interception donne le résultat de l’addition, ainsi D16 + B16 = 1816, et inversement comme B16 + D16 = 1816.

Dans les exemples précédents, nous avons un résultat sur une case et une retenue à 1. Nous pouvons maintenant appliquer la propagation des retenues en fonction du nombre de cases du résultat.

Prenons un exemple avec H1 = 90A116 additionné à H2 = 91A12. L’ordre importe peu H1 + H2 est donc équivalent à H2 + H1. Nous prenons l’hypothèse que nous sommes sur des tailles fixées à 4 cases et donc si nous dépassons 4 cases en résultat, nous produirons une retenue positive.

Table 1.6. Mise en œuvre d’un déroulement de l’algorithme d’addition

Retenue 1 1 1 0 0
H1 + 9 0 A 1
H2 + 9 F A 1
__ __ __ __ __
Résultat 1 3 0 4 2

Si nous reprenons l’exemple de la table ci-dessus et que nous utilisons la table de la figure 1.2, nous constatons que la première retenue positive sera à 0. Elle d’ailleurs toujours à 0 (nous pourrons le constater lors du cours matériel que cette retenue initiale sera branchée à la masse électrique). Ensuite, nous faisons le calcul de droite à gauche, case par case, en appliquant les concepts de l’addition et de la retenue. Donc 1 + 1 donne 2 sans retenue positive, puis nous faisons le calcul sur les cases suivantes des nombres H1 et H2 soit 0 + A + A donnant 4 en résultat avec 1 en retenue positive puis et le calcul est 1 + 0 + F donnant 0 en résultat avec 1 en retenue positive puis 1 + 9 + 0 donnant 3 puis 1 en retenue positive. Nous pouvons donc conclure que la valeur est 3042 (en fonction de la taille du nombre additionné) avec 1 en retenue positive. Ou, nous pourrions tolérer 1304216, si nous avions une capacité plus grande de résultat. Il est donc important de manipuler les tailles correctes des mots résultats utilisés pour conclure entre résultat et retenue.

La soustraction entre hexadécimaux

[Note]

Nom de l’algorithme : Soustraction entre hexadécimaux

Donnée d’entrée : Deux nombres entiers hexadécimaux H1 et H2

Donnée produite : Un nombre entier décimal avec une retenue négative potentielle

But : Soustraire deux nombres hexadécimaux pour en produire un résultat et une retenue négative potentielle en fonction de la place disponible pour le résultat.

Les calculs de soustraction entre hexadécimaux utilisent les mêmes algorithmes que toutes les autres soustractions. La soustraction se positionne sur les valeurs des cases en fonction du rang d’indice. Et comme tout algorithme de soustraction, il faut maintenant considérer les tailles des mots résultat. En effet, si nous avons des mots de taille 1 alors le résultat est de taille 1. Si le résultat ne peut pas tenir sur une case alors nous avons une retenue négative. Le phénomène de la retenue négative se propage en fonction de la taille n et s’applique sur la case d’indice n+1.

Prenons deux hexadécimaux H1 et H2 de taille 1 nous avons : H1 - H2 = 516 - F16 = -1016 +1516 - F16 = 616 - 1016

Pour illustrer cet algorithme de soustraction, nous allons présenter différents calcul entre les chiffres de 0 à F :

Figure 1.3. Table des soustractions des chiffres hexadécimaux de 0 à F

Table des soustractions des chiffres hexadécimaux de 0 à F

A partir de la table de la figure 1.3, l’algorithme de soustraction prend en entrée la ligne du haut de la matrice de 1016 à 1F16 est fait la soustraction case par case avec les cases de la première colonne. Les cases internes contiennent le résultat des soustractions, par exemple 1816 - E16 = A16.

Prenons un exemple avec H2 = 11116 soustrait à H1 = 100116. Attention, la soustraction ne donne pas le même résultat (sauf cas particuliers) si nous faisons H1 – H2 ou H2 – H1. Nous prenons l’hypothèse que nous sommes sur des tailles fixées de mots, nous devons rajouter les 0 significatifs à H2 = 011116.

Table 1.7. Mise en œuvre d’un déroulement de l’algorithme de la soustraction

Retenue négative 0 -1 -1 0 0
H1 + 1 0 0 1
H2 + 0 1 1 1
__ __ __ __ __
Résultat 0 0 E F 0

Si nous reprenons l’exemple de la table ci-dessus et que nous utilisons la table de la figure 1.3, nous constatons que la première retenue sera à 0. Ensuite, nous faisons le calcul de droite à gauche, case par case, en appliquant les concepts de la soustraction et de la retenue négative. Donc 1 - 1 donne 0 pas de retenue. Ensuite, nous avons 0 – 1. En l’état, il n’est pas possible de faire le calcul directement, nous avons donc besoin d’une base pour en réalité faire 10 – 1, ce qui donne F en résultat et -1 en retenue négative. Le fait d’ajouter une base peut aussi se dire, descendre une base. La retenue négative est aussi appelée propagation de la base du fait d’avoir eu recours à l’ajout d’une base pour faire le calcul aux cases précédentes. Cette retenue négative est distribuée aux cases suivantes des nombres H1 et H2. Ainsi le calcul devient 0 – 1 – 1, soit 0 – 2 ce qui nécessite de faire appel à une base pour obtenir 10 – 2, donnant E en résultat et provoquant la diffusion de -1, une retenue négative, aux cases suivantes. Nous obtenons ensuite 1 – 0 – 1 soit 0 en résultat et pas de retenue.

La multiplication entre hexadécimaux

[Note]

Nom de l’algorithme : Multiplication hexadécimale avec une base

Donnée d’entrée : Deux nombres entiers hexadécimal H1 et H2, dont au moins une base

Donnée produite : Un nombre entier hexadécimal

But : Multiplication deux nombres hexadécimaux pour en produire un résultat. Il y a au moins une base hexadécimale parmi H1 et/ou H2.

Il est très simple de mettre en place cette multiplication, car au niveau architecture et algorithme il s’agit d’un simple ajout de zéros fin du nombre hexadécimal.

Rappelons qu’une base est un 1 suivi de N zéro. Donc 10, 100, 1000, 10000, … sont des bases. Donc, il suffit de compter les zéros de la base pour les ajouter au deuxième nombre à multiplier.

Ainsi 10E0103016 * 1000016 = 10E0103000002

Nous considérons que nous avons assez de place pour produire le résultat. Attention cependant, dans une architecture hardware les tailles des mots sont limitées. Par exemple, vous avez du 64 bits. Donc, soit il faut plusieurs mots pour produire un résultat, soit il y aura une erreur de dépassement. Pour garantir la taille des stockages rentre en jeu les logiciels de pilotage du matériel, comme les outils avec les langages typés.

[Note]

Nom de l’algorithme : Multiplication hexadécimale quelconque

Donnée d’entrée : Deux nombres entiers hexadécimaux H1 et H2 quelconques

Donnée produite : Un nombre entier hexadécimal

But : Multiplication deux nombres hexadécimaux pour en produire un résultat hexadécimal.

Nous allons regarder la multiplication des chiffres hexadécimaux de 0 à F :

Figure 1.4. Table des multiplications des chiffres hexadécimaux de 0 à F

Table des multiplications des chiffres hexadécimaux de 0 à F

A partir de la table de la figure 1.4, nous constatons que la mise sous fore du résultat en matrice permet de généraliser les résultats obtenus. L’algorithme de multiplication se fait à partir d’une lecture de cette table donnée en utilisant les deux entrées possibles en ligne * colonne ou en colonne * ligne, car la multiplication est associative. Il suffit de prendre une valeur de la première ligne puis une valeur de la première colonne et l’interception donne le résultat de la multiplication, ainsi D16 * B16 = 8F16, et inversement comme B16 * D16 = 8F16.

Pour faire une multiplication de nombres hexadécimaux quelconques, nous devons faire de la recopie, du décalage et de l’addition.

Par exemple, nous voulons multiplier H1 = 1A0B16 et B2 = 10116. L’ordre importe peu et H1 * H2 est équivalent à H2 * H1. La vraie différence est que pour l’un ou pour l’autre, nous aurons plus de calculs à faire.

Table 1.8. Mise en œuvre d’un déroulement de l’algorithme de la multiplication

H1 1 A 0 B
H2 + 1 0 1
__ __ __ __ __ __ __
Retenue 0 0 0 1 0 0 0
+ 1 A 0 B
+ 0 0 0 0
+ 1 A 0 B
__ __ __ __ __ __ __
Résultat 1 A 2 5 0 B

Pour cet algorithme de multiplication, nous fixons nos hexadécimaux, et faisons H1 * H2. A partir du premier chiffre à droite de H2, nous recopions H1 car il s’agit d’un 1. Puis il faut établir un décalage et faire à partir du chiffre suivant de H2 un série de zéro équivalent au nombre de cases de H1, car il s’agit d’un 0. Et enfin après un décalage, nous faisons une recopie de H1 car il y a un 1. Une fois notre addition construite, il faut additionner colonne par colonne en propageant le cas échéant la retenue positive. Ainsi nous obtenons B = 0 + B, puis 0, puis 15 = 0 + A + B donnant 5 en résultat et une retenue à 1. Ensuite 2 = 1+ 1 + 0 + 0, puis A puis 1. Soit H1 * H2 = 1A250B16.

La division entre hexadécimaux

[Note]

Nom de l’algorithme : Division entière hexadécimale avec une base

Donnée d’entrée : Deux nombres entiers hexadécimaux H1 et H2, dont au moins une base

Donnée produite : Deux nombres entiers hexadécimaux

But : Diviser deux nombres hexadécimaux pour en produire un résultat d’un nombre entier avec un reste éventuel. Il y a au moins une base hexadécimale parmi H1 et/ou H2. Il est possible de provoquer une troncature et la perte de valeurs.

Il est très simple de mettre en place cette division, car au niveau architecture et algorithme, il s’agit d’un simple décalage à droite en perdant les bits de poids faible.

Rappelons qu’une base est un 1 suivi de N zéro. Donc 10, 100, 1000, 10000, … sont des bases. Donc, il suffit de compter les zéros de la base pour trouver la longueur du décalage à faire.

Ainsi 1010101016 / 1000016 = 101016

[Note]

Nom de l’algorithme : Division euclidienne entière hexadécimale quelconque

Donnée d’entrée : Deux nombres entiers hexadécimaux H1 et H2 quelconques

Donnée produite : Deux nombres entiers hexadécimaux

But : Diviser deux nombres hexadécimaux pour en produire un résultat d’un nombre entier avec un reste éventuel. Il est possible de provoquer une troncature et la perte de valeurs.

Pour aborder cet algorithme, il faut en redonner le principe. Une division euclidienne est faite de dividende, diviseur, quotient et reste en utilisant : quotient * diviseur + reste = dividende. Les hypothèses sont que dividende et diviseur sont fixés, ce sont les données d’entée. Nous cherchons les valeurs du quotient et du reste. Dans cet algorithme, nous faisons de la division entière, donc notre quotient sera un entier, tout comme le reste à partir du dividende et diviseur entiers donnés.

Pour commencer, le diviseur sera plus grand que le dividende, sinon l’entier du quotient sera toujours l’entier 0 avec le dividende égal au reste. Si nous avons un dividende plus grand que le diviseur, nous allons devoir faire des étapes de multiplications et de soustractions jusqu’à obtenir le plus grand entier possible pour le quotient.

A partir du diviseur, nous regardons et ajustons combien de fois il peut-être de dedans. Pour cela, nous utilisons des indices sur le dividende pour en demander juste une sur-approximation du diviseur. Ensuite, et comme nous sommes en hexadécimal, nous multiplions par un chiffre compris entre 0 et F pour obtenir le diviseur qui sera soustrait à la partie du dividende sélectionnée.

S’il reste des chiffres au niveau du dividende, alors il sera ajouté en case de poids faible du résultat obtenu par soustraction. Si le chiffre ainsi reconstitué est plus petit que le diviseur et si il reste des chiffres au niveau du dividende alors il y aura un 0 dans le quotient et le processus de sur approximation sera refait avec le nouveau chiffre donné en case de poids faible sur le résultat précédent. S’il y a plus de possibilité de soustraire le diviseur au dividende restant alors le dividende restant sera le reste de la division.

Figure 1.5. Algorithme de division euclidienne

Algorithme de division euclidienne

Dans le détail, les éléments de l’algorithme de la figure 1.5 sont :

na et nb les tailles en nombre de chiffres des nombres A / B.

c1 et c2 les indices calculés déterminant la longueur de A, puis A’, puis A", … le nombre A qui sera divisé par B. C le chiffre calculé du quotient, au fur et à mesure.

Pour illustrer et utiliser l’algorithme de la division euclidienne, prenons H1 / H2, avec H1 = C42A16 et H2 = E16 :

Figure 1.6. Division euclidienne hexadécimale

Division euclidienne hexadécimale

Dans le principe de l’algorithme de la division, pour l'exemple de la figure 1.6, nous regardons si E est plus grand que C. La réponse est Non, donc 0 est placé en quotient. Après le recalcul des indices sur le dividende, la question devient est-ce que C4 est plus grand que E. La réponse est Oui, et avec la table de la figure 1.6, nous voyons que E * E = C4. Donc, nous plaçons E en quotient, puis nous faisons C4 – C4. Après le recalcul des indices, nous faisons descendre le 2 du dividende. Ensuite la question devient est-ce que 2 est plus que E. La réponse est Non, donc 0 est placé en quotient. Après le recalcul des indices, la question devient est-ce que CA est plus grand que E. La réponse est Oui, et avec la table de la figure 1.6, nous voyons que E * 3 = 2A. Donc, nous plaçons 3 en quotient, nous faisons 2A – 2A. Il n’y a plus de recalcul des indices à faire puisque nous n’avons plus de chiffre dans le dividende. Nous pouvons conclure que C42A / E = E03, avec un reste est 016 et un quotient à E0316.

LE CODAGE OCTAL ET DCB

Pourquoi l’octal ?

L’octal est une métrique à base 8, c’est-à-dire que nous disposons des chiffres de 0 à 7 pour coder les valeurs. Il s’agit d’un codage régulièrement utilisé au début de l'informatique. Les premières machines travaillaient sur des mots de 12 bits et donc l’octal était parfaitement compatible.

Il est à noter que ce codage est encore utilisé pour un gain de place sur l’intervalle des codages binaires. Il permet de limiter les regroupements de chiffres binaires à 3 au lieu de 4 pour un codage hexadécimal.

Conversion de l’octal entier vers un décimal entier

[Note]

Nom de l’algorithme : Table de conversion

Donnée d’entrée : O un nombre entier octal quelconque

Donnée produite : N un nombre entier décimal

But : Traduction du nombre entier octal O en une valeur N entière.

Pour manipuler cet algorithme, il est plus simple de passer par la structure de données qui est une table et de dérouler les correspondances.

Les tables que nous allons prendre se lisent de droite à gauche. Donc l’indice de droite est 0 puis 1 puis 2 …. . Il est important de travailler avec les indices puisqu’ils vont déterminer les valeurs de correspondances.

Voici une table des indices sur 5 cases :

Table 1.9. Table des valeurs des indices

4 3 2 1 0

La base octale en entier décimale est 8. Entre la base 8 et les indices, nous fabriquons des puissances de 8 pour faire notre transformation d’une base à l’autre.

Table 1.10. Table de la base 16 à la puissance des indices

84 83 82 81 80

Maintenant que nous avons établi les puissances, nous pouvons les transformer en entiers décimaux :

Table 1.11. Table des valeurs des entiers décimaux, valeurs calculées en fonction des puissances de la base 8

4096 512 64 8 1

La table de correspondance entre le mot hexadécimal et la production de l’entier peut donc se faire :

Table 1.12. Algorithme et résultat décimal en utilisant la table de conversion

Mot octal 1 4 3 0 2
Opérateur * * * * *
Valeur décimale calculée 4096 512 64 8 1
Résultat 4096 2048 192 0 2
6338 4096 + 2048 + 192 + 0 + 2

La taille des mots que nous utilisons n’est pas importante pour le moment. Comme nous manipulons des valeurs entières positives, nous pouvons utiliser l’intégralité des cases. Inutile de compléter au début des mots octaux une suite de zéros.

Le seul zéro significatif est le mot d’une case :

Table 1.13. Algorithme et résultat décimal en utilisant la table de conversion pour la plus petite valeur positive

Plus petit mot hexédécimal positif 0
Opérateur *
Valeur décimale du plus petit mot 1 = 80
Résultat 0

Conversion d’un décimal entier vers l’octal entier

[Note]

Nom de l’algorithme : Division par 8

Donnée d’entrée : N un nombre entier décimal quelconque

Donnée produite : O un nombre entier octal

But : Traduction du nombre entier N en un nombre entier octal.

Le principe de l’algorithme est à partir d’un nombre décimal faire la division euclidienne par 8 :

  • Si nous divisons le nombre décimal N par 8, nous avons :

    • Un reste

    • Un quotiuent

  • La fin de l’algorithme de la division par 8 est lorsque le reste vaut entre 0 et 7 et qu’il n’est plus possible de constituer le quotient.

  • Après la fin de la division, il y a une reconstitution du nombre hexadécimal produit en lisant et concaténant les restes dans l’ordre inverse de leur fabrication. Ainsi le dernier reste produit devient le bit de poids fort et le premier bit produit devient le bit de poids faible.

Exemple pour trouver l’octal à partir du nombre N = 18110 :

Figure 1.7. Mise en œuvre graphique d’un déroulement de l’algorithme par division

Mise en œuvre graphique d’un déroulement de l’algorithme par division

Si nous lisons les restes produits du dernier au premier, nous avons 2 puis 6 puis 5 soit en octal 2658.

Conversion d’un octal entier vers un binaire entier et inversement

[Note]

Nom de l’algorithme : Conversion octal vers un binaire

Donnée d’entrée : O un nombre entier octal quelconque

Donnée produite : B un nombre entier binaire

But : Traduction du nombre entier octal O en un nombre entier binaire B.

Le principe de cet algorithme concise à traiter 1 par 1 les chiffres octaux du nombre O donné. Nous avons vu dans la partie des codages binaires qu’il est possible de coder les entiers décimaux de 0 à 8 sur 3 bits. Donc, chaque chiffre octal sera codé sur 3 bits. Les 0 en bits de poids fort sont significatifs, il faut alors tous les noter pour trouver la conversion des nombres.

Example 1.3. Nous voulons traduire le nombre octal O = 5716 en un nombre binaire B :

H = 57

B = 101 111

Donc, B = 101 1112


[Note]

Nom de l’algorithme : Conversion binaire vers un octal

Donnée d’entrée : B un nombre entier binaire quelconque

Donnée produite : O un nombre entier octal

But : Traduction du nombre entier binaire B en un nombre entier octal O.

Le principe de cet algorithme est de prendre le nombre binaire B, de le découper par parquet de 3 bits en partant par les bits de poids faible. Si en fonction du découpage, il manque dans le dernier trio de chiffres des valeurs, il faut le compléter avec des zéros significatifs dans les bits de poids fort.

Example 1.4. Nous voulons traduire 11001101112 en une valeur octale :

B = 1100110111

En trio = 1 100 110 111

Complétion de zéros significatifs = 001 100 110 111

O = 1 4 6 7

Soit O = 14678


Pourquoi le DCB ?

Le DCB (Décimal Codé Binaire) ou BCD (Binary Coded Decimal) est un codage assimilable à la base 10. Il est sur base des codages hexadécimaux en supprimant les lettres. Le principe de codage base 10 vers DCB est similaire au codage hexadécimal vers binaire.

Dans DCB, chaque chiffre de la représentation décimale est codé sur un groupe de 4 bits :

Par exemple : 3dcb = 00112 ou 5dcb = 01012

  • Avantage :

    • affichage décimal grandement facilité

    • affichage des caractères

    • affichage des formats comme Xml

    • coût linaire de conversion avec certaines bases numériques

  • Inconvénient :

    • en binaire, des combinaisons de bits sont inutilisées. Soit une perte de place de stockage

    • des opérations binaires complexes (comme les additions qui nécessitent une logique supplémentaire ou la multiplication qui nécessite l'utilisation d'algorithmes complexes à bases de décalages, ajouts, …)

    • lenteur importante

Même si il y a parfois des pertes d’emplacements dû à son système de codage. Les bits supplémentaires donnent les signes et peuvent tout de même s’utiliser pour des valeurs numériques spéciales, comme l'infini, les débordements et les erreurs.

Ce codage est utile pour le langage COBOL. Les dates des BIOS (Basic Input/Output System) des ordinateurs ou celles de la PS3 (Play Sation 3) sont souvent codées en DCB.

A l’origine, les codages des dates provenaient des systèmes Motorola par exemple dans les IBM PC AT. Il permet d’avoir des codages intermédiaires lorsque nous construirons les codages des caractères (ASCII). Ces codages sont utiles pour les Systèmes de Gestion des Bases de Données.

Ce codage est utilisé pour les calculs des calculatrices programmables comme celles de Texas Instruments, Hewlett-Packard ou autres. Le format BCD utilisé est celui de la virgule flottante, ou il intègre deux ou trois chiffres pour l'exposant lors des transformations des réels.

Conversion d’un décimal entier vers un DCB entier et inversement

[Note]

Nom de l’algorithme : Conversion décimale vers un DCB

Donnée d’entrée : N un nombre entier décimal quelconque

Donnée produite : D un nombre entier DCB

But : Traduction du nombre entier N en un nombre entier DCB.

[Note]

Nom de l’algorithme : Conversion DCB vers un décimal

Donnée d’entrée : D un nombre entier DCB

Donnée produite : N un nombre entier décimal quelconque

But : Traduction du nombre entier DCB en un nombre entier N.

Pour produire ces algorithmes, il est plus simple de passer par une table de correspondance. Les cas non désirés sont exclus du résultat, nous verrons qu’il y aura un vrai impact au niveau des calculs.

Figure 1.8. Table de correspondance décimal- DCB.

Table de correspondance décimal- DCB.

Example 1.5. Prenons un exemple avec N = 724310 la valeur en DCB est :

DCB = 0111 0010 0100 0011dcb


[Note]

Nous verrons dans le chapitre des codages des caractères que le DCB dans sa version étendue est utile. Utilisé par IBM, EBCDIC (Extended Binary Code Decimal Information Code) est la variante du code DCB sur 8 bits (1 octet).

Dans son principe l’octet est séparé en deux quartets avec :

  • si le premier quartet est 1111

  • alors le deuxième quartet représente un entier (avec l’ensemble de ce codage il est possible de représenter les caractères)

Example 1.6. Pour le chiffre 3ebcdic :

3ebcdic = 1111 00112


Example 1.7. Conversion de EBCDIC en DCB pour 25ebcdic nous avons :

25ebcdic = 1111 00102 1111 01012


Example 1.8. Conversion pour 25dcb

il faut prendre les deux quartets de poids faible de chaque octet soit: 00012 10002.


Conversion d’un DCB vers un binaire

[Note]

Nom de l’algorithme : Conversion DCB vers binaire

Donnée d’entrée : Un nombre entier DCB

Donnée produite : Un nombre entier binaire B

But : Utilisation de la multiplication par 1010 du DCB pour obtenir le binaire

Table 1.14. Mise en œuvre d’un déroulement de l’algorithme de la multiplication

D1 0 0 0 0 1 1 0
D2 + 0 0 0 1 0 1 0
__ __ __ __ __ __ __
Retenue 0 0 0 0 0 0 0
+ 0 0 0 0 0 0 0
+ 0 0 0 1 1 0
+ 0 0 0 0 0
+ 0 1 1 0
__ __ __ __ __ __ __
Retenue 1 1 1 1 0 0 0
+ 0 1 1 1 1 0 0
+ 0 0 0 0 1 0 1
__ __ __ __ __ __ __
Résultat 1 0 0 0 0 0 1

A partir du déroulement du tableau ci-dessus, et de D = 0110 0101dcb, nous prenons la partie 0110 pour la multiplier par 10, soit 1010 puis nous ajoutons la partie 0101 au résultat pour obtenir le binaire 0100 00012.

Conversion d’un binaire vers un DCB

[Note]

Nom de l’algorithme : Conversion binaire vers DCB

Donnée d’entrée : Un nombre entier binaire B

Donnée produite : Un nombre entier DCB

But : Utilisation de la division euclidienne par binaire pour obtenir le DCB.

Pour convertir un binaire en DCB, il suffit de diviser le binaire par puissance de 10102 puis de construire le DCB à partir des reste et quotient.

Par exemple, nous voulons convertir le binaire entier B = 0100 00012 en DCB. Donc il suffit simplement de faire la division euclidienne de B avec 1010.

Figure 1.9. Mise en œuvre d’un déroulement de l’algorithme du convertisseur binaire vers un DCB

Mise en œuvre d’un déroulement de l’algorithme du convertisseur binaire vers un DCB

La partie bit de faible est maintenant le reste de la division euclidienne et la partie bit de fort est le quotient de la division soit D = 01100101dcb.

L’addition des DCB

[Note]

Nom de l’algorithme : Addition entre DCB avec correction des erreurs

Donnée d’entrée : Deux nombres entiers DCB D1 et D2

Donnée produite : Un nombre entier DCB avec une retenue potentielle

But : Additionner deux nombres DCB pour en produire un résultat et une retenue potentielle en fonction de la place disponible pour le résultat.

Compte tenu que les chiffres DCB sont codés sur 4 bits. La dynamique de codage en entier positif sur 4 bits est de 00002 à 11112 et donc de 010 à 1510 en décimal. Or la dynamique de codage en entier positif des DCB est de 00002 à 10012 et donc de 010 à 910 en entier décimal. Il nous manque donc 6 codages possibles sur la place disponible, il faut donc en tenir compte lors des calculs et instaurer une récupération de l’erreur.

Lorsque le résultat par calcul est supérieur à 1001dcb, il faut ajouter 0110dcb pour corriger l’erreur et passer à la base suivante.

Par exemple, nous voulons additionner N2 = 8910 à N1 = 12310 en passant par les DCB, D1 = 000100100011dcb et D2 = 10001001dcb avec corrections d’erreurs :

Table 1.15. Mise en œuvre d’un déroulement de l’algorithme de l’addition DCB avec correction des erreurs

N1 1 2 3
N2 + 0 8 9
______ ______ _____
Retenue 0000 0000 0110
+ 0001 0010 0011
+ 0000 1000 1001
______ ______ _____
Retenue 0001 0101 1000
+ 0001 1010 1100
Erreur 0110 0110
______ ______ _____
Résultat 0010 0001 0010
Vérification 2 1 2

Le résultat s’explique en tenant compte qu’aucune valeur ne peut dépasser 1001dcb. Donc, il faut faire les additions binaires classiques puis faire les interprétations des erreurs, ajouter les 0110dcb nécessaires pour enfin donner le résultat.

Il y a des méthodes et algorithmes plus rapides pour avoir un résultat, notamment l’addition directe en décimal puis de faire la transformation binaire ensuite :

Par exemple, nous pouvons additionner N2 = 8910 à N1 = 12310 directement puis faire une traduction finale en DCB :

Table 1.16. Mise en œuvre d’un déroulement d’une addition DCB avec un algorithme direct

Retenue 0 1 1000
+ 0001 1010 1100
Erreur 0110 0110
_____ _____ _____
Résultat 0010 0001 0010
Vérification 2 1 2

La multiplication des DCB

[Note]

Nom de l’algorithme : Multiplication DCB avec corrections des erreurs

Donnée d’entrée : Deux nombres entiers DCB D1 et D2 quelconques

Donnée produite : Un nombre entier DCB

But : Multiplication deux nombres DCB pour en produire un résultat binaire.

Par exemple, nous pouvons multiplier N1 = 2510 avec N2 = 710 :

Table 1.17. Mise en œuvre d’un déroulement de l’algorithme de l’addition DCB avec correction des erreurs

N1 2 5
N2 + 0 7
_____ _____ _____
Retenue 0000 0000 0110
D1 + 0010 0101
D2 + 0000 0111
_____ _____ _____
Retenue 0001 0111 1000
+ 0010 0101
+ 0100 1010
+ 1001 0100
_____ _____ _____
Retenue 0000 0000 1100
+ 0001 0000 0011
Erreur + 0110 0110
____ ____ _____
Retenue 0000 0000 0000
+ 0001 0000 0011
Erreur + 0110
_____ _____ _____
Retenue 0000 0001 1100
+ 0001 0110 1001
Erreur + 0110
_____ _____ _____
Résultat 0001 0111 0101
Vérification 1 7 5

Le résultat du tableau ci-dessus s’explique en tenant compte des erreurs produites pas le calcul. Il faut donc ajouter les 0110dcb pour obtenir le résultat.

D’autres méthodes existent comme le principe d’ajustement de l’erreur en la trouvant par division en puissance de 1010dcb.

Par exemple, nous pouvons multiplier N1 = 610 avec N2 = 510, soit 0110dcb * 0101dcb :

Table 1.18. Mise en œuvre d’un déroulement de l’algorithme de multiplication DCB avec correction des erreurs

D1 0 0 0 0 0 1 1 0
D2 + 0 0 0 0 0 1 0 1
__ __ __ __ __ __ __ __
Retenue 0 0 0 0 0 0 0 0
+ 0 0 0 0 0 1 1 0
+ 0 0 0 0 0 0 0
+ 0 0 1 1 0
__ __ __ __ __ __ __ __
0 0 0 1 1 1 1 0
/ 0 0 0 0 0 1 0 1
__ __ __ __ __ __ __ __
Quotient 0 0 1 1
Reste 0 0 0 0
Résultat 1 0 0 0 0 0 1 1

Le résultat du tableau ci-dessus, est d’abord une multiplication, puis une division par 1010dcb car il y a besoin d’une correction d’erreur. Le quotient et le reste de la division permettent la construction du résultat.

Le codage de DCB négatifs - L’algorithme du complément à 9

Figure 1.10. Les données informatiques

Les données informatiques

Il existe plusieurs méthodes pour coder des DCB entiers négatifs. Il faut considérer tout d’abord la taille des mots de codage. Effectivement tout le sens de la négation sera porté par les bits de poids fort du mot. Donc, il est obligatoire de fixer la taille des mots DCB pour manipuler et identifier les bits de poids fort.

[Note]

Nom de l’algorithme : Complément à 9

Donnée d’entrée : Un nombre D entier DCB, dont la taille est fixée

Donnée produite : Un nombre –D entier DCB, dont la taille est fixée

But : Suit une table de correspondance. Le DCB positif devient négatif et inversement le nombre DCB négatif devient positif.

Le signe pour le codage des négatifs en DCB diffère si le codage est compacté ou étendu.

Pour un octet d'un codage DCB compacté (c’est-à-dire 2 chiffres par octet), les 4 bits de poids faible représentent le signe (à droite de l’octet).

Pour un octet d'un codage DCB étendu (ou en EBCDIC c’est-à-dire 1 chiffre par octet), les 4 bits de poids fort représentent le signe.

Figure 1.11. Table de correspondance complément à 9

Table de correspondance complément à 9

Example 1.9. En utilisant le tableau de la figure 1.9 :

Soit D = 0011 0111dcb

-D = 0110 0010dcb


La soustraction des DCB

[Note]

Nom de l’algorithme : Soustraction entre DCB avec récupération des erreurs

Donnée d’entrée : Deux nombres entiers DCB, D1 et D2

Donnée produite : Un nombre entier DCB

But : Soustraire deux nombres DCB pour en produire un résultat DCB avec la méthode du complément à 9.

Par exemple, nous pouvons soustraire D2 = 0010dcb à D1 = 0101dcb.

Table 1.19. Mise en œuvre d’un déroulement de l’algorithme de la multiplication

D1 0 0 1 0 1
D2 - 0 0 0 1 0
__ __ __ __ __
Retenue 0 1 1 1 0
+ 0 0 1 0 1
+ 0 0 1 1 1
__ __ __ __ __
Retenue 0 1 0 0 0
+ 0 1 1 0 0
+ 0 0 1 1 0
__ __ __ __ __
1 0 0 1 0
+ 1
__ __ __ __ __
Résultat 0 0 0 1 1

A partir de l’exemple de la table ci-dessus, la soustraction est une addition en utilisant le complément à 9. La première étape est de convertir D2 = 0010dcb en complément à 9, soit –D2 = 0111dcb. Ensuite, il faut faire l’addition bit à bit. Le résultat étant plus grand que 1001dcb, il faut ajouter 0110dcb. Comme le résultat obtenu à une retenue, il faut injecter cette retenue au résultat. En l’état le résultat est positif et il s’agit donc de la valeur finale.

Par example, nous pouvons soustraire D2 = 0011dcb à D1 = 0001dcb.

Table 1.20. Soustraction avec le complément à 9

D1 0 0 0 0 1
D2 - 0 0 0 1 1
__ __ __ __ __
Retenue 0 0 0 0 0
+ 0 0 0 0 1
+ 0 0 1 1 0
__ __ __ __ __
Résultat initial 0 0 1 1 1
__ __ __ __ __
Résultat cplt à 9 0 0 0 1 1

A partir de l’exemple de la table ci-dessus, la soustraction est une addition en utilisant le complément à 9. La première étape est de convertir D2 = 0011dcb en complément à 9, soit –D2 = 0110dcb. Ensuite, il faut faire l’addition bit à bit. Le résultat est 0111dcb. Il faut appliquer le complément à 9 pour obtenir la valeur finale D = 0010dcb.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels