Algoritmo de bot para multiplicacion

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 el funcionamiento 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. Elcomplemento 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 para obtener 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 deese 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 bits el 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 unnú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 el complemento 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 esel 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 A está 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 byteal 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 y por 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 o no realizar ninguna acción. Luego de evaluar cada caso se debe realizar un corrimiento a la derecha, manteniendo el valor del bit más significativo y desechando el valor del bit menos significativo. Los cuatrocasos que se tienen se pueden ver en la siguiente tabla:
0 0 -> No realizar ninguna acción
0 1 -> P = P + A
1 0 -> P = P + S
1 1 -> No realizar ninguna acción
Veamos el algoritmo paso a paso usando los numeros A, S y P de arriba. Primero tenemos el numero P original:
0000 0000 1111 101[0 0] P
Se comparan los ultimos dos digitos [0 0] con los cuatro casos posibles y se ve que no se deberealizar ninguna accion por lo que en la primer iteracion simplemente se realiza un corrimiento a la derecha:
1.
0000 0000 0111 110[1 0] ->
Ahora los ultimos dos digitos [1 0] indican que se debe realizar la suma P=P+S y despues el corrimiento a la derecha:
2.
1111 1011 0111 110[1 0] P=P+S
1111 1101 1011 111[0 1] ->
Despues del corrimiento los ultimos dos digitos son [0 1] por lo que se deberealizar la suma P=P+A y despues el corrimiento a la derecha:
3.
0000 0010 1011 111[0 1] P=P+A
0000 0001 0101 111[1 0] ->
Ahora los ultimos dos digitos son [1 0], se realiza la suma P=P+S y despues el corrimiento a la derecha:
4.
1111 1100 0101 111[1 0] P=P+S
1111 1110 0010 111[1 1] ->
Los ultimos dos digitos [1 1] al igual que cuando fueron [0 0] indican que solo se debe realizar el...