miércoles, 20 de octubre de 2010

Algebra de Boole

ALGEBRA DE BOOLE

A mediados del siglo XIX, George Boole (1815-1864), en sus libros: "The Mathematical Analysis of Logic" (1847) y "An Investigation of te Laws of Thought" (1854), desarrolló la idea de que las proposiciones lógicas podían ser tratadas mediante herramientas matemáticas. Las proposiciones lógicas (asertos, frases o predicados de la lógica clásica) son aquellas que únicamente pueden tomar valores Verdadero/Falso, o preguntas cuyas únicas respuestas posibles sean Sí/No. Según Boole, estas proposiciones pueden ser representadas mediante símbolos y la teoría que permite trabajar con estos símbolos, sus entradas (variables) y sus salidas (respuestas) es la Lógica Simbólica desarrollada por él. Dicha lógica simbólica cuenta con operaciones lógicas que siguen el comportamiento de reglas algebraicas. Por ello, al conjunto de reglas de la Lógica Simbólica se le denomina ÁLGEBRA DE BOOLE.

A mediados del siglo XX el álgebra Booleana resultó de una gran importancia práctica, importancia que se ha ido incrementando hasta nuestros días, en el manejo de información digital (por eso hablamos de Lógica Digital). Gracias a ella, Shannon (1930) pudo formular su teoría de la codificación y John Von Neumann pudo enunciar el modelo de arquitectura que define la estructura interna de los ordenadores desde la primera generación.
Todas las variables y constantes del Álgebra booleana, admiten sólo uno de dos valores en sus entradas y salidas: Sí/No, 0/1 o Verdadero/Falso. Estos valores bivalentes y opuestos pueden ser representados por números binarios de un dígito (bits), por lo cual el Álgebra booleana se puede entender cómo el Álgebra del Sistema Binario. Al igual que en álgebra tradicional, también se trabaja con letras del alfabeto para denominar variables y formar ecuaciones para obtener el resultado de ciertas operaciones mediante una ecuación o expresión booleana. Evidentemente los resultados de las correspondientes operaciones también serán binarios.
Todas las operaciones (representadas por símbolos determinados) pueden ser materializadas mediante elementos físicos de diferentes tipos (mecánicos, eléctricos, neumáticos o electrónicos) que admiten entradas binarias o lógicas y que devuelven una respuesta (salida) también binaria o lógica. Ejemplos de dichos estados son: Abierto/Cerrado (interruptor), Encendida/Apagada (bombilla), Cargado/Descargado (condensador) , Nivel Lógico 0/Nivel lógico 1 (salida lógica de un circuito semiconductor), etcétera.
Los dispositivos con los cuales se implementan las funciones lógicas son llamados puertas (o compuertas) y, habitualmente, son dispositivos electrónicos basados en transistores. Estos dispositivos, y otros que veremos a lo largo de esta unidad, son los que permiten el diseño, y la ulterior implementación, de los circuitos de cualquier ordenador moderno, así como de muchos de los elementos físicos que permiten la existencia de las telecomunicaciones modernas, el control de máquinas, etcétera. De hecho, pensando en los ordenadores como una jerarquía de niveles, la base o nivel inferior sería ocupada por la lógica digital (en el nivel más alto del ordenador encontraríamos los actuales lenguajes de programación de alto nivel).
En esta unidad se representan las puertas lógicas elementales, algunas puertas complejas y algunos ejemplos de circuitos digitales simples, así como algunas cuestiones de notación. Por otra parte se plantean actividades de trabajo, muchas de las cuales implican una respuesta escrita en vuestro cuaderno de trabajo. El deseo del autor es que os resulte sencillo y ameno adentraros en el mundo de la lógica digital y despertaros la curiosidad, tanto por ella, como por la matemática que subyace en ella.

Memorias logicas.."

Desarrollo de Problemas

Diseñe a nivel de Circuitos Lógicos una memoria de 2 X 2. Considere pastillas de memoria de 2 X 2 para elaborar una memoria de 16 X 8. Ejemplifique su utilización para la escritura del valor 4AC5 en la posición (125)8 y una lectura de la posición (100)8 considerando que contiene el valor (111020)3.
Procedimiento:
Para poder ejemplificar el uso de la memoria, primero debemos transformar los números que usaremos a la base binaria, la cual es la que se usa a nivel de circuitos lógicos:
(4AC5)h = (0100101011000101)2
(125)8 = (001010101)2
(100)8 = (001000000)2

(111020)3 = (101100101)2 Figura 1.

Para la elaboración de nuestra memoria lógica de 16 X 8 utilizamos 32 unidades de memoria 2 X 2, tal como se muestra en la figura 1. Esta memoria tiene cuatro entradas diferentes, las cuales son la del bus de datos (2 bits), el bus de dirección (1 bit), el bus de control (1 bit) y el chip select (1 bit), que se utiliza para desconectar los flip-flop de memoria que no se utilizan en una operación.

