Cours de l’Arithmétique des ordinateurs

• Comment les nombres négatifs sont-ils représentés ? 
• Quel est le plus grand nombre qui puisse être représenté par un mot machine ? 
• Que se passe-t-il si une opération génère un nombre plus grand que ce qu’il n’est possible de représenter ? 
• Qu’en est-il des fractions et des nombres réels ? 

Comment le matériel fait-il réellement pour additionner, soustraire, multiplier ou diviser des nombres le plus rapidement possible ? 

Le but de ce chapitre est de dévoiler ce mystère 

Chapitre 4 :Arithmétique des ordinateurs 

1. Abdesslem Page : 1 

1011 en base 2, représente : 

( 1 * 23) + ( 1 * 22) + ( 0 * 21) + ( 1 * 20)dix= ( 1 *8 ) + ( 1*4 ) + ( 0 * 2 ) + ( 1*1 ) dix = 8 + 4 + 0 + 1 dix = 11 dix Puisqu’un mot MIPS possède 32 bits , le nombre 1101deuxsera représenté comme suit : (32 bits de large ) 

• Le bit du poids faible est le bit le plus à droite. 
• Le bit du poids fort est le bit le plus à gauche. 

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

Représentation des nombres 

1. Abdesslem Page : 2 

Représentation distinguant le positif du négatif : 

• Utilisation de 1 bit de signe : ⇒ 0 va avoir une représentation positif et négatif 

Un nombre ayant deux représentations est plus grave qu’un déséquilibre entre les nombres positifs et les nombres négatifs. 

• Complément à 2 (adopter pour les ordinateurs 32 bits) 

0000 0000 0000 0000 0000 0000 0000 0000deux = 0 dix 0000 0000 0000 0000 0000 0000 0000 0001deux = 1dix 0000 0000 0000 0000 0000 0000 0000 0010deux = 2dix 

………………………………………………………………………. 0111 1111 1111 1111 1111 1111 1111 1110deux = 2.147.483.646dix 0111 1111 1111 1111 1111 1111 1111 1111deux = 2.147.483.647dix 

Représentation des nombres 

1. Abdesslem Page : 3 

0000 0000 0000 0000 0000 0000 0000 0000deux = 0 dix 0000 0000 0000 0000 0000 0000 0000 0001deux = 1dix 0000 0000 0000 0000 0000 0000 0000 0010deux = 2dix 

………………………………………………………………………. 0111 1111 1111 1111 1111 1111 1111 1110deux = 2.147.483.646dix 0111 1111 1111 1111 1111 1111 1111 1111deux = 2.147.483.647dix 1000 0000 0000 0000 0000 0000 0000 0000deux = -2.147.483.648 dix 1000 0000 0000 0000 0000 0000 0000 0001deux = -2.147.483.647 dix 

………………………………………………………………………. 1111 1111 1111 1111 1111 1111 1111 1110deux = -2 dix 1111 1111 1111 1111 1111 1111 1111 1111deux = -1 dix 

Représentation des nombres 

1. Abdesslem Page : 4 

• Cette convention s’appelle complément à deux : tout les nombres négatifs ont un 1 comme bit de poids fort. 
• Le matériel n’a donc besoin de tester que ce bit pour déterminer si un nombre est positifs ou non . 
• Ce bit particulier est appelé souvent le bit de signe. 
• Un nombre binaire de 32 bits sera alors représenté comme suit : 

(x31 * -231)+ ( x30 * 2 30 ) + …………….+ ( x1 * 2 1 ) + (x0 * 20) 

xi: signifie : le ième bit de x 

• x + (-x) = 0 
• 1 seul nombre négatif -2.147.483.648 dix qui n ’a pas de nombre positif correspondant 

Représentation des nombres 

1. Abdesslem Page : 5 

Exemple: 

Prendre l’opposé de 2 dix et ajouter 1 2 dix = 0000 0000 0000 0000 0000 0000 0000 0010 deux 

Prendre l’opposé de ce nombre en inversant ses bits et en ajoutant 1 donne : 

1111 1111 1111 1111 1111 1111 1111 1101 deux +0000 0000 0000 0000 0000 0000 0000 0001 deux ——————————————————— 

= 1111 1111 1111 1111 1111 1111 1111 1110 deux = -2 dix 

