Para poder entender todo el desarrollo tecnológico que nos ha llevado al nivel que tenemos en estos días debemos de empezara a estudiar sistemas numéricos, desde el usual sistema decimal, pasar por el sistema octal, hexadecimal y el binario, todos estos anteriormente mencionados son de gran utilidad en el funcionamiento interno de una computadora, siendo las direcciones de memoria representadas en sistema hexadecimal, las operaciones de suma, resta, multiplicación, división etc se realizan en sistema binario, ya que resulta mucho mas fácil para una computadora realizar operaciones a ese nivel, al ser solo un sistema bi estable se reducen las condiciones que deben de ser previstas para su buen funcionamiento, así pues para optimizar su desempeño se logro crear componentes que de igual manera reaccionan solo a dos estados, 0 1, y con ello se logra simplificar el estudio, modelado, construcción y operación de la computadoras actuales, la mayor parte del desarrollo tecnológico esta basado en el mismo concepto, palabras de longitud n, donde n representa el numero de bits de cada palabra siendo los primeros procesadores de longitud de palabra de 8 bits lo cual representa un byte, así pues se podían procesar palabras o instrucciones de 1 byte = 8 bits, actualmente los procesadores pueden ejecutar palabras hasta de 64 bits lo cual representa un gran avance en cuanto ala longitud de la instrucciones mas complejas y el numero de instrucciones por ciclo de reloj, aun asi los procesadores gráficos siguen siendo los mas complejos y los que longitud de palabra mas extensa tiene siendo los de ultima generación capaces de procesar palabras hasta de 512 bits, ya que la cantidad de datos he instrucciones necesarias para mostrar un solo circulo es infinitamente mas demandante que solo calcular posiciones del puntero dentro de la pantalla, así mismo el ancho del bus de las memorias actuales dependiendo de la aplicación pueden llegara a ser busses de 256 bits para poder abastecer la cantidad de datos necesarios para poder solucionar las instrucciones y requerimientos del usuario, el mayor salto tecnológico se dio poder hacer mas pequeños los circuitos integrados y memorias y demás componentes de una computadora, al irlos haciendo mas pequeños se pudieron ir apilando mas y mas circuitos y por ende se pudo llegar a un nivel de complejidad mayor, lo que desemboco en un mejor diseño y mas complejo de los futuros procesadores, y memorias.
En general en este curso de arquitectura de computadoras obtuvimos los conocimientos mínimos necesarios para entender el funcionamiento interno de una computadora, y como poder sacarle mayor provecho a la lógica de programación, al poder abstraer de una manera mas eficiente el modelado que requerimos para representar la posible solución aun problema de la vida diaria.
lunes, 8 de diciembre de 2008
domingo, 7 de diciembre de 2008
Decodificadores
Un decodificador es un circuito combinacional que convierte información binaria de bits (entradas) en un m´aximo de 2n salidas únicas. Si la información codificada de n bits tiene combinaciones no utilizadas, por ejemplo en un decodificador BCD, entonces el decodificador puede tener menos de 2n salidas.
La figura 1 muestra el circuito esquemático básico de un decodificador de 2 entradas y cuatro salidas.
Adicionalmente, la figura 1 muestra en forma de un diagrama de tiempos o cronograma las salidas
D0 D1 D2 D3 , en función de las entradas S1 y S0 .
Diagrama esquemático y cronograma correspondiente a un decodificador básico de dos a cuatro líneas.
Flip-Flop
Flip-Flops
Un circuito flip-flop puede mantener un estado binario indefinidamente (Siempre y cuando se le este suministrando potencia al circuito) hasta que se cambie por una señal de entrada para cambiar estados. La principal diferencia entre varios tipos de flip-flops es el numero de entradas que poseen y la manera en la cual las entradas afecten el estado binario.
Circuito básico de un flip-flop
Se menciono que un circuito flip-flop puede estar formado por dos compuertas NAND o dos compuertas NOR. Estas construcciones se muestran en los diagramas lógicos de las figuras. Cada circuito forma un flip-flop básico del cual se pueden construir uno mas complicado. La conexión de acoplamiento intercruzado de la salida de una compuerta a la entrada de la otra constituye un camino de retroalimentación. Por esta razón, los circuitos se clasifican como circuitos secuenciales asincrónicos. Cada flip-flop tiene dos salidas, Q y Q´ y dos entradas S (set) y R (reset). Este tipo de flip-flop se llama Flip-Flop RS acoplado directamente o bloqueador SR (SR latch). Las letras R y S son las iniciales de los nombres en inglés de las entradas (reset, set).
Circuito flip-flop básico con compuertas NOR
Para analizar la operación del circuito de la figura anterior se debe recordar que la salida de una compuerta NOR es 0 si cualquier entrada es 1 y que la salida es 1 solamente cuando todas las entradas sean 0. Como punto de partida asúmase que la entrada de puesta a uno (set) es 1 y que la entrada de puesta a 0 (reset) sea 0. Como la compuerta 2 tiene una entrada de 1, su salida Q´ debe ser 0, lo cual coloca ambas entradas de la compuerta 1 a 0 para tener la salida Q como 1. Cuando la entrada de puesta a uno (set) vuelva a 0, las salidas permanecerán iguales ya que la salida Q permanece como 1, dejando una entrada de la compuerta 2 en 1. Esto causa que la salida Q´ permanezca en 0 lo cual coloca ambas entradas de la compuerta número 1 en 0 y así la salida Q es 1. De la misma manera es posible demostrar que un 1 en la entrada de puesta a cero (reset) cambia la salida Q a 0 y Q´ a 1. Cuando la entrada de puesta a cero cambia a 0, las salidas no cambian.
Cuando se aplica un 1 a ambas entradas de puesta a uno y puesta a cero ambas salidas Q y Q´ van a 0. Esta condición viola el hecho de que las salidas Q y Q´ son complementos entre si. En operación normal esta condición debe evitarse asegurándose que no se aplica un 1 a ambas entradas simultáneamente.
Un flip-flop tiene dos entradas útiles. Cuando Q=1 y Q´=0 estará en el estado de puesta a uno (o estado 1). Cuando Q=0 y Q´=1 estará en el estado de puesta a cero (o estado 0). Las salidas Q y Q´ son complementos entre si y se les trata como salidas normales y de complemento respectivamente. El estado binario de un flip-flop se toma como el valor de su salida normal.
Bajo operación normal, ambas entradas permanecen en 0 a no ser que el estado del flip-flop haya cambiado. La aplicación de un 1 momentáneo a la entrada de puesta a uno causará que el flip-flop vaya a ese estado. La entrada de puesta en uno debe volver a cero antes que se aplique un uno a la entrada de puesta a cero. Un 1 momentáneo aplicado a la entrada de puesta a cero causará que el flip-flop vaya al estado de borrado (o puesta a cero). Cuando ambas entradas son inicialmente cero y se aplica un 1 a la entrada de puesta a uno o se aplica un 1 a la entrada de puesta a cero mientras que el flip-flop este borrado, quedaran las salidas sin cambio. Cuando se aplica un 1 a ambas entradas de puesta a uno y puesta a cero, ambas salidas irán a cero. Este estado es indefinido y se evita normalmente. Si ambas salidas van a 0, el estado del flip-flop es indeterminado y depende de aquella entrada que permanezca por mayor tiempo en 1 antes de hacer la transición a cero.
Circuito flip-flop básico con compuertas NAND
El circuito básico NAND de la figura anterior opera con ambas entradas normalmente en 1 a no ser que el estado del flip-flop tenga que cambiarse. La aplicación de un 0 momentáneo a la entrada de puesta a uno, causará que Q vaya a 1 y Q´ vaya a 0, llevando el flip-flop al estado de puesta a uno. Después que la entrada de puesta a uno vuelva a 1, un 0 momentáneo en la entrada de puesta a cero causará la transición al estado de borrado (clear). Cuando ambas entradas vayan a 0, ambas salidas irán a 1; esta condición se evita en la operación normal de un flip-flop.
Flip-flop RS temporizado
El flip-flop básico por si solo es un circuito secuencial asincrónico. Agregando compuertas a las entradas de circuito básico, puede hacerse que el flip-flop responda a los niveles de entrada durante la ocurrencia del reloj. El flip-flop RS temporizado mostrado en la siguiente figura consiste en un flip-flop básico NOR y dos compuertas NAND. Las salidas de las dos compuertas AND permanecen en cero mientras el pulso del reloj (abreviado en inglés CP) sea 0, independientemente de los valores de entrada S y R se permite llegar al flip-flop básico. El estado de puesta a uno se logra con S=1, R=0 y CP=1. Para cambiar el estado de puesta a cero (o borrado) las entradas deben ser S=0, R=1 y CP=1. Con S=1 y R=1, la ocurrencia de los pulsos de reloj causará que ambas salidas vayan momentáneamente a 0. Cuando quite el pulso, el estado del flip-flop será indeterminado, es decir, podría resultar cualquier estado, dependiendo de si la entrada de puesta a uno o la de puesta a cero del flip-flop básico, permanezca el mayor tiempo, antes de la transición a 0 al final del pulso.
Flip-flop RS temporizado
El símbolo gráfico del flip-flop RS sincronizado se muestra en la figura anterior. Tiene tres entradas: S, R y CP. La entrada CP no se describe dentro del recuadro debido a que se reconoce fácilmente por un pequeño triángulo. El triángulo es un símbolo para el indicador dinámico y denota el hecho que el flip-flop responde a una transición del reloj de entrada o flanco de subida de una señal de un nivel bajo (o binario) a un nivel alto (1 binario). Las salidas del flip-flop se marcan con Q y Q´ dentro del recuadro. Se le puede designar al flip-flop un nombre de variable diferente aunque se escriba una Q dentro del recuadro. En este caso la letra escogida para la variable del flip-flop se marca por fuera del recuadro y a lo largo de la línea de salida. El estado del flip-flop se determina del valor de su salida normal Q. Si se desea obtener el complemento de salida normal, no es necesario usar un inversor ya que el valor complementado se obtiene directamente de la salida Q´.
La tabla característica del flip-flop se muestra en la figura antes presentada. Esta tabla resume la operación del flip-flop en forma de tabulado. Q es el estado binario del flip-flop en un tiempo dado (refiriéndose al estado presente), las columnas S y R dan los valores posibles de las entradas y Q(t + 1) es el estado del flip-flop después de la ocurrencia de un pulso de reloj (refiriéndose al siguiente estado).
La ecuación característica de un flip-flop se deduce del mapa de la figura antes mencionada. Esta ecuación especifica el valor del siguiente estado como una función del presente estado y de las entradas. La ecuación característica de una expresión algebraica para la información binaria de la tabla característica. Los dos estados indeterminados se marcan con una X en el mapa, ya que pueden resultar como 1 o como 0. Sin embargo la relación SR=0 debe incluirse como parte de la ecuación característica para especificar que S y R no pueden ser iguales a 1 simultáneamente.
Flip-flop D
El flip-flop D mostrado en la figura anterior es una modificación del flip-flop RS sincronizado. Las compuertas NAND 1 y 2 forman el flip-flop básico y las compuertas 3 y 4 las modifican para conformar el flip-flop RS sincronizado. La entrada D va directamente a la entrada S y su complemento se aplica a la entrada R a través de la compuerta 5. Mientras que el pulso de reloj de entrada sea un 0, las compuertas 3 y 4 tienen un 1 en sus salidas, independientemente del valor de las otras entradas. Esto esta de acuerdo a los requisitos de que las dos entradas del flip-flop básico NAND permanezcan inicialmente en el nivel de 1. La entrada D se comprueba durante la ocurrencia del pulso de reloj. Si es 1, la salida de la compuerta 3 va a 0, cambiando el flip-flop al estado de puesta a uno (a no ser que ya este en ese estado). Si en 0, la salida de la compuerta 4 va a 0, cambiando el flip-flop al estado de borrado.
Flip-flop D temporizado El flip-flop tipo D recibe su nombre por la habilidad de transmitir “datos” a un flip-flop. Es básicamente un flip-flop RS con un inversor en la entrada R. el inversor agregado reduce el numero de entradas de dos a uno. Este tipo de flip-flop se llama algunas veces bloqueador D con compuertas o flip-flop de bloqueo. La entrada CP se le da a menudo la designación variable G (de gate) para indicar que esta entrada esta habilita el flip-flop de bloqueo para hacer posible que los datos entren al mismo.
El símbolo para el flip-flop D sincronizado se muestra en la figura. La tabla característica se lista en la parte © y la ecuación característica se lista en la parte (d). la ecuación característica muestra que el siguiente estado del flip-flop es igual a la entrada D y es independiente del valor del presente estado.
Flip-flop JK
Un flip-flop JK es un refinamiento del flip-flop RS ya que el estado independiente del termino RS se define en el tipo JK. Las entradas J y K se comportan como las entradas R y S para poner a uno o cero (set o reset) al flip-flop (nótese que en el flip-flop JK la entrada J se usa para la entrada de puesta a uno y la letra K para la entrada de puesta a cero). Cuando ambas entradas se aplican a J y K simultáneamente, el flip-flop cambia a su estado de complemento, esto es, si Q=1 cambia a Q=0 y viceversa.
Un flip-flop sincronizado se muestra en la figura anterior. La salida Q se aplica con K y CP a una compuerta AND de tal manera que el flip-flop se ponga a cero (clear) durante un pulso de reloj solamente si Q fue 1 previamente. De manera similar la salida Q´ se aplica a J y CP a una compuerta AND de tal manera que el flip-flop se ponga a uno con un pulso de reloj, solamente si Q´ fue 1 previamente.
Flip-flop JK temporizado
Como se muestra en la tabla característica de la figura, el flip-flop JK se comporta como un flip-flop RS excepto cuando J y K sean ambos 1. Cuando J y K sean 1, el pulso de reloj se transmite a través de una compuerta AND solamente; aquella cuya entrada se conecta a la salida del flip-flop la cual es al presente igual a 1. Así, si Q=1, la salida de la compuerta AND superior se convertirá en 1 una vez que se aplique un pulso de reloj y el flip-flop se ponga a cero. Si Q´=1 la salida de la compuerta AND se convierte en 1 y el flip-flop se pone a uno. En cualquier caso, el estado de salida del flip-flop se complementa.
Las entradas en el símbolo gráfico para el flip-flop JK deben marcarse con una J (debajo de Q) y K (debajo de Q´). La ecuación característica se da en la figura y se deduce del mapa de la tabla característica.
Nótese que debido a la conexión de retroalimentación del flip-flop JK, la señal CP que permanece en 1 (mientras que J=K=1) causará transiciones repetidas y continuas de las salidas después que las salidas hayan sido completadas. Para evitar esta operación indeseable, los pulsos de reloj deben de tener un tiempo de duración que es menor que la demora de propagación a través del flip-flop. Esta es una restricción, ya que la operación del circuito depende del ancho de los pulsos. Por esta razón los flip-flops JK nunca se construyen como se muestra en la figura. La restricción del ancho del pulso puede ser eliminada con un maestro esclavo o una construcción activada por flanco de la manera discutida en la siguiente sección. El mismo razonamiento se aplica al flip-flop T presentado a continuación.
Flip-Flop T temporizado
El flip-flop T es la versión de una entrada, del flip-flop JK. Como se muestra en la figura anterior, el flip-flop J se obtiene de un tipo JK a la cual se le unen las dos entradas. El nombre T se deriva de la habilidad del flip-flop de variar (“toggle”) o cambiar estado. Independientemente del presente estado del flip-flop, este asume el estado de complemento cuando ocurre el pulso de reloj mientras que la entrada T esté en lógica 1. El símbolo, la tabla característica y la ecuación característica del flip-flop se muestran en la figura anterior.
Mapas de Karnaugh
MÉTODO DE REDUCCIÓN DE MAPAS DE KARNAUGH.
En el capítulo anterior se resolvieron problemas que dependiendo del número de términos que tenía la función canónica, el número de compuertas lógicas utilizadas es igual al número de términos obtenidos MAS UNO, por lo tanto, los circuitos obtenidos son de dos niveles con un tiempo mínimo de retardo, pero que de ninguna manera es el más sencillo ni el más económico.
El objetivo de este capítulo es dar a conocer la mayoría de los métodos utilizados para minimizar funciones canónicas y así poder construir un circuito con menor número de compuertas.
Los métodos utilizados para la minimización de funciones Booleanas son: El algebraico, para lo cual se utilizan los postulados y teoremas del álgebra de Boole y el método gráfico de Karnaugh.
2.1 Minimización por mapas de Karnaugh.
Los mapas de Karnaugh es uno de los métodos más prácticos. Se puede decir que es el más poderoso, cuando el número de variables de entrada es menor o igual a seis; más allá, ya no es tan práctico. En general, el mapa de Karnaugh se considera como la forma gráfica de una tabla de verdad, o como una extensión del diagrama de Venn.
Antes de explicar como se utiliza el mapa de Karnaugh en la minimización de funciones, veremos como se obtiene el mapa. Esto nace de la representación geométrica de los números binarios. Un número binario de n bits, puede representarse por lo que se denomina un punto en un espacio N. Para entender lo que se quiere decir con esto, considérese el conjunto de los números binarios de un bit, es decir, 0 y 1. Este conjunto puede representarse por dos puntos en un espacio 1; esto es, por dos puntos unidos por una línea. Tal representación se denomina un cubo 1.
De la Figura 2.1 se observa que el cubo 1 se obtuvo proyectando al cubo 0 y que el cubo 2 se obtendrá proyectando al cubo 1.
De la Figura 2.2.(a), se observa que al reflejarse el cubo 1 se obtiene un cuadrilátero cuyos vérticesrepresentan un número binario. Estos números se obtienen al agregar un 0 a la izquierda de los vértices del cubo que se refleja y un 1 a la izquierda de los vértices del cubo reflejado. Del cubo 2 se observa que se obtienen cuatro vértices, los cuales corresponden a la combinación de dos variables (22=4), pero si se sigue la trayectoria indicada en la Figura 2.2.(b), se podrá observar que al pasar de un vértice al otro, existe un solo cambio, lo que da lugar a un código especial, debido a que no sigue la formación del código binario.
Más adelante le daremos un nombre a este código.
Ahora, si a cada vértice del cubo 2 se le asigna un casillero, se tendrá la siguiente Figura 2.3.
De la Figura 2.3.(b), si proyectamos el cubo 2, obtendremos el cubo 3, el cual se muestra en la Figura 2.4.
De la Figura 2.4.(4b), si seguimos la trayecto ria marcada por las flechas, obtendremos la tabla de la Figura 2.4.(c), en donde de un carácter a otro existe un solo cambio; otra característica de la tabla, es el reflejo que existe entre los caracteres 1-2 y 5-6 de la columna C y el reflejo entre los caracteres 2-3-4 -5 en la columna B. El reflejo que existe siempre es con respecto al eje central de simetría.
Ahora que tenemos el cubo 3, podemos obtener la representación en la forma de la Figura 2.3.(a), (b) y (c), lo cual se logra haciendo un corte al cubo 3, como se muestra en la Figura 2.5.
El levantamiento del cubo 3, a partir de la Figura 2.5, se muestra en la Figura 2.6.
Ahora, si asignamos una área a cada punto, como se muestra en la Figura 2.7, se obtendrá la representación que se denomina mapa del cubo N, que en este caso fue desarrollado para un cubo 3.
Como se tienen ocho casilleros, éstos corresponden a la combinación de tres variables, las cuales pueden ser A, B y C, siendo A la más significativa y C la menos significativa, por lo que la tabla funcional para la primera tabla corresponde al código binario y la otra corresponde al código especial, que en realidad de conoce como código de GRAY o código reflejado. Como veremos, ambos códigos están implícitos en el mapa de Karnaugh.
Si observamos el mapa de la Figura 2.8.(d), cada casillero tiene asignado un número, el cual corresponde a un número del código binario. De la misma figura pero del inciso (e), si seguimos la trayectoria marcada por las flechas, cada número representa a un carácter del código Gray. En la tabla anterior, se muestran las tablas de cada uno de los códigos mencionados.
Compuertas Lógicas
Compuerta AND
La compuerta AND o Y lógica es una de las compuertas más simples dentro de la Electrónica Digital.
Su representación es la que se muestra en las siguientes figuras.
La primera es la representación de una compuerta AND de 2 entradas y la segunda de una compuerta AND de 3 entradas.
La compuerta Y lógica más conocida tiene dos entradas A y B, aunque puede tener muchas más (A,B,C, etc.) y sólo tiene una salida X.
La compuerta AND de 2 entradas tiene la siguiente tabla de verdad.
Se puede ver claramente que la salida X solamente es "1" (1 lógico, nivel alto) cuando la entrada A como la entrada B están en "1". En otras palabras...
La salida X es igual a 1 cuando la entrada A y la entrada B son 1
Esta situación se representa en álgebra booleana como:X = A*B o X = AB.
Una compuerta AND de 3 entradas se puede implementar con interruptores, como se muestra en el siguiente diagrama.
La tabla de verdad se muestra al lado derecho donde: A = Abierto y C = Cerrado.
Una compuerta AND puede tener muchas entradas.
Una compuerta AND de múltiples entradas puede ser creada conectando compuertas simples en serie.
El problema de poner compuertas en cascada, es que el tiempo de propagación de la señal desde la entrada hasta la salida, aumenta.
Si se necesita una compuerta AND de 3 entradas y no una hay disponible, es fácil crearla con dos compuertas AND de 2 entradas en serie o cascada como se muestra en el siguiente diagrama.
Se observa que la tabla de verdad correspondiente es similar a la mostrada anteriormente, donde se ultilizan interruptores.
Se puede deducir que el tiempo de propagación de la señal de la entrada C es menor que los de las entradas A y B (Estas últimas deben propagarse por dos compuertas mientras que la entrada C se propaga sólo por una compuerta)
De igual manera, se puede implementar compuertas AND de 4 o más entradas
La compuerta O lógica o compuerta OR es una de las compuertas mas simples dentro de la Electrónica Digital.
La salida X de la compuerta OR será "1" cuando la entrada "A" o la entrada "B" estén en "1".
Expresándolo en otras palabras:
En una compuerta OR, la salida será "1", cuando en cualquiera de sus entradas haya un "1".
La compuerta OR se representa con la siguiente función booleana: X = A+B ó X = B+A
Compuerta OR de dos entradas.
La representación de la compuerta "OR" de 2 entradas y su tabla de verdad se muestran a continuación.
La compuerta OR también se puede implementar con interruptores como se muestra en la figura de arriba a la derecha, en donde se puede ver que: cerrando el interruptor A "O" el interruptor B se encenderá la luz
"1" = cerrado , "0" = abierto, "1" = luz encendida
Compuerta OR de tres entradas
En las siguientes figuras se muestran la representación de la compuerta "OR" de tres entradas con su tabla de verdad y la implementación con interruptores
La lámpara incandescente se iluminará cuando cualquiera de los interruptores (A o B o C) se cierre.
Se puede ver que cuando cualquiera de ellos esté cerrado la lampara estará alimentada y se encenderá. La función booleana es X = A + B + C
Compuerta NOT (No) o compuerta inversora
Dentro de la electrónica digital, no se podrían lograr muchas cosas si no existiera la compuerta NOT (compuerta NO), también llamada compuerta inversora.
Esta compuerta como la compuerta AND y la compuerta OR es muy importante. La compuerta NOT entrega en su salida el inverso (opuesto) de la entrada. El símbolo y la tabla de verdad son los siguientes:
AX
0 1
1 0
La salida de una compuerta NOT tiene el valor inverso al de su entrada. En el caso del gráfico anterior la salida X = A.
Esto significa que si a la entrada tenemos un "1" lógico, a la salida hará un "0" lógico y si a la entrada tenemos un "0" a la salida habrá un "1"
Nota: El apóstrofe en la siguiente expresión significa "negado": X = A’ y es igual a X = A
Las compuertas NOT se pueden conectar en cascada, logrando después de dos compuertas, la entrada original.
A X´ X´´
0 1 1
1 0 0
Un motivo para implementar un circuito que tenga en su salida, lo mismo que tiene en su entrada, es conseguir un retraso de la señal con un propósito especial.
Circuito NAND equivalente
El circuito NAND equivalente es una forma alternativa de lograr el mismo resultado de una compuerta NAND como la que ya se conoce.
Comparando las tablas de verdad que se presentan a continuación, se puede ver que el valor de la salidas (F) es igual.
La primera tabla es la tabla de verdad de un circuito NAND equivalente y la segunda es la tabla de verdad de la compuerta NAND
Se puede ver también que la fórmula booleana utilizada para el circuito equivalente da un resultado (F) igual al resultado de la fórmula booleana de la compuerta NAND (F).
Teorema deMorgan
Entonces (observando las 2 tablas anteriores): A . B = A + B
Esta última igualdad es llamada "El teorema deMorgan". Este teorema es muy útil para simplificar circuitos combinacionales booleanos.
Es especialmente útil cuando hay que simplificar expresiones booleanas grandes y complejas que están negadas (que tienen una línea horizontal en la parte superior) una o mas veces.
El circuito NAND equivalente se representa también comop se muestra en el gráfico siguiente:
Los pequeños círculos que están a la entrada de la compuerta OR reemplazan a las compuertas inversoras que se muestran en el primer gráfivo de este artículo. (el circulo pequeño es un inversor)
Circuito NOR equivalente
La compuerta NOR equivalente es una forma alternativa de lograr el mismo resultado de una compuerta NOR (No "O") como la que ya se conoce.
Comparando las tablas de verdad que se presentan a continuación, se puede ver que el valor de la salidas (F) es igual.
Se puede ver también que la fórmula booleana utilizada para el circuito equivalente da un resultado (F) igual al resultado de la fórmula booleana de la compuerta NOR (F).
Teorema deMorgan
Comparando los diagramas superiores (la compuerta NOR y su circuito equivalente) se obtiene la siguiente igualdad:
Esta última igualdad es llamada "El teorema deMorgan".
Este teorema es muy útil para simplificar circuitos combinacionales booleanos, especialmente cuando existen expresiones grandes y complejas que están negadas (que tienen una línea horizontal en la parte superior) una o más veces.
El circuito NOR equivalente se representa también de la siguiente manera:
Los pequeños círculos que están a la entrada de la compuerta NAND reemplazan a las compuertas NOT o compuertas inversoras (el circulo pequeño es un inversor)
Álgebra Booleana
Para cualquier sistema algebraico existen una serie de postulados iniciales, de aquí se pueden deducir reglas adicionales, teoremas y otras propiedades del sistema, el álgebra booleana a menudo emplea los siguientes postulados:
Cerrado. El sistema booleano se considera cerrado con respecto a un operador binario si para cada par de valores booleanos se produce un solo resultado booleano.
Conmutativo. Se dice que un operador binario " º " es conmutativo si A º B = B º A para todos los posibles valores de A y B.
Asociativo. Se dice que un operador binario " º " es asociativo si (A º B) º C = A º (B º C) para todos los valores booleanos A, B, y C.
Distributivo. Dos operadores binarios " º " y " % " son distributivos si A º (B % C) = (A º B) % (A º C) para todos los valores booleanos A, B, y C.
Identidad. Un valor booleano I se dice que es un elemento de identidad con respecto a un operador binario " º " si A º I = A.
Inverso. Un valor booleano I es un elemento inverso con respecto a un operador booleano " º " si A º I = B, y B es diferente de A, es decir, B es el valor opuesto de A.
Para nuestros propósitos basaremos el álgebra booleana en el siguiente juego de operadores y valores:
- Los dos posibles valores en el sistema booleano son cero y uno, a menudo llamaremos a éstos valores respectivamente como falso y verdadero.
- El símbolo · representa la operación lógica AND. Cuando se utilicen nombres de variables de una sola letra se eliminará el símbolo ·, por lo tanto AB representa la operación lógica AND entre las variables A y B, a esto también le llamamos el producto entre A y B.
- El símbolo "+" representa la operación lógica OR, decimos que A+B es la operación lógica OR entre A y B, también llamada la suma de A y B.
- El complemento lógico, negación ó NOT es un operador unitario, en éste texto utilizaremos el símbolo " ' " para denotar la negación lógica, por ejemplo, A' denota la operación lógica NOT de A.
- Si varios operadores diferentes aparecen en una sola expresión booleana, el resultado de la expresión depende de la procedencia de los operadores, la cual es de mayor a menor, paréntesis, operador lógico NOT, operador lógico AND y operador lógico OR. Tanto el operador lógico AND como el OR son asociativos por la izquierda. Si dos operadores con la misma procedencia están adyacentes, entonces se evalúan de izquierda a derecha. El operador lógico NOT es asociativo por la derecha.
Utilizaremos además los siguientes postulados:
P1 El álgebra booleana es cerrada bajo las operaciones AND, OR y NOT
P2 El elemento de identidad con respecto a · es uno y con respecto a + es cero. No existe elemento de identidad para el operador NOT
P3 Los operadores · y + son conmutativos.
P4 · y + son distributivos uno con respecto al otro, esto es, A· (B+C) = (A·B)+(A·C) y A+ (B·C) = (A+B) ·(A+C).
P5 Para cada valor A existe un valor A' tal que A·A' = 0 y A+A' = 1. Éste valor es el complemento lógico de A.
P6 · y + son ambos asociativos, ésto es, (AB) C = A (BC) y (A+B)+C = A+ (B+C).
Es posible probar todos los teoremas del álgebra booleana utilizando éstos postulados, además es buena idea familiarizarse con algunos de los teoremas más importantes de los cuales podemos mencionar los siguientes:
Teorema 1: A + A = A
Teorema 2: A · A = A
Teorema 3: A + 0 = A
Teorema 4: A · 1 = A
Teorema 5: A · 0 = 0
Teorema 6: A + 1 = 1
Teorema 7: (A + B)' = A' · B'
Teorema 8: (A · B)' = A' + B'
Teorema 9: A + A · B = A
Teorema 10: A · (A + B) = A
Teorema 11: A + A'B = A + B
Teorema 12: A' · (A + B') = A'B'
Teorema 13: AB + AB' = A
Teorema 14: (A' + B') · (A' + B) = A'
Teorema 15: A + A' = 1
Teorema 16: A · A' = 0
Los teoremas siete y ocho son conocidos como Teoremas de DeMorgan en honor al matemático que los descubrió.
Características:
Un álgebra de Boole es un conjunto en el que destacan las siguientes características:
1- Se han definido dos funciones binarias (que necesitan dos parámetros) que llamaremos aditiva (que representaremos por x
+ y) y multiplicativa (que representaremos por xy) y una función monaria (de un solo parámetro) que representaremos por x'.
2- Se han definido dos elementos (que designaremos por 0 y 1)
Y 3- Tiene las siguientes propiedades:
Conmutativa respecto a la primera función: x + y = y + x
Conmutativa respecto a la segunda función: xy = yx
Asociativa respecto a la primera función: (x + y) + z = x + (y +z)
Asociativa respecto a la segunda función: (xy)z = x(yz)
Distributiva respecto a la primera función: (x +y)z = xz + yz
Distributiva respecto a la segunda función: (xy) + z = (x + z)( y + z)
Identidad respecto a la primera función: x + 0 = x
Identidad respecto a la segunda función: x1 = x
Complemento respecto a la primera función: x + x' = 1
Complemento respecto a la segunda función: xx' = 0
Propiedades Del Álgebra De Boole
Idempotente respecto a la primera función: x + x = x
Idempotente respecto a la segunda función: xx = x
Maximalidad del 1: x + 1 = 1
Minimalidad del 0: x0 = 0
Involución: x'' = x
Inmersión respecto a la primera función: x + (xy) = x
Inmersión respecto a la segunda función: x(x + y) = x
Ley de Morgan respecto a la primera función: (x + y)' = x'y'
Ley de Morgan respecto a la segunda función: (xy)' = x' + y'
Función Booleana
Una función booleana es una aplicación de A x A x A x....A en A, siendo A un conjunto cuyos elementos son 0 y 1 y tiene estructura de álgebra de Boole.
Supongamos que cuatro amigos deciden ir al cine si lo quiere la mayoría. Cada uno puede votar si o no. Representemos el voto de cada uno por xi. La función devolverá sí (1) cuando el numero de votos afirmativos sea 3 y en caso contrario devolverá 0.
Si x1 vota 1, x2 vota 0, x3 vota 0 y x4 vota 1 la función booleana devolverá 0.
Producto mínimo (es el número posible de casos) es un producto en el que aparecen todas las variables o sus negaciones.
El número posible de casos es 2n.
Siguiendo con el ejemplo anterior. Asignamos las letras A, B, C y D a los amigos. Los posibles casos son:
Votos Resultado
ABCD
1111 1
1110 1
1101 1
1100 0
1011 1
1010 0
1001 0
1000 0
0111 1
0110 0
0101 0
0100 0
0011 0
0010 0
0001 0
0000 0
Las funciones booleanas se pueden representar como la suma de productos mínimos (minterms) iguales a 1.
En nuestro ejemplo la función booleana será:
f(A,B,C,D) = ABCD + ABCD' + ABC'D + AB'CD + A'BCD
Diagramas De Karnaugh
Los diagramas de Karnaugh se utilizan para simplificar las funciones booleanas.
Se construye una tabla con las variables y sus valores posibles y se agrupan los 1 adyacentes, siempre que el número de 1 sea potencia de 2.
En esta página tienes un programa para minimización de funciones booleanas mediante mapas de Karnaugh
Álgebra Booleana y circuitos electrónicos
La relación que existe entre la lógica booleana y los sistemas de cómputo es fuerte, de hecho se da una relación uno a uno entre las funciones booleanas y los circuitos electrónicos de compuertas digitales. Para cada función booleana es posible diseñar un circuito electrónico y viceversa, como las funciones booleanas solo requieren de los operadores AND, OR y NOT podemos construir nuestros circuitos utilizando exclusivamente éstos operadores utilizando las compuertas lógicas homónimas
Un hecho interesante es que es posible implementar cualquier circuito electrónico utilizando una sola compuerta, ésta es la compuerta NAND
Para probar que podemos construir cualquier función booleana utilizando sólo compuertas NAND, necesitamos demostrar cómo construir un inversor (NOT), una compuerta AND y una compuerta OR a partir de una compuerta NAND, ya que como se dijo, es posible implementar cualquier función booleana utilizando sólo los operadores booleanos AND, OR y NOT. Para construir un inversor simplemente conectamos juntas las dos entradas de una compuerta NAND. Una vez que tenemos un inversor, construir una compuerta AND es fácil, sólo invertimos la salida de una compuerta NAND, después de todo, NOT ( NOT (A AND B)) es equivalente a A AND B. Por supuesto, se requieren dos compuertas NAND para construir una sola compuerta AND, nadie ha dicho que los circuitos implementados sólo utilizando compuertas NAND sean lo óptimo, solo se ha dicho que es posible hacerlo. La otra compuerta que necesitamos sintetizar es la compuerta lógica OR, ésto es sencillo si utilizamos los teoremas de DeMorgan, que en síntesis se logra en tres pasos, primero se reemplazan todos los "·" por "+" después se invierte cada literal y por último se niega la totalidad de la expresión:
A OR B
A AND B.......................Primer paso para aplicar el teorema de DeMorgan
A' AND B'.....................Segundo paso para aplicar el teorema de DeMorgan
(A' AND B')'..................Tercer paso para aplicar el teorema de DeMorgan
(A' AND B')' = A' NAND B'.....Definición de OR utilizando NAND
Si se tiene la necesidad de construir diferentes compuertas de la manera descrita, bien hay dos buenas razones, la primera es que las compuertas NAND son las más económicas y en segundo lugar es preferible construir circuitos complejos utilizando los mismos bloques básicos. Observe que es posible construir cualquier circuito lógico utilizando sólo compuertas de tipo NOR (NOR = NOT(A OR B)). La correspondencia entre la lógica NAND y la NOR es ortogonal entre la correspondencia de sus formas canónicas. Mientras que la lógica NOR es útil en muchos circuitos, la mayoría de los diseñadores utilizan lógica NAND.
. Circuitos Combinacionales
Un circuito combinacional es un sistema que contiene operaciones booleanas básicas (AND, OR, NOT), algunas entradas y un juego de salidas, como cada salida corresponde a una función lógica individual, un circuito combinacional a menudo implementa varias funciones booleanas diferentes, es muy importante recordar éste echo, cada salida representa una función booleana diferente.
Un ejemplo común de un circuito combinacional es el decodificador de siete segmentos, se trata de un circuito que acepta cuatro entradas y determina cuál de los siete segmentos se deben iluminar para representar la respectiva entrada, de acuerdo con lo dicho en el párrafo anterior, se deben implementar siete funciones de salida diferentes, una para cada segmento. Las cuatro entradas para cada una de éstas funciones booleanas son los cuatro bits de un número binario en el rango de 0 a 9. Sea D el bit de alto orden de éste número y A el bit de bajo orden, cada función lógica debe producir un uno (para el segmento encendido) para una entrada dada si tal segmento en particular debe ser iluminado, por ejemplo, el segmento e debe iluminarse para los valores 0000, 0010, 0110 y 1000
Los circuitos combinacionales son la base de muchos componentes en un sistema de cómputo básico, se puede construir circuitos para sumar, restar, comparar, multiplicar, dividir y muchas otras aplicaciones más.
Circuitos Secuenciales
Un problema con la lógica secuencial es su falta de "memoria". En teoría, todas las funciones de salida en un circuito combinacional dependen del estado actual de los valores de entrada, cualquier cambio en los valores de entrada se refleja (después de un intervalo de tiempo llamado retardo de propagación) en las salidas. Desafortunadamente las computadoras requieren de la habilidad para "recordar" el resultado de cálculos pasados. Éste es el dominio de la lógica secuencial. Una celda de memoria es un circuito electrónico que recuerda un valor de entrada después que dicho valor ha desaparecido. La unidad de memoria más básica es el flip-flop Set/Reset. Aunque recordar un bit sencillo es importante, la mayoría de los sistemas de cómputo requieren recordar un grupo de bits, ésto se logra combinando varios flip-flop en paralelo, una conexión de éste tipo recibe el nombre de registro. A partir de aquí es posible implementar diferentes circuitos como registros de corrimiento y contadores, éstos últimos también los conocemos como circuitos de reloj. Con los elementos mencionados es posible construir un microprocesador completo.
Relación entre la lógica combinacional y secuencial con la programación
En ésta lección hemos dado una repasada muy básica a los elementos que forman la base de los modernos sistemas de cómputo, en la sección dedicada al diseño electrónico estudiaremos a profundidad los conceptos aquí presentados, pero para aquellos que están más interesados en el aspecto programático podemos decir que con los elementos vistos en ésta lección es posible implementar máquinas de estado, sin embargo la moraleja de ésta lección es muy importante: cualquier algoritmo que podamos implementar en software, lo podemos a su vez implementar directamente en hardware. Ésto sugiere que la lógica booleana es la base computacional en los modernos sistemas de cómputo actuales. Cualquier programa que Usted escriba, independientemente del lenguaje que utilice, sea éste de alto ó bajo nivel, se puede especificar como una secuencia de ecuaciones booleanas.
Un hecho igualmente interesante es el punto de vista opuesto, es posible implementar cualquier función de hardware directamente en software, en la actualidad ésta es la función principal del lenguaje ensamblador y otros con capacidad de trabajar directamente en hardware, como el C y el C++. Las consecuencias de éste fenómeno apenas se están explotando, se infiere la existencia de un futuro muy prometedor para el profesional de la programación, especialmente aquellos dedicados a los sistemas incrustados (embedded systems), los microcontroladores y los profesionales dedicados a la Programación Orientada a Objetos. Para tener éxito en éstos campos de la investigación es fundamental comprender las funciones booleanas y la manera de implementarlas en software. Aún y cuando Usted no desee trabajar en hardware, es importante conocer las funciones booleanas ya que muchos lenguajes de alto nivel procesan expresiones booleanas, como es el caso de los enunciados if-then ó los bucles while.
Suscribirse a:
Entradas (Atom)