Digital Logic Circuit - Prüfungsfrage

Ich habe eine Prüfungsfrage, die ich nicht gelöst habe:

Ich brauche eine digitale Logikschaltung aufzubauen , die 4 - Bit - Zahl und zurück erhält , truewenn die Zahl ist 0, 7oder 14. Ich habe nur ein XORGate (2 Eingänge), einen NOR(3 Eingänge), einen NAND(2 Eingänge) und einen 3-zu-8-Decoder.

Ich denke, diese Frage ist unlösbar, ich habe keine Kombination gefunden, die das kann. Irgendeine Idee, wie man es löst?

Ich habe einen Algorithmus in C # geschrieben, der jede mögliche Kombination von diesen Nor 3->1 Xor 2->1 Nand 2->1und ausprobiert Decoder 3->8.

Nachdem es 7½ Millionen Jahre lang 2 Stunden gelaufen war , gab es 42 False zurück. Ich glaube, dies beweist, dass die Frage keine Antwort hat, da dieser Algorithmus jede mögliche Kombination überprüft. :)

Ich wurde gebeten, es zu beschreiben, daher ist der nächste Teil eine Erklärung der Teile des Codes, Teil für Teil. TL; DR - Sie können am Ende einfach zum Code unten springen :)

Lassen Sie uns über die Eingangsleitungen sprechen, die entweder 0 oder 1 Zustände haben und für jeden der möglichen Eingänge (0 bis 15) unterschiedliche Werte enthalten:

für die erste Zeile sieht es so aus: 0 1 0 1 0 1 ... Die zweite ist: 0 0 1 1 0 0 1 1 ... die dritte: 0 0 0 1 1 1 1 ... wie binär Zählen ... Du hast die Idee: P

Also habe ich ein Objekt erstellt, das jede Linie in jedem seiner Zustände darstellt:

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

Wie es heißt, gibt bitLine.IsActiveWhenInputIs [5] zurück, ob die Zeile aktiv war, als die Eingabe 5 war.

Dies ist ein Code, der die Eingabezeilen insgesamt erstellt:

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

Wir werden auch eine Bitleitung "immer wahr" und "immer falsch" erstellen, um einen konstanten "0" -Eingang oder "1" -Eingang bereitzustellen.

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

Nun, wenn Sie bemerken, was wir suchen, ist tatsächlich eine bestimmte BitLine, eine, die wahr ist, wenn die Eingabe 0, 7, 14 ist. Lassen Sie uns sie in unserer Klasse darstellen:

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

Dies machte die Dinge wirklich einfach: Was wir tatsächlich suchen, ist eine Möglichkeit, diese neededBitLine von der Eingabebitleitung "zu fälschen" (so stelle ich meinem Programm dar, was meine Ausgabe sein soll).

Nun, das ist , wie wir weitermachen: jedes Mal , wenn wir etwas logisches Element auf unserer Bitleitungen verwenden wie Xor, Nor, Nandoder sogar das Decodersind wir tatsächlich eine neue BITLINE Schaffung \ s. Wir kennen den Wert jeder der Zeilen in jeder möglichen Eingabe von 0 bis 15, sodass wir den neuen BitLine-Wert auch in jeder möglichen Eingabe berechnen können!

Nand Nor und Xor sind alle unkompliziert:

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]);
    }
}

Für jede mögliche Eingabe wird angegeben, wie sich die neue BitLine verhält.

Die Handhabung des Decoders ist ein wenig knifflig, aber die Idee ist: "Wenn die Bits am Eingang die Zahl x in binärer Form darstellen, ist die x-te Ausgangsbitleitung wahr, während alle anderen falsch sind. Im Gegensatz zu den anderen." Funktion erhält dieser ein Array mit Bitleitungen und fügt dem Array 8 neue Bitleitungen hinzu.

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

Jetzt haben wir alle unsere Grundelemente, sprechen wir also über den Algorithmus:

