Circuito lógico digital - pergunta do exame

14

Tenho uma pergunta do exame que não resolvi:

Preciso construir um circuito lógico digital que esteja recebendo o número de 4 bits e retornar truese o número for 0, 7ou 14. Eu tenho apenas uma XORporta (2 entradas), uma NOR(3 entradas), uma NAND(2 entradas) e um decodificador de 3 a 8.

Eu acho que essa pergunta é insolúvel, não encontrei nenhuma combinação que possa fazer isso. Alguma idéia de como resolvê-lo?

digital-logic circuit-analysis logic-gates boolean-algebra nrofis
fonte

1

Como uma dica: dados 4 bits e um decodificador de 3-8, você deve tratar um dos bits de maneira diferente.

Brian Drummond

2

@BrianDrummond, mas eu já sei disso e ainda não consegui resolvê-lo. Toda solução que eu tentei sente que falta um portão OU. Eu não posso encontrado tal combinação com os portões dado que pode resolver o problema ... Note que eu tenho somente uma porta por tipo ...

nrofis

3

@BrianDrummond: se você postar uma descrição da solução que acha que existe, poderíamos verificar isso. É difícil dizer que não existe solução, mas é fácil verificar se uma solução é válida.

pasaba por aqui

2

@Ido Kessler ... Fiquei intrigado com a sua solução e, se a sua prova estiver correta, lamento que você a tenha excluído. Até agora, ninguém parece ter uma solução. Talvez se você incluísse uma descrição do seu algoritmo, isso melhoraria a resposta. Quão confiante você está de que está correto e sem erros?

Tut

3

@jalalipop, eu fiz ontem. Ido Kessler e pasaba por aqui estava certo, meu professor disse que a questão estava errado eo NAND deve ser NOR ....

nrofis

24

Eu escrevi um algoritmo em C # que tenta todas as combinações possíveis desses Nor 3->1 Xor 2->1 Nand 2->1e Decoder 3->8.

Depois de executá-lo por ~~7,5 milhões de anos e~~ 2 horas, retornou 42 Falso. Acredito que isso prova que a pergunta não tem resposta, pois esse algoritmo verifica todas as combinações possíveis. :)

Me pediram para descrevê-lo, então a próxima parte é uma explicação das partes do código, parte por parte. TL; DR - você pode simplesmente pular o código no final :)

Vamos falar sobre as linhas de entrada, elas têm 0 ou 1 estados e, para cada uma das entradas possíveis (0 a 15), possuem valores diferentes:

para a primeira linha, fica assim: 0 1 0 1 0 1 ... A segunda é: 0 0 1 1 0 0 1 1 ... a terceira: 0 0 0 0 1 1 1 1 .... como binária contando ... você teve a ideia: P

Então eu criei um objeto que representa cada linha em cada um de seus estados:

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

Como diz bitLine.IsActiveWhenInputIs [5], retorna se a linha estava ativa quando a entrada era 5.

Este é um código que cria as linhas de entrada completamente:

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

Também criaremos linhas de bits "sempre verdadeiras" e "sempre falsas" - para fornecer uma entrada constante "0" ou "1".

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

Agora, se você notar, o que estamos procurando é realmente um bitLine específico, verdadeiro quando a entrada é 0, 7, 14. Vamos representá-lo em nossa 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)
}

Isso tornou as coisas realmente simples: o que realmente estamos procurando é uma maneira de "forjar" este necessário BitLine a partir da linha de bits de entrada (é assim que eu represento ao meu programa o que eu quero que minha saída seja).

Agora, é assim que continuamos: toda vez que usamos algum elemento lógico em nossas bitLines Xor, como Nor, Nandou mesmo o Decoder, estamos realmente criando um novo bitLine \ s. Conhecemos o valor de cada uma das linhas em todas as entradas possíveis de 0 a 15, para que possamos calcular também o novo valor do bitLine em todas as entradas possíveis!

Nand Nor e Xor são todos diretos:

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 possível, representa como o novo BitLine atuará.

Manusear o decodificador é um pouco complicado, mas a idéia é "se os bits na entrada representam o número x em binário, a linha de bits da x-ésima saída será verdadeira, enquanto todos os outros serão falsos. Diferente da outra função, este obtém uma matriz de linhas de bits e adiciona 8 novas linhas de bits à 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);
        }
    }
}

Agora temos todos os nossos elementos básicos, então vamos falar sobre o algoritmo:

Vamos fazer um algoritmo recursivo, a cada profundidade ele tentará usar outros elementos (nem \ ne e xor \ decodificador) nas linhas de bits disponíveis no momento e, em seguida, definirá o elemento como inutilizável para a próxima profundidade recursiva. Sempre que chegarmos ao fundo e não tivermos mais elementos para usar, verificaremos se temos uma linha de bits que é o que estávamos procurando.

Esse código verifica, a qualquer momento, se o grupo atual de linhas contém a linha que estamos procurando:

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 é a função que ela usa para verificar se duas linhas são iguais:

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

