Funciones booleanas

Descripción en VHDL de arquitecturas para implementar el algoritmo CORDIC

Anexo B

Funciones booleanas
El álgebra de Boole provee las operaciones y las reglas para trabajar con el conjunto {0, 1}. Los dispositivos electrónicos pueden estudiarse utilizando este conjunto y las reglas asociadas al álgebra de Boole. Las tres operaciones utilizadas mas comúnmente son complemento, suma booleana(OR) y producto (AND).

B.1 Funciones y expresiones booleanas
Sea B = {0, 1}. La variable x se denomina Variable booleana si asume únicamente valores del conjunto B. Una función de Bn, el conjunto {(x1, x2, ... , xn) | xi ∈ B, 1 ≤ i ≤ n} en B se denomina función booleana de grado n. Las funciones booleanas pueden representarse usando expresiones construidas a partir de variables y operacionesbooleanas. Las expresiones booleanas en las variables x1, x2, ... , xn se definen en forma recursiva como sigue 0, 1, x1, x2, ... , xn son expresiones booleanas. Si E1 y E2 son expresiones booleanas, entonces E1, (E1 . E2) y (E1 + E2) son expresiones booleanas. Cada expresión booleana representa una función. Los valores de esta función se obtienen sustituyendo 0 y 1 en las variables presentes en laexpresión. Las funciones booleanas F y G de n variables se dicen equivalentes si y solo si F(b1, b2, ... , bn) = G(b1, b2, ... , bn), cuando b1, b2, ... , bn ∈ B. Una función booleana de grado 2 es una función de un conjunto con cuatro elementos, pares de elementos del conjunto {0, 1} en B, un conjunto con dos elementos. De manera tal que existen 16 funciones booleanas diferentes de grado 2.123

Descripción en VHDL de arquitecturas para implementar el algoritmo CORDIC

B.2 Identidades del álgebra booleana
Las identidades del álgebra booleana son particularmente útiles para simplificar el diseño de circuitos. Son proposiciones equivalentes y se pueden demostrar utilizando tablas de verdad. Las identidades se muestran en la tabla B.1 Identidad Nombre Doble complemento IdempotenciaIdentidad Dominancia Conmutatividad Asociatividad Distributividad DeMorgan Tabla B.1

x=x
x+x=x x.x=x x+0=x x.1=x x+1=1 x.0=0 x+y=y+x x.y=y.x x + (y + z) = (x + y) + z x . (y . z) = (x . y) . z x + y . z = (x + y) . (x + z) x . (y + z) = x . y + x . z ( x. y ) = x + y ( x + y ) = x. y

B.3 Representación de funciones booleanas
Expansiones de suma-producto
Un minitérmino de las variablesbooleanas x1, x2, ... , xn es un producto booleano y1 . y2 ... yn en donde y i = xi o bien y i = xi . Un literal es una variable booleana o su complemento. Por lo tanto un minitérmino es un producto de n literales con un literal para cada variable. Un minitérmino tiene un valor de 1 si y solo si cada variable y i tiene un valor de 1. Tomando sumas booleanas de distintos minitérminos se puedeconstruir una expresión booleana con un conjunto específico de valores. En particular una suma booleana de minitérminos tiene un valor de 1 cuando exactamente uno de los minitérminos en la suma tiene valor 1 y adquiere el valor 0 para cualquier otra combinación de valores de las variables. Una expansión de suma-producto es una suma de minitérminos. Los minitérminos en la suma booleana corresponden aaquellas combinaciones de valores en los cuales la función adquiere el valor 1. A modo de ejemplo se puede encontrar la función booleana correspondiente a la tabla B.2

124

Descripción en VHDL de arquitecturas para implementar el algoritmo CORDIC

x y z F(x,y,z) 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1

Tabla B.2 Para representar F, se necesita una expresión que valga 1en caso de que x = 0 e y = z = 1 o bien x = y = z = 1. Dicha expresión se puede construir por medio de una suma booleana de dos productos diferentes. Por lo tanto la función F quedaría F ( x, y, z ) = x. y.z + x. y.z

B.4 Completitud funcional
Toda función booleana puede representarse por una suma de minitérminos. Cada minitérmino es el producto booleano de variables booleanas o sus...