Para poder almacenar datos en esta memoria como si fuera en realidad una sola memoria de 16 X 8 es necesario partir los 8 bits de entrada en 4 entradas de dos bits c/u, ya que las pastillas de memoria física sólo admiten dos bits. Así, los dos bits menos significativos pasan a la primera columna de pastillas físicas, los dos bits siguientes pasan a la segunda columna, los siguientes dos pasan a la tercera columna y los dos bits más significativos pasan a la cuarta columna de pastillas físicas.
Asimismo, el bus de dirección es de cuatro bits en la memoria lógica 16 X 8, mientras que las pastillas físicas 2 X 2 solo admiten 1 bit de dirección. Para solucionar este problema partimos los cuatro bits en dos bloques, uno de tres bits (los más significativos) y uno de un bit. El bloque de tres bits lleva un decodificador, el cual dependiendo de la salida que tenga prende el banco de memoria lógica que dice la entrada. (recordemos que los tres bits representan los ocho bancos de memoria física que hay). Esta salida se utilizará posteriormente por los bancos físicos de 2 X 2 como chip select. El bit restante es el que indica a los bancos físicos en cuál de las posiciones de memoria será almacenado el dato (si es en la posición 0 o 1 del banco).
Con el bit de control no hay problema; recordemos que éste sólo tiene que indicar si la operación es de lectura (0) o escritura (1).
Ahora explicaremos los ejemplos con más detalle:
Guardar el dato 0100101011000101 en la posición 001010101: como ésta es una memoria de 8 bits, el dato quedará recortado en 1100 0101; y como la misma es de 16 posiciones, la dirección quedará recortada en 0101:
Primero partimos el dato en cuatro bloques: 11 00 01 01;
La dirección, la partimos en dos bloques de esta manera: 010 y 1;
Al decodificar el 010 tenemos como respuesta que el dato va almacenado en la CK 2 de la memoria lógica 16 X 8, y que a su vez va almacemada el los bits 1.0 y 1.1 de éstos cuatro bancos de memoria física 2 X 2.
El dato previamente partido en cuatro bloques va a entrar en su respectiva pastilla de memoria física 2 X 2.

Lectura de la posición 001000000, considerando que contiene el valor 101100101: al igual que el problema anterior, la dirección se recorta a 0000; el dato se recorta a 01100101:
Primero partimos la dirección en dos bloques: así tenemos que el banco de memoria a leer es el banco 0, y la posición física de memoria sera la posición 0;
Considerando que el dato almacenado es el 01 00 00 00, el chip select habilitará la compuerta de salida del flip-flop (junto con el resultado negado de las entradas de dirección y control) y deshabilitará la compuerta de entrada del mismo.
Así finalmente el dato podrá ser extraído mediante el bus de datos (el cual es bidireccional) y leído;


El diseño y confección de este display es muy fácil; como podemos ver en la gráfica detallada (figura 6), del teclado numérico se genera un impulso que el búfer de entrada reconoce como código ASCII; dado que en este código los dígitos del 0 al 9 están representados por los números del 48 al 57, o sea del 00110000 al 00111001, podemos descartar los cuatro bits más significativos, dejando como resultado los números en binario del 0 al 9 (0000 al 1001). Este número se pasa a una especie de decodificador que lo interpreta, y, conectándose las salidas con los respectivos segmentos del display (por medio de una compuerta OR), se obtiene como resultado la salida deseada.


Diseñe a nivel de circuitos lógicos un sumador completo de 3 bits.
Para este problema teníamos que tomar en cuenta las reglas para la suma binaria, las cuales son:
Suma Salida de Arrastre
Regla 1 0 + 0 = 0
Regla 2 0 + 1 = 1
Regla 3 1 + 0 = 1
Regla 4 1 + 1 = 0 y arrastre 1 = 10
En el circuito sumador que diseñamos tenemos tres entradas y dos salidas, las entradas corresponden a las dos variables que utilizamos y la entrada de arrastre (la llamamos carry in), y las salidas corresponden a la suma de columnas y la salida de arrastre (la cual denominamos carry out).
Para realizar la suma de las variables A y B utilizamos una función XOR (or exclusivo) la cual dará un resultado de 1 cuando las variables tengan distintos valores. Para la suma de arrastre consideramos una función AND.

Para comprobar si nuestro sumador funciona, sumaremos estas dos cantidades binarias (001)2 y (111)2 así:
1 1 1
( 0 0 1 )2 que equivale a ( 1 )10
( 1 1 1 )2 que equivale a ( 7 )10
1 0 0 0 que equivale a ( 8 )10 o sea el resultado de
sumar (1 )10 y ( 7 ) 10 que es lo mismo que
sumar ( 001 )2 y ( 111 )2.