Estructura de Computadores: Contadores y Secuenciadores de la Universidad Europea

Estructura de Computadores

Contadores y Secuenciadores

Índice

Objetivos de aprendizaje 3 1. Presentación 3 2. Sistemas secuenciales 3 3. Máquina de Moore. 4 4. Tablas de transición para Moore 6 4.1. Tabla de codificación de estados. 6 4.2. Tabla de transiciones. 6 4.3. Equivalencia con estados codificados 6 4.4. Tabla de salidas 7 5. Transformación de las tablas de transición de estados a los flip-flop 7 6. Circuitos básicos: contadores 9 7. Contador en módulo P mediante máquina de Moore 10 8. Ejemplo completo de contador de unos en módulo 4 12 9. Resumen 14 Referencias bibliográficas 15

@ Copyright Universidad Europea. Todos los derechos reservados. 2

Objetivos de aprendizaje

Los objetivos que se pretenden alcanzar en este recurso son los siguientes: • Aprender que representan y cómo funcionan los sistemas secuenciales. • Identificar el funcionamiento de la máquina de Moore y saber interpretar su diagrama y tablas. • Analizar casos de circuitos secuenciales para ejemplificar los sistemas digitales existentes.

1. Presentación

A continuación se presentan los contenidos necesarios para saber cómo usar los registros junto con la lógica combinacional para generar circuitos secuenciales. Centraremos el estudio en los contadores y secuenciadores definidos por Moore. Hay que dejar claro que hay muchos más sistemas de control que utilizan esta tecnología, como compiladores o analizadores y otras técnicas de implementación (además de Moore), como por ejemplo Mealy. Tanto Moore como Mealy son dos maneras diferentes de construir un sistema secuencial. Por simplicidad, nos centraremos en uno de ellos, principalmente por ser un sistema secuencial de fácil comprensión (que sea un sistema de fácil comprensión no significa que sea el sistema más óptimo). La principal diferencia de un sistema secuencial frente a uno combinacional es que en los sistemas combinacionales las secuencias que se produzcan en las entradas dependerán de las secuencias que se produzcan en la salida, mientras que en los sistemas secuenciales también dependerá del estado actual, que se verá afectado por las secuencias de entradas anteriores.

2. Sistemas secuenciales

En los sistemas secuenciales las salidas dependen de las entradas y de los estados en los que se encuentre. Además, para cada conjunto de entradas la máquina evoluciona cambiando de estado. Así, el comportamiento para las salidas y los estados se puede definir de la siguiente manera: Z(t + 1) = E(t) . X(t) E(t+1) = E(t) . X(t) ¿Cuál es la nomenclatura de estas fórmulas? • Z(t + 1): salidas futuras del sistema. • E(t): estado actual.

@ Copyright Universidad Europea. Todos los derechos reservados. 3

• X(t): entradas actuales. • E(t + 1): estado futuro. A continuación se definen dos conceptos básicos para poder avanzar a lo largo del texto: 1. Máquinas finitas. Una máquina de estados finita es una máquina (digital en nuestro caso) en la que su construcción se puede realizar en un conjunto de estados finitos (puede ser de tamaño grande, pero finito). Hay que pensar en un semáforo o en una máquina de expendedora. Para utilizarlas hay que seguir una serie de pasos. Cada uno de esos pasos es un estado, siendo el comportamiento de la máquina diferente para cada uno de ellos. En el semáforo el avance de estado viene determinado por el reloj y en cada estado la salida es el conjunto de luces a encender, mientras que en la máquina expendedora, el avance viene determinado por la intervención del usuario y la salida es el mensaje de la pantalla, el avance de motores, etc. 2. Diagramas y tablas de transición. Antes de profundizar en cada una de las máquinas hay que entender el significado de los diagramas y tablas de transición y su correcto funcionamiento. Un diagrama de estados es semejante a un árbol o grafo de estados, donde reflejaremos los estados mediante un círculo, en el que se indicará el estado en el que nos encontramos y una flecha, que indicará la existencia de una transición entre un estado y otro o entre el mismo estado. Sobre este diagrama debemos identificar las entradas con las transiciones (entre un estado y otro, o entre el mismo estado) y las salidas con los círculos. Se dice que una tabla de transición de estados es la representación de un diagrama de transición de estados, donde la tabla se encuentra compuesta por: o Filas, identificando los estados que hay en el diagrama. o Columnas, identificando las combinaciones de la entrada.

3. Máquina de Moore

En una máquina de Moore la salida depende del estado. Debido a que el estado únicamente varía en función de la señal de reloj (de forma síncrona), las salidas se realizarán de la misma manera. Estas son las funciones por las que se rige la máquina de Moore:

@ Copyright Universidad Europea. Todos los derechos reservados. 4

E2/Z2 E1/Z1 E3/Z3