Représentation des nombres 

1. Abdesslem Page : 6 

Par conséquent : 

Ä La manière de convertir un nombre binaire représenté avec n bit en un nombre représenté avec plus de n bits: extension signée. 

Répliqué le bit du signe: 

(16)bits : 0000 0000 0000 0010 deux 2 dix (32)bits : 0000 0000 0000 0000 0000 0000 0000 0010 deux -2 dix 

(16) bits : 1111 1111 1111 1110 deux 

(32) bits : 1111 1111 1111 1111 1111 1111 1111 1110 deux 

• -x = x + 1 

Représentation des nombres 

1. Abdesslem Page : 7 

On peut faire des décalages à droite ou à gauche de tout les bits d’un mots tout en remplissant les bits vidés par des zéro . 

Exemple : 

le registre $16 contient 0000 0000 0000 0000 0000 0000 0000 1101deux 

Une instruction de décalage de 8 bit vers la gauche du contenue du registre $16 va donner comme résultat: 

0000 0000 0000 0000 0000 1101 0000 0000 deux 

Il existe deux instructions pour ce genre d’opération : 

• sll (shift left logical ) Décalage à gauche . 
• srl (shift right logical ) Décalage à droite . 

Soit l’instruction MIPS suivante 

sll $10 , $16 , 8 # reg $10 = reg $16 << 8 bits 

Opérations logiques du MIPS 

1. Abdesslem Page : 8 

Sll et srl sont deux opérations logiques dans le format de l’instruction en MIPS et du type R , ici la valeur de décalage 8 est mise dans le champs decval , la version en langage machine sera alors : 

op rs rt rd decval fonct 

0 0 16 10 8 0 

Opérations logiques du MIPS 

1. Abdesslem Page : 9 

and $8,$9,$10 # reg $8 = reg $9 ET reg$10 

$9 contient :0000 0000 0000 0000 0000 1101 0000 0000 deux 

$10 contient :0000 0000 0000 0000 0011 1100 0000 0000 deux 

$8 contient 0000 0000 0000 0000 0000 1100 0000 0000 deux 

or $8,$9,$10 # reg $8 = reg $9 OU reg$10 

$8 contient 0000 0000 0000 0000 0011 1101 0000 0000 deux 

andi $8,$9,100 # reg $8 = reg $9 ET 100 

ori $8,$9,100 # reg $8 = reg $9 OU 100 

Opérations logiques du MIPS 

1. Abdesslem Page : 10 

Commencer par les petits éléments pour aboutir a un ensemble plus complexe (du bas en haut) 

La conception est un processus créative et non une simple méthode 

Processus de conceptionConception 

CPU – La conception est l’assemblage 

des différents composants. 

Datapath Control 

– Décomposition de haut en bas 

ALU Regs Shifter 

d’une fonction complexe (fonctionnement) en fonctions primitives. 

Nand Gate 

1. Abdesslem Page : 11 

Top-Down Design Bottom-Up Design 

Démarche descendante 

Démarche ascendante 

Raffinement de chaque constituant 

Abstraction sur un ensemble de constituants 

Conception Architecturale 

Conception Architecturale 

Conception Logique 

Conception Logique 

10/11/2012 06:36 I. Abdesslem 

Démarche Démarche de de conception conception 

Spécification 

Placement/Routage 

Silicium 

–12 – 

Exigences : 

beq, bne, slt, slti, sltu, sltiu 

addu, subu, addiu: (sans détection de débordement). 

add, sub, addi: (détection de débordement). 

add, addu, sub, subu, addi, addiu 

and, or, andi, ori 

Conception de l’UAL 

1. Abdesslem Page : 13 

Format des instructions arithmétiques de MIPS 

Type-R : 

Type-I : 

31 25 20 15 5 0 

op Rs Rt Rd funct 

op Rs Rt Immed 16 

Type op funct 

ADDI 10 xx 

ADDIU 11 xx 

SLTI 12 xx 

SLTIU 13 xx 

ANDI 14 xx 

ORI 15 xx 

XORI 16 xx 

LUI 17 xx 

Type op funct 

ADD 00 40 

ADDU 00 41 

SUB 00 42 

SUBU 00 43 

AND 00 44 

OR 00 45 

XOR 00 46 

NOR 00 47 

Type op funct 

