Multiplication séquentielle

Supposons que notre ALU contienne des registres de n bits. Un multiplieur séquentiel opère sur 2 nombres non signés, $A = a_{n-1} \ldots a_1a_0$ et $B= b_{n-1} \ldots b_1b_0$. Ces deux nombres sont contenus dans deux registres A et B, et on utilise un registre supplémentaire P. L'algorithme de calcul de $A\times B$ est le suivant :

1.

$P \leftarrow0$

2.

faire n fois

(a)

si le chiffre de poid faible de A est 1 alors

• $P \leftarrow P + B$,
• sinon $P \leftarrow P + 0$

(b)

décalage des registres P et A vers la droite : le bit de poids fort de P reçoit la retenue sortante, le bit de poids faible de P est transféré dans le bit de poids fort de A. L'ancien bit de poids faible de A est perdu.

Le résultat se trouve dans P (les bits de poids fort) et dans A (les bits de poids fables).

 

! n additions sont nécessaires