Tengo una pregunta del examen que no pude resolver:
Necesito construir un circuito lógico digital que reciba un número de 4 bits y devolver true
si el número es 0
, 7
o 14
. Solo tengo una XOR
puerta (2 entradas), una NOR
(3 entradas), una NAND
(2 entradas) y un decodificador de 3 a 8.
Creo que esa pregunta no tiene solución, no encontré ninguna combinación que pueda hacer eso. ¿Alguna idea de cómo solucionarlo?
Respuestas:
Escribí un algoritmo en C # que intenta todas las combinaciones posibles de esos
Nor 3->1
Xor 2->1
Nand 2->1
yDecoder 3->8
.Después de ejecutarlo durante
7½ millones de años2 horas, devolvió42Falso. Creo que esto prueba que la pregunta no tiene respuesta ya que este algoritmo verifica todas las combinaciones posibles. :)Me pidieron que lo describiera, así que la siguiente parte es una explicación de las partes del código, parte por parte. TL; DR : puede saltar al código hacia abajo al final :)
Hablemos de las líneas de entrada, tienen 0 o 1 estados y para cada una de las posibles entradas (0 a 15) tienen diferentes valores:
para la primera línea se ve así: 0 1 0 1 0 1 ... La segunda es: 0 0 1 1 0 0 1 1 ... la tercera: 0 0 0 0 1 1 1 1 .... como binaria contando ... tienes la idea: P
Entonces creé un objeto que representa cada línea en cada uno de sus estados:
Como dice bitLine.IsActiveWhenInputIs [5] devuelve si la línea estaba activa cuando la entrada era 5.
Este es un código que crea las líneas de entrada por completo:
También crearemos líneas de bits "siempre verdaderas" y "siempre falsas" para proporcionar una entrada constante "0" o una entrada "1".
Ahora, si se da cuenta, lo que estamos buscando es en realidad una línea de bits específica, una que sea verdadera cuando la entrada es 0, 7, 14. Represéntelo en nuestra clase:
Esto hizo las cosas realmente simples: lo que realmente estamos buscando es una forma de "falsificar" esta necesaria BitLine desde la línea de bits de entrada (así es como represento a mi programa lo que quiero que sea mi salida).
Ahora, así es como vamos en: cada vez que utilizamos algún elemento lógico en nuestras líneas de bits como
Xor
,Nor
,Nand
o incluso elDecoder
, en realidad estamos creando una nueva línea de bits \ T. ¡Conocemos el valor de cada una de las líneas en cada entrada posible de 0 a 15, por lo que también podemos calcular el nuevo valor de bitLine \ s en cada entrada posible!Nand Nor y Xor son sencillos:
Para cada entrada posible, representa cómo actuará la nueva BitLine.
Manejar el decodificador es un poco complicado, pero la idea es "si los bits en la entrada representan el número x en binario, entonces la línea de bits de salida x-ésima será verdadera, mientras que todas las demás serán falsas. A diferencia del otro función, esta obtiene una matriz de línea de bits y agrega 8 nuevas líneas de bits a la matriz.
Ahora tenemos todos nuestros elementos básicos, así que hablemos sobre el algoritmo:
Vamos a hacer un algoritmo recursivo, en cada profundidad intentará usar otros elementos (ni \ nand \ xor \ decoder) en las líneas de bits disponibles actualmente, y luego establecerá el elemento como inutilizable para la siguiente profundidad recursiva. Cada vez que lleguemos al fondo y no tengamos más elementos para usar, verificaremos si tenemos una línea de bits que es lo que estábamos buscando.
Este código verifica en cualquier momento si el grupo actual de líneas contiene la línea que estamos buscando:
Esta es la función que utiliza para verificar si dos líneas son iguales:
Ok, ahora para la parte principal, este es el algoritmo principal:
Esta función recibe una lista de las líneas de bits disponibles, la longitud de la lista, un valor booleano que representa si cada elemento está disponible actualmente (xor / nor / nand / decoder) y una línea de bits que representa la línea de bits que estamos buscando.
En cada etapa, verifica si tenemos más elementos para usar, si no, verifica si archivamos nuestra línea de bits necesaria.
Si todavía tenemos más elementos, entonces para cada elemento llama a una función que se supone que maneja la creación de nuevas BitLines usando esos elementos y luego llama a la siguiente profundidad recursiva.
Las siguientes funciones del controlador son bastante sencillas, se pueden traducir a "elegir 2 \ 3 de las líneas de bits disponibles y combinarlas con el elemento relevante. Luego llame a la siguiente profundidad de la recursión, solo que esta vez no contendrá este elemento ".
esas son las funciones:
Y esto es todo, solo llamamos a esta función con la línea necesaria que estamos buscando, y verifica todas las combinaciones posibles de las partes eléctricas para verificar si es posible combinarlas de tal manera que al final una sola línea sea salida con los valores necesarios.
* observe que uso la misma lista todo el tiempo, por lo que no necesitaré crear nuevas instancias de bitlines todo el tiempo. Le doy un búfer de 200 por ese motivo.
Este es el programa completo:
Espero que esta vez sea una explicación válida: P
fuente
Esto no responde, para descartar la solución más obvia.
Sin embargo, la simplificación de la expresión anterior es:
eso no es lo esperado:
Por esta razón, creo que es probable un error en la pregunta, siendo "nand" gate "ni"
fuente
Una respuesta válida a su pregunta sería cualquier circuito que devuelva siempre verdadero. Porque devolverá verdadero también si los números de entrada son 0,7 o 14.
Creo que la pregunta debería pedir explícitamente un circuito que resulte verdadero si los números de entrada son 0,7, o 14. Y de lo contrario, las salidas son falsas.
fuente
Es factible. Como sugerencia, los dos bits intermedios son iguales para todos estos patrones de bits, por lo que su fijación producirá 0 que luego puede ser una entrada al decodificador con los otros dos bits. Las puertas restantes se aplican a las tres salidas del decodificador para proporcionar la salida correcta de un solo bit.
fuente