Digital Logic circuit - exam question

Question

I have a question from exam that I failed to solve:

I need to build a digital logic circuit that is receiving 4 bit number and return true if the number is 0, 7 or 14. I have only one XOR gate (2 inputs), one NOR(3 inputs), one NAND(2 inputs) and one 3-to-8 decoder.

I think that question is unsolvable, I didn't find any combination that can do that. Any idea how to solve it?

As a hint : given 4 bits and a 3-8 decoder, you have to treat one of the bits differently. — user16324, Commented Sep 18, 2017 at 11:28
@BrianDrummond but I already know that, and I still didn't succeed to solve it. Every solution that I tried feels that it missing one OR gate. I can't found such combination with the given gates that can solve the problem... Note that I have only ONE gate per type... — nrofis, Commented Sep 18, 2017 at 13:07
@BrianDrummond: if you post a description of the solution you think exists, we could verify it. It is difficult to say that no solution exists, but easy to verify if a solution is valid. — pasaba por aqui, Commented Sep 19, 2017 at 14:38
@Ido Kessler ... I was intrigued by your solution and if your proof is correct them I'm sorry you deleted it. No one so far seems to have a solution. Perhaps if you included a description of your algorithm, it would improve the answer. How confident are you that it is correct and bug-free? — Tut, Commented Sep 19, 2017 at 14:43
@jalalipop, I did yesterday. Ido Kessler and pasaba por aqui were right, my professor said that the question was wrong and the NAND should be NOR.... — nrofis, Commented Sep 26, 2017 at 14:24

Ido Kessler · Accepted Answer · 2017-09-21 23:33:17Z

I wrote an algorithm in C# that tries every possible combination of those Nor 3->1 Xor 2->1 Nand 2->1 and Decoder 3->8.

After running it for ~~7½ million years~~ 2 hours, it returned 42 False. I believe this prooves that the question has no answer as this algorithm check every possible combination. :)

I was asked to describe it, so the next part is an explanation of the parts of the code, part by part. TL;DR - you can just skip to the code down at the end :)

Let's talk about the input lines, they have either 0 or 1 states and for each of the possible inputs (0 to 15) they hold different values:

for the first line it looks like that: 0 1 0 1 0 1 ... The second is: 0 0 1 1 0 0 1 1... the third: 0 0 0 0 1 1 1 1 .... like binary counting... you got the idea :P

So I created an object that represents each line in each of his states:

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

As it say bitLine.IsActiveWhenInputIs[5] return whether the line was active when the input was 5.

This is a code that creates the input lines altogether:

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

We will create an "always true" and "always false" bit lines as well - to provide a constant "0" input or "1" input.

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

Now if you notice, what we are looking for is actually a specific bitLine, one that is true when the input is 0, 7, 14. Let's represent it in our class:

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

This made things really simple: what we are actually looking for is a way to "forge" this neededBitLine from the input bit line (this is how I represent to my program what I want my output to be).

Now, this is how we go on: every time we use some logical element on our bitLines like Xor,Nor,Nand or even the Decoder, we are actually creating a new bitLine\s. We know the value of each of the lines in every possible input from 0 to 15, so we can compute the new bitLine\s value in every possible input as well!

Nand Nor and Xor are all straightforward:

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

For each possible input, it represents how the new BitLine will act.

Handling the decoder is a little bit tricky, but the idea is "if the bits at the input represent the number x in binary, then the x-th output bit line will be true, while all the others will be false. Unlike the other function, this one gets an array of bitline, and add 8 new bitlines to the array.

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

Now we have all our basic elements, so let's talk about the algorithm:

We are going to do a recursive algorithm, at each depth it will try to use another elements (nor\nand\xor\decoder) on the currently available bitlines, and then set the element to unusable for the next recursive depth. Whenever we arrive at the bottom and we have no more elements to use, we will check whether we have a bitline that is what we were looking for.

This code check in any given time whether the current group of lines contains the line we are looking for:

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

This is the function it uses to check whether two lines are equal:

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

Ok, so now for the main part, this is the main algorithm:

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

This function receives a list of the available bitLines, the list length, a boolean representing whether each element is currently available (xor/nor/nand/decoder), and a bitLine representing the bitLine we are searching for.

At each stage, it checks if we have any more elements to use, if not - it checks whether we archive our needed bitline.

If we still have more elements, so for each element it calls a function that supposed to handle creating new bitLines using those elements and calling the next recuresive depth afterwards.

The next handler functions are all pretty straightforward, they can be translated to "choose 2\3 from the available bitlines, and combine them using the relevant element. Then call the next depth of the recursion, just that this time it won't contain this element!".

those are the functions:

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

And this is it, we just call this function with the needed line we are looking for, and it checks every possible combination of the electric parts to check whether it's possible to combine them in such a way that in the end a single line will be outputted with the needed values.

*notice that I use the same list all the time, so I won't need to create new bitlines instances all the time. I give it a buffer of 200 for that reason.

This is the complete 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();
        }
    }
}

Hope this time it is a valid explanation :P