Type op funct 

SLT 00 52 

SLT 00 52 

SLTU 00 53 

SLTU 00 53 

1. Abdesslem Page : 14 

L’Unité Arithmétique et Logique 

Spécification fonctionnelle Entrées: 2 x 32-bit opérandes A, B, 4-bit pour mode. Sorties: 32-bit résultat S, 1-bit retenu, 1 bit débordement Opérations: add, addu, sub, subu, and, or, xor, nor, slt, sltU 

Diagramme de bloc : 

32 32 

CFZFA OF 

B UAL 

m 4 (S-selec (2 bits), Invert, Cin) S 

32 Registres temporaires à 32 bits 

Operations signés : débordement pas de retenu ! 

1. Abdesslem Page : 15 

Décomposition du diagramme de bloc 

A 32 B 

32 

a31 b31a0 b04 

ALU31 mco s31 

cin ALU0 

mco s0 

cin M 

OF 

ZF 

32 S 

Réalisation de l’UAL de 32 bits en termes de 32 UAL à 1 bit 

1. Abdesslem Page : 16 

Conception de l’UAL à 1 bit 

Les opérations logiques : 

S-select 

A 

Mux Result 

B 

andor 

1. Abdesslem Page : 17 

Conception de L’UAL à 1 bit 

B 

Cin 

A 

1-bit Full 

S Adder 

Cout 

0 1 1 1 

+ 

0 0 1 0 1 (0) 0 (1) 0(1) 1 (0) 

Fonction combinatoire 

Cin AS B 

Cout 

1. Abdesslem Page : 18 

Conception de L’UAL à 1 bit 

aibi 

S-select CarryIn 

andor 

Result 

add 

Mux 

1-bit Full AdderCarryOut 

1. Abdesslem Page : 19 

Conception de L’UAL à 1 bit 

• A – B = A + (– B) = A + B + 1 Mettre Invert à 1 et mettre CarryIn à 1 

invert S-select AB Mux 

CarryIn 

andor 

Result 

1-bit 

add Full AdderCarryOut 

Mux 

1. Abdesslem Page : 20 

UAL 32 bits 

• Elle est obtenue en connectant 32 UAL 1 bit les unes aux autres. 
  

invertI. Abdesslem 

Page : 21 

Qu’en est t’il pour l’instruction slt ? 

Qu’en est t’il pour le branchement conditionnelle ? 

32 32 

CF A OF 

B UAL m 4 S 

32 

résultat 

ZF 

Exercices 

1. Abdesslem Page : 22 
   

L’UAL construite ne réalise pas l’instruction de positionnement si inferieur slt. (slt $1,$2,$3) 

On rappelle que slt produit 1 dans $1 si $2 < $3, et 0 sinon. 

Il faut utiliser l’entrée e3 qui prend la valeur de s31 (bit le plus significatif) du multiplexeur 

Si s31 = 1 (c-à-d le résultat est négatif) on positionne donc tous les bits de $1 à 0 sauf le bit de poids faible. 

Page : 23 I. Abdesslem 

Déroulement de l’instruction Slt 

L’UAL élémentaire 

invert 

CIn 

S-select Si 

Bi Mux 

add 

1. Abdesslem Page : 24 

2 Ai 

andor 

1-bit Full Addere3 

CO 

Mux 

Slt $1,$2,$3 

Page : 25 

1. Abdesslem 

Correction 

Slt $1,$2,$3 

1. Abdesslem 

Page : 26 

Déroulement de l’instruction Beq et Bne 

1. Abdesslem 

Page : 27 

Diagramme de bloc 

Mode et débordement 

A 32 B 

32 

a31 b31 

a0 b04 

ALU0 co s31 cin ? 

ALU0 co s0 

cin M 

cin M 

Produire S-select, Invert, 

32 

c-in, … 

Débordement 

S

1. Abdesslem Page : 28 

Complement Décimale 

binaire à 2 0 0000 1 0001 2 0010 3 0011 

00000 -11111 -21110 -3 

1101 4 0100 5 0101 6 0110 7 0111 

-41100 -51011 -61010 -7 

1001 Examples: 7 + 3 = 10 mais … 

-8 1000 10 

1 

1 1 0 1 1 1 

71 1 0 0 

+ 

0 0 1 1 3 

