Fundamentos de investigacion

Algoritmo de Booth
El algoritmo de Booth es un procedimiento algorítmico para realizar la multiplicación de dos números con signo, expresados en base binaria en notación complemento a dos.
Procedimiento
Supongamos dos números, multiplicando y multiplicador, con longitudes en bits, x para el primero, e y para el segundo:
* Construimos una matriz de tres filas y x+y+1 columnas.Identificaremos las filas como, A la primera, S la segunda y P la tercera.
* Se inician los x primeros bits de cada fila con:
* A, el multiplicando.
* S, el complemento a dos del multiplicando.
* P, ceros.
* Los siguientes y bits se completan con:
* A, ceros.
* S, ceros.
* P, el multiplicador.
* Para finalizar la matriz, se inician a 0 todos los valoresde la última columna.

Una vez iniciada esta matriz, se realiza el algoritmo.
* Se realizan y iteraciones del siguiente bucle.
1. Comparar los dos últimos bits de P, para realizar la siguiente acción:
* 00 o 11: no se hace nada.
* 01: P = P + A. Se ignora el acarreo.
* 10: P = P + S. Se ignora el acarreo.
2. Desplazamiento aritmético de P a laderecha (se conserva el bit de signo).
* Finalmente, tras y iteraciones, se elimina el último bit de la derecha (menos significativo), obteniendo el resultado.

Multiplicación mediante el algoritmo de Booth
El algoritmo de booth es un algoritmo que sirve para multiplicar (y dividir) números binarios con signo de manera rápida y sencilla en complemento a dos. Aqui explico de manera detallada elfuncionamiento de ese algoritmo y muestro una implementacion del mismo para microcontroladores PIC.
La manera en que se representan los números binarios negativos es mediante su complemento a dos. El complemento a uno consiste en invertir el valor de cada bit, esto es que si se tiene el número 5 binario b’00000101′ su complemento a uno sería b’11111010′. Una vez teniendo el complemento a 1 paraobtener el complemento a dos simplemente se le debe sumar un 1, asi que se tiene b’11111010 + 1′ de modo que el complemento a dos del número 5 binario es b’11111011′.
Ese es un dato muy importante ya que de ese modo se representan los números binarios negativos y el complemento a dos es parte del algoritmo de multiplicación de Booth. También es importante explicar que utilizando números de 8 bitsel número mayor que se puede representar en complemento a dos es 127 y -127 que en binario son b’01111111′ y b’1000001′ respectivamente.
En ensamblador MPASM la manera de obtener el complemento a dos de un número es:
comf NUM,f
incf NUM,w
movwf NUMC2
donde NUM es el registro en el que se encuentra el número que se quiere pasar a complemento a dos y NUMC2 es el registro donde se guarda elcomplemento a dos del número. Hasta ahí todo bien, ahora pasemos al algorítmo.
Supongamos que queremos multiplicar dos números de 8 bits, digamos que queremos multiplicar 5*(-6) donde 5 es el multiplicando y -6 es el multiplicador, con esos datos se forman 3 arreglos distintos de la siguiente manera:
A=0000 0101 0000 0000 0
S=1111 1010 0000 0000 0
P=0000 0000 1111 1010 0
El byte superior de Aestá formado por el multiplicando, el siguiente byte se forma con ceros y se agrega un bit extra que también es 0.
El byte superior de S está formado por el complemento a dos del multiplicando, el siguiente byte al igual que el caso anterior se forma con ceros y al final se agrega un bit extra que es 0.
El byte superior de P está formado por ceros, el siguiente byte es el valor del multiplicador ypor ultimo se tiene el bit extra.
Se puede observar que los tres números formados son de 17 bits cuando los números que se van a multiplicar son de 8 de modo que los números formados siempre serán de N+1 bits, siendo N el número de bits de los factores.
Sigamos entonces. Este algorítmo consiste en comparar los últimos dos digitos del número P y dependiendo de el caso que sea realizar un suma...