Tengo una pregunta de examen que no he logrado resolver:
Necesito construir un circuito lógico digital que está recibiendo 4 número de bits y regresar true si el número es 0, 7 o 14.
Solo tengo una XOR puerta (2 entradas), uno NOR(3 entradas), uno NAND(2 entradas) y uno de 3 a 8 decodificador.
Creo que esa pregunta es irresoluble, yo no encuentro ninguna combinación que puede hacer eso. Alguna idea de cómo solucionarlo?
Escribí un algoritmo en C# que intenta todas las combinaciones posibles de esos Nor 3->1 Xor 2->1 Nand 2->1 y Decoder 3->8.
Después de correr por 7 millones de años de 2 horas, volvió 42 Falso. Creo que este prooves que la pregunta no tiene respuesta ya que este algoritmo de verificación de cada una de las combinaciones posibles. :)
Me pidieron describir, por lo que la siguiente parte es una explicación de las partes del código, parte por parte. TL;DR - sólo puede saltarse el código de abajo en el final :)
Vamos a hablar de las líneas de entrada, tienen 0 o 1 de los estados y cada una de las posibles entradas (de 0 a 15) que tienen valores diferentes:
para la primera línea que se ve como que: 0 1 0 1 0 1 ... El segundo es: 0 0 1 1 0 0 1 1... la tercera: 0 0 0 0 1 1 1 1 .... como la cuenta binaria... tienes la idea :P
Así que he creado un objeto que representa cada línea, en cada uno de sus miembros:
class BitLine{
bool[] IsActiveWhenInputIs = new bool[16];
}
Como dice bitLine.IsActiveWhenInputIs[5] devolver si la línea se activa cuando la entrada fue de 5.
Este es un código que crea las líneas de entrada por completo:
var bitLineList = new BitLine[6]; // initialize new array of bitLines
for (int i = 0; i < 6; i++) bitLineList [i] = new BitLine(); // initialize each bitLine
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 4; j++)
{
int checker = 1 << j; // check whether the j-th bit is activated in the binary representation of the number.
bitLineList[j].IsActiveWhenInputIs[i] = ((checker & i) != 0); // if it's active, the AND result will be none zero, and so the return value will be true - which is what we need :D
}
}
Vamos a crear un "cierto siempre" y "siempre falso" líneas de bits, así como para proporcionar un constante "0" de entrada o de "1" a la entrada.
for (int i = 0; i < 16; i++){
bitLineList[4].IsActiveWhenInputIs[i] = false;
bitLineList[5].IsActiveWhenInputIs[i] = true;
}
Ahora si te das cuenta, lo que estamos buscando es realmente una específica bitLine, una que es cierto cuando la entrada es 0, 7, 14. Vamos a representar en nuestra clase:
var neededBitLine = new BitLine();
for (int i = 0; i < 16; i++){
neededBitLine.IsActiveWhenInputIs[i] = ((i % 7) == 0); // be true for any number that is devideble by 7 (0,7,14)
}
Esto hizo que las cosas realmente simple: lo que realmente estamos buscando es una manera de "forjar" este neededBitLine de los bits de la entrada de línea (esto es cómo me representan a mi programa lo que yo quiero que mi salida).
Ahora, esto es cómo vamos: cada vez que usamos la lógica elemento en nuestro bitLines como Xor,Nor,Nand o incluso el Decoder, en realidad estamos creando un nuevo bitLine\s. Sabemos el valor de cada una de las líneas en cada posible entrada de 0 a 15, por lo que podemos calcular la nueva bitLine\s valor en cada posible entrada así!
Nand Nor y Xor son todos muy sencilla:
void Xor(BitLine b1, BitLine b2, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = b1.IsActiveWhenInputIs[i] != b2.IsActiveWhenInputIs[i];
}
}
void Nand(BitLine b1, BitLine b2, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] && b2.IsActiveWhenInputIs[i]);
}
}
void Nor(BitLine b1, BitLine b2, BitLine b3, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] || b2.IsActiveWhenInputIs[i] || b3.IsActiveWhenInputIs[i]);
}
}
Para cada posible entrada, representa el modo en que el nuevo BitLine de actuar.
El manejo de la decodificador es un poco complicado, pero la idea es que "si los bits en la entrada representan el número x en binario, el x-ésimo bit de salida de línea será verdadera, mientras que todos los demás serán falsos. A diferencia de la otra función, esto se obtiene una matriz de bitline, y añade 8 nuevos bitlines a la matriz.
void Decoder(BitLine b1, BitLine b2, BitLine b3, List<BitLine> lines, int listOriginalLength)
{
for (int optionNumber = 0; optionNumber < 8; optionNumber++)
{
for (var i = 0; i < 16; i++)
{
int sum = 0;
if (b1.IsActiveWhenInputIs[i]) sum += 4;
if (b2.IsActiveWhenInputIs[i]) sum += 2;
if (b3.IsActiveWhenInputIs[i]) sum += 1;
lines[listOriginalLength+optionNumber].IsActiveWhenInputIs[i] = (sum == optionNumber);
}
}
}
Ahora tenemos todos nuestros elementos básicos, así que vamos a hablar sobre el algoritmo:
Vamos a hacer un algoritmo recursivo, en cada profundidad se va a tratar de utilizar otro de los elementos (ni\nand\xor\decodificador) disponibles actualmente bitlines, y, a continuación, establezca el elemento inservible para la siguiente profundidad de recursión. Cuando llegamos a la parte inferior y no tenemos más elementos a usar, vamos a comprobar si tenemos una bitline que es lo que estábamos buscando.
Este código de verificación en cualquier momento dado de si el actual grupo de líneas que contiene la línea que estamos buscando:
bool CheckIfSolutionExist(List<BitLine> lines, int linesLength BitLine neededLine)
{
for(int i = 0; i<linesLength; i++){
if (lines[i].CheckEquals(neededLine))
{
return true;
}
}
return false;
}
Esta es la función que se utiliza para comprobar si dos líneas son iguales:
bool CheckEquals(BitLine other)
{
for (var i = 0; i < 16; i++)
{
if (this.IsActiveWhenInputIs[i] != other.IsActiveWhenInputIs[i])
{
return false;
}
}
return true;
}
Ok, así que ahora para la parte principal, este es el principal algoritmo:
bool Solve(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if ((!nand) && (!nor) && (!xor) && (!decoder))
{
return CheckIfSolutionExist(lines, listLength, neededLine);
}
else
{
if (HandleNand(lines, nand, nor, xor, decoder, neededLine,listLength))
{
return true;
}
if (HandleNor(lines, nand, nor, xor, decoder, neededLine,listLength))
{
return true;
}
if (HandleXor(lines, nand, nor, xor, decoder, neededLine,listLength))
{
return true;
}
if (HandleDecoder(lines, nand, nor, xor, decoder, neededLine,listLength))
{
return true;
}
return false;
}
}
Esta función recibe una lista de los disponibles bitLines, la lista de longitud, un valor booleano que representa si cada elemento está disponible actualmente (xor/nor/nand/decodificador), y un bitLine que representa el bitLine que estamos buscando.
En cada etapa, se verifica si tenemos más elementos a utilizar, si no se comprueba si nos archivar nuestras necesario bitline.
Si todavía tenemos más elementos, por cada elemento que se llama a una función que se supone que debe manejar la creación de nuevas bitLines utilizando los elementos y de llamar a la siguiente recuresive profundidad posteriormente.
El siguiente controlador de funciones son todos bastante sencillo, que se puede traducir a "elegir 2\3 de la disposición bitlines, y combinarlos con el elemento relevante. A continuación, llame a la siguiente profundidad de la recursión, sólo que esta vez no contienen este elemento!".
esas son las funciones de:
bool HandleNand(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (nand)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
BitLine.Nand(lines[i], lines[j],lines[listLength]);
if (Solve(lines,listLength+1, false, nor, xor, decoder, neededLine))
{
return true;
}
}
}
}
return false;
}
bool HandleXor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (xor)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
BitLine.Xor(lines[i], lines[j],lines[listLength]);
if (Solve(lines,listLength+1, nand, nor, false, decoder, neededLine))
{
return true;
}
}
}
}
return false;
}
bool HandleNor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (nor)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
for (int k = j; k < listLength; k++)
{
BitLine.Nor(lines[i], lines[j], lines[k],lines[listLength]);
if (Solve(lines,listLength+1, nand, false, xor, decoder, neededLine))
{
return true;
}
}
}
}
}
return false;
}
bool HandleDecoder(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (decoder)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
for (int k = j; k < listLength; k++)
{
BitLine.Decoder(lines[i], lines[j], lines[k],lines,listLength);
if (Solve(lines,listLength+8, nand, nor, xor, false, neededLine))
{
return true;
}
}
}
}
}
return false;
}
Y esto es todo, nos acaba de llamar a esta función con la necesaria línea que estamos buscando, y se comprueba cada combinación posible de las partes eléctricas para comprobar si es posible combinarlos de tal manera que en el final de una sola línea que se obtienen con los valores necesarios.
*aviso que voy a usar la misma lista todo el tiempo, así que no necesitamos crear una nueva bitlines casos todo el tiempo. Le doy un buffer de 200 por esa razón.
Este es el programa completo:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApp2
{
public class BitLine
{
public bool[] IsActiveWhenInputIs = new bool[16];
public static void Xor(BitLine b1, BitLine b2, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = b1.IsActiveWhenInputIs[i] != b2.IsActiveWhenInputIs[i];
}
}
public static void Nand(BitLine b1, BitLine b2, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] && b2.IsActiveWhenInputIs[i]);
}
}
public static void Nor(BitLine b1, BitLine b2, BitLine b3, BitLine outputBitLine)
{
for (var i = 0; i < 16; i++)
{
outputBitLine.IsActiveWhenInputIs[i] = !(b1.IsActiveWhenInputIs[i] || b2.IsActiveWhenInputIs[i] || b3.IsActiveWhenInputIs[i]);
}
}
public static void Decoder(BitLine b1, BitLine b2, BitLine b3, List<BitLine> lines, int listOriginalLength)
{
for (int optionNumber = 0; optionNumber < 8; optionNumber++)
{
for (var i = 0; i < 16; i++)
{
int sum = 0;
if (b1.IsActiveWhenInputIs[i]) sum += 4;
if (b2.IsActiveWhenInputIs[i]) sum += 2;
if (b3.IsActiveWhenInputIs[i]) sum += 1;
lines[listOriginalLength + optionNumber].IsActiveWhenInputIs[i] = (sum == optionNumber);
}
}
}
public bool CheckEquals(BitLine other)
{
for (var i = 0; i < 16; i++)
{
if (this.IsActiveWhenInputIs[i] != other.IsActiveWhenInputIs[i])
{
return false;
}
}
return true;
}
}
public class Solver
{
bool CheckIfSolutionExist(List<BitLine> lines, int linesLength, BitLine neededLine)
{
for (int i = 0; i < linesLength; i++)
{
if (lines[i].CheckEquals(neededLine))
{
return true;
}
}
return false;
}
bool HandleNand(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (nand)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
BitLine.Nand(lines[i], lines[j], lines[listLength]);
if (Solve(lines, listLength + 1, false, nor, xor, decoder, neededLine))
{
return true;
}
}
}
}
return false;
}
bool HandleXor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (xor)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
BitLine.Xor(lines[i], lines[j], lines[listLength]);
if (Solve(lines, listLength + 1, nand, nor, false, decoder, neededLine))
{
return true;
}
}
}
}
return false;
}
bool HandleNor(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (nor)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
for (int k = j; k < listLength; k++)
{
BitLine.Nor(lines[i], lines[j], lines[k], lines[listLength]);
if (Solve(lines, listLength + 1, nand, false, xor, decoder, neededLine))
{
return true;
}
}
}
}
}
return false;
}
bool HandleDecoder(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if (decoder)
{
for (int i = 0; i < listLength; i++)
{
for (int j = i; j < listLength; j++)
{
for (int k = j; k < listLength; k++)
{
BitLine.Decoder(lines[i], lines[j], lines[k], lines, listLength);
if (Solve(lines, listLength + 8, nand, nor, xor, false, neededLine))
{
return true;
}
}
}
}
}
return false;
}
public bool Solve(List<BitLine> lines, int listLength, bool nand, bool nor, bool xor, bool decoder, BitLine neededLine)
{
if ((!nand) && (!nor) && (!xor) && (!decoder))
{
return CheckIfSolutionExist(lines, listLength, neededLine);
}
else
{
if (HandleNand(lines, listLength, nand, nor, xor, decoder, neededLine))
{
return true;
}
if (HandleNor(lines, listLength, nand, nor, xor, decoder, neededLine))
{
return true;
}
if (HandleXor(lines, listLength, nand, nor, xor, decoder, neededLine))
{
return true;
}
if (HandleDecoder(lines, listLength, nand, nor, xor, decoder, neededLine))
{
return true;
}
return false;
}
}
}
class Program
{
public static void Main(string[] args)
{
List<BitLine> list = new List<BitLine>();
var bitLineList = new BitLine[200];
for (int i = 0; i < 200; i++) bitLineList[i] = new BitLine();
// set input bit:
for (int i = 0; i < 16; i++)
{
for (int j = 0; j < 4; j++)
{
int checker = 1 << j;
bitLineList[j].IsActiveWhenInputIs[i] = ((checker & i) != 0);
}
}
// set zero and one constant bits:
for (int i = 0; i < 16; i++)
{
bitLineList[4].IsActiveWhenInputIs[i] = false;
bitLineList[5].IsActiveWhenInputIs[i] = true;
}
list.AddRange(bitLineList);
var neededBitLine = new BitLine();
for (int i = 0; i < 16; i++)
{
neededBitLine.IsActiveWhenInputIs[i] = (i%7==0); // be true for any number that is devideble by 7 (0,7,14)
}
var solver = new Solver();
Console.WriteLine(solver.Solve(list, 6, true, true, true, true, neededBitLine));
Console.ReadKey();
}
}
}
Espero que esta vez es una explicación válida :P
Esta es una no-respuesta, para descartar la solución más obvia.
Voy a número de bits por su peso: \$ b_1 \$, \$ b_2 \$, \$ b_4 \$ y \$ b_8 \$.
Como bits \ $ b_2 \$ \ $ b_4 \$ son iguales en todos los números válidos, podríamos cosa acerca de implementar la lógica de la expresión:
$$ ( \text{nor} ~ \{ x=0, x=3, x=6 \} ) ~ \text{nand} ~ ( b_2 ~ \text{xor} ~ b_4 ) $$
donde x es { \$ b_1 \$, \$ b_4 \$, \$ b_8 \$ }, implementado con el decodificador de 3 a 8.
Sin embargo, la simplificación de la expresión anterior es:
$$ ( x=0 ~ \text{or} ~ x=3 ~ \text{or} ~ x=6 ) ~ \text{or} ~ ( b_2 = b_4 ) $$
que no es el esperado:
$$ ( x=0 ~ \text{or} ~ x=3 ~ \text{or} ~ x=6 ) ~ \text{and} ~ ( b_2 = b_4 ) $$
Por esta razón, creo que probable un error en la pregunta, "nand" puerta de un "ni".
Es factible. Como una sugerencia que el mediados dos bits son iguales para todos estos patrones de bits para que xoring les producirá 0 que puede entonces ser una entrada al decodificador con los otros dos bits. Las puertas restantes se aplican a las tres salidas de decodificador para proporcionar la salida bit solo correcto.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