+ 1 0 1 1 1 0 1 0 

– 6 

0 1 1 1 

1. Abdesslem Page : 29 

-4 – 5 = -9 mais … 

Overflow 

Décimale 

– 4 – 57 

Détection de Débordement 

• Débordement: le résultat est assez grand ou assez petit pour être représenté. 

Example: – 8 ≤ 4-bit nombre binaire ≤ 7 

• Lorsqu’on additionne deux nombres de signes différents 

Ä Pas de débordement 

• Débordement se présente lorsqu’on additionne : 
• 2 nombres positives et leurs sommes est négative. 
• 2 nombres négatives et leurs somme est positive. 
• si Carry in UAL31 ≠ Carry out UAL31 on peut détecter le overflow. 

10 

1 

1 1 0 1 1 1 

71 1 0 0 

+ 

0 0 1 1 3 

+ 1 0 1 1 1 0 1 0 

– 6 

0 1 1 1 

1. Abdesslem Page : 30 

0 

–4–57 

Logique de détection de débordement 

• Débordement = CarryIn[N – 1] XOR CarryOut[N – 1] 

A0B0 

CarryIn0 

CarryOut0 A1B1 

1-bit ALU Result0 

X Y X XOR Y 

CarryIn1 

0 0 0 0 1 1 1 0 1 

CarryOut1 

1 1 0 

A2B2 

1-bit ALU Result1 

CarryIn2 

A3B3 

1-bit ALU Result2 

CarryIn3 

CarryOut3 1-bit ALU Result3 

Overflow 

1. Abdesslem Page : 31 

Amélioration de la performance (méthode de la retenue anticipé) 

C0 = Cin 

A B C-out A0B0GPS0 0 0 “kill” 

0 1 C-in “propage” 1 0 C-in “propage” 

C1 = G0 + C0 • P0 

1 1 1 “génère” 

A1B1GSPG = A and B génère une retenue P = A xor B propage une retenue 

C2 = G1 + G0 • P1 + C0 • P0 • P1 

A2B2GSPC3 = G2 + G1 • P2 + G0 • P1 • P2 + C0 • P0 • P1 • P2 

A3B3 

GS P 

G 

C4 = . . . 

P 

1. Abdesslem Page : 32 

Pour Améliorer le temps de propagation de la retenue è utilisation d’additionneur complet avec propagation et génération de la retenue 

G0 = A0 and B0 génère une retenue P 0= A0 xor B0 propage une retenue 

1. Abdesslem 

Page : 33 

G0 P0 

Additionneur complet à 1 bit avec génération et propagation de la retenue 

C0 S0 A0B0 

Amélioration de la performance (méthode de la retenue anticipé) 

CLA 

4-bit Adder 

4-bit Adder 

4-bit Adder 

C0 

G0P0C1 = G0 + C0 • P0 

C2 = G1 + G0 • P1 + C0 • P0 • P1 

GP 

C3 = G2 + G1 • P2 + G0 • P1 • P2 + C0 • P0 • P1 • P2 

1. Abdesslem C4 = . . . 

Page : 34 

Exigences additionnelles (Multiplication) 

Instruction Example Meaning add add $1,$2,$3 $1 = $2 + $3 subtract sub $1,$2,$3 $1 = $2 – $3 add immediate addi $1,$2,100 $1 = $2 + 100 add unsigned addu $1,$2,$3 $1 = $2 + $3 subtract unsigned subu $1,$2,$3 $1 = $2 – $3 add imm. unsign. addiu $1,$2,100 $1 = $2 + 100 

multiply mult $2,$3 Hi, Lo = $2 x $3 multiply unsigned multu$2,$3 Hi, Lo = $2 x $3 divide div $2,$3 Lo = $2 ÷ $3, 

Hi = $2 mod $3 divide unsigned divu $2,$3 Lo = $2 ÷ $3, 

Hi = $2 mod $3 Move from Hi mfhi $1 $1 = Hi Move from Lo mflo $1 $1 = Lo 

1. Abdesslem Page : 35 

• Exemple de multiplication (non signée): 

Multiplicande 1000 Multiplicateur 1001 1000 0000 0000 1000 Produit 01001000 

• m bits x n bits = m+n bit produit (en ignorant le bit de signe) 
• Multiplication binaire est simple: 

