Compuerta Logicas

Arturo Díaz Pérez

Análisis y Complejidad de Algoritmos

Modelos Computacionales
Arturo Díaz Pérez
¬
®
¯

El circuito lógico
La máquina de estados finitos
La máquina de acceso aleatorio
La máquina de Turing

Models

Análisis y Diseño de Algoritmos

Compuertas Lógicas
F Compuerta Lógica
ß Un dispositivo físico que realiza una función booleana
/f: N → { 0, 1 }
/Frecuentemente n se codifica como unanúmero en base 2
/n = xk-12k-1 + xk-22k-2 + ... + x121 + x020 +, xi= 0, 1
f

Las compuertas lógicas pueden ser construidas por tecnologías
diferentes
Se acostumbra utilizar un símbolo lógico para cada compuerta
Los símbolos se utilizan para dibujar circuitos lógicos

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Models

1

Arturo Díaz Pérez

Circuitos Lógicos
F CircuitoLógico
ß Una DAG en la cual todos sus vértices, excepto los vértices de
entrada y salida, están etiquetados con compuertas lógicas
ß Los circuitos lógicos ejecutan programas estrictamente
secuenciales, esto es, programas que consisten únicamente de
asignmientos
ß No contienen ciclos ni saltos
ß Los circuitos lógicos constituyen los bloques básicos para la
construcción de computadoras digitales.
ßCuando se combinan con celdas de memoria binarias, se
pueden construir máquinas con memoria (máquinas de estados
finitos)

Models

Análisis y Diseño de Algoritmos

Circuitos Lógicos
x1

a

sum

b
cin

x2
x3

cout
x4

x1 := a xor b
x2 := a nand cin
x3 := b nand cin
x4 := a nand b
sum := x1 xor cin
cout := (x2 nand x3) nand x4
Análisis y Diseño de Algoritmos

Análisis y Complejidad de AlgoritmosModels

2

Arturo Díaz Pérez

Máquinas de Estados Finitos
F Máquinas de estados finitos
ß Es una máquina con memoria
ß Ejecuta una serie de pasos en los cuales
/toma su estado actual de un conjunto de estados Q
/define su salida a partir de un conjunto de símbolos de
entrada Σ
ß FSM = < Σ, Ψ, Q, δ, λ>
/Σ, alfabeto de símbolos de entrada
/Ψ, alfabeto de símbolos de salida
/Q, conjunto finito deestados
/δ, función de transición
3 δ : Σ ×Q→ Q

/λ, función de transición
3 λ:Σ
Análisis y Diseño de Algoritmos

× Q→ Ψ

Models

Máquinas de Estados Finitos
Salida

Entrada

L

Memoria

Estado

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Models

3

Arturo Díaz Pérez

FSM: Ejemplo
0/0

1/0
0/0
1/0

a

b

1/0

c

0/(z_out := NOT y_in)

ESTADO
a
b
c
-

V0

V1

0
0
1
1

0
1
01

0

x_in

1
01,0
10,0
10, ¬yin
--,-

00,0
00,0
00,¬yin
--,-

Models

Análisis y Diseño de Algoritmos

FSM: Estructura General
x
d logic 0
D 0 Q
CLK

d logic 1

D 1 Q
CLK
memory
part

clk
z logic

z
logical part
Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Models

4

Arturo Díaz Pérez

Autómata Finito
F Autómata Finito
ß AF = < Σ, Q, δ, q0, F>
/Σ, alfabeto de símbolosde entrada
/Q, conjunto finito de estados
/δ, función de transición
3 δ : Σ ×Q→ Q

/q0, estado inicial
/F ⊂ Q, conjunto0 de estados finales
0
1

q0/0

q1/1
1

Models

Análisis y Diseño de Algoritmos

Autómata de Pila
F Autómata de Pila
ß Consiste de
/una cinta de entrada,
/un control finito y
/ una pila
Cinta de Entrada
ß AF = < Σ, Γ, Q, δ, q0, Z0, F>
/Σ, alfabeto de símbolos de entrada
/Γ,alfabeto de símbolos de la pila
/Q, conjunto finito de estados
/δ, función de transición

Mecanismo
de
Control
Pila

3 δ:Q×Σ×Γ→Q× Γ

/q0, estado inicial
/Z0, símbolo inicial de la pila
Análisis y Diseño
de Algoritmos
/F
⊂ Q, conjunto de estados finales

Análisis y Complejidad de Algoritmos

Models

5

Arturo Díaz Pérez

Autómata de Pila
F Autómata de Pila
ß Consiste de
/una cinta de entrada,
/un controlfinito y
/ una pila
Cinta de Entrada

Mecanismo
de
Control
Pila
Análisis y Diseño de Algoritmos

Models

La Máquina de Acceso Aleatorio: RAM
F RAM: Random Access Machine
ß Es modelada como dos máquinas de estados finitos:
/unidad central de procesamiento (CPU)
/memoria de acceso aleatorio
/cmd: READ, WRITE, NO-OP
/instrucciones:
3 LOAD, STORE, ADD, SUB, MULT, DIV,
3 READ, WRITE,
3 JUMP, JZ,...