[PDF] Systèmes numériques Chapitre X Numération et arithmétique

View - Download Systèmes numériques Chapitre X Numération et arithmétique

Previous PDF

Next PDF

Systèmes numériques

Chapitre X

Numération et arithmétique

Serge BOADA

1993

Révision février 2011

Systèmes numériques HEIG-VD/SBA 2009

page 2 Le présent manuel est une version informatique du manuel écrit par Serge Boada en

1993. Je remercie son auteur pour le travail réalisé.

Mise à jour de ce manuel,

Je remercie tous les utilisateurs de ce manuel de m'indiquer les erreurs qu'il comporte. De même, si

des informations semblent manquer ou sont incomplètes, elles peuvent m'être transmises, cela permettra une mise à jour régulière de ce manuel.

Dernière mise à jour le 17 février 2011

Etienne Messerli

Contact: Etienne Messerli

e-mail : etienne.messerli@heig-vd.ch

Tél.: +41 (0)24 / 55 76 302

Coordonnées à la HEIG-VD :

Institut REDS

HEIG-VD,

Haute Ecole d'Ingénierie et de Gestion du Canton de Vaud

Route de Cheseaux 1

CH-1400 Yverdon-les-Bains

Tél : +41 (0)24 / 55 76 330

Internet : http://www.heig-vd.ch

Institut REDS

Internet : http://www.reds.ch

Autres personnes à contacter:

M. Yoan Graf yoan.graf@heig-vd.ch Tél direct +41 (0)24/55 76 259 M. Cédric Bardet cedric.bardet@heig-vd.ch Tél direct +41 (0)24/55 76 251

Systèmes numériques HEIG-VD/SBA 2009

page 3

TABLE DES MATIERES

X.1 INTRODUCTION ............................................................................................. 4

X.2 NUMERATION DE POSITION ...................................................................... 4

X.3 CHANGEMENTS DE BASE ........................................................................... 4

X.4 ADDITION BINAIRE ...................................................................................... 8

X.5 RETENUE ANTICIPEE .................................................................................. 9

X.6 SOUSTRACTION ET COMPLEMENT A 2 ............................................... 11 X.7 AUTRES REPRESENTATIONS DES NOMBRES NEGATIFS ............... 12 X.8 DEPASSEMENT DE CAPACITE ................................................................. 12 X.9 MULTIPLICATION D'ENTIERS BINAIRES SANS SIGNE ................... 13 X.10 MULTIPLICATION D'ENTIERS EN COMPLEMENT A 2 .................... 16 X.11 DIVISION D'ENTIERS BINAIRES SANS SIGNE ..................................... 18 X.12 DIVISION D'ENTIERS EN COMPLEMENT A 2 ...................................... 23

X.13 STRUCTURE D'UNE RALU......................................................................... 23

X.14 VIRGULE FIXE ET VIRGULE FLOTTANTE .......................................... 29 X.15 FORMATS STANDARD EN VIRGULE FLOTTANTE ............................ 30

X.16 LES OPERATIONS SUR LES NOMBRES

EN VIRGULE FLOTTANTE ........................................................................ 33 X.17 BITS DE GARDE ET ARRONDIS ............................................................... 38

X.18 EXERCICES .................................................................................................... 39

Systèmes numériques HEIG-VD/SBA 2009

page 4

X.1 INTRODUCTION

Dans le chapitre sur les machines séquentielles complexes, nous avons été amenés à réaliser des opérations d'addition et de soustraction en binaire. Mais nos connaissances actuelles ne nous permettent guère de faire des calculs plus complexes, ne serait-ce qu'une multiplication ou une division, de manière efficace. Pas plus qu'elles ne nous permettent de comprendre la structure d'une RALU, qui est justement très influencée par les besoins liés

à la multiplication et à la division. Avant de nous attaquer à la conception d'un processeur,

il est maintenant temps de combler cette lacune. Jusqu'ici, nous avons utilisé des mots binaires essentiellement dans le but de coder l'information. Nous allons étudier maintenant leur utilisation pour la représentation des nombres.

X.2 NUMÉRATION DE POSITION