– 0 => place 0 ( 0 x multiplicande) – 1 => place une copie ( 1 x multiplicande) 

• 4 versions de multiplications (matériel et algorithme): 

(Multiplication, non signée) 

1. Abdesslem Page : 36 

0 0 0 0 

A3 A2 A1 A0 A3 A2 A1 A0 B1A3 A2 A1 A0 B2A3 A2 A1 A0 B3 

• Etage P7 

i accumule P6 P5 A * P2 4 i si BP3 i == 1 P2 P1 P0 • Pour multiplier 32 bit pb. de hardware? 

B0 

(Multiplication, non signée) 

1. Abdesslem Page : 37 

Chemin de données multiplication (Version 1) 

1 ère proposition : Registre Multiplicande (64-bit), UAL 64-bit, registre produit (64-bit), Registre multiplicateur (32-bit). 

0000…00000000 Produit 

Multiplicande 0000…00001000 

Shift Left 

64 bits 

Shift Right 64-bit UAL 

32 bits 

Write Contrôle64 bits 

Multiplicateur = chemin de données + contrôle 

Bit n°0 

1. Abdesslem 

Multiplicateur 

0000..1001 

Page : 38 

Algorithme de muliplication (Version 1) 

début 

Multiplicateur0 = 1 Multiplicateur0 1. Test Multiplicateur0 = 0 1a. Add multiplicande au produit & placer le résultat dans le registre Produit 

• Produit Multiplicateur Multiplicande 

2. Shift le registre Multiplicande de 1 bit à gauche. 0000 0000 0011 0000 0010 

• 0000 0010 0001 10000 0100 
• 0000 0110 0000 20000 1000 

3. Shift le registre Multiplicateur de 1 bit à droite. 

• 0000 0110 0000 30001 0000 
• 0000 0110 0000 4 

0010 0000 

32nd 

Non: < 32 répétitions répétition? 

Fin 

Oui: 32 répétitions 

1. Abdesslem Page : 39 

La moitié (1/2) des bits de la multiplicande était toujours à 0 

UAL 64-bit semble lente et peu économique 

0 est insérer à gauche de la multiplicande lors du décalage => les bits de poids faible du produit ne peuvent jamais changés une fois qu’ils sont crées. 

Qu’est ce qui ce passe si on décalais le produit à droite? 

Observations sur la (Version 1) 

1. Abdesslem Page : 40 

• Registre Multiplicande (32-bit), UAL (32 -bit), registre Produit 64-bit, registre Multiplicateur 32-bit. 
  

Product 

Multiplier 

Shift Right 

Contrôle

Hardware multiplication (Version 2) 

Multiplicande 

32-bit UAL 

32 bits 

1. Abdesslem Page : 41 

32 bits 

64 bits 

Write 

Shift Right 

B0B1B2B3P0 P1 P2 P3 P4 P5 P6 P70 0 0 0 A0 A1 A2 A3 

A0 A1 A2 A3 

A0 A1 A2 A3 

A0 A1 A2 A3 

• Multiplicande ne change pas et le produit se décale à droite 

Comment Ça marche? 

1. Abdesslem Page : 42 
   

début Algorithme de multiplication (Version 2) 

0000 0000 0011 0010 1: 0010 0000 0011 0010 2: 0001 0000 0011 0010 3: 0001 0000 0001 0010 1: 0011 0000 0001 0010 2: 0001 1000 0001 0010 3: 0001 1000 0000 0010 1: 0001 1000 0000 0010 2: 0000 1100 0000 0010 3: 0000 1100 0000 0010 1: 0000 1100 0000 0010 2: 0000 0110 0000 0010 3: 0000 0110 0000 0010 

0000 0110 0000 0010 

Multiplicateur0 = 1 

1. Multiplicateur0 Test Multiplicateur0 = 0 1a. Add multiplicande à la moitié gauche du produit & place le résultat dans la moitié gauche du registre produitProduct Multiplicateur Multiplicand 

12332nd 

répétition? 4 

2. Shift le registre produit à droite de 1 bit. 

Non: < 32 répétitions 

1. Abdesslem Page : 43 
2. Shift le registre multiplicateur à droite de 1 bit. 

FinOui: 32 répétitions 

