Digital Logic Circuit - Prüfungsfrage

14

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?

nrofis
quelle
1
Als Tipp: Bei 4 Bits und einem 3-8-Decoder müssen Sie eines der Bits anders behandeln.
Brian Drummond
2
@BrianDrummond aber das weiß ich schon und es ist mir immer noch nicht gelungen es zu lösen. Bei jeder Lösung, die ich ausprobiert habe, fehlt ein ODER-Gatter. Ich kann nicht eine solche Kombination mit den gegebenen Gatter gefunden, die das Problem lösen kann ... Beachten Sie, dass ich pro Typ nur ein Tor haben ...
nrofis
3
@BrianDrummond: Wenn Sie eine Beschreibung der Lösung veröffentlichen, die Ihrer Meinung nach existiert, können wir diese überprüfen. Es ist schwer zu sagen, dass es keine Lösung gibt, aber einfach zu überprüfen, ob eine Lösung gültig ist.
Pasaba por aqui
2
@Ido Kessler ... Ihre Lösung hat mich fasziniert, und wenn Ihre Beweise stimmen, tut es mir leid, dass Sie sie gelöscht haben. Bisher scheint niemand eine Lösung zu haben. Vielleicht würde es die Antwort verbessern, wenn Sie eine Beschreibung Ihres Algorithmus einfügen würden. Wie sicher sind Sie, dass es korrekt und fehlerfrei ist?
Bis zum
3
@jalalipop habe ich gestern gemacht. Ido Kessler und pasaba por aqui waren recht, mein Professor sagte , dass die Frage falsch war und das NAND sollte NOR sein ....
nrofis

Antworten:

24

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

Ido Kessler
quelle
6
Möglicherweise möchten Sie eine allgemeine Beschreibung der Funktionsweise dieser Art von Solver hinzufügen. Es ist nicht sofort ersichtlich, wenn man diesen völlig unkommentierten Codedump liest.
Dave Tweed
2
Dies ist eine faszinierende Lösung, und ich hoffe, Sie können eine Beschreibung des Algorithmus bereitstellen. Haben Sie ähnliche Testfälle durchgeführt, um die Methode zu beweisen? (Übrigens, ich mag die subtile Douglas Adams Referenz)
Tut
2
Ich werde hinzufügen, dass ich diesen Algorithmus mit einem Testfall ausprobiert habe, den ich überprüfen konnte: x == 2, x == 3, x == 4, ..., x == 11. Da die Ausführung sehr lange dauert, stelle ich fest, dass auch x% 3 == 0 und x% 5 == 0 möglicherweise nicht möglich sind, und ich konnte auf beide keine Antwort finden. Aber der Algorithmus hat für alle oben genannten Fälle, für die ich eine Lösung von Hand gefunden habe, den Wert true zurückgegeben.
Ido Kessler
3
+1! @IdoKessler können Sie versuchen, das 2-Bit-Eingangs-NAND durch ein 2-Bit-Eingangs-NOR zu ändern, und prüfen, ob Ihre Software eine Lösung bietet? Tatsächlich gibt es mit diesem Gatter anstelle eines NAND eine Lösung.
Next-Hack
3
@ next-hack es gab True zurück, als ich es änderte, um ein 2-Bit-NOR zu verwenden
Ido Kessler
8

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

b1b2b4b8

b2b4

(Noch {x=0,x=3,x=6}) und (b2 xor b4)

b1b4b8 } ist, implementiert mit dem 3-8-Decoder.

Die Vereinfachung des vorherigen Ausdrucks ist jedoch:

(x=0 oder x=3 oder x=6) oder (b2=b4)

das ist nicht zu erwarten:

(x=0 oder x=3 oder x=6) und (b2=b4)

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

pasaba por aqui
quelle
2
Vielleicht stimmt das, ich habe auch keine Antwort gefunden.
Nrofis
2
+1. Ich glaube, Sie haben Recht, und das NAND sollte ein NOR sein.
Brian Drummond
2

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.

Augustin Tena
quelle
2
Wow, ich habe keine solche Antwort erwartet. Die Schaltung sollte genau dann true zurückgeben, wenn der Eingang 0, 7 oder 14 ist ...
nrofis
1
genau wie das.
Augustin Tena
2
+1 für die genaue Betrachtung der technischen Daten. Dies ist eine schlechte Technik, wenn Sie eine solche Spezifikation von einem Kunden erhalten. In diesem Fall besteht die richtige Antwort darin, den Kunden auf das Problem mit der Spezifikation hinzuweisen und zu überprüfen, was sie wirklich wollen. Bei einer Prüfungsfrage wird jedoch ein Umdenken gezeigt, und es wird korrekterweise eine sehr einfache Antwort gegeben.
Olin Lathrop
-3

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.

John
quelle
Schon gemacht. Ich habe keine Kombination gefunden, die die Frage löst ...
Nrofis
Verwenden Sie xor, um die vier Bits für den Decoder auf drei Bits zu reduzieren. Der Decoder hat drei Ausgänge, die für die drei übereinstimmenden Muster 1 sind. Noch sie zusammen und nutzen das Nand-Gate als Inverter.
John
4
@John ... Ihre Lösung liefert 6 Produktbegriffe (nicht vereinfacht), von denen 3 ungültig sind. Mit anderen Worten, obwohl Ihre Lösung für 0, 7 oder 14 true zurückgibt; es gibt auch true für 1, 6 oder 8 zurück.
Tut