Circuit logique numérique - question d'examen

14

J'ai une question d'examen que je n'ai pas réussi à résoudre:

J'ai besoin de construire un circuit logique numérique qui reçoit un numéro de 4 bits et de revenir truesi le numéro est 0, 7ou 14. Je n'ai qu'une seule XORporte (2 entrées), une NOR(3 entrées), une NAND(2 entrées) et un décodeur 3 à 8.

Je pense que cette question est insoluble, je n'ai trouvé aucune combinaison qui puisse le faire. Une idée de comment le résoudre?

digital-logic circuit-analysis logic-gates boolean-algebra nrofis
la source

1

À titre indicatif: étant donné 4 bits et un décodeur 3-8, vous devez traiter l'un des bits différemment.

Brian Drummond

2

@BrianDrummond mais je le sais déjà, et je n'ai toujours pas réussi à le résoudre. Chaque solution que j'ai essayée a l'impression qu'il manque une porte OU. Je ne trouve pas une telle combinaison avec les portes données qui peut résoudre le problème ... Notez que je n'ai qu'une seule porte par type ...

nrofis

3

@BrianDrummond: si vous postez une description de la solution que vous pensez exister, nous pourrions la vérifier. Il est difficile de dire qu'aucune solution n'existe, mais facile à vérifier si une solution est valide.

pasaba por aqui

2

@Ido Kessler ... J'ai été intrigué par votre solution et si votre preuve est correcte, je suis désolé que vous l'ayez supprimée. Jusqu'à présent, personne ne semble avoir de solution. Peut-être que si vous incluiez une description de votre algorithme, cela améliorerait la réponse. Dans quelle mesure êtes-vous sûr qu'il est correct et sans bogue?

Tut

3

@jalalipop, je l'ai fait hier. Ido Kessler et pasaba por aqui avaient raison, mon professeur a dit que la question était fausse et que la NAND devrait être NOR ....

nrofis

24

J'ai écrit un algorithme en C # qui essaie toutes les combinaisons possibles de ceux-ci Nor 3->1 Xor 2->1 Nand 2->1et de Decoder 3->8.

Après l'avoir fait fonctionner pendant ~~7½ millions d'années~~ 2 heures, il a renvoyé 42 faux. Je crois que cela prouve que la question n'a pas de réponse car cet algorithme vérifie toutes les combinaisons possibles. :)

On m'a demandé de le décrire, donc la partie suivante est une explication des parties du code, partie par partie. TL; DR - vous pouvez simplement passer au code à la fin :)

Parlons des lignes d'entrée, elles ont 0 ou 1 état et pour chacune des entrées possibles (0 à 15) elles ont des valeurs différentes:

pour la première ligne ça ressemble à ça: 0 1 0 1 0 1 ... La seconde est: 0 0 1 1 0 0 1 1 ... la troisième: 0 0 0 0 1 1 1 1 .... comme binaire en comptant ... vous avez l'idée: P

J'ai donc créé un objet qui représente chaque ligne dans chacun de ses états:

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

Comme il est dit, bitLine.IsActiveWhenInputIs [5] indique si la ligne était active lorsque l'entrée était à 5.

Ceci est un code qui crée complètement les lignes d'entrée:

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

Nous allons également créer des lignes de bits "toujours vrai" et "toujours faux" - pour fournir une entrée "0" ou "1" constante.

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

Maintenant, si vous remarquez, ce que nous recherchons est en fait un bitLine spécifique, celui qui est vrai lorsque l'entrée est 0, 7, 14. Représentons-le dans notre classe:

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

Cela a rendu les choses vraiment simples: ce que nous recherchons en fait est un moyen de "forger" ce nécessaire BitLine à partir de la ligne de bits d'entrée (c'est ainsi que je représente pour mon programme ce que je veux que ma sortie soit).

Maintenant, voici comment nous allons le: chaque fois que nous utilisons un élément logique sur nos lignes de bits comme Xor, Nor, Nandou même Decoder, nous créons en fait une nouvelle Bitline \ s. Nous connaissons la valeur de chacune des lignes dans chaque entrée possible de 0 à 15, nous pouvons donc également calculer la nouvelle valeur bitLine dans chaque entrée possible!

Nand Nor et Xor sont tous simples:

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

Pour chaque entrée possible, il représente la façon dont la nouvelle BitLine va agir.

La manipulation du décodeur est un peu délicate, mais l'idée est "si les bits à l'entrée représentent le nombre x en binaire, alors la x-ème ligne de bits de sortie sera vraie, tandis que toutes les autres seront fausses. Contrairement à l'autre , celle-ci obtient un tableau de lignes de bits et ajoute 8 nouvelles lignes de bits au tableau.

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

Maintenant, nous avons tous nos éléments de base, parlons donc de l'algorithme:

Nous allons faire un algorithme récursif, à chaque profondeur, il essaiera d'utiliser un autre élément (ni \ nand \ xor \ decoder) sur les lignes de bits actuellement disponibles, puis définira l'élément sur inutilisable pour la prochaine profondeur récursive. Chaque fois que nous arrivons en bas et que nous n'avons plus d'éléments à utiliser, nous vérifierons si nous avons une ligne de bit qui correspond à ce que nous recherchions.

Ce code vérifie à tout moment si le groupe de lignes actuel contient la ligne que nous recherchons:

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

C'est la fonction qu'il utilise pour vérifier si deux lignes sont égales:

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

Ok, alors maintenant pour la partie principale, voici l'algorithme 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;
    }
}

Cette fonction reçoit une liste des bitLines disponibles, la longueur de la liste, un booléen représentant si chaque élément est actuellement disponible (xor / nor / nand / decoder) et un bitLine représentant le bitLine que nous recherchons.

