Circuito de lógica digital - pregunta de examen

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

Después de ejecutarlo durante 7½ millones de años 2 horas, devolvió 42 Falso. Creo que esto demuestra que la pregunta no tiene respuesta ya que este algoritmo verifica cada combinación posible. :)

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 : puedes saltar al código al final :)

Hablemos sobre las líneas de entrada, tienen 0 o 1 estados 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 el conteo binario ... tienes la idea: P

Así que 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 en conjunto:

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 cierto" y "siempre falso", para proporcionar una entrada constante de "0" o una entrada de "1".

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

Ahora, si observa, lo que estamos buscando es en realidad una línea de bits específica, una que es verdadera cuando la entrada es 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 hizo las cosas realmente simples: lo que realmente estamos buscando es una manera de "forjar" esta línea de bits necesaria 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 continuamos: cada vez que usamos algún elemento lógico en nuestras líneas de bits como Xor , Nor , Nand o incluso el Decoder , en realidad estamos creando una nueva línea de bits. . Sabemos el valor de cada una de las líneas en cada entrada posible de 0 a 15, ¡así que podemos calcular el nuevo valor de bitLine en cada entrada posible también!

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.

El manejo del 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 del bit de salida x-th será verdadera, mientras que todas las demás serán falsas. A diferencia de la otra función, esta obtiene una matriz de línea de bits y agrega 8 nuevas líneas de bits 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 hablemos sobre el algoritmo:

Vamos a hacer un algoritmo recursivo, en cada profundidad intentará usar otros elementos (ni \ ny \ xor \ decodificador) en las líneas de bits disponibles actualmente, y luego establecerá el elemento como inutilizable para la siguiente profundidad recursiva. Cuando lleguemos al final y no tengamos más elementos para usar, verificaremos si tenemos una línea de bits que es lo que buscábamos.

Este código comprueba en cualquier momento si el grupo de líneas actual 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 usa 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 para 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 / decoder) y una línea de bits que representa la línea de bits que estamos buscando.

En cada etapa, comprueba si tenemos más elementos para usar, si no, comprueba si archivamos nuestra línea de bits necesaria.

Si todavía tenemos más elementos, entonces para cada elemento se llama una función que se supone que debe manejar la creación de nuevas líneas de bits utilizando esos elementos y luego invocar la siguiente profundidad recuresiva.

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 recursión, solo que esta vez ganó. no contiene 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 así es, simplemente llamamos a esta función la línea necesaria que buscamos y verifica cada combinación posible de las partes eléctricas para verificar si es posible combinarlas de tal manera que al final una sola La línea se mostrará con los valores necesarios.

* note 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:

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

Esto no es una 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 los 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:

$$ (\ 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 3-8.

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

$$ (x = 0 ~ \ text {o} ~ x = 3 ~ \ text {o} ~ x = 6) ~ \ text {o} ~ (b_2 = b_4) $$

eso no es lo esperado:

$$ (x = 0 ~ \ text {o} ~ x = 3 ~ \ text {o} ~ x = 6) ~ \ text {y} ~ (b_2 = b_4) $$

Por esta razón, creo que es probable que haya un error en la pregunta, al ser "nand" gate a "ni" one.

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 salga verdadero si los números de entrada son 0,7 o 14. Y eso da como resultado falso de otra manera.

Es factible. Como una sugerencia, los dos bits del medio son iguales para todos estos patrones de bits, por lo que al realizarlos se producirá 0, que puede ser una entrada para el decodificador con los otros dos bits. Las puertas restantes se aplican a las tres salidas del decodificador para proporcionar la salida de bit único correcta.