Funciones de la Máquina de Moore

Observemos el diagrama y supongamos que la máquina se encuentra en el estado E1: • Si la entrada es XA, la máquina avanza hasta el estado E2. • Si la entrada es XB, avanzaremos al estado E3. En cada estado las salidas tienen un valor determinado Z1, Z2 0 Z3 si la máquina se encuentra en el estado E1, E2 0 E3 respectivamente.

Representación del diagrama de Moore y sus tablas: el reconocedor de secuencias 11

En este diagrama obtendremos como salida 1 si la secuencia es 11. Desde el punto de vista de los estados:

@ Copyright Universidad Europea. Todos los derechos reservados. 5

EO -> X(t - 1) = 0 Representa el estado de "no hay nada reconocido", es decir, la última entrada ha sido un 0. E1 -> X(t - 1) = 1, X(t - 2) = 0 Representa el estado de "tengo un 1 reconocido", es decir, la última entrada ha sido un 1, pero la anterior a esta un 0. E2 -> X(t - 1) = 1, X(t - 2)= 1 Tengo dos 1 reconocidos, es decir, las dos últimas entradas han sido un 1.

4. Tablas de transición para Moore

Como ya hemos comentado, las tablas de transición son una representación organizada de la información contenida en un diagrama de transición de estados. Las tablas necesarias para representar toda la información que aparecen en los diagramas son las siguientes:

4.1. Tabla de codificación de estados

En este caso, al tener más de dos estados, tres en nuestro caso, se necesitan dos bits para codificar el estado:

4.2. Tabla de transiciones

Codifica cómo evoluciona la máquina de estado según las entradas:

4.3. Equivalencia con estados codificados

Como se puede ver a continuación, no importan los estados:

@ Copyright Universidad Europea. Todos los derechos reservados. 6

4.4. Tabla de salidas

En todas estas tablas, que no son más que tablas de verdad, solo queda por identificar las entradas y las salidas. • Entradas: estado actual [Q1(t), Qo(t)] y entradas [X(t)]. • Salidas: estado futuro [Q1(t+1), Qo(t+1)] y salidas [Z(t)].

5. Transformación de las tablas de transición de estados a los flip-flop

El circuito combinacional resultante se realimenta; es decir, en un cambio de estado con la entrada al sistema de una nueva señal de "entrada", el circuito avanza calculando el estado futuro. Posteriormente, este estado futuro pasa a ser estado actual. Esto se realiza mediante una realimentación de las salidas con las entradas. Para que esta realimentación sea síncrona se necesitan intercalar en el circuito biestables que hacen que la transición del estado futuro al estado presente sea coordinada. ¿Cuál sería el esquema general de una máquina secuencial? El esquema general de una máquina secuencial, haciendo el sincronismo con biestables D, sería el siguiente:

@ Copyright Universidad Europea. Todos los derechos reservados. 7

Ejemplo del reconocedor de secuencia 11 con biestables D

Una vez determinada la tabla de transiciones, y con todos los elementos codificados en binario, solo hay que codificar las funciones de salida con respecto a las de entrada: • Función de salda: Z(t)=f(Q1 (t), Qo (t)). • Función de transición bit1: Q1 (t+1)=f(Q1 (t), Qo (t),X(t)). • Función de transición bit0: Qo (t+1)=f(Q1 (t), Qo (t),X(t)). Como las salidas del sistema se van a almacenar temporalmente en biestables D, podemos interpretar que la salida de nuestro sistema no es Qx(t+1), sino D x. Así Q1(t+1)=D1 y Qo(t+1)=Do.

Tabla 1. Resultado final

De la tabla anterior se obtiene la siguiente función: D1 = x · (Q0 + Q1), Do = x · 20 . Q1

@ Copyright Universidad Europea. Todos los derechos reservados. 8

Tabla 2. Resultado final

De esta segunda tabla se obtiene esta otra función: Z - Q! Por último, únicamente nos quedaría implementar el circuito lógico para la tabla que anteriormente habíamos diseñado. Quedaría implementado teniendo como entradas X(t) y la señal de reloj y como salida Z(t). ¿Cómo se realiza la implementación de un circuito lógico?

Proceso detallado de implementación de un circuito lógico

6. Circuitos básicos: contadores

Los circuitos contadores unicamente se van a encargar de realizar la cuenta del número de pulsos recibidos en la entrada de reloj. Este tipo de circuitos se implementa de una manera más sencilla haciendo uso de los biestables de tipo T. Dichos biestables los organizaremos en cadena uno detrás de otro. Se presentan, a continuación, los distintos tipos de contadores: • Contador asincrono. En el contador asincrono la entrada será la señal de reloj del primer biestable, mientras que la salida de cada uno de los biestables que

@ Copyright Universidad Europea. Todos los derechos reservados. 9