Multiplicacionj Binaria Mediante Algoritmo

Multiplicación binaria mediante algoritmo.

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.

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:

...