Matematica Discreta
Reynaldo Pastor Oropeza
Dirigido a todos los estudiantes de el curso de Matematica DIscreta en la especialidad de Informatica
Oneymer Castañeda
C.I.: 20.044.920.
Circuito Secuencial
En la tematica anterior se analizaron los circuitos combinatorios en los que la salida depende sólo de la entrada. Estos circuitos carecen de memoria. En el presente capÃtulo se comenzará por estudiar los circuitos en los que la salida depende no sólo de la entrada, sino también del estado del sistema en el momento en que se introduce la entrada. El estado del sistema está determinado por el proceso anterior. En este sentido, estos circuitos tienen memoria; se conocen como circuitos secuenciales y su importancia es evidente en el diseño de computadoras
Circuitos secuenciales
Las operaciones dentro de una computadora digital se llevan a cabo en intervalos discretos. La salida depende del estado del sistema al igual que de la entrada. Se supondrá que el estado del sistema cambia sólo en el tiempo t=0, 1, . . . . Una manera sencilla de introducir la secuenciación en los circuitos es introducir un retraso unitario de tiempo.
Un retraso unitario de tiempo acepta como entrada un bit xt en el tiempo t y produce xt−1, el bit recibido como entrada en el tiempo t – 1. El retraso unitario de tiempo se dibuja como se muestra en la figura 12.1.1.
Circuitos secuenciales y maquina de estado finito
Un sumador en serie acepta como entrada dos números binarios
x =0xNxN−1···x0 y =0yN yN−1···y0
y produce la suma zN+1zN · · · z0 de x y y. Los números x y y se introducen de manera secuencial por pares, x0, y0; . . . ; xN, yN; 0, 0. Se produce la suma z0, z1, . . . , zN+1.
Circuito sumador en serie
En la figura 12.1.1 se ilustra un circuito que usa un retraso unitario de tiempo para implementar un sumador en serie. Se mostrará la manera en que el sumador en serie calcula la suma de x=010 y y=011. Primero se establece x0 =0 y y0 =1. (Se supone que en este instante i=0. Esto se puede preparar haciendo x=y=0). El estado del sistema se observa en la figura 12.1.3a). Después, se hace x1=y1=1. El retraso unitario de tiempo envÃa i=0 como el tercer bit al sumador completo. El estado del sistema se ve en la figura 12.1.3b). Por último, se hace x2 = y2=0. Esta vez el retraso unitario de tiempo envÃa i=1 como el tercer bit al sumador completo. El estado del sistema se observa en la figura 12.1.3c). Se obtiene la suma z=101.
Maquina de estado finito
Una máquina de estado finito es un modelo abstracto de una máquina con una memoria interna primitiva.
Una máquina de estado finito M consiste en
a) Un conjunto finito Ide sÃmbolos de entrada.
b) Un conjunto finito Ode sÃmbolos de salida.
c) Un conjunto finito Sde estados.
d) Una función f del siguiente estado de S×Ien S. e) Una función g de salida de S×I en S. f) Un estado inicial σ ∈S. Se escribe M=(I, O, S, f, g, σ).
Sean y . Defina un par de funciones y por las reglas dadas en la tabla 12.1.1.S ×I →O f:S×I →SS ={
Maquina de estado finito sumador en serie
Máquina de estado finito sumador en serie Diseñe una máquina de estado finito que realice la suma en serie. Se representará la máquina de estado finito por su diagrama de transición. Como el sumador en serie acepta pares de bits, el conjunto de entrada será {00, 01, 10, 11}. El conjunto de salida es {0, 1}. Dada una entrada xy, se toma una de dos acciones: se suman x y y, o se suman x, y y 1, dependiendo de si el bit de acarreo es 0 o 1. Entonces existen dos estados que se llamarán C (acarreo) y NC (ningún acarreo). El estado inicial es NC. En este punto se pueden dibujar los vértices y designar el estado inicial en el diagrama de transición (vea la figura 12.1.5). Después se consideran las entradas posibles en cada vértice. Por ejemplo, si 00 es entrada a NC, debe producirse 0 y seguir en el estado NC. Entonces NC tiene un ciclo con etiqueta 00/0. Como otro ejemplo, si entra 11 a C, se calcula 1 +1 +1 =11. En este caso, la salida es 1 y se continúa en el estado C. AsÃ, C tiene un ciclo con etiqueta 11/1. Como un último ejemplo, si estamos en el estado NC y la entrada es 11, debe producirse 0 y nos movemos al estado C. Al considerar todas las posibilidades, se llega al diagrama de transición de la figura 12.1.6.
