Post on 17-Jul-2015
Presentan: Hctor Herrera Uco Ulises Santos Lpez
1
IntroduccinEl algoritmo de Booth es un algoritmo de multiplicacin para dos nmeros binarios con signo mediante el complemento a 2. El algoritmo fue inventado por Andrew Donald Booth en 1950.
2
Descripcin de funcionamiento Se define un byte A esta formado por el multiplicando , el siguiente
byte se forma con 0 y se agrega un bit extra que tambin es 0. Se define un Byte S que esta formado por el complemento a 2 del
multiplicando, el siguiente byte al igual que el caso anterior esta formado por 0 y al final se agrega un bit extra que es 0. Se define un byte P que esta formado por 0 , el siguiente byte es el
valor del multiplicador y por ultimo se obtiene un bit extra que es 0.
3
Descripcin de funcionamientoConsiste en comparar los ltimos dos dgitos del numero P y dependiendo del caso se realizara una suma o no se realizara ninguna accin, luego de evaluar cada caso se debe realizar el corrimiento de un bit hacia la derecha. Manteniendo el bit mas significativo y desechando el menos significativo.
4
Casos a evaluar0,0 0,1 1,0 1,1 No realizar ninguna accin. P=P+A. P=P+S. No realizar ninguna accin.
5
Obtencin del resultadoEl algoritmo obtiene el resultado realizando N interacciones (corrimientos hacia la derecha) que es el numero de bits de los factores.
6
EjemploSe requiere multiplicar 3 por -6 donde 3 es el multiplicando y -6multiplicador, con estos datos podemos definir A, S y P. A: 0000,0011,0000,0000,0 S: 1111,1101,0000,0000,0 P: 0000,0000,1111,101[0,0]
7
Como los dos ltimos bits de P son 00 no se realiza ninguna operacin tan solo se realiza el primer corrimiento. Pc1: 0000,0000,0111,110[10] Ahora los dos ltimos bits de P son 10 por lo que se debe realizar Pc2=(Pc1+S) y realizando el segundo corrimiento.
Pc1
0 01 1
01
01
01
01
00
01
00
10
10
10
10
10
00
10
00
S+Pc1+s
1 1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
Pc2: 1111,1110,1011,111[01]
8
Los dos ltimos bits ahora de P son 01 por lo cual se debe realizar Pc3=(Pc2+A) y su corrimiento a la derecha.Pc2
1 1 0 0
1 0
1 0
1 0
1 0
1 1
0 1
1 0
0 0
1 0
1 0
1 0
1 0
1 0
0 0
1 0
APc2+A
0 0
0
0
0
0
0
1
1
0
1
1
1
1
1
0
1
Pc3: 0000,0000,1101,111[10]
9
Los dos ltimos bits ahora de P son 10 por lo cual se debe realizar Pc4=(Pc3+S) y su corrimiento a la derecha.Pc3
0 0 1 1
0 1
0 1
0 1
0 1
0 0
0 1
1 0
1 0
0 0
1 0
1 0
1 0
1 0
1 0
0 0
SPc3+S
1 1
1
1
1
1
0
1
1
1
0
1
1
1
1
0
1
Pc4: 1111,1110,1110,111[11] Los siguientes 2 ltimos bits de P son 11 por lo que no se debe realizar ninguna operacin, tan solo se debe recorrer un bit a la derecha.10
Pc5: 1111,1111,0111,011[11] Pc6: 1111,1111,1011,101[11] Pc7: 1111,1111,1101,110[11]
Solo realizar corrimiento. Solo realizar corrimiento. Solo realizar corrimiento.
R=Pc8: [1111,1111,1110,1110(1)] (-18) Despus de 8 iteraciones se obtiene el resultado ya que los productos son de 8 bits. Comprobando: [0000,0000,0001,0010] (+18) [1111,1111,1110,1110] Ca2 de 18= (-18)
11