À chaque étape, il vérifie si nous avons d'autres éléments à utiliser, sinon - il vérifie si nous archivons notre ligne de bit nécessaire.

Si nous avons encore plus d'éléments, donc pour chaque élément, il appelle une fonction censée gérer la création de nouvelles bitLines en utilisant ces éléments et appeler la profondeur récursive suivante par la suite.

Les fonctions de gestionnaire suivantes sont toutes assez simples, elles peuvent être traduites en "choisissez 2 \ 3 parmi les lignes de bits disponibles et combinez-les en utilisant l'élément approprié. Ensuite, appelez la profondeur suivante de la récursivité, juste que cette fois elle ne contiendra pas cet élément! ".

ce sont les fonctions:

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

Et voilà, nous appelons simplement cette fonction avec la ligne nécessaire que nous recherchons, et elle vérifie toutes les combinaisons possibles des pièces électriques pour vérifier s'il est possible de les combiner de telle manière qu'au final, une seule ligne sera sortie avec les valeurs nécessaires.

* remarquez que j'utilise la même liste tout le temps, donc je n'aurai pas besoin de créer de nouvelles instances de lignes de bits tout le temps. Je lui donne un tampon de 200 pour cette raison.

Voici le programme complet:

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

J'espère que cette fois c'est une explication valable: P

Ido Kessler
la source

6

Vous souhaiterez peut-être inclure une description détaillée du fonctionnement de ce type de solveur. Il n'est pas immédiatement évident de lire ce vidage de code entièrement sans commentaires.

Dave Tweed

2

Il s'agit d'une solution intrigante et j'espère que vous pourrez fournir une description de l'algorithme. Avez-vous fait des tests similaires pour prouver la méthode? (BTW, j'aime la référence subtile de Douglas Adams)

Tut

2

J'ajouterai que j'ai essayé cet algorithme avec un cas de test que j'ai pu vérifier: x == 2, x == 3, x == 4, ..., x == 11. Comme cela prend beaucoup de temps, je remarque que les x% 3 == 0 et x% 5 == 0 peuvent également être impossibles, et je n'ai pas pu trouver de réponse pour les deux. Mais l'algorithme est retourné vrai pour tous les cas ci-dessus pour lesquels j'ai trouvé une solution à la main.

Ido Kessler

3

+1! @IdoKessler pouvez-vous essayer de changer la NAND d'entrée 2 bits avec une entrée NOR 2 bits, et vérifier si votre logiciel donne une solution? En fait, avec cette porte, au lieu d'une NAND, il y a une solution.

Next-hack

3

@ next-hack, il est retourné True lorsque je l'ai changé pour utiliser un NOR 2 bits

Ido Kessler

8

Il s'agit d'une non-réponse, pour écarter la solution la plus évidente.

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

$b_2$ $b_4$

(ni {X = 0, X = 3, X = 6}) nand (b_{2} xor b_{4})

$( \text{nor} ~ \{ x=0, x=3, x=6 \} ) ~ \text{nand} ~ ( b_2 ~ \text{xor} ~ b_4 )$

$b_1$ $b_4$ $b_8$

Cependant, la simplification de l'expression précédente est:

(X = 0 ou X = 3 ou X = 6) ou (b_{2} = b_{4})

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

ce n'est pas prévu:

(X = 0 ou X = 3 ou X = 6) et (b_{2} = b_{4})

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

Pour cette raison, je pense que probablement une erreur dans la question, étant "nand" porte un "ni" un.

pasaba por aqui
la source

2

C'est peut-être vrai, je n'ai pas trouvé de réponse non plus.

nrofis

2

+1. Je crois que vous avez raison, et la NAND devrait être un NOR.

Brian Drummond

2

Une réponse valide à votre question serait tout circuit qui renvoie toujours vrai. Parce que cela retournera vrai aussi si les nombres d'entrée sont 0,7 ou 14.

Je pense que la question devrait explicitement demander un circuit qui sort vrai si les nombres d'entrée sont 0,7 ou 14. Et qui sort faux sinon.

Agustin Tena
la source

2

Wow, je ne m'attendais pas à une telle réponse. Le circuit devrait retourner vrai si et seulement si l'entrée est 0, 7 ou 14 ...

nrofis

1

exactement comme ça.

Agustin Tena

2

+1 pour avoir examiné attentivement les spécifications. C'est une mauvaise ingénierie lors de l'obtention d'une telle spécification d'un client. Dans ce cas, la bonne réponse consiste à signaler le problème de la spécification au client et à vérifier ce qu'il veut vraiment. Mais, pour une question d'examen, cela montre une réflexion hors des sentiers battus et fournit correctement une réponse très simple.

Olin Lathrop

-3

C'est faisable. À titre indicatif, les deux bits du milieu sont égaux pour tous ces modèles de bits, donc les xorer produira 0 qui peut ensuite être une entrée pour le décodeur avec les deux autres bits. Les portes restantes sont appliquées aux trois sorties du décodeur pour fournir la sortie à bit unique correcte.

John
la source

Je l'ai déjà fait. Je n'ai trouvé aucune combinaison qui résout la question ...

nrofis

Utilisez le xor pour réduire les quatre bits à trois bits pour le décodeur. Le décodeur aura trois sorties qui sont 1 pour les trois modèles correspondants. Ni les utiliser ensemble et utiliser la porte nand comme onduleur.

John

4

@John ... Votre solution fournit 6 termes de produits (non simplifiés), dont 3 sont invalides. En d'autres termes, bien que votre solution renvoie vrai pour 0, 7 ou 14; il renvoie également vrai pour 1, 6 ou 8.

Tut

Circuit logique numérique - question d'examen

Réponses: