Dada una función booleana específica, ¿hay alguna restricción en el mínimo? de multiplexores necesarios para implementar esa función? ¿Hay alguna teoría sobre eso?
Dada una función booleana específica, ¿hay alguna restricción en el mínimo? de multiplexores necesarios para implementar esa función? ¿Hay alguna teoría sobre eso?
Primero, tienes que definir "multiplexor". En general, asumamos un multiplexor básico de 2 vías que tiene 2 entradas de datos, una entrada de selección y una salida de datos. Pero cuando trabaje con SSI / MSI TTL o CMOS, puede obtener cualquier cosa hasta un multiplexor 16: 1 como bloque de construcción.
Definitivamente hay un número máximo de muxes requeridos para cualquier función de entrada N: simplemente construyes un mux de 2 vías N que tiene N entradas seleccionadas, y empatas cada una de las entradas de datos 2 N alta o baja según sea necesario. Esto requiere 2 N-1 + 2 N-2 + ... + 2 0 = 2 N ? ? 1 muxes.
\ begin {array} {cc} N & muxes 1 & 1 \\ 2 & 3 \\ 3 & 7 \\ 4 & 15 \\ ... & ... \\ N & 2 ^ N - 1 \ end {array}
Sin embargo, el número mínimo de muxes para cualquier función arbitraria de N variables depende mucho de la función. Hay algunas funciones que se implementan de manera sorprendentemente eficiente con muxes de 2 entradas, especialmente si permite que un mux alimente la entrada seleccionada de otra. Todas las primeras familias de Actel (ahora Microsemi) FPGA utilizaron los muxes como su elemento lógico básico, en lugar del LUT (tabla de consulta) ahora omnipresente.Por ejemplo, un AND de 2 entradas o un OR de 2 entradas solo requiere un mux, por lo que un OR de N o AND de N se puede construir a partir de solo N? 1 muxes. Un XOR o XNOR de 2 entradas requiere solo dos muxes, por lo que un árbol XOR N-way (generador de paridad) requiere solo 2 (N ?? 1) muxes.
El método teórico para implementar físicamente una función booleana es mediante un mapa de Karnaugh . Básicamente, es un método gráfico / matemático para obtener la expresión canónica de Una función booleana de su tabla de verdad.
La expresión canónica es la fórmula que implementa la función booleana; El uso del mapa de Karnaugh no garantiza que la expresión obtenida tenga el número mínimo de términos, pero es el mejor método (hasta cuatro / cinco variables, para seis o más variables hay otro método, más complicado). La experiencia del diseñador ayuda a encontrar la expresión con un número mínimo de términos.
¿Por qué buscar el número mínimo de términos ? La razón es que hasta cuatro variables, cada término de la expresión se implementa con una puerta simple. Además, cada término de la expresión obtenida se puede transformar por leyes de Morgan , que tiende a Para reducir la variedad de puertas requeridas. Prácticamente, puede implementar cualquier función lógica utilizando solo compuertas NAND o NOR.
Muchas veces, este método de diseño ofrece ventajas sobre la implementación de la función booleana mediante multiplexores.
Comercialmente, es fácil encontrar multiplexores de dos y tres variables (cuatro u ocho canales), por lo que implementar funciones booleanas de hasta tres variables es muy simple usando multiplexores (y además, se recomienda). A partir de cuatro variables, se debe evaluar la implementación de la función booleana por compuertas, puede ser más sencillo y económico utilizar multiplexores .
Por ejemplo, suponga que desea implementar una función booleana de cuatro variables. El uso de la tecnología CMOS (familia 4000) requiere, como mínimo, dos multiplexores (por ejemplo, dos 4051). También se necesitan puertas para vincular la salida de los dos multiplexores y obtener la función deseada. Este último paso puede no ser directo.
En resumen, para implementar una función lógica de \ $ n \ $ variables, se necesita un multiplexor de \ $ 2 ^ n \ $ canales. Esto es fácil de encontrar en el mercado hasta 8 canales (\ $ 2 ^ 3 \ $).
Lea otras preguntas en las etiquetas digital-logic