La hormiga

Problema 1: Se desea diseñar una máquina secuencial cuyo objetivo es permitir a la hormiga encontrar la salida del laberinto.

La hormiga dispone de dos sensores: en las antenas izquierda y derecha (I y D), que están en 1 si la antena respectiva entra en contacto con las paredes del laberinto sino están en cero (entradas a la máquina de estados finitos)

La hormiga también dispone de tres señales de actuación, que son las salidas de la máquina: una señal para avanzar hacia delante A, otra para doblar levemente hacia la izquierda DI y otra para doblar levemente hacia la derecha DD.

La estrategia para diseñar el cerebro de la hormiga es mantener la pared a la derecha de la hormiga. Para ello debe indicar lo siguiente:

a. Diagrama de estados

b. Tabla de estados

c. Circuito secuencial lógico

d. Simulación asumiendo valores correspondientes

Laberinto

Solución

Para desarrollar el diagrama de estados, se elige emplear el modelo de Moore. Es decir, las salidas estarán asociadas al estado.

Se definen los estados posibles, y en cada uno de éstos debe observarse los valores de las entradas que llevan a otros estados. Debe notarse que se tienen cuatro combinaciones posibles para los valores permitidos a las entradas, esto implica dibujar 4 transiciones a estados próximos. Sin embargo es posible simplificar el diagrama rotulando las transiciones como una expresión lógica de las entradas.

Ejemplos:

 Si debe pasarse a cierto estado cuando cualesquiera de las antenas tocan una pared, la transición puede rotularse ( I + D).

 Si debe pasarse a cierto estado cuando ambas antenas no tocan a alguna pared, la transición puede rotularse ( I ' D'). Es decir, que ambas no toquen.

 Si la transición es cuando la izquierda no toque y la derecha entre en contacto con la pared, la transición se anota: (I' D).

Para encontrar los estados debe analizarse las diversas situaciones en que se puede encontrar la hormiga en su recorrido del laberinto. Observando las entradas, y las acciones que ésta puede realizar, a continuación se plantean algunas de las situaciones:

No se encuentran otras situaciones que no se hayan planteado, entonces se procede a conectar los diferentes estados, mediante el siguiente un diagrama:

Nótese que los estados E y G se tratan como si fuera un solo estado. En ambos se toca con la antena izquierda, y el objetivo(local, para cumplir la estrategia) es dejar de tocar la pared.

El diagrama muestra que los estados B y C podrían tratarse como uno solo(son equivalentes). Ya que tienen iguales salidas; y para iguales entradas, se pasa a igual estado próximo(más adelante se verán algoritmos para determinar estados equivalentes).

Si se funden los estados B y C se llega al siguiente diagrama, que representa el cerebro de la hormiga:

Problema 2: Diseñe un contador síncrono de 3 bits con control de modo X.

Si X = 0 el contador es binario ascendente. Si X = 1 el contador avanza según código Gray. Utilice FF JK. Para ello debe indicar lo siguiente:

a. Diagrama de estados

b. Tabla de estados

c. Circuito secuencial lógico

d. Simulación asumiendo valores correspondientes

Solución

A continuación se indican las secuencias:

binario: 000, 001, 010, 011, 100, 101, 110, 111

Gray: 000, 001, 011, 010, 110, 111, 101, 100

El diagrama de estados se construye para la secuencia binaria, con transiciones con entrada de control igual a cero. Luego, se marcan las transiciones para contar en Gray:

Problema 3: Diseñe un reconocedor de patrón finito que consta de una entrada X y salida Z. La salida se activa cada vez que se presenta la secuencia 010, y mientras que la secuencia 100 no se haya presentado, en cuyo caso la salida se desactiva permanentemente.

Ejemplos de secuencias X/Z que se deben obtener:

X: 0 0 1 0 1 0 1 0 0 1 0 …

Z: 0 0 0 1 0 1 0 1 0 0 0 …

X: 1 1 0 1 1 0 1 0 0 1 0 …

Z: 0 0 0 0 0 0 0 1 0 0 0 …

Solución

Luego deben completarse las transiciones que faltan.

Si en E5 llega un cero, debe ir al estado permanente E6, ya que habría reconocido la secuencia 100. Si estando en E3 (los últimos 3 bits de la secuencia son 010) llega un 1, los últimos dos serán ahora 01, esto implica pasar al estado E2.

En E1 debe permanecer si llegan secuencias de ceros. En E4 debe permanecer

...