Repr©sentation des informations

  • View
    799

  • Download
    1

Embed Size (px)

DESCRIPTION

Premier chapitre de la matière Structure Machine pour LMD MI

Text of Repr©sentation des informations

  • 1. Structure Machine pour L1Slimane OULAD NAOUIslimane.ouladnaoui(at)univ-ghardaia.dz Facult des Sciences et technologiesDpartement des Mathmatiques et dInformatique Universit de GhardaiaFvrier 2013

2. Table des matires1 Reprsentation des Informations 21.1 Prambule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .21.2 Reprsentation des nombres signs . . . . . . . . . . . . . . . . .21.2.1 Reprsnetation signe valeur absolue(SVA) (signed-magnitude) 31.2.2 Reprsentation par le complment la base diminu(diminished radix complement) . . . . . . . . . . . . . . . . . . . . . . 41.2.3 Reprsentation par le complment la base(radix com- plement) . . . . . . . . . . . . . . . . . . . . . . . . . . . .51.2.4 Arithmtique en complment vrai . . . . . . . . . . . . .61.3 Reprsentation des nombres rels . . . . . . . . . . . . . . . . . . 71.3.1 Format en virgule xe . . . . . . . . . . . . . . . . . . . .71.3.2 Format en virgule ottante . . . . . . . . . . . . . . . . . 71.3.3 Arithmtique en virgule ottante . . . . . . . . . . . . . . 81.3.4 La norme IEEE 754 . . . . . . . . . . . . . . . . . . . . .91.4 Autre codages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4.1 Le codage BCD (Binary-Coded Decimal) . . . . . . . . . 101.4.2 Le code Excess3, (XS3)ou STIBITIZ . . . . . . . . . . . . 101.4.3 Le code Gray ou binaire richi . . . . . . . . . . . . . . . 101.4.4 Codage des caractres . . . . . . . . . . . . . . . . . . . . 11 1 3. Structure Machine Pour L1Licence MIChapitre 1Reprsentation desInformations Objectif : Connatre les reprsentations des dirents types de donnes,notamment les nombres et larithmtique associe.1.1 PrambuleLordinateur traite dirents types dinformation(textes, images, son, vi-dos...), lhomme utilise des symbles (lettres, chires....) pour les reprsenter,cest ce quon appelle la reprsentation externe .Pour les manipuler, lordinateur exige un codage ou une traduction pralable,nous passons donc unereprsentation interne . Dans la reprsentation in-terne, des suites de bits (pouvant prendre les valeurs o ou 1) sont utilises.Gnralement la machine travaille avec un paquet de taille dnie de bits ap-pel mot mmoire (de n bits), souvent des multiples de 8 (octet(8 bits), word(16bits), double word (32 bits)...). Le processeur est alors dit processeur n-bits.Exemples :Intel 4004 4 bits (1971)Intel 8086 16 bits (1978)Pentium III 64 bits (1999)Core i7 980x 128 bits (dernier processeur dIntel)1.2 Reprsentation des nombres signstant donn que le premier objectif des ordinateurs est de calculer rapide-ment, la reprsentation des nombres a t la premire forme tudie.Dans nos programmes, le choix dune reprsentation est x lors de la dclaration(types : integer, real en Pascal, oat en C..etc). Comprendre la reprsentationdes nombres permet de raliser des gains en espace mmoire et en temps detraitement.En S1, nous avons vu la reprsentation dune catgorie particulire de nombres,ce sont les nombres non signs (positifs).Univ. de Ghardaia, Dpt. MI 2013 Page 2/11 4. Structure Machine Pour L1 Licence MIOn rappelle la notation positionnelle sur (n + p bits) dun nombre N dans unebase b :En reprsentation binaire non signe (RBNS), le vecteur (an1 , ..., a0 , a1 , ..., ap ),tel que : n1 ai bi N = i=p ai des entiers [0, b 1] an1 (ap ) est le chire de poids fort(faible) La reprsentation des entiers naturels ne pose pas de dicult, mais celle desentiers relatifs est plus dlicate puisque il faut pouvoir reprsenter et manipulerle signe. Le but est de trouver une reprsentation transparente dans les op-rations quelque soit le signe. Voyons comment reprsenter les nombres signs(entiers relatifs).1.2.1 Reprsnetation signe valeur absolue(SVA) (signed-magnitude) Lide la plus simple consiste rserver un bit pour coder le signe(S ) dunombre, le reste des (n 1) bits reprsentent alors sa valeur absolue(V A).La convention retenue est dutiliser le bit du plus fort poids (bit le plus gauche)pour le signe : 0 si le nombre est positif, 1 sil est ngatif. Si nous travaillons surn bits, ce codage peut tre schmatis ainsi : 1 bit n1 bitsan1 an2 an3 a0SVA 0:+ 1:Exemples : Sur 3 bits : Reprsentation SVA sur 3 bits quivalent dcimalSVA +0000 +1001 +2010 +3011 -0100 -1101 -2110 -3111 4 bits6 bits8 bits+50101 +27 011011 -24 10011000 -5 1101 -27 111011 -128 hors limites (9 bits ncessaires !)Intervalle reprsentable : sur n bits : la plus petite valeur (ngative) est :111 1, alors que la plus grande (positive) est : 011 1 ce qui donne linter-valle de valeurs reprsentables suivant : [(2n1 1), 2n1 1]Univ. de Ghardaia, Dpt. MI 2013Page 3/11 5. Structure Machine Pour L1 Licence MIAvantage : Mthode simple et naturelle.Inconvnients :Deux reprsentations pour 0 (+0,-0)Complique les oprations daddition/soustraction (traitement spcial dusigne)En raison de ces dfauts, cette reprsentation nest pas utilise actuellement.Exercice : Calculer sur 8 bits en SVA : 1-2 ; puis sur 4 bits avec la mmemthode 2-6 . Indication : pour calculer x y en SVA si yx alors calculery x puis introduire le signe.1.2.2 Reprsentation par le complment la base dimi-nu(diminished radix complement)Dans cette reprsentation un nombre positif est cod de la mme faon quenRBNS, alors quun nombre ngatif N est reprsent par son complment N telque : N + N = bn 1, (b : la base utilise, n : nombre de bits de la reprsenta-tion).En systme binaire (b = 2) en parle du complment 1(C1) ou lecompl-ment restreint (CR) : N + N = 2n 1 N = 2n 1 N .Pour obtenir le complment 1 dun nombre N il sut donc de le retrancher de2n 1 qui scrit 11 . . . 1 sur n bits, ce qui revient inverser tous ses bits. (car1 0 = 1 et 1 1 = 0).Exemples : Soit sur 5 bits le nombre suivant : 01101 reprsentant (+13)10 ,son complment 1 est le nombre 10010 qui est la reprsentation de (13)10 enC1. Reprsentation en C1 sur 3 bits quivalent dcimalC1 +0000 +1001 +2010 +3011 -3100 -2101 -1110 -0111Rsultat : le complment 1 du complment 1 dun nombre N est le nombrelui mme : C1(C1(N )) = NIntervalle reprsentable :sur n bits :la plus petite valeur (ngative) est : 100 0, alors que la plus grande (posi-tive) est : 011 1 ce qui donne lintervalle de valeurs reprsentables suivant :[(2n1 1), 2n1 1]Avantage :Mthode intuitive (inverser les bits pour obtenir le complmentdun nombre).Inconvnients :Les mmes remarques que pour le codage en SV A : 2 repr-sentations pour 0, et oprartions moins videntes.Exercice : Calculer sur 8 bits en C1 : 63-28 ; puis 28-63.Univ. de Ghardaia, Dpt. MI 2013Page 4/11 6. Structure Machine Pour L1 Licence MI1.2.3 Reprsentation par le complment la base(radixcomplement)Comme dans la mthode prcdente un nombre positif est reprsent parson code RBNS, mais le codage dun nombre ngatif seectue en complman-tation la base : N + N = bn , (b : la base utilise, n : le nombre de bits de lareprsentation).En systme binaire (b = 2) en parle ducomplment 2(C2) ou lecompl-ment vrai(CV ) : N + N = 2n N = 2n NPour obtenir le complment 2 dun nombre N il sut donc de le retrancherde 2n .En rapprochant les deux quations de C1 et C2, on obtient : C2(N ) = C1(N )+1.Le passage dun entier positif lentier ngatif de mme valeur absolue, et in-versement, se fait en complmentant le nombre bit bit puis en ajoutant 1 aursultat.Exemples :Reprsenter en C2 sur 8 bits le nombre -77.(77)10 = (?)8 = C1(+77)+1 = C1(01001101)+1 = 10110010+1 = (10110011)8 C2C2Sur 3 bits :Reprsentation en C2 sur 3 bitsquivalent dcimalC2+0000+1001+2010+3011-4100-3101-2110-1111Intervalle reprsentable : sur n bits : la plus petite valeur (ngative) est :100 0, alors que la plus grande (positive) est : 011 1, ce qui donne linter-valle de valeurs reprsentables suivant : [2n1 , 2n1 1]Avantages : Une seule reprsentation pour 0 Oprations arithmtiques plus simples ( laddition et la soustration sonttraites de la mme manire) (a b = a + (b) = a + C2(b))Rsultat : le complment 2 du complment 2 dun nombre N est le nombrelui mme : C2(C2(N )) = N .La reprsentation en C2 sest impose dans les calculateurs modernes, car ellesimplie de nombreuses oprations sur les entiers.Remarquesastuces : 1. Le nombre n de bits de travail tant limit, ceci implique quesi le nombre occupe moins de n bits, on doit le compltersi le nombre occupe plus de n bits, il doit tre tronqu. 2. Dans les trois mthodes SV A, C1 et C2, le bit de poids fort indique lesigneUniv. de Ghardaia, Dpt. MI 2013Page 5/11 7. Structure Machine Pour L1Licence MI3. Pour trouver rapidement le C2 dun nombre, il sut dinverser tous les bits qui suivent le premier 1 rencontr en commenant du poids le plus inverser faible ( droite), Ex : trouver C2(01010) C2( 01010 ) = 10110 garder4. Pour trouver la valeur dcimale dune chane (an1 . . . a0 ) en C1 on peut utiliser lun des procds suivants : n2 si an1 = 0 alors (Nbre positif) (N )10 = ai 2i i=0 sinon (Nbre ngatif) complter(inverser les bits), puis introduire le signe n2 (N )10 = an1 (2n1 1) + ai 2i i=05. Pour trouver la valeur dcimale dune chane (an1 . . . a0 ) en C2 on peut utiliser lun des procds suivants : n2 si an1 = 0 alors (Nbre positif) (N )10 = ai 2i i=0 sinon (Nbre ngatif) complter(inverser les bits) et ajouter 1, puis introduire le signe n2 (N )10 = an1 2n1 + ai 2i i=06. Pour pouvoir travailler il est ncessaire de fournir la fois le nombre de bits ainsi que la mthode de reprsentation des donnes, Ex. la chane suivante (10100110) code sur 8 bits peut reprsenter selon le codage adopt soit :(a) 166 en RBNS(b) -90 en C2(c) -89 en C1(d) -38 en SVA1.2.4 Arithmtique en complment vrai 2 nombres positifs : sur 5 bits +9 01001 +4 00100+13 01101 rsultat positif nombre positif et nombre ngatif infrieur+9 01001 -411100+51 00101 bit de retenue ignorer nombre positif et nombre ngatif plus grand -9 10111+4 001005 11011 rsultat ngatif deux nombres ngatifs-9 10111-4 1110013 1 10011 bit de retenue ne pas considrerUniv. de Ghardaia, Dpt. MI 2013Page 6/11 8. Structure Machine Pour L1 Licence MI nombres gaux et opposs -9 10111+901001 01 00000 bi