Układ logiki cyfrowej - pytanie egzaminacyjne

Mam pytanie z egzaminu, którego nie udało mi się rozwiązać:

Muszę zbudować cyfrowy układ logiczny, który otrzymuje 4-bitową liczbę i zwrócić, truejeśli liczba jest 0, 7lub 14. Mam tylko jedną XORbramę (2 wejścia), jedno NOR(3 wejścia), jedno NAND(2 wejścia) i jeden dekoder 3 do 8.

Myślę, że to pytanie jest nierozwiązywalne, nie znalazłem żadnej kombinacji, która mogłaby to zrobić. Masz pomysł, jak to rozwiązać?

Napisałem algorytm w języku C #, który wypróbowuje każdą możliwą kombinację tych Nor 3->1 Xor 2->1 Nand 2->1i Decoder 3->8.

Po uruchomieniu go przez 7 i pół miliona lat przez 2 godziny, zwrócił 42 Fałsz. Uważam, że to dowodzi, że pytanie nie ma odpowiedzi, ponieważ ten algorytm sprawdza każdą możliwą kombinację. :)

Poproszono mnie o opisanie tego, więc następna część zawiera wyjaśnienie części kodu, część po części. TL; DR - możesz po prostu przejść do kodu na końcu :)

Porozmawiajmy o liniach wejściowych, mają one 0 lub 1 stanów i dla każdego z możliwych wejść (od 0 do 15) mają różne wartości:

dla pierwszego wiersza wygląda to tak: 0 1 0 1 0 1 ... Drugi to: 0 0 1 1 0 0 1 1 ... trzeci: 0 0 0 0 1 1 1 1 .... jak binarny liczenie ... masz pomysł: P

Stworzyłem więc obiekt reprezentujący każdą linię w każdym z jego stanów:

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

Jak to mówi bitLine.IsActiveWhenInputIs [5] zwraca, czy linia była aktywna, gdy wejście miało wartość 5.

To jest kod, który tworzy linie wejściowe:

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

Stworzymy również „zawsze prawdziwe” i „zawsze fałszywe” linie bitowe - w celu zapewnienia stałego wejścia „0” lub „1”.

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

Teraz, jeśli zauważysz, to, czego szukamy, to konkretna bitLine, która jest prawdziwa, gdy dane wejściowe wynoszą 0, 7, 14. Przedstawmy to w naszej klasie:

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

To sprawiło, że wszystko stało się naprawdę proste: tak naprawdę szukamy sposobu na „wykuwanie” tej potrzebnej BitLine z wejściowej linii bitowej (w ten sposób reprezentuję mój program, co chcę, aby moje wyjście było).

Teraz, to jak idziemy na: za każdym razem używamy jakiegoś logicznego elementu na naszych bitLines jak Xor, Nor, Nanda nawet Decoderjesteśmy rzeczywiście tworzenia nowego bitLine \ s. Znamy wartość każdej linii na każdym możliwym wejściu od 0 do 15, więc możemy obliczyć nową wartość bitLine również na każdym możliwym wejściu!

Nand Nor i Xor są proste:

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

Dla każdego możliwego wejścia reprezentuje on działanie nowej BitLine.

Obsługa dekodera jest nieco trudna, ale pomysł jest taki: „jeśli bity na wejściu reprezentują liczbę x w formacie binarnym, wówczas x-ta wyjściowa linia bitowa będzie prawdziwa, podczas gdy wszystkie inne będą fałszywe. W przeciwieństwie do innych funkcja ta pobiera tablicę bitline i dodaje 8 nowych bitline do tablicy.

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

Teraz mamy wszystkie nasze podstawowe elementy, więc porozmawiajmy o algorytmie:

Zrobimy algorytm rekurencyjny, na każdej głębokości będzie próbował użyć innych elementów (ani \ nand \ xor \ dekodera) na aktualnie dostępnych liniach bitowych, a następnie ustawi element na niezdatny do użytku dla następnej rekurencyjnej głębokości. Za każdym razem, gdy dojdziemy do końca i nie mamy już więcej elementów do użycia, sprawdzimy, czy mamy linię bitową, której szukaliśmy.

Ten kod w dowolnym momencie sprawdza, czy bieżąca grupa linii zawiera poszukiwaną linię:

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

Jest to funkcja, której używa do sprawdzania, czy dwie linie są równe:

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

Ok, więc teraz w głównej części jest to główny algorytm:

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

Ta funkcja otrzymuje listę dostępnych linii bitowych, długość listy, wartość logiczną wskazującą, czy każdy element jest aktualnie dostępny (xor / nor / nand / dekoder) oraz bitLine reprezentującą poszukiwaną bitLine.

Na każdym etapie sprawdza, czy mamy więcej elementów do użycia, jeśli nie - sprawdza, czy zarchiwizowaliśmy potrzebną linię.

Jeśli nadal mamy więcej elementów, to dla każdego elementu wywołuje funkcję, która powinna obsługiwać tworzenie nowych bitLines przy użyciu tych elementów i wywoływanie następnej głębokości rekurencyjnej.

Wszystkie następne funkcje obsługi są dość proste, można je przetłumaczyć na „wybierz 2 \ 3 z dostępnych linii bitowych i połącz je za pomocą odpowiedniego elementu. Następnie wywołaj następną głębokość rekurencji, tyle że tym razem nie będzie ona zawierała ten element! ”.

są to funkcje:

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

I to jest to, po prostu wywołujemy tę funkcję z potrzebną linią, której szukamy, i sprawdza każdą możliwą kombinację części elektrycznych, aby sprawdzić, czy można je połączyć w taki sposób, że ostatecznie jedna linia będzie generowane z potrzebnymi wartościami.

* zauważ, że używam tej samej listy przez cały czas, więc nie będę musiał cały czas tworzyć nowych instancji linii bitów. Z tego powodu daję mu bufor 200.

Oto kompletny program:

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

Mam nadzieję, że tym razem jest to prawidłowe wyjaśnienie: P

To nie jest odpowiedź, aby odrzucić najbardziej oczywiste rozwiązanie.

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

$b_2$$b_4$

$b_1$$b_4$$b_8$

Uproszczenie poprzedniego wyrażenia jest jednak następujące:

to nie jest oczekiwane:

Z tego powodu uważam, że prawdopodobny jest błąd w pytaniu, ponieważ „nand” oznacza „ani”, ani jeden.

Poprawną odpowiedzią na twoje pytanie będzie każdy obwód, który zawsze zwraca wartość true. Ponieważ zwróci wartość true również wtedy, gdy liczby wejściowe to 0,7 lub 14.

Sądzę, że pytanie powinno wyraźnie dotyczyć obwodu, który odpowiada prawdzie, jeśli liczby wejściowe wynoszą 0,7 lub 14, a w przeciwnym razie zwraca fałsz.

To jest wykonalne. Podpowiedź, że dwa środkowe bity są równe dla wszystkich tych wzorów bitów, więc xoring ich da 0, które następnie mogą być wejściem do dekodera z pozostałymi dwoma bitami. Pozostałe bramki są stosowane do trzech wyjść dekodera w celu zapewnienia prawidłowego wyjścia jednobitowego.