Circuito lógico digital - pregunta de examen

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 regrese truesi el número es 0, 7o 14. Solo tengo una XORpuerta (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?

Como pista: dados 4 bits y un decodificador 3-8, debe tratar uno de los bits de manera diferente.
@BrianDrummond Lo probé con cada 3 bits. Sé que las 3 respuestas posibles son 0000, 0111, 1110. Los 2 bits en el centro son iguales: si son ceros, los otros dos deberían ser cero, y si son unos, los otros dos deberían ser 0 y 1. .
Bueno. Esa descripción y la lista de partes te dicen cómo hacerlo.
@BrianDrummond pero ya lo sé, y todavía no logré resolverlo. Cada solución que probé siente que le falta una puerta OR. No puedo encontrar tal combinación con las puertas dadas que pueda resolver el problema... Tenga en cuenta que solo tengo UNA puerta por tipo...
@BrianDrummond Mi idea era conectar los bits primero, tercero y cuarto al decodificador y manejar la salida 0, 2 y 6. La salida 0 también necesita que el segundo bit sea 0, el 2 y el 6 necesitan que el segundo bit sea 1. Y no logré encontrar una manera de verificar eso con las puertas dadas...
@BrianDrummond ¿Alguna idea? ¿Puedes resolver esto?
@BrianDrummond: si publica una descripción de la solución que cree que existe, podríamos verificarla. Es difícil decir que no existe una solución, pero es fácil verificar si una solución es válida.
@Ido Kessler ... Estaba intrigado por su solución y si su prueba es correcta, lamento que la haya eliminado. Nadie hasta ahora parece tener una solución. Quizás si incluyera una descripción de su algoritmo, mejoraría la respuesta. ¿Qué tan seguro está de que es correcto y libre de errores?
@Tut, no lo borró. Alguien más lo hizo...
@nrofis... ¿Cómo lo sabes? Si su respuesta fue eliminada por un mod, me gustaría saber por qué. La presentación de un método que se supone que debe probar que el problema no tiene solución ciertamente debería permitirse como respuesta.
@Tut, conozco a Ido, compartí la pregunta con él. Le pregunté por qué eliminó su respuesta y me dijo que su respuesta fue eliminada por mod. Su calificación también es demasiado baja para escribir comentarios....
@nrofis ¿Alguna vez obtuvo una solución de su profesor? Me intrigaría ver si hubo un error en el examen o si nos perdimos algo.
@jalalipop, lo hice ayer. Ido Kessler y pasaba por aqui tenían razón, mi profesor dijo que la pregunta estaba mal y que la NAND debería ser NOR....

Respuestas (4)

Escribí un algoritmo en C# que prueba todas las combinaciones posibles de esos Nor 3->1 Xor 2->1 Nand 2->1y Decoder 3->8.

Después de ejecutarlo durante 7½ millones de años 2 horas, devolvió 42 Falso. Creo que esto prueba que la pregunta no tiene respuesta ya que este algoritmo verifica todas las combinaciones posibles. :)

Me pidieron que lo describiera, por lo que la siguiente parte es una explicación de las partes del código, parte por parte. TL; DR : puede saltar al código al final :)

Hablemos de las líneas de entrada, tienen estados 0 o 1 y para cada una de las entradas posibles (0 a 15) tienen valores diferentes:

para la primera línea se ve así: 0 1 0 1 0 1 ... El segundo es: 0 0 1 1 0 0 1 1 ... el tercero: 0 0 0 0 1 1 1 1 .... como binario contando... ya entendiste :P

Entonces creé un objeto que representa cada línea en cada uno de sus estados:

class BitLine{
    bool[] IsActiveWhenInputIs = new bool[16];
}

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:

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
    }
}

También crearemos líneas de bit "siempre verdadero" y "siempre falso" para proporcionar una entrada constante "0" o "1".

for (int i = 0; i < 16; i++){
    bitLineList[4].IsActiveWhenInputIs[i] = false;
    bitLineList[5].IsActiveWhenInputIs[i] = true;
}

Ahora, si nota, lo que estamos buscando es en realidad una línea de bits específica, una que sea verdadera cuando la entrada sea 0, 7, 14. Representémosla 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 simplificó las cosas: lo que en realidad estamos buscando es una forma de "forjar" este BitLine necesario a partir de la línea de bits de entrada (así es como represento en mi programa lo que quiero que sea mi salida).

Ahora, así es como continuamos: cada vez que usamos algún elemento lógico en nuestras líneas de bits como Xor, o incluso el Nor, en realidad estamos creando una nueva línea de bits. ¡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 valor de la nueva línea de bits en cada entrada posible!NandDecoder

Nand Nor y Xor son sencillos:

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 entrada posible, representa cómo actuará el nuevo 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 de la otra función, esta obtiene una matriz de líneas de bits y agrega 8 líneas de bits nuevas 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 que tenemos todos nuestros elementos básicos, hablemos del algoritmo:

Vamos a hacer un algoritmo recursivo, en cada profundidad intentará usar otros elementos (nor\nand\xor\decoder) en las líneas de bits disponibles actualmente, y luego configurará el elemento como inutilizable para la siguiente profundidad recursiva. Siempre que lleguemos al fondo y no tengamos más elementos para usar, comprobaremos si tenemos una línea de bits que es la que buscábamos.

