next up previous contents
Next: Multiplication à conservation de Up: Multiplication Previous: Multiplication

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).


 \begin{figure}
\leavevmode
\epsfxsize = 14 true cm
\epsfysize = 9 true cm
\epsfbox{multSeq.eps}\end{figure}


! n additions sont nécessaires




Patrick Marcel
2001-01-24