You might want to include a high-level description of how this kind of solver works. It isn't immediately obvious from reading this entirely-uncommented code dump. — Dave Tweed, Commented Sep 21, 2017 at 12:50
This is an intriguing solution and I hope you can provide a description of the algorithm. Have you done any similar test cases to prove the method? (BTW, I like the subtle Douglas Adams reference) — Tut, Commented Sep 21, 2017 at 13:10
I will add that I tried this algorithm with some test case I could check: x==2, x==3, x==4, ... , x==11. As it take a long time to run I notice that the x%3==0 and x%5==0 might be impossible as well, and I couldn't find an answer to both of them. But the algorithm returned true for all the above cases for which I found a solution by hand. — Ido Kessler, Commented Sep 21, 2017 at 23:49
+1! @IdoKessler can you try changing the 2-bit input NAND with a 2-bit input NOR, and check if your software gives a solution? In fact, with that gate, instead of a NAND, there is a solution. — next-hack, Commented Sep 22, 2017 at 6:10
@next-hack it returned True when I changed it to use a 2-bit NOR — Ido Kessler, Commented Sep 22, 2017 at 8:44

pasaba por aqui · Accepted Answer · 2017-09-19 15:03:39Z

8

This is a non-answer, to discard the most obvious solution.

I will number bits by its weight: \$ b_1 \$, \$ b_2 \$, \$ b_4 \$ and \$ b_8 \$.

As bits \$ b_2 \$ and \$ b_4 \$ are equal in all the valid numbers, we could thing about implement the logic expression:

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

where x is { \$ b_1 \$, \$ b_4 \$, \$ b_8 \$ }, implemented with the 3-8 decoder.

However, the simplification of previous expression is:

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

that is not the expected:

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

For this reason, I think probable an error in the question, being "nand" gate a "nor" one.

edited Sep 19, 2017 at 15:03

answered Sep 19, 2017 at 13:56

pasaba por aqui

5933 silver badges22 bronze badges

2

\$\begingroup\$ Maybe that's true, I didn't find answer nither. \$\endgroup\$
– nrofis
Commented Sep 19, 2017 at 18:26
2

\$\begingroup\$ +1. I believe you're right, and the NAND should be a NOR. \$\endgroup\$
– user16324
Commented Sep 19, 2017 at 18:46

Add a comment |

Voltage Spike · Accepted Answer · 2017-09-19 17:54:53Z

2

A valid answer to your question would be any circuit that returns always true. Because it will return true also if the input numbers are 0,7, or 14.

I think the question should explicitly ask for a circuit that ouputs true if the input numbers are 0,7, or 14. And that outputs false otherwise.

edited Sep 19, 2017 at 17:54

Voltage Spike♦

88.8k49 gold badges90 silver badges234 bronze badges

answered Sep 19, 2017 at 17:02

Agustin Tena

1951 silver badge4 bronze badges

2

\$\begingroup\$ Wow, I didn't expect such answer. The circuit should return true if and only if the input is 0, 7 or 14... \$\endgroup\$
– nrofis
Commented Sep 19, 2017 at 18:22
1

\$\begingroup\$ exactly like that. \$\endgroup\$
– Agustin Tena
Commented Sep 20, 2017 at 8:38
2

\$\begingroup\$ +1 for looking at the specs carefully. This is bad engineering when getting such a spec from a customer. In that case, the right answer is to point out the problem with the spec to the customer and verify what they really want. But, for a exam question it shows thinking out of the box, and it correctly provides a very simple answer. \$\endgroup\$
– Olin Lathrop
Commented Sep 21, 2017 at 11:47

Add a comment |

John · Accepted Answer · 2017-09-19 18:19:08Z

-3

It is doable. As a hint the middle two bits are equal for all of these bit patterns so xoring them will produce 0 which can then be an input to the decoder with the other two bits. The remaining gates are applied to the three decoder outputs to provide the correct single bit output.

answered Sep 19, 2017 at 18:19

John

4702 silver badges5 bronze badges

\$\begingroup\$ Already done that. I didn't find any combination that solve the question... \$\endgroup\$
– nrofis
Commented Sep 19, 2017 at 18:24
\$\begingroup\$ Use the xor to reduce the four bits to three bits for the decoder. The decoder will have three outputs which are 1 for the three matching patterns. Nor them together and use the nand gate as an inverter. \$\endgroup\$
– John
Commented Sep 19, 2017 at 18:31
4

\$\begingroup\$ @John ... Your solution yields 6 product terms (unsimplified), 3 of which are invalid. In other words, although your solution returns true for 0, 7 or 14; it also returns true for 1, 6 or 8. \$\endgroup\$
– Tut
Commented Sep 19, 2017 at 19:02

Add a comment |

Stack Exchange Network

Digital Logic circuit - exam question

4 Answers 4

Your Answer

Not the answer you're looking for? Browse other questions tagged
digital-logic
circuit-analysis
logic-gates
boolean-algebra
or ask your own question.

Hot Network Questions

Digital Logic circuit - exam question

4 Answers 4

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged digital-logiccircuit-analysislogic-gatesboolean-algebra or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
digital-logic
circuit-analysis
logic-gates
boolean-algebra
or ask your own question.