• Seule la partie gauche du produit est modifiée. (sur 32 bits) Ä Combiner le registre produit et le registre multiplicateur (gagner de l’espace) 
• Registre multiplicande (32-bit), UAL 32 -bit, Registre produit (64-bit) dont 32 registre multiplicateur 

Multiplicande 

32 bits 

32-bit UAL 

Shift Right Produit (Multiplicateur) 

Contrôle 

64 bits 

Write 

Observations sur la (Version 2) et hardware de la (Version 3) 

1. Abdesslem Page : 44 

Algorithme de multiplication (Version 3) 

début 

Multiplicande Produit 

0010 0000 0011 0010 0010 0011 0001 0001 0010 0011 0001 0001 1000 0010 0000 1100 0010 0000 0110 

Produit0 = 1 

1. Produit0 Test Produit0 = 0 1a. Add multiplicande à la moitié gauche du produit & Place le résultat dans la moitié gauche du registre produit2. Shift le regsitre produit à droite de 1 bit. 1234 

32nd répétition? 

Non: < 32 répétitions 

1. Abdesslem Page : 45 

FinOui: 32 répétitions 

Observations sur la version 3 de la multiplication 

• 2 étapes pour chaque calcul d’un bit (multiplicateur et produit combinés) 
• Hi/Lo sont les deux demies parties du registre produit gauche et droite 
• MultU, multiplication non signée 
• Comment réaliser la multiplication d’une manière plus vite? 
• Comment on traite la multiplication signée? 

– Algorithme de Booth est une manière élégante pour la 

multiplication des nombres signées en utilisant le même matériel utilisée en version 3, de plus on gagne dans certains cycles. 

1. Abdesslem Page : 46 

Motivation pour l’algorithme de Booth 

• Example 2 x 6 = 0010 x 0110:0010 x 0110 + 0000 décalage (0 multiplicateur) + 0010 addition (1 multiplicateur) + 0010 addition (1 multiplicateur) + 0000 décalage (0 multipliacteur) 

…00001100 

• UAL addition ou soustraction peut avoir le même résultat mais de manière différente: 
• 6 = – 2 + 8 0110 = – 00010 + 01000 = 11110 + 01000 
• For example 0010 x 0110 

0000 décalage(0 multiplicateur) – 0010 sub(le premier 1 du multiplicateur) 

0000 décalage (les 1 de milieu) + 0010 addition (juste après la liste des 1) 

00001100 

1. Abdesslem Page : 47 

Algorithme de booth 

fin d’exécution 

Milieu 0 1 d’ 1 Execution 1 1 0 Début d’exécution Bit courant Bit à droite Explication Example Op 

1 0 début d ’exe. des 1s 0001111000 sub 1 1 milieu d ’exe. des 1s 0001111000 rien 0 1 fin d ’exe. des 1s 0001111000 add 0 0 milieu d ’exe. des 0s 0001111000 rien 

temps d’exécution est meilleur (décalage est plus rapide que l ’addition) 

• Remplacer la chaîne de 1s dans le multiplicateur par une soustraction lorsqu’on identifie le premier 1et une addition pour le bit juste après le dernier 1 de la chaîne.

1. Abdesslem Page : 48 

Exemple (2 x 7), algorithme de Booth 

Opération Multiplicande Produit suivant? 

1. Val. initiale 0010 0000 0111 0 10 -> sub 

1a. P = P – m 1110 + 1110 1110 0111 0 dec. P (ext. signée) 

1b. 0010 1111 0011 1 11 -> nop, dec. 

2. 0010 1111 1001 1 11 -> nop, dec. 
3. 0010 1111 1100 1 01 -> add 

4a. 0010 + 0010 

0001 1100 1 dec. 

4b. 0010 0000 1110 0 fin 

1. Abdesslem Page : 49 

Exemple (2 x -3), algorithme de Booth 

Opération Multiplicande Produit suivant? 

1. Val. initiale 0010 0000 1101 0 10 -> sub 1a. P = P – m 1110 + 1110 1110 1101 0 dec. P (ext. signée) 

1b. 0010 1111 0110 1 01 -> add + 0010 

2a. 0001 0110 1 dec. P 

2b. 0010 0000 1011 0 10 -> sub + 1110 

3a. 0010 1110 1011 0 dec. 

3b. 0010 1111 0101 1 11 -> nop 

