Recodage de Booth

Le but de ce recodage est de réduire le nombre de produits partiels. Il est basé sur la constatation suivante : $2^{i+j} - 2^i = 2^{i+j-1} + 2^{i+j-2} + \ldots + 2^i$Ainsi lors d'une multiplication, lorsqu'une séquence de j 1 apparait dans le multiplicande (du bit i + j -1 au bit i), on peut remplacer les jadditions par :

• une addition pour le rang i+j et
• une soustraction pour le rang i.

Par exemple le nombre 000111110011100 se recode en 0010000 0100 00, où indique une soustraction et 1 indique une addition.

? Multiplier 3 par 15 en employant le recodage de Booth.

! Recodage non lié à une implantation particulière.