Este código verifica en cualquier momento si el grupo actual de líneas 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 utiliza para verificar 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, ahora la parte principal, este es el algoritmo principal:

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 las líneas de bits disponibles, la longitud de la lista, un valor booleano que representa si cada elemento está actualmente disponible (xor/nor/nand/decodificador) 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 líneas de bits 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 usando el elemento relevante. Luego llame a la siguiente profundidad de la recursividad, solo que esta vez no contendrá este elemento!".

esas son las funciones:

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, simplemente 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 quede una sola línea. salida con los valores necesarios.

*Tenga en cuenta que uso la misma lista todo el tiempo, por lo que no tendré que crear nuevas instancias de líneas de bits 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 sea una explicación válida :P

Es posible que desee incluir una descripción de alto nivel de cómo funciona este tipo de solucionador. No es inmediatamente obvio al leer este volcado de código completamente sin comentarios.
Esta es una solución intrigante y espero que pueda proporcionar una descripción del algoritmo. ¿Ha realizado casos de prueba similares para probar el método? (Por cierto, me gusta la referencia sutil de Douglas Adams)
Sí, es un poco demasiado. ¿Es esto exhaustivo?
@pipe sí, lo es.
@Tut, agregué una descripción larga de la solución :) con suerte, esta vez está bien. Y me puse a pensar que nadie entendía la referencia jaja
@DaveTweed espero que esté bien ^^
Agregaré que probé este algoritmo con algún caso de prueba que pude verificar: x==2, x==3, x==4, ... , x==11. Como tarda mucho tiempo en ejecutarse, me doy cuenta de que x%3==0 y x%5==0 también pueden ser imposibles, y no pude encontrar una respuesta para ambos. Pero el algoritmo se volvió verdadero para todos los casos anteriores para los cuales encontré una solución a mano.
+1! @IdoKessler, ¿puede intentar cambiar la entrada NAND de 2 bits con una entrada NOR de 2 bits y verificar si su software ofrece una solución? De hecho, con esa puerta, en lugar de una NAND, hay una solución.
@next-hack devolvió True cuando lo cambié para usar un NOR de 2 bits
@next-hack Esta es su solución: conecta el segundo y tercer bit a xor. conecte el decodificador a los primeros, segundos y cuartos bits. conecte el 3->1 ni a la salida del decodificador 0, 3, 6. conectar el 2->1 nor a la salida 3->1 nor y la salida xor. (Al llegar a una solución le pedí que imprimiera sus acciones)
sí, encontré una solución hace algunos días pero con un NOR, por eso pregunté si su programa también podría encontrarlo :)

Esta es una no respuesta, para descartar la solución más obvia.

Numeraré los bits por su peso: b 1 , b 2 , b 4 y b 8 .

como bits b 2 y b 4 son iguales en todos los números válidos, podríamos pensar en implementar la expresión lógica:

( ni   { X = 0 , X = 3 , X = 6 } )   y   ( b 2   xor   b 4 )

donde x es { b 1 , b 4 , b 8 }, implementado con el decodificador 3-8.

Sin embargo, la simplificación de la expresión anterior es:

( X = 0   o   X = 3   o   X = 6 )   o   ( b 2 = b 4 )

eso no es lo esperado:

( X = 0   o   X = 3   o   X = 6 )   y   ( b 2 = b 4 )

Por esta razón, creo probable un error en la pregunta, siendo la puerta "nand" una puerta "ni".

Tal vez sea cierto, yo tampoco encontré respuesta.
+1. Creo que tienes razón, y la NAND debería ser NOR.

Una respuesta válida a su pregunta sería cualquier circuito que siempre sea verdadero. Porque también devolverá verdadero si los números de entrada son 0,7 o 14.

Creo que la pregunta debería pedir explícitamente un circuito que dé como resultado verdadero si los números de entrada son 0,7 o 14. Y que dé como resultado falso de lo contrario.

Wow, no esperaba tal respuesta. El circuito debe devolver verdadero si y solo si la entrada es 0, 7 o 14...
exactamente así.
+1 por mirar las especificaciones cuidadosamente. Esta es una mala ingeniería cuando se obtiene una especificación de este tipo de un cliente. En ese caso, la respuesta correcta es señalar el problema con la especificación al cliente y verificar lo que realmente quiere. Pero, para una pregunta de examen, muestra un pensamiento innovador y proporciona correctamente una respuesta muy simple.

es factible Como sugerencia, los dos bits del medio son iguales para todos estos patrones de bits, por lo que al eliminarlos 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.

Ya hecho eso. No encontré ninguna combinación que resuelva la pregunta...
Use el xor para reducir los cuatro bits a tres bits para el decodificador. El decodificador tendrá tres salidas que son 1 para los tres patrones coincidentes. Ni juntarlos y usar la puerta nand como inversor.
@John ... Su solución produce 6 términos de productos (sin simplificar), 3 de los cuales no son válidos. En otras palabras, aunque su solución sea verdadera para 0, 7 o 14; también devuelve verdadero para 1, 6 u 8.
Circuito lógico digital - pregunta de examen
RespuestasAquíPolítica de privacidad1y, 0v