Un système de numération est un langage consistant en une liste ordonnée de symboles

appelés chiffres (digits), des règles définissant leur utilisation pour créer des nombres, ainsi

que des règles définissant un jeu d'opérations telles que l'addition, la multiplication, etc.,

appelé arithmétique. Le nombre de symboles différents est appelé base. Ainsi, en base 10 (ou décimal), nous avons dix symboles ou chiffres, alors qu'en base 2 (ou binaire), nous n'en avons que deux. Le nombre de symboles différents étant très inférieur aux valeurs quantitatives que l'on désire représenter, on utilise la juxtaposition de chiffres pour créer des nombres. En général, chaque chiffre dans un nombre se voit attribuer un facteur de pondération, ou "poids", qui dépend de sa position dans le nombre. C'est ce que nous appellerons des

systèmes de numération de position. Le binaire pur, le décimal ou l'hexadécimal font partie

de cette catégorie, mais pas le code de Gray. A l'exception de quelques codes BCD spéciaux qui n'ont plus guère d'intérêt aujourd'hui, comme l'excédent-de-trois ou le 4-2-2-1, les systèmes de numération de position utilisent

une pondération exprimée en puissances croissantes de la base, la plus faible à droite et la

plus forte à gauche. Ainsi, en base dix, le nombre 1993 correspond à l'expression polynomiale 0123

103109109101.

Dans ce qui suit, nous nous restreindrons aux bases 2, 10 et 16, de loin les plus utilisées en

électronique numérique.

X.3 CHANGEMENT DE BASE

Du fait que notre base de travail habituelle est la base 10 et que les machines de traitement de l'information travaillent en base 2, il est souvent nécessaire de procéder à des changements de base. Bien évidemment, une conversion par substitution à l'aide d'une table (ce dont nous nous étions contentés jusqu'ici) n'est pas utilisable pour de grands nombres. Il nous faudra donc des méthodes de conversion algorithmiques. Celles-ci font intervenir des calculs

Systèmes numériques HEIG-VD/SBA 2009

page 5 arithmétiques qui seront effectués en binaire par une machine électronique, mais en décimal si nous travaillons "à la main". a) conversion "à la main" de base 10 en base 2 D'une façon générale, un nombre entier en base b, que nous désignerons par E b , peut s'écrire sous la forme polynomiale : 0 01 11 1 ...bdbdbdbdE m mm mb où d m

à d

0 sont les différents chiffres en base b constituant le mot qui représente le nombre.

Mais nous pouvons également écrire :

012m1mmb