Wir werden einen rekursiven Algorithmus ausführen. Bei jeder Tiefe wird versucht, andere Elemente (weder \ nund \ xoder \ decoder) für die derzeit verfügbaren Bitleitungen zu verwenden, und das Element wird dann für die nächste rekursive Tiefe auf unbrauchbar gesetzt. Immer wenn wir unten ankommen und keine Elemente mehr zu verwenden sind, werden wir prüfen, ob wir eine Bitleitung haben, nach der wir gesucht haben.

Mit diesem Code können Sie jederzeit überprüfen, ob die aktuelle Zeilengruppe die gesuchte Zeile enthält:

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

Mit dieser Funktion wird geprüft, ob zwei Zeilen gleich sind:

bool CheckEquals(BitLine other)
{
    for (var i = 0; i < 16; i++)
    {
        if (this.IsActiveWhenInputIs[i] != other.IsActiveWhenInputIs[i])
        {
            return false;
        }
    }
    return true;
}

Ok, nun zum Hauptteil, dies ist der Hauptalgorithmus:

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

Diese Funktion empfängt eine Liste der verfügbaren BitLines, die Listenlänge, einen Booleschen Wert, der angibt, ob jedes Element aktuell verfügbar ist (xor / nor / nand / decoder), und eine BitLine, die die gesuchte BitLine darstellt.

In jeder Phase wird überprüft, ob weitere Elemente zu verwenden sind. Andernfalls wird überprüft, ob die benötigte Bitleitung archiviert wird.

Wenn wir noch mehr Elemente haben, ruft es für jedes Element eine Funktion auf, die das Erstellen neuer BitLines mit diesen Elementen und den anschließenden Aufruf der nächsten rekursiven Tiefe handhaben soll.

Die Funktionen des nächsten Handlers sind alle ziemlich einfach. Sie können übersetzt werden, um "2 \ 3 aus den verfügbaren Bitleitungen auszuwählen und sie mit dem entsprechenden Element zu kombinieren. Rufen Sie dann die nächste Tiefe der Rekursion auf, nur dass sie diesmal nicht enthalten ist dieses Element! "

das sind die funktionen:

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

Und das ist es, wir rufen diese Funktion einfach mit der benötigten Leitung auf, die wir suchen, und sie prüft jede mögliche Kombination der elektrischen Teile, um zu prüfen, ob es möglich ist, sie so zu kombinieren, dass am Ende eine einzelne Leitung entsteht mit den benötigten Werten ausgegeben.

* Beachten Sie, dass ich immer dieselbe Liste verwende, sodass ich nicht ständig neue Bitlines-Instanzen erstellen muss. Ich gebe es aus diesem Grund einen Puffer von 200.

Dies ist das vollständige Programm:

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();
        }
    }
}

Hoffe, diesmal ist es eine gültige Erklärung: P

Dies ist eine Nichtantwort, um die naheliegendste Lösung zu verwerfen.

$b_1$$b_2$$b_4$$b_8$

$b_2$$b_4$

$b_1$$b_4$$b_8$ } ist, implementiert mit dem 3-8-Decoder.

Die Vereinfachung des vorherigen Ausdrucks ist jedoch:

das ist nicht zu erwarten:

Aus diesem Grund halte ich einen Fehler in der Frage für wahrscheinlich, nämlich "nand" gate a "nor" one.

Eine gültige Antwort auf Ihre Frage wäre jede Schaltung, die immer wahr zurückgibt. Denn es wird auch dann true zurückgegeben, wenn die eingegebenen Zahlen 0,7 oder 14 sind.

Ich denke, die Frage sollte explizit nach einer Schaltung fragen, die true ausgibt, wenn die Eingabenummern 0,7 oder 14 sind. Andernfalls wird false ausgegeben.

Es ist machbar. Als Hinweis sind die mittleren zwei Bits für alle diese Bitmuster gleich, so dass das Xoring von ihnen 0 erzeugt, was dann eine Eingabe in den Decoder mit den anderen zwei Bits sein kann. Die verbleibenden Gatter werden an die drei Decoderausgänge angelegt, um die korrekte Einzelbitausgabe bereitzustellen.