De manera que, suponed que las variables de entrada
valen todas 0, aquí tendríamos 0s, quiere decir que tendríamos
establecido este camino, y por lo tanto y1
tomaría el valor 0, que es este 0 de aquí.
En el segundo árbol ocurriría lo mismo, tendríamos definido este
camino y el y0 sería igual a 0, este 0 es exactamente este de aquí.
Veamos otro ejemplo.
Cuando las x valen 1 0 1, aquí tendría un 1 0 1, 1 0 1,
y esto me definirá el camino pues, 1 0 1.
Este 1 de aquí es exactamente este 1 de la
tabla de verdad.
Cuando x0, x1, x2 valen 1 0 1, este árbol de multiplexores me saca
un 0 por y1, exactamente lo mismo que me está diciendo la tabla de verdad.
En el segundo árbol de multiplexores, pues lo mismo, ¿no?
Si aquí tenemos un 1, hemos definido éste
camino de datos, éste 0 de aquí, se corresponde,
exactamente, con este 0 de la tabla de verdad.
La implementación de funciones booleanas con multiplexores se basa en
la aplicación interactiva de una regla de descomposición conocida con
el nombre de "Ley de Shannon", que dice que cualquier
función booleana se puede expresar como la suma de dos productos:
El primer producto, formado por cualquier variable,
aquí hemos escogido x0
pero podríamos haber puesto cualquier variable.
x0, la variable negada, multiplicada por el valor de la función, donde
la variable x0, la hemos substituido por un 0, y el
segundo producto, formado por ésta misma variable, ésta
vez sin negar, por el valor que toma la función, cuando en la variable x0
hemos colocado un 1.
Bién, ésta regla de descomposición puede implementarse directamente
con un multiplexor, utilizando la variable como señal de control.
Cuando x0 es 0, establecemos esta conección, y la f me queda
conectada a f(0,x1,...) y el resto de las variables,
lo mismo que me está diciendo la regla de descomposición,
que cuando la x0 es 0 éste término desaparece,
éste término es 1, y por lo tanto la función, coincide con f(1, x1,...)
y el resto de variables. Esta misma regla de
descomposición podríamos ir aplicándola iterativamente.
Por ejemplo, podríamos aplicarla a la función f(0, x1, x2,...)
y decir que es igual a x1-barra, por f(0, 0, x2,...)
más x1 por f(0, 1, x2, ...).
más x1 por f(0, 1, x2, ...).
Y a su vez, esto lo podríamos implementar,
por un multiplexor, controlado por x1 uno,
donde aquí tendríamos, f(0, 0, x2, ...), y aquí
donde aquí tendríamos, f(0, 0, x2, ...), y aquí
tendríamos f(0, 1, x2, ...), etc. Y esto podríamos
tendríamos f(0, 1, x2, ...), etc. Y esto podríamos
hacerlo, tantas veces como quisiéramos. Fijaros que en cada paso, al pasar
de aquí a aquí hemos, digamos, extraído una variable.
Ésto es una función de n variables, éstas
son funciones de n-1 variables, éstas
son funciones de n-2 variables porque
el resto de variables originales son valores fijos.
De manera que, repitiendo esta iteración n veces,
acabaríamos llegando a unos multiplexores,
donde las entradas, siempre serían de la forma f(0, 0, 1 ,1, ...),
es decir, no tendrían ya ninguna variable.
Y ésto es precisamente el valor de la
función cuando las entradas son 0 0 1 1 ... cero, uno, uno.
Es decir, ésto es una entrada en la tabla de verdad,
de la función f.
Vamos a ver ahora, una nueva técnica de
diseño que combina multiplexores con bloques de memoria ROM.
Ésta es una técnica que se utiliza en las
FPGAs y otros dispositivos programables que veremos más adelante.
De hecho, lo veremos en las últimas semanas del curso,
pero que os voy a dar un pequeño adelanto.
Las FPGAs son dispositivos que, cuando se explican a un nivel muy general,
se dice que contienen millares de puertas lógicas más un interconeccionado que
el usuario puede configurar a voluntad para construir los circuitos que desea.
Pero en realidad, no son puertas lógicas, lo
que contiene, o al menos, no solo puertas lógicas,
sino un conjunto de bloques, cada uno de los
cuales puede implementar un cierto número de funciones booleanas.
Pues bién, estos bloques se componen de pequeñas memorias ROM y de multiplexores
A estas pequeñas memorias ROM se les llama "Look Up Tables", o LUTs en general
A estas pequeñas memorias ROM se les llama "Look Up Tables", o LUTs en general
y son memorias, en general, de 2 elevado a n palabras, de 1 bit.
Donde n, además, es un número relativamente pequeño.
Veamos un ejemplo de cómo se
pueden combinar éstas LUTs con los multiplexores:
Supongamos que tenemos unas memorias ROM,unas LUTs, de 2 elevado a 6
palabras, palabras de un bit, que por lo tanto
tiene 6 bits de dirección, y que por lo tanto, sabemos, que son capaces
de implementar cualquier función booleana de seis variables.
Supongamos que ahora lo que queremos es
implementar una función de 8 variables, ¿cómo podemos hacerlo?.
Pués, lo que
podemos es aplicar el Teorema de Shannon dos veces, en dos iteraciones.
de manera que, aplicándolo la primera vez
habríamos pasado de una función de 8 variables, que es
la que queremos construir, a dos funciones de 7 variables, y ahora
podríamos volverlo a aplicar aquí, y obtener 4 funciones
que ahora dependerán de 6 variables. Aquí tenemos la función de 8 variables.
Estas funciones, (5) y (6), son funciones de 7 variables,
como véis aquí. Aplicando por segunda vez el Teorema de
Shannon, llegamos a éstas 4 funciones, (1), (2), (3), (4)
que dependen solo de 6 variables, y que por lo
tanto ya pueden implementarse directamente con éstas
pequeñas memorias ROM, con éstas LUTs. Éste
circuito, como véis, combinando LUTs
de 6 variables, más multiplexores, permite
construir, una función de 8 variables. Evidentemente,
ésto se puede extender a cualquier número de variables.
De hecho, este circuito admite otra implementación ...
fijémonos que esta parte, formada por los multiplexores,
es un bloque al cual entran 1, 2, 3, 4 tres,
entradas, que son las salidas de las LUTs, más x1 y x0.
Es decir, en el fondo este conjunto de trés multiplexores
implementa una función de 6 variables, y por lo tanto, este
bloque puede a su vez ser sustituido por una LUT.
Ésto lo vemos,
en el dibujo siguiente. ¿Véis?
Hemos sustituido los multiplexores por una LUT.
Bien,
pués así es como se trabaja con memorias ROM más multiplexores.
Os dejo un quiz, para ver si habéis comprendido, todos estos conceptos.