db)d...b)db)dbd((...((E Des divisions successives par la base b nous donneront des restes successifs d 0 , puis d 1 d m . Nous pouvons donc procéder de cette manière pour passer "à la main" de base 10 en base 2, en effectuant bien sûr les calculs en base 10.

Calculons par exemple le nombre 1993 en base 2 :

Nous obtenons : 1993

10 = 111 1100 1001 2 La partie fractionnaire d'un nombre peut s'écrire : k k2 21
1b bd...bdbdF mais également : 1 11 2k1 1k1 k b)d...b)db)dbd((...((Fb En multipliant la partie fractionnaire par la base, nous obtenons d -1 comme partie entière. Une nouvelle multiplication par b de la partie fractionnaire résultante donnerait d -2 comme partie entière, et ainsi de suite. Par multiplications successives nous obtiendrons donc les chiffres de la partie fractionnaire d'un nombre. 2 1993
996
498
249
124
62
31
15 7 3 1 1 0 0 1 0 0 1 1 1 1

1 restes

Systèmes numériques HEIG-VD/SBA 2009

page 6 Calculons par exemple la fraction 0.8

Le calcul ne se termine pas. Nous obtenons :

22101100.0110011001100.08.0

b) Conversion "à la machine" de base 10 en base 2 Dans la machine, les nombres décimaux seront bien sûr représentés en binaire, soit en

BCD, soit en ASCII. La conversion ASCII

BCD n'offrant aucune difficulté, nous nous

concentrons sur la conversion BCD binaire pur. Les expressions pour la partie entière et pour la partie fractionnaire d'un nombre, obtenues par mises en évidence successives de la base b ou de son inverse b -1 , que nous avons utilisé sous a), nous donnent directement des algorithmes de conversion. Pour la partie entière, avec un nombre de m+1 chiffres BCD, nous pouvons utiliser l'algorithme ci-dessous, écrit en pseudo Ada : resultat := 0; for i in m downto 0 loop resultat := resultat * 1010 2 + chiffre_BCD_de_rang [ i ]; -- le calcul est effectue en binaire end loop;

Pour convertir 1993

10 en binaire, nous aurions ainsi la suite de calculs : Pour la partie fractionnaire, nous pouvons utiliser l'algorithme suivant (en pseudo Ada) : resultat := 0; -- k chiffres decimaux apres la virgule for i in k downto 1 loop resultat := (resultat + chiffre_BCD_de_rang[ -i ] ) / 1010 2 -- le calcul est effectue en binaire end loop; x 2 0,8 0,6 0,2 0,4 0,8 partie fractionnaire 1 1 0 0 d -1 d -2 d -3 d -4 partie entière ((0001 x 1010 + 1001) x 1010 + 1001) x 1010 + 0011

BCD rang 3 BCD rang 2 BCD rang 1 BCD rang 0

Systèmes numériques HEIG-VD/SBA 2009

page 7 Cependant, ces divisions par 1010 2 seront souvent sans fin, ce qui provoquera une accumulation d'erreurs d'arrondi ou de troncature. Il peut être plus judicieux de procéder

comme pour la partie entière, puis de diviser une seule fois à la fin par dix à la puissance k

(en binaire bien sûr, et cela n'est pas un simple décalage de la virgule). La méthode ci-dessus est la plus utilisée dans les systèmes à microprocesseur. Elle pose cependant le problème de la multiplication et de la division en binaire, problème dont nous nous occuperons plus loin. Dans l'exercice X.18.1, nous verrons une autre méthode algorithmique sans multiplication ni division. L'implémentation de ces algorithmes fait appel à des machines séquentielles complexes, alors que le problème de la conversion BCD binaire est de type combinatoire. C'est là un exemple de décomposition en séquence d'un problème combinatoire, dans le but de diminuer le coût du circuit. c) Conversion " à la main " de base 2 en base 10 Pour convertir un nombre binaire en décimal, il suffit d'additionner les poids respectifs des " 1 " apparaissant dans la représentation binaire. Une table des puissances de deux nous facilite donc la tâche.

Nous aurons, par exemple :

d) Conversion " à la machine " de base 2 en base 10 En fait, on réalise une conversion de binaire en BCD naturel, puisqu'une machine binaire ne peut pas générer directement des chiffres décimaux. Quelle que soit la base dans laquelle on désire exprimer un nombre, il est possible d'effectuer la conversion selon des algorithmes similaires à ceux que nous avons décrits pour la conversion de base 10 en base 2 (cas b)). 1 1 1 1 1 0 0 1 0 0 1 2 x 2 0 x 2 1 x 2 2 x 2 3 x 2 4 x 2 5 x 2 6 x 2 7 x 2 8 x 2 9 x 2 10 total :1 0 0 8 0 0 64
128
256
512
1'024 1'993

Systèmes numériques HEIG-VD/SBA 2009

page 8 Mais les calculs doivent être effectués dans la base de destination, donc en BCD pour une

conversion de base 2 en base 10. Ces calculs sont évidemment différents de ceux effectués sur des nombres binaires purs. Ils demandent des circuits ou des algorithmes différents.

En s'inspirant de la méthode utilisée pour passer "à la main" de base 10 en base 2 (cas a)),

nous pouvons effectuer les calculs en base 2. C'est par une suite de divisions par 1010 (dix) que nous obtiendrons des restes correspondants aux chiffres successifs de la partie entière d'un nombre, le chiffre de poids faible d'abord. Par une suite de multiplications par

1010 de la partie fractionnaire en base 2, nous obtiendrons des parties entières successives

correspondant aux chiffres de la partie fractionnaire en base 10, le poids fort d'abord. Dans l'exercice X.18.3, nous verrons une autre méthode algorithmique, qui ne nécessite ni multiplication ni division. Ces conversions peuvent aussi s'effectuer de façon purement combinatoire à l'aide de circuits standard spécifiquement prévus à cet effet, tels que les 74184 et 74484 pour le passage de BCD à binaire, et les 74185 et 74485 pour le passage de binaire à BCD. Mais il faut déjà 5 circuits à 20 pattes de type 74484 pour convertir en binaire un nombre de 4 décades, et 12 circuits pour un nombre de 6 décades ! Comme ces conversions interviennent généralement dans une interface homme-machine, elles n'ont pas besoin

d'être effectuées très vite et peuvent donc s'accommoder d'un traitement séquentiel, plus

économique.

X.4 ADDITION BINAIRE

Pour additionner deux nombres décimaux à la main, nous procédons par additions successives des chiffres de même poids (en commençant par le poids faible) et du report de

l'addition précédente. La même méthode peut être appliquée à l'addition en binaire. Par

exemple : Il nous suffit de disposer d'un circuit permettant d'additionner deux bits d'entrée et un report, puis de cascader autant de circuits qu'il y a de bits dans le plus grand nombre envisagé. Cet additionneur à deux bits et un report répond à la table X.1 ci-dessous : A N B N C N S N C N+1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 er nombre : 2 e nombre : 1 9 8 6 10 9 0 10 = 0 1 1 1 1 1 0 0 0 0 1 0 2

0 0 0 0 0 1 0 1 1 0 1 0

2 somme : 2 0 7 6 10 = 1 0 0 0 0 0 0 1 1 1 0 0 2

1 111 1111ĸ reports

Fig. X.1

Systèmes numériques HEIG-VD/SBA 2009

page 9 Pour additionner deux nombres A et B de quatre bits, nous pouvons donc utiliser un circuit selon le schéma bloc de la figure X.2. Il faut cependant constater qu'avec A = 0111 et B =

0001, par exemple, le report devra se propager à travers les quatre cellules.

Fig. X.2

Cette configuration est donc économique mais donne lieu à un temps de réaction assez long. Un premier pas vers une accélération du fonctionnement consiste à utiliser un additionner de deux nombres de quatre bits, tel le 74LS283 que nous connaissons déjà,

conçu globalement à partir d'une table de vérité à 9 variables d'entrée et non pas comme

une cascade d'additionneurs à un bit. S'il s'agit d'additionner des nombres de plus de quatre bits, en cascadant des 74LS283 nous aurons cependant encore un assez long temps de propagation du report.

X. 5 RETENUE ANTICIPÉE

La technique d'anticipation du report (carry look-ahead) nous permet d'accélérer la propagation du report d'un additionneur intégré au suivant. Pour comprendre cette

technique, examinons de plus près la table X.1 : les deux premières lignes ne génèrent pas

de report, les quatre suivantes génèrent un report s'il y avait un report d'entrée, nous dirons

qu'il y a propagation du report, alors que les deux dernières lignes génèrent de toutes façons un report.

Appelons G

N la fonction de génération du report et P N la propagation.

Nous avons G

N = A N and B N et P N = A N xor B N Ces deux fonctions ne dépendent donc pas du report d'entrée. C N A N B N S N C N+1 C N A 0 B 0 S 0 C N Aquotesdbs_dbs35.pdfusesText_40

[PDF] multiplication des nombres décimaux exercices

[PDF] organiser un concert dans une église

[PDF] organiser concert caritatif

[PDF] organiser un concert en plein air

[PDF] comment organiser un concert de musique

[PDF] comment organiser un concert de charité

[PDF] comment organiser un concert pdf

[PDF] organiser concert dans un bar

[PDF] la guerre de cent ans cm1 evaluation

[PDF] numéro siret collectivités territoriales

[PDF] obtenir numero siret gratuit

[PDF] immatriculation syndicat professionnel

[PDF] exercice sur les fonctions de référence seconde

[PDF] insee rouen

[PDF] moteurs de recherche français