Vamos a ver ahora la tercera operación aritmética, la multiplicación.
Dados dos números, X e Y de n y m bits respectivamente, se
trata de calcular el producto P como la multiplicación de X por Y.
El valor más grande que puede tomar P corresponde al caso
en que tanto la X como la Y tomen su valor máximo,
2 elevado a n-1 y 2 elevado a m-1.
Haciendo unas pequeñas operaciones podemos ver que este valor es siempre
menor que 2 elevado a n+m, es decir P siempre
es un número que como máximo va a tener n+m bits.
Veamos un primer algoritmo para realizar el producto, vamos a expresar
Y como y_(m-1) por 2 elevado a (m-1)
mas y_(m-2) por 2 elevado a (m-2), más y_1 por 2
más y_0, tengamos en cuenta que todas
las y_i son simplemente 0s y 1s, y el
producto lo vamos a escribir como X multiplicado
por todo el número Y. El algoritmo simplemente lo que hace es
calcular cada uno de estos productos parciales, esto sería p_0, esto
sería p_1, esto sería p_(m-1)
y finalmente sumarlos todos. Estos productos
parciales son muy sencillos de realizar porque las y_i
siempre son o 0s o 1s,
es decir, el resultado será simplemente X por 2 o 0, o X por
2 al cuadrado o 0, y además sabemos que multiplicar
por 2 elevado a i en general es añadir i
0s a la derecha del número resultante.
Puesto que las y_i hemos dicho que son 0s o
1s, calcular cada uno de estos productos, calcular el producto del número
X por y_i es algo tan sencillo como utilizar
n puertas AND para ir generando los productos
booleanos, porque las y_i sólo son o 0s o 1s.
Oor otro lado, hacer los productos por las potencias
de 2 quiere decir simplemente ir colocando
0s a la derecha, es decir, el producto
p_0, X por y_0, imaginemos
que nos da este resultado, lo colocaríamos aquí.
El producto p_1, imaginemos que nos
de este resultado, estamos haciendo este ejemplo, ¿vale?
Lo colocaríamos para sumarlo pero habiéndole
añadido previamente a la derecha un 0,
o dicho de otra manera, desplazando previamente
el producto p_1 una posición hacia
la izquierda; p_2, que hay
que multiplicarlo por 2 al cuadrado, lo pondríamos
añadiéndole dos 0s; en este caso, fijaros
que el bit del multiplicando es 0, es
por eso que todo el resultado es 0. p_3, es cuando multiplicamos por este
1 y consistiría en multiplicar el resultado que hemos obtenido aquí
por 2 elevado a 4, sería colocar este resultado con 3 ceros a la derecha.
Aquí tenemos este segundo algoritmo que implementa de una manera digamos
condensada los productos parciales más la suma de todos los productos parciales.
Aquí tenemos un loop que va acumulando en una variable acc que inicialmente se
ha inicializado a 0 los productos de X por y_i por 2 elevado a i.
Este tipo de algoritmos sabemos bien como implementarlos, se trata en primer
lugar de construir un módulo básico
que implemente las operaciones internas al loop.
Se tratará de
este módulo básico donde va a entrar
el producto del número X, esto serán n bits por el y_i
correspondiente a un módulo que lo irá
acumulando, que lo irá sumando habiendo
añadido los 0s a la derecha que sean necesarios en cada
momento, a un valor acumulador de entrada y generará el valor de
acumulador de salida. En general este acumulador de salida en el
caso máximo tendrá un total de n+m bits y por lo tanto el de entrada también.
Y puesto que esto es una estructura loop que se repite m veces
lo que hemos de hacer es concatenar o conectar un total de m módulos
como el que acabamos de definir para tener el multiplicador que
deseamos. Tengamos en cuenta, como siempre, que las
líneas representan buses de tamaños n
en este caso y m+n en el resultado final y
en todos los resultados parciales, n+m, n+m, n+m,
y las entradas X siempre son de n bits. Pues ya
tenemos una manera de implementar la multiplicación con un sistema digital.
Vamos a ver la última operación aritmética, la división.
El planteamiento es el siguiente: dados dos números, X e
Y de n bits se trata de calcular dos
valores Q y R, cociente y resto, tal que se cumple esta condición.
El cociente Q va a ser en general un número fraccionario.
Para evitar el tener que ir controlando en cada momento
cuántas cifras enteras y cuántas cifras fraccionarias tiene el cociente
vamos a imponer la condición de que X sea menor
que Y, o dicho de otra manera, vamos a forzar
que Q sea un número fraccionario puro.
Puesto que Q será un número fraccionario,
de alguna manera hemos de determinar cuándo acabaremos
la división, en el fondo, cuántos bits vamos a permitir que tenga el cociente Q.
El número de bits de Q lo vamos a limitar a p bits, o lo que es lo mismo,
vamos a definir o a forzar que la precisión del resultado
será 2 elevado a menos p.
Que la precisión sea 2 elevado a -p quiere decir que el error que cometemos al
decir que Q es el resultado de la división de X partido por Y, el error este,
va a ser menor que 2 elevado a -p o, lo que es lo mismo, X/Y-Q,
que es lo mismo que R/Y, esto será menor que 2 elevado a -p;
es decir, R será siempre menor que Y por 2 elevado a -p.
Para calcular la división cuando no se cumpla esta condición de que la X
sea menor que Y, será necesario alinear
previamente los operandos y corregir el resultado obtenido.
Lo que vamos a hacer en el caso
de que la X sea mayor que la Y es sustituir la
Y por una nueva Y que será igual a la original multiplicada por
una cierta potencia de 2, digamos 2 elevado a k, tal que la X
sí que sea menor a Y por 2 elevado a k.
Una vez hecho esto, haremos la división de X entre Y', que ya
cumple la condición de que X sea menor que Y', y a
continuación el cociente que obtendremos tendremos
que corregirlo multiplicándolo por 2 elevado a k.
Para que la precisión del resultado
sea de Q sea 2 elevado a -p
necesitaremos calcular Q' con una precisión
de 2 elevado a -p más k. Esta definición
es equivalente a la que tenemos aquí a la derecha:
Se trata de calcular una pareja de números, Q y R, cociente
y resto, tal que X partido por Y sea igual al cociente más
el resto partido por Y, donde Q es un múltiplo de 2 elevado a -p, es
decir, la precisión de Q es 2 elevado a -p, sabiendo que el error
cometido es siempre menor 2 elevado a -p.
Aquí tenemos un algoritmo que refleja
bastante fielmente el proceso manual de división.
Inicializamos el resto, las r's son resto y las q's son
los distintos bits del cociente, inicializamos el resto
al valor de X y entramos en un loop que se
repite p veces; recordemos que p es el número de bits del cociente Q.
En cada iteración lo que hacemos es coger el resto, añadirle
un 0 por la derecha y restarle el divisor Y.
Si el resultado de esta
resta es positivo, ponemos un 1 en el cociente y
dejamos el resultado de la resta como resto.
Si la d es negativa, ponemos un 0 en el cociente y añadimos un 0
más a la derecha del resto, ... y esto lo repetimos p veces.
El resultado
será una serie de valores binarios de bits q(i),
que, puesto que sabemos que el número q es un número
fraccionario puro, tendremos que multiplicar por 2 elevado a -p.
Este sería el bit p-ésimo, y este sería el bit 1.
Por la misma razón, el resto tendremos que calcularlo
como el último valor calculado, el valor del resto calculado
en la iteración p multiplicado por 2 elevado a p.
Aquí tenemos un ejemplo cuando la X vale 21, la
Y vale 35 y forzamos que la precisión del resultado sea
2 elevado a -6. Inicialmente en r pondremos el
valor de X, y a continuación en la primera iteración en
i=1, calculamos d como 2 por r,
es decir, 21 por 2 = 42 menos 35, que es 7.
Aquí tenemos el valor de d. Puesto que d es positivo,
ponemos 1 en el cociente y dejamos esta diferencia en el resto.
Pasamos a la siguiente iteración, i=2, calculamos
de nuevo la d como 2 veces el resto anterior,
es decir 14, dos por siete 14 menos 35 nos da -21.
Como este valor es negativo ponemos un 0 en el
cociente, y dejamos como resto el valor anterior multiplicado por 2.
Tercera iteración, volvemos a multiplicar el último resto, 14 por 2,
28; le restamos 35, da -7. Como el resultado es negativo ponemos
un 0 en el cociente y dejamos como resto el valor anterior multiplicado
por 2, etc. Así podríamos continuar en la iteración
número 4 calculamos d como 2 por 28 menos 35, que es 21; 21 es un número
positivo, ponemos un uno en el cociente y dejamos este valor de d en
el resto. Bien, así hasta la iteración sexta.
Estos valores nos están diciendo cual será el cociente.
El cociente será 1 0 0 1 1 0; 1 0 0 1 1 0 en base 2
multiplicado por 2 elevado a -p; es decir, este será el cociente;
mientras que R será el último valor
calculado de R, 14, dividido por 2 elevado a 6.
Esto es un circuito
capaz de realizar la división binaria. Como siempre, lo que hemos de hacer
es crear un módulo básico capaz de implementar las operaciones internas al
loop, este es el módulo básico, donde lo que podemos
ver es que coge el número r, al que previamente se le ha concatenado un
0 por la derecha, es decir, coge 2 multiplicado por r,
le resta el valor de Y, y obtiene un resultado d.
Este resultado d puede ser positivo o negativo.
En el caso de que sea positivo estaríamos en esta situación.
En el cociente ha de aparecer un 1, de ahí que necesitemos
este inversor, y en el resto colocamos el valor de d puesto que
aquí tenemos un 0 se establece esta conexión, y en r me aparece d.
Si por el contrario, la resta d ha sido un número
negativo estamos en esta situación, hemos de poner un 0 en el
cociente y, puesto que aquí tendremos un 1, establecemos esta conexión y
en el resto colocamos el valor anterior del resto multiplicado por 2.
Este 2 por r,
otra vez, lo podremos implementar como r a la que
hemos concatenado un 0 por la derecha. Puesto que el loop se ejecuta
p veces, lo que hemos de hacer es utilizar p módulos
como los que acabamos de definir concatenados
de esta manera, conectados de esta manera, y este será el circuito capaz
de realizar la división binaria.
Valga decir que X e Y son números de n bits, por lo tanto estas líneas van a
ser buses de n bits y, en general, el resto siempre es un valor menor que X.
Puesto que aquí inicializamos el resto al valor de exactamente X,
las salidas r van a ser también buses de n bits.
Bien, pues este es el diseño
final del divisor binario.
Con esto acabamos esta lección. Hemos visto un conjunto de circuitos
capaces de ejecutar las operaciones de suma, resta, multiplicación y división,
y hemos introducido, aunque muy brevemente, la representación de números
negativos mediante el complemento a 2.
Elena ValderramaProfessor
Jean-Pierre DeschampsProfessor
Lluis TerésProfessor
Merce RullanProfesoraTitular
Joaquín Saiz AlcaineIngeniero Informático
David BañeresProfesor Agregado
Juan Antonio MartínezCollaborator
