MicroPIC

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. 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 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 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 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 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 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 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 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 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 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 cuatro casos 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 debe realizar 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 debe realizar 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 corrimiento a la derecha:

5.
1111 1111 0001 011[1 1] ->

De nuevo se tiene [1 1] por lo que se realiza unicamente el corrimiento y en lo sucesivo se tendra siempre el mismo caso:

6. 1111 1111 1000 101[1 1] ->
7. 1111 1111 1100 010[1 1] ->
8. 1111 1111 1110 0010 [1] ->

Despues de 8 iteraciones termina el algoritmo, se desecha el bit menos significativo (el bit extra) y se obtiene el producto de la multiplicacion:
5*(-6) = 1111 1111 1110 0010 = -30

Cabe mencionar que el numero de iteraciones que realiza el algoritmo es igual N, que es el numero de bits de los factores y el resultado final es igual a 2N, en este caso se multiplican factores de 8 bits por lo que el resultado final es de 16.

Esta es la manera en la que funciona el algoritmo. Solamente hay que tener en cuenta que al realizar los corrimientos a la derecha se debe mantener siempre el bit mas significativo, esto es que si se tiene ‘1101′ y se realiza el corrimiento el resultado sera ‘1110′ y no ‘0110′.

Implementacion del algoritmo de Booth en MPASM

Aplicando los pasos que acabo de explicar realice una implementacion del algoritmo de Booth para la multiplicacion en MPASM para realizar multiplicaciones de numeros signados de 8 bits en microcontroladores PIC 16F.

El algoritmo implementado sigue los mismos pasos descritos, compara los ultimos dos digitos del factor P y realiza alguna de las acciones posibles para despues llevar acabo el corrimiento. Como mencione en un principio el algoritmo solo puede multiplicar numeros que van del -127 al 127 y el resultado lo da a traves de los registros RESULTADOH:RESULTADOL.

Para poder utilizar esta rutina (multibooth) se deben declarar los registros A1, A2, A3, S1, S2, S3, P1, P2, P3, MULTIPLICANDO, MULTIPLICADOR, RESULTADOH, RESULTADOL y CONT.

En los registros RESULTADOH:RESULTADOL se muestra el valor positivo del resultado y si este fuera negativo se activa la bandera SIGNO (bit 0 del registro A3) para indicar que se trata de un numero negativo.

Una vez explicado el algoritmo creo que no hay necesidad de explicar la implementacion de la rutina aunque si asi fuera siempre estan los comentarios para exponer y aclarar las dudas.

Espero que esto les sirva.

Descargar codigo: Multiplicacion mediante el algoritmo de Booth