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.
