Algoritmo de booth

Multiplicación: algoritmo de Booth
El algoritmo de Booth permite multiplicar números positivos y negativos representados en complemento a 2. Existen 2 posibles arquitecturas: Empleando el registroR2 para almacenar el multiplicador y mantenerlo la final de la operación. R1 contiene el multiplicando y C-R3-R4 contiene el resultado. R1 CONT

Operación {+,-}

R2

R2 -1

C

R3

R4Empleando el registro R4 para almacenar el multiplicador. El valor del multiplicador se pierde al final de la operación. R1 contiene el multiplicando y C-R3-R4 contiene el resultado. R1 CONT

Operación{+,-}

C

R3

R4

R4 -1

Principio de funcionamiento (empleando la primera arquitectura): Se analizan el bit menos significativo de R2 (R20) y R2-1 y se establecen los siguientes casos: R200 0 1 1 R2-1 0 1 0 1 Operación No se realiza ninguna operación R3=R3+R1 (Inicio cadena 0’s) R3=R3-R1 (Inicio cadena 1’s) No se realiza ninguna operación

En cada iteración se incrementa el contador(CONT), se desplaza C-R3-R4 a la derecha y se rota circularmente a la derecha R2.

Ejemplos:
a) A·B=01102·00102=0000011002 (610·210=1210) CONT 0 1 1 C R3 R4 R2321 R20 R2-1 Operación realizada0 0000 xxxx 001 0 0 Inicializar 0 0000 0xxx 000 1 0 Desplazar C-R3-R4, rotar R2-R2-1 0 0000 0xxx 000 1 0 R3=R3-A 1 1010 (R3=R3+ca2(A)) 1 1010 2 1 1101 00xx 000 0 1 Desplazar C-R3-R4, rotar R2-R2-1 2 11101 00xx 000 0 1 R3=R3+A 0 0110 0 0011 3 0 0001 100x 100 0 0 Desplazar C-R3-R4, rotar R2-R2-1 4 0 0000 1100 010 0 0 Desplazar C-R3-R4, rotar R2-R2-1 Nota: Rotando R2 una vez más se restaura el valordel multiplicador. b) A·B=01102·11102=1111101002 (610·(-210)=-1210) CONT 0 1 1 C 0 0 0 1 1 1 1 1 R3 0000 0000 0000 1010 1010 1101 1110 1111 R4 xxxx 0xxx 0xxx R2321 111 011 011 R20 0 1 1 R2-1 0 0 0Operación realizada Inicializar Desplazar C-R3-R4, rotar R2-R2-1 R3=R3-A

2 3 4

00xx 100x 0100

001 100 110

1 1 0

1 1 1

Desplazar C-R3-R4, rotar R2-R2-1 Desplazar C-R3-R4, rotar...