UNIVERSIDAD NACIONAL DE COLOMBIA- SEDE MANIZALES
Informe 05 (FIBONACCI)
D. J. Estupian, L. P. Giraldo, Y. Idarraga, Sistemas Digitales Docente: Luis Enrique Avendao Laboratorio 05, 11 de enero de 2012
ResumenEste reporte muestra el diseo de un circuito secuencial capaz de realizar la Serie de Fibonacci. - Abstract - This report shows the design of a sequential circuit capable of performing the Fibonacci Series. Palabras Claves Secuencial, serie, Fibonacci.
I. I NTRODUCCIN En este documento se muestra el desarrollo del laboratorio, en el que se diseo un circuito secuencial capaz de realizar y mostrar mediante un display la Serie de Fibonacci. II. MARCO TERICO Sistemas Secuenciales A diferencia de los sistemas combinacionales, en los sistemas secuenciales, los valores de las salidas, en un momento dado, no dependen exclusivamente de los valores de las entradas en dicho momento, sino tambin dependen del estado anterior o estado interno. El sistema secuencial ms simple es el biestable, de los cuales, el de tipo D (o cerrojo) es el ms utilizado actualmente. La mayora de los sistemas secuenciales estn gobernados por seales de reloj. A stos se los denomina sncronos o sincrnicos, a diferencia de los asncronos o asincrnicos que son aquellos que no son controlados por seales de reloj. En todo sistema secuencial nos encontraremos con: 1. Un conjunto nito, n, de variables de entrada (X1, X2,..., Xn). 2. Un conjunto nito, m, de estados internos, de aqu que los estados secuenciales tambin sean denominados autmatas nitos. Estos estados proporcionarn m variables internas (Y1,Y2,..., Ym). 3. Un conjunto nito, p, de funciones de salida (Z1, Z2,..., Zp). Dependiendo de como se obtengan las funciones de salida, Z, los sistemas secuenciales pueden tener dos estructuras como las que se observan en la g 1, denominadas Mquina de Moore, a), y Mquina de Mealy, b).
Figura 1. Estructura Autmata de Moore, a), Autmata de Mealy, b)
Flip-op Los Flip-Flop o Biestable, como tambin se les conoce, son circuitos secunciales constituidos por puertas lgicas capaces de almacenar un bit, que es la informacin binaria ms elemental. Existe una gran variedad de biestables, los cuales se clasican en: Asncronos: R-S ; J-K ; T Sncronos: Activados por Nivel: R-S ; J-K ; D Activados por Flanco: Edgetriggered y Master-Slave (maestro-esclavo) R-S; D ; J-K ; T. Biestable Asncronos R-S: Posee dos entradas denominadas Reset (R) y Set (S) y dos salidas, Q1 y Q2. Este dispositivo se puede construir mediante dos puertas NOR o dos puertas NAND. Biestable Asncrono J-K: El biestable asncrono J-K es como el R-S, al cual se le ha eliminado el defecto de funcionamiento cuando las dos entradas valen 1. En este caso Q1 y Q2 siempre son complementarias. Biestable Asncrono T: Posee una sola entrada y dos salidas complementarias. Como ya se ha indicado, no se fabrica como tal, pero se construye fcilmente a partir de un biestable J-K, uniendo sus dos entradas. Biestables Sncronos Activados Por Nivel: Es esta una de las dos modalidades del sincronismo utilizadas para activar los biestables, es decir, para que la informacin presente en las entradas produzca efectos a la salida. Para que esto ocurra, en este tipo de biestable, es necesario que la seal de reloj se encuentre a nivel alto. Los cambios que se produzcan en las entradas de informacin, mientras dicha seal permanezca en este estado, se reejaran en la salida.
Dario Javier Estupian Vallejo: [email protected], Codigo 0810020, Estudiante de Ingenieria Electronica, Universidad Nacional de Colombia Manizales. Lizette Paola Giraldo Montoya: [email protected], Codigo 0810522, Estudiante de Ingenieria Electronica, Universidad Nacional de Colombia Manizales. Yuliana Idarraga Hernandez: [email protected], Codigo 0810034, Estudiante de Ingenieria Electronica, Universidad Nacional de Colombia Manizales.
UNIVERSIDAD NACIONAL DE COLOMBIA- SEDE MANIZALES
Biestable Sincrono R-S Activado Por Nivel: La forma ms elemental de construir un circuito R-S sincrono consiste en colocar dos puertas AND a la entrada de un R-S Asincrono. Mientras la seal de reloj permanece en nivel bajo, el valor de las entradas no produce ningun efecto sobre las salidas. Esta seal en nivel alto se convierte en una llave que permite el paso de la informacin. Biestable Sincrono J-K Activado Por Nivel: Se construye de la misma forma de los R-S, es decir, colocando un par de puertas AND a la entrada de un circuito Asncrono. Biestable Sincrono D Activado Por Nivel: Este dispositivo posee una entrada de datos (D), otra de reloj (C) y dos salidas complementarias (Q y Q). Su caracterstica fundamental reside en que el valor de la salida Q es igual que el de la entrada D siempre y cuando la seal de reloj este activa (nivel 1). Cuando la seal de reloj pasa a inactiva (nivel 0), el biestable queda enclavado con la informacin que tuviera en ese momento. A este tipo de biestable se le conoce tambin con el nombre de LATCH o cerrojo, y existe una gran variedad de circuitos integrados disponibles. Biestable Sincronos Activados por Flanco: Como hemos comprobado en los biestables activados por nivel los cambios producidos en las entradas, mientras permanece la seal de reloj en nivel activo, se reejan en la salida. Esta forma de funcionamiento puede ocasionar problemas cuando la conmutacin en las seales de entradas se realiza con una frecuencia elevada. Reducir el tiempo de duracin del nivel activo no es una solucin suciente, ya que este, por otra parte, debe ser lo sucientemente largo como para permitir la conmutacin de los dispositivos ms lentos que forman parte del sistema.
los dos anteriores. Para empezar a construirla necesitamos, por tanto, dos numeros de partida: a1 y a2 De esta forma,
a3 = a2 + a1
(2)
a4 = a3 + a2
(3)
y as sucesivamente. La ms conocida es la que tiene a1 = 1 y a2 = 1, cuyos trminos son: 1 1 2 3 5 8 13 21 34 55 89 144 233 377 ... nmeros que son conocidos como Nmeros de Fibonacci. Los trminos de cualquier sucesin de Fibonacci tienen la particularidad de que el cociente entre dos trminos consecutivos se aproxima al Nmero de Oro (1.6180339887499...), es decir, el lmite de los cocientes an+1/an tiende al Nmero de Oro cuando n tiende a innito. Adems, las series de Fibonacci cumplen otras curiosas propiedades, como por ejemplo, que la suma de n trminos es igual al trmino n+2 - 1:
a1 + a2 + a3 + a4 + ..... + an1 + an = an+2 1
(4)
Aparte de que esta sucesin tiene varias propiedades interesantes, como que se puede formar cualquier nmero natural mediante la suma de trminos de la sucesin, sin que ninguno se repita, lo ms curioso de esta sucesin es su presencia en la naturaleza. La sucesin de Fibonacci est muy ligado a la vida y estos hechos lo demuestran: Los machos de una colmena de abejas tienen un rbol genealgico que cumple con esta sucesin. El hecho es que los znganos, el macho de la abeja, no tiene padre (1), pero s que tiene una madre (1, 1), dos abuelos, que son los padres de la reina (1, 1, 2), tres bisabuelos, ya que el padre de la reina no tiene padre (1, 1, 2, 3), cinco tatarabuelos (1, 1, 2, 3, 5), ocho tataratatarabuelos (1, 1, 2, 3, 5, 8) y as sucesivamente, cumpliendo con la sucesin de Fibonacci. En la mano humana tambin se encuentra esta recurrencia, la longitud del metacarpo es la suma de las dos falanges proximales y la longitud de la primera falange es la suma de las dos falanges distales. El nmero de ptalos de una or es generalmente un trmino de Fibonacci. Hay ores con 2 ptalos, 3, 5, 8, 13, 21, 34, pero muy rara vez es un nmero que no est en esta sucesin. En la relacin entre la altura de un ser humano y la altura de su ombligo. En las espirales de los girasoles. Entre muchas otras.
Serie de FIbonacci En matemticas, la secuencia de Fibonacci es una serie de nmeros enteros que fue descrita por primera vez en Europa por Leonardo de Pisa, tambin conocido como Fibonacci. Una sucesin de Fibonacci es aquella cuya ley de recurrencia es:
an = an 1 + an 2 donde: an es el trmino en posicin "n" an1 es el trmino anterior (n-1) xn2 es el anterior a ese (n-2)
(1)
Es decir, cada termino de la sucesion se obtiene sumando
UNIVERSIDAD NACIONAL DE COLOMBIA- SEDE MANIZALES
III.
M ARCO E XPERIMENTAL
En esta practica se dise un circuito secuencial para implementar la serie de bonacci, que esta dada por la ecuacin 1. Para esto lo primero que se debe hacer es construir el diagrama de transicin de estados, y hacer la tabla de verdad que nos permita obtener las funciones de todos los estados siguientes. Para la primera parte del circuito, el contador de estados, la tabla de verdad es la siguiente: Estado 0 1 2 3 4 5 6 7 A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 Q1 0 0 0 1 1 1 1 1 Q2 0 1 1 0 0 1 1 1 Q3 1 0 1 0 1 0 1 1
Para obtener el circuito que realice en si la serie de Fibonacci, se tiene la tabla de verdad: Estado 0 1 2 3 4 5 6 7 A 0 0 0 0 1 1 1 1 B 0 0 1 1 0 0 1 1 C 0 1 0 1 0 1 0 1 V1 0 0 0 0 0 1 1 1 V2 0 0 0 0 1 0 1 1 V3 0 0 1 1 0 0 0 0 V4 1 1 0 1 1 0 1 1
Se procede de la misma manera y se obtienen las formulas para los estados siguientes V1, V2, V3, V4, los estados de visualizacion, y asi se tienen las siguientes expresiones: V1 = A(BxorC) V2 = AC V3 = AB V4 = AB + (AxorC) De esto se obtiene el circuito que se muestra en la gura 3
De la que se obtienen las formulas para los estados siguientes Q1, Q2, Q3, llegando a las siguientes expresiones: Q1 = A + BC Q2 = AC + (BxorC) A3 = AB + C Con esto el circuito obtenido para el contador de estados es el que se muestra en la gura 2
Figura 3. Circuito Serie de Fibonacci
Por nes practicos y con el objetivo de simplicar el circuito se decidi utilizar ip-po tipo D para el diseo del circuito. El circuito obtenido nalmente, integrando los dos expuestos con anterioridad, es decir el contador de estados y el contador de la serie de bonacci, es el que se muetra en la gura 4.
Figura 2. Circuito Contador de Estados
UNIVERSIDAD NACIONAL DE COLOMBIA- SEDE MANIZALES
Figura 4. Circuito Serie de Fibonacci y Contador de estados
IV.
CONCLUSIONES
Durante el desarollo de esta practica, se logr comprender mejor el funcionamiento de un sistema secuencial y todas sus posibles aplicaciones. Con la prctica se logro visualizar la serie de Fibonacci, lo que nos sirve de ejemplo para saber las muchas aplicaciones que tiene un contador. El uso de una serie secuencial no necesariamente implica que esta serie tiene que estar en orden, sino que tambin se puede realizar saltndose nmeros o en forma ascendente o descendente. Se aprendio el uso y el diseo de series secuenciales con manipulacin de ip op ya sea tipo D, JK o T. R EFERENCIAS
[1] [2] [3] [4] http://html.rincondelvago.com/circuitos-secuenciales.html. http://es.wikipedia.org/wiki/Sistema_secuencial. http://ciberconta.unizar.es/leccion/n005/700.HTM. http://html.rincondelvago.com/ip-op.html.