Ok, agora a parte principal é o principal algoritmo:

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 função recebe uma lista dos bitLines disponíveis, o comprimento da lista, um booleano representando se cada elemento está disponível no momento (xor / nor / nand / decoder) e um bitLine representando o bitLine que estamos procurando.

Em cada estágio, ele verifica se temos mais elementos para usar, se não - verifica se arquivamos nossa linha de bits necessária.

Se ainda temos mais elementos, então para cada elemento ele chama uma função que deveria lidar com a criação de novas bitLines usando esses elementos e chamando a próxima profundidade recursiva posteriormente.

As próximas funções do manipulador são bem diretas, elas podem ser traduzidas para "escolher 2 \ 3 das linhas de bits disponíveis e combiná-las usando o elemento relevante. Em seguida, chame a próxima profundidade da recursão, só que desta vez não conterá este elemento! ".

essas são as funções:

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

E é isso, apenas chamamos essa função com a linha necessária que estamos procurando e verifica todas as combinações possíveis de peças elétricas para verificar se é possível combiná-las de tal maneira que, no final, uma única linha seja emitido com os valores necessários.

* observe que eu uso a mesma lista o tempo todo, portanto não precisarei criar novas instâncias de linhas de bit o tempo todo. Dou-lhe um buffer de 200 por esse motivo.

Este é o 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 desta vez seja uma explicação válida: P

Ido Kessler
fonte

6

Você pode incluir uma descrição de alto nível de como esse tipo de solucionador funciona. Não é imediatamente óbvio lendo este despejo de código totalmente descomentado.

Dave Tweed

2

Esta é uma solução intrigante e espero que você possa fornecer uma descrição do algoritmo. Você já fez casos de teste semelhantes para provar o método? (Aliás, gosto a referência subtil Douglas Adams)

TUT

2

Acrescentarei que tentei esse algoritmo com algum caso de teste para verificar: x == 2, x == 3, x == 4, ..., x == 11. Como demora muito para ser executado, percebo que os x% 3 == 0 e x% 5 == 0 também podem ser impossíveis, e não consegui encontrar uma resposta para os dois. Mas o algoritmo retornou verdadeiro para todos os casos acima, para os quais eu encontrei uma solução manualmente.

Ido Kessler

3

+1! @IdoKessler, você pode tentar alterar a NAND de entrada de 2 bits por uma NOR de entrada de 2 bits e verificar se o seu software fornece uma solução? De fato, com esse portão, em vez de um NAND, existe uma solução.

next-hack

3

@ próxima cortá-lo retornou True quando eu mudei para usar um 2-bit NOR

Ido Kessler

8

Esta é uma não resposta, para descartar a solução mais óbvia.

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

$b_2$ $b_4$

(nem {x = 0 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$ }, implementado com o decodificador 3-8.

No entanto, a simplificação da expressão anterior é:

(x = 0 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 )$

esse não é o esperado:

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

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

Por esse motivo, acho provável um erro na pergunta, sendo "nand" gate a "nem" one.

pasaba por aqui
fonte

2

Talvez seja verdade, também não encontrei resposta.

Nrofis 19/09

2

+1. Eu acredito que você está certo, e o NAND deve ser um NOR.

Brian Drummond

2

Uma resposta válida para sua pergunta seria qualquer circuito que retorne sempre verdadeiro. Porque ele retornará verdadeiro também se os números de entrada forem 0,7 ou 14.

Eu acho que a pergunta deveria pedir explicitamente um circuito que produza true se os números de entrada são 0,7 ou 14. E que gera false caso contrário.

Agustin Tena
fonte

2

Uau, eu não esperava essa resposta. O circuito deve retornar true se e somente se a entrada for 0, 7 ou 14 ...

nrofis

1

exatamente assim.

Agustin Tena

2

+1 para observar as especificações com cuidado. Isso é péssimo em engenharia ao obter essas especificações de um cliente. Nesse caso, a resposta certa é apontar o problema com as especificações para o cliente e verificar o que ele realmente deseja. Mas, para uma pergunta de exame, mostra o pensamento fora da caixa e fornece corretamente uma resposta muito simples.

21917 Olin Lathrop

-3

É factível. Como uma dica, os dois bits do meio são iguais para todos esses padrões de bits, portanto, a xorá-los produzirá 0, que poderá ser uma entrada para o decodificador com os outros dois bits. As portas restantes são aplicadas às três saídas do decodificador para fornecer a saída correta de bit único.

John
fonte

Já fiz isso. I não encontrou qualquer combinação que resolver a questão ...

nrofis

Use o xor para reduzir os quatro bits para três bits para o decodificador. O decodificador terá três saídas, que são 1 para os três padrões correspondentes. Nem os dois juntos e use o portão nand como um inversor.

John

4

@ John ... Sua solução produz 6 termos de produto (sem simplificação), 3 dos quais são inválidos. Em outras palavras, embora sua solução retorne verdadeiro para 0, 7 ou 14; ele também retorna verdadeiro para 1, 6 ou 8. #

197 Tut Tut

Circuito lógico digital - pergunta do exame

Respostas: