En semanas anteriores estudiamos la síntesis directa de circuitos combinacionales a partir de estructuras algorítmicas del tipo if then else, case, y todas estas. Pues bien, esta relación entre algoritmos y circuitos también existe en el caso de circuitos secuenciales. Y este es el tema que vamos a analizar en esta lección. Algunos sistemas son, digamos secuenciales por su propia naturaleza, como por ejemplo, todos aquellos sistemas que incluyen una referencia you sea implícita o explícita a intervalos de tiempo sucesivos. Hemos vistos casos de estos anteriormente, por ejemplo, hemos visto circuitos que son capaces de generar o detectar secuencias de símbolos, o circuitos que son capaces de controlar la ejecución de secuencias de eventos. Y no solo eso, incluso algunos algoritmos que no incluyen referencias temporales también pueden implementarse utilizando circuitos secuenciales. Estudiaremos esta relación entre algoritmos y circuitos secuenciales a través de un primer ejemplo. Vamos a construir un circuito que calcula la raíz cuadrada por defecto de un número natural x. Lo vamos a hacer utilizando un algoritmo, un método, muy sencillo, simplemente vamos a ir calculando los cuadrados de los números naturales, uno al cuadrado, dos al cuadrado, tres al cuadrado, n al cuadrado, y vamos a ir comparando el número x con cada uno de estos valores. En el momento que el último valor de uno de estos cuadrados que cumple que x todavía es menor que el valor al cuadrado, nos está dando la raíz cuadrada por defecto, la raíz cuadrada de x por defecto será i menos uno, y el menos uno ponemos el menos precisamente porque calculamos la raíz cuadrada por defecto. ¿Bien? Vale, pues este algoritmo realiza estos cálculos a base de ir computando cada vez parejas de dos números, r y s, tal que s es r más uno al cuadrado. Fijaros, dice, lo que haría el algoritmo es ir calculando todas estas parejas cuando r vale cero, s vale cero más uno, uno, al cuadrado, que es uno. Cuando r vale uno s es uno más uno, dos, al cuadrado, cuatro, etcétera. Y fijaros que aquí las, la s, que son cada uno de estos valores al cuadrado, que hemos ido calculando aquí, aparecen desplazadas respecto al número natural cuyo cuadrado es precisamente la s, es decir, dos al cuadrado es cuatro y el dos aparece fijaros en la iteración siguiente. Tres al cuadrado es nueve y en cambio el tres aparece en la iteración siguiente. Y esto se hace simplemente para que cuando encontremos el último valor de s tal que x todavía es menor o igual que s, directamente el valor de, de r, nos de directamente la raíz cuadrada por defecto y no tengamos que restarle uno como en este caso. Bien, este es el algoritmo básicamente, dentro de este loop lo que hace el algoritmo es primero calcular r más dos al cuadrado y después incrementar en uno el valor de r. Para evitar tener que hacer este, este cuadrado, este elevar al cuadrado, se utiliza esta igualdad. R más dos al cuadrado se puede ver como r más uno al cuadrado, más dos veces r más uno, más uno, pero hemos dicho que r más uno al cuadrado es s, ¿eh? De aquí que r más dos al cuadrado se pueda escribir como s más dos veces r más uno, más uno, que es exactamente el término que tenemos aquí. Bien, bueno, podéis seguir el algoritmo en esta tabla para comprobar que funciona como hemos dicho. Y aquí tenemos un ejemplo para x igual a 47, ¿no? Iríamos calculando todas estas parejas, este sería el resultado de las parejas, y la condición de finalización del loop es que s sea menor o igual que el número x cuya raíz cuadrada queremos calcular. Si x es 47 pues en la primera iteración s es menor que 47, por lo tanto la condición se cumple, continuaríamos ejecutando el loop. En la segunda iteración cuatro sigue siendo menor que 47, por lo tanto se sigue ejecutando el loop, seguiríamos así hasta que s alcanza el valor 49, en ese momento la s you no es menor o igual que 47, la condición no se cumple y por lo tanto se acaba el loop, y cuando acabamos el loop definimos que la raíz cuadrada es el valor de r en esa iteración. El valor de r en este caso sería seis. Un comentario antes de continuar con el algoritmo. Éste, el que hemos visto, no es un algoritmo eficiente para calcular la raíz cuadrada, pero aún así lo mantenemos por razones didácticas, ¿de acuerdo? Fijaros, el número de pasos necesarios para calcular la raíz cuadrada por defecto de un número x es la propia raíz cuadrada. Cuando hemos visto el ejemplo de x igual 47, la raíz cuadrada por defecto es seis y hemos visto que necesitábamos iterar el algoritmo, iterar el loop seis veces. Quiere decir que si x es un número de n bits y por lo tanto x el mayor valor que puede tomar es dos elevado a n menos uno, el número de pasos necesarios para calcular la raíz cuadrada será del orden de dos elevado a n partido por dos. Y esto es un, coste digamos, un número de iteraciones que crece exponencialmente. Bien, de todas maneras, mantenemos este algoritmo seguimos con él, si queremos implementarlo pues sabemos cómo hacerlo, de hecho tendríamos que construir un módulo básico, como siempre, que nos implementa las operaciones del loop, y a continuación añadir, concatenar, convenientemente tantos módulos como sea necesario. Y aquí viene el problema. ¿Cuántos módulos son necesarios? Dice pues el problema es que a priori no lo sabemos porque a priori no sabemos cuándo va a dejar de cumplirse la condición s menor o igual que x. Este es el problema. Esto quiere decir que tal cual no podríamos implementar este algoritmo con técnicas combinacionales como las que hemos visto hasta ahora. Pero lo que podemos es modificar este algoritmo. Vamos a hacer la siguiente modificación. Si se cumple la condición del when estaríamos aquí, hacemos las operaciones definidas dentro del loop, es decir, calculamos el valor siguiente de r y s, tal como hacíamos anteriormente. Si por el contrario la condición no se cumple, es decir, de hecho lo que ocurre es que you hemos finalizado el cálculo, entonces seguiremos manteniendo el valor de la última r y la última s calculada. Esta estructura if then else si sabemos implementarla, necesitaríamos pues definir un módulo básico que en función de x, r y s va calculando los siguientes valores de next r y next s. Esto sería más o menos pues un comparador, capaz de compararnos el valor de x con el valor de s, y el resultado de este comparador, imaginemos que el comparador diese un uno si solo si, se cumple la condición, nos definiría dos caminos de datos distintos, a través de dos multiplexores dos a uno, de n bits, que nos irían calculando next r y next s, de la siguiente manera, aquí tendríamos un módulo que nos calcularía estas operaciones, vamos a llamarlo el módulo A, en caso de que se cumpla la condición next r será el valor calculado en este módulo y next s será el valor calculado en este módulo, y en caso de que no se cumpla la condición pues el valor de next r será el valor de r y el valor de next s será el valor de s. ¿Eh? Aquí tendríamos que hacer esta conexión y esto sería el módulo básico que estamos buscando. Todo lo que tendríamos que hacer ahora es concatenar estos módulos de manera que las entradas r y s de cualquiera de los módulos coincide con las salidas next r y next s del módulo anterior. La salida next r del primer módulo calcula la raíz cuadrada de x en caso de que x sea menor que dos, o devuelve un uno en caso contrario. Si realmente la x es menor que dos las salidas del resto de los módulos siguen manteniendo los mismos valores de r y s, y por tanto por root acabaremos viendo el valor que se ha generado en el primer módulo. La salida del segundo módulo calcula la raíz cuadrada de x siempre que x esté comprendido entre dos y cuatro, o devuelve el dos en caso contrario. Y otra vez ocurre lo mismo. Si realmente la x está entre estos valores, a partir de aquí todo el resto de módulos repetirán los valores de r y s y por root nos aparecerá la raíz cuadrada correcta. Y así, como veis, sucesivamente. Desafortunadamente, si bien este circuito es teóricamente posible construirlo, no nos va a resultar útil en la gran mayoría de los casos. Recordemos que decíamos que si x es un número de n bits, es decir, la raíz cuadrada es del orden de dos elevado a n partido por dos, el número de pasos que necesitamos, el número de iteraciones que requiere el algoritmo es del orden de dos elevado a n partido por dos, y por lo tanto el número de módulos básicos que necesitamos es también de este orden. Exactamente, si n es un número par necesitaremos dos elevado a n partido por dos menos uno, y si n es impar necesitaremos dos elevado a n partido por dos, n partido por dos calculado por defecto. Un ejemplo sencillo si trabajamos con números de 32 bits, el número de pasos del algoritmo, el número de iteraciones es del orden de dos elevado a 16, más de 65000, y por lo tanto, el número de módulos que necesitaremos es del orden de 65536. Número evidentemente exageradamente grande. Se impone pues buscar otra solución. Vamos a intentar ahora una implementación secuencial del algoritmo. Los circuitos combinacionales implementan básicamente funciones booleanas, pero los circuitos secuenciales hemos visto que incorporan dos posibilidades más, el poder recordar eventos, es decir, la capacidad de memoria, y dos, la posibilidad de establecer en qué instante de tiempo definido por una variable externa a la que llamamos reloj, se ejecuta cada acción, la capacidad de memoria y la capacidad de sincronización. Lo que vamos a hacer es, vamos a aprovechar esta capacidad de memoria y vamos a guardar en la memoria los valores calculados de r y s. Y además vamos a asociar las acciones a realizar a ciclos de reloj. Por ejemplo, en el primer ciclo de reloj vamos a inicializar los valores de r y s y en cada uno de los ciclos sucesivos de reloj vamos a implementar una iteración del algoritmo. Este es el circuito secuencial que proponemos. Hemos dicho que asociábamos a cada ciclo de reloj una iteración, por ejemplo, a este ciclo de reloj le vamos a asociar la iteración cero, la iteración cero es esta primera parte de inicialización de los valores de r y s, a este ciclo de reloj le vamos a asociar la iteración uno, la iteración dos, etcétera. ¿Qué quiere decir? Que durante este tiempo, durante este ciclo, es cuando se implementarán, se ejecutarán las operaciones correspondientes a la primera iteración del bucle, aquí se implementarán las, las operaciones correspondientes a la segunda iteración, etcétera. Este circuito combinacional nos va calculando en cada momento los siguientes valores de r y s de acuerdos, de acuerdo con el algoritmo. De hecho este circuito combinacional es el mismo bloque, body loop, que vimos en, en las implementaciones anteriores. Y estos valores next r y next s que calcula el circuito combinacional entran en la memoria cuando llega el siguiente flanco de reloj, es decir, cuando acabamos una iteración y comenzamos la otra, de ahí que digamos que la actualización de los valores de r y s, la sincronización tiene lugar en este punto. Hemos añadido además una variable end que toma el valor uno cuando deja de cumplirse la operación, la condición, es decir, cuando hemos de salir de loop, cuando hemos acabado todas las operaciones. Cuando salimos del loop el valor que tenemos guardado en r es el valor que se va a devolver como resultado de la raíz cuadrada. Esta es la señal end correspondiente a esta variable. Llegados a este punto nos podríamos plantear el porqué no hemos utilizado un grafo de comportamiento para describir es te circuito. Vamos a hacer unos pocos números. Si x es un número de n bits vamos a necesitar dos n bits de memoria, n para guardar r y n para guardar s. A la hora de construir el grafo de comportamiento nos planteábamos qué debe recordar el circuito. En este caso el circuito lo que debe recordar son las parejas r y s. ¿Y cuántas parejas r y s hay? Pues si r tiene n bits hemos quedado que el número de parejas es aproximadamente igual a n, dos elevado a n partido por dos. Es decir, nuestro grafo necesitaría dos elevado a n partido por dos, nodos. Os recuerdo el ejemplo anterior, que si n era igual a 32 dos elevado a n partido por dos es 65536, como veis un número de nodos excesivamente alto. Lo que es más, si tenemos que el número x tiene n bits, quiere decir que hay dos elevado a n posibles combinaciones de entradas y que por lo tanto el número de arcos posibles del grafo de comportamiento sería dos elevado a n, por dos elevado a n partido por dos. Es decir, la conclusión es que si el número de nodos, si el número de estados que requiere nuestro circuito es pequeño o moderado podemos trabajar con los grafos de comportamiento, si este número es excesivamente grande, el grafo de comportamiento no nos va a solucionar el problema y entonces hemos de ir hacia soluciones de tipo algorítmico, soluciones de tipo implementación directa del algoritmo con un sistema secuencial como la que hemos visto hasta ahora.