4a 1111 0101 1 dec. 

4b. 0010 1111 1010 1 Fin 

1. Abdesslem Page : 50 

Preuve de l’algorithme de Booth (représentation complément à 2) 

Soit a: multiplicateur et b: multiplicande, ai: le i eme bit de a. 

ai ai-1 opération 

0 0 Ne rien faire 0 1 Ajout de b 1 0 Soustraire b 1 1 Ne rien faire 

ai-1-ai01 -10Un décalage à gauche de la multiplicande peut être considéré comme une multiplication par une puissance de 2 selonba 

× ( 

Booth () = 

= ab 

baabaa × – 

)).2(….)2()2(( 01 – 31 

– (…2)() × 31 + + a 10 30 – × × 1 + 30 + + a 0 0 + baa 29 – 30 (2) × × 30 + baa 30 – 31 2) × × 31 Représentation en complément à 2 

1. Abdesslem Page : 51 

Observations sur l’algorithme de Booth 

• Problème pour des 1 isolées (addition suivi d’une soustraction) 
• Résolution du pb grâce là la factorisation judicieuse de la représentation en complément à 2 

Exercice 

Algorithme de Booth , réduire le nombre d’op. éviter les op. en présence de 0 et 1. Modifier l’algorithme de Booth pour traiter 3 bits à la fois et calculer la multiplicande 2 bits par 2 bits. 

1. Abdesslem Page : 52 

Division 

1001 Quotient Diviseur 1000 1001010 Dividende 

–100010101 

1010 –100010 reste (ou modulo résulatat) 

Le grand nombre a soustraire, création d ’un bit à chaque étape 

binaire => 1 * diviseur ou 0 * diviseur Dividende = Quotient x Diviseur + Reste 

=> | Dividend | = | Quotient | + | Diviseur | 

3 versions de divisions, comme pour la multiplication (plus simple au moins coûteux) 

1. Abdesslem Page : 53 

Division version 1 du matériel 

• registre Diviseur 64-bit, UAL 64 bit, registre Reste 64 bit, registre Quotient 32 bit. 
  

Reste 

Ecrire Control 64 bits 

diviseur 

Décalage à droite 

64 bits 

Décalage à gauche 

UAL 64-bit 

Quotient 

32 bits 

1. Abdesslem Page : 54 

Algorithme de division (version 1) 

début: Placé la dividende dans le reste 

1. Sub registre diviseur du register reste et 

placer le résultat dans le registrer reste . 

reste ≥ 0 

Test Reste < 0 reste 

2a. Décalage du 

2b. Restaurer la valeur en additionnant le registre quotient 

registre diviseur au reste et en plaçant la à gauche en 

somme dans le registre reste. de plus, décalage insérant un 1 

du registre quotient en insérant un 0. 

3.décalage de 1 bit vers la droite du registre diviseur . 

n+1 repetition? 

Fin 

Non: < n+1 répétitions 

Oui: n+1 répétitions 

1. Abdesslem Page : 55 

Exemple de division (7 / 2) 

Reste Quotient Diviseur 0000 0111 0000 0010 0000 1: 1110 0111 0000 0010 0000 2: 0000 0111 0000 0010 0000 3: 0000 0111 0000 0001 0000 1: 1111 0111 0000 0001 0000 2: 0000 0111 0000 0001 0000 3: 0000 0111 0000 0000 1000 1: 1111 1111 0000 0000 1000 2: 0000 0111 0000 0000 1000 3: 0000 0111 0000 0000 0100 1: 0000 0001 0000 0000 0100 2: 0000 0011 0001 0000 0100 3: 0000 0011 0001 0000 0010 1: 0000 0001 0001 0000 0010 2: 0000 0001 0011 0000 0010 3: 0000 0001 0011 0000 0001 

12345 

réponse 

réponse 

Quotient = 3 Reste = 1 

Quotient = 3 Reste = 1 

1. Abdesslem Page : 56 

Observations sur la version 1 de la division 

• 1/2 des bits du diviseur sont toujours à 0 => 1/2 des 64-bit de l’addition 

=> 1/2 du diviseur 

• au lieu de décaler le diviseur à droite, on décale le reste à gauche? 
• La première étape, ne peut produire un 1 dans le bit quotient (sinon ça serais plus grand) 

=> décalage avant la soustraction, Gagner une itération. 

1. Abdesslem 

Page : 57 

Division version 2 du matériel 

• registre Diviseur 32-bit, UAL 32 bit, registre Reste 64 bit, registre Quotient 32 bit. 
  

1. Abdesslem 

Reste 

Diviseur 

32-bit ALU 

32 bits 

64 bits 

Quotient 

Shift Left 

Ecrire 

32 bits 

Shift Left 

Control

Page : 58 

Algorithme de division (version 2) 

début: Placer la dividende dans le registre reste 

3.décalage de 1 bit vers la gauche du registre reste 

2b. Restaurer la valeur ancienne en additionnant le registre diviseur à la partie gauche du reste et en plaçant la somme dans la partie gauche du registre 

reste. De plus, décalage du registre quotient en insérant un 0. 

2a. Décalage du registre quotient à gauche en insérant un 1 

n repetition? 

1. Abdesslem 

Non: < n répétitions 

Page : 59 

1. Sub registre diviseur de la partie gauche du registre reste et placer le résultat dans la partie 

gauche du registre reste 

reste ≥ 0 

Test Reste < 0 reste 

Fin 

Oui: n répétitions 

Reste Quotient Diviseur 

0000 0111 0000 0010 1: 0000 1110 0000 0010 2: 1111 1110 0000 0010 3: 0000 1110 0000 0010 1: 0001 1100 0000 0010 2: 1111 1100 0000 0010 3: 0001 1100 0000 0010 1: 0011 1000 0000 0010 2: 0001 1000 0000 0010 3: 0001 1000 0001 0010 1: 0011 0000 0001 0010 2: 0001 0000 0001 0010 3: 0001 0000 0011 0010 

1. Abdesslem 

1réponse 

Quotient = 3 2Reste = 1 

34 

Page : 60 

Exemple de division (7 / 2) 

Division version 3 du matériel 

• registre Diviseur 32-bit, UAL 32 bit, registre Reste 64 bit, 0 registre Quotient. 

Diviseur 

32 bits 

32-bit UAL 

“HI” “LO” Shift Left reste (Quotient) 

Control 

64 bits 

Ecrire 

1. Abdesslem 

Page : 61 

Algorithme de division 

Début: placer la dividende dans la moitié droite reste (version 3) 

3b. Restaurer la valeur originale en additionnant le registre diviseur à la moitié gauche du registre reste , et place la somme dans la moitié gauche du registre reste. Décaler le registre reste en insérant un 0. 

1. Abdesslem 

1.décalage du registre reste à gauche de 1 bit. 

2. Soustraire le diviseur de la moitié gauche du registre reste et placer le résultat dans la moitié gauche du registre reste. 

Reste ≥ 0 

Test Reste < 0 Reste 

3a. Décalage du registre reste à gauche en insérant un 1 dans le nouveau bit 

nth 

Non: < n repetitions répétition? 

Oui: n répétitions Décalage de la moitié gauche du registre reste à droite de 1 bit. 

Page : 62 

Reste Diviseur 0000 0111 0010 0000 1110 0010 

1: 1111 1110 0010 2: 0001 1100 0010 

1: 1111 1100 0010 2: 0011 1000 0010 1: 0001 1000 0010 2: 0011 0001 0010 

1: 0001 0001 0010 2: 0010 0011 0010 

3: 0001 0011 0010 

1. Abdesslem 

1réponse 

Quotient = 3 2Reste = 1 

34 

Page : 63 

Exemple de division (7 / 2) 

Observations sur la version 3 de la division 

• Même matériel que la multiplication: UAL pour additionner ou soustraire, un registre 64 bit pour décaler à droite ou à gauche. 
• Les registres Hi et Lo de MIPS sont combinés pour être utilisées comme registre 64-bits à la division et à la multiplication. 
• Division signée: faire la division positive, modifier le signe du quotient ou du reste si nécessaire. 

– Note: la dividende et le reste doivent avoir le même signe. 

– Note: 

• –7 ÷ 2 = –3, reste = –1 
• –7 ÷ 2 = –4, reste = +1 (juste en formule mais plus difficile à mettre en œuvre) 

1. Abdesslem Page : 64 

télécharger gratuitement cours de l’Arithmétique des ordinateurs