f(x)=x^2+x+1 and x values between 0 to 4

[nafri]

hi every one ı want to design f(x)=x^2+x+1 and x values between 0 to 4 with logic gates. how can ı design this

 

[KeepItSimpleStupid]

I believe you can do it using the Karnaugh Map. The technique is here: https://en.wikipedia.org/wiki/Karnaugh_map

I'm WAY too rusty.

 

[MrAl]

Hi,

This is an unusually simple problem because the input range is so limited and so the output is very limited too.

The best way to approach this is probably to simply write out all the possible input logic states in one column and follow that by their equivalent output states. This will create a list of 1's and 0's you can examine by eye. Since the number of input states is so limited you can see patterns right away that would lead to a set of simple gates.
Start by trying to figure out what would be the simplest way to generate bit 0 of the output, then how to generate bit 1, then 2, etc. You'll see how simple this gets right away.

I'll give you one example and one hint...

In the following, bit 0 is the least significant bit, bit 1 is next, etc. So for the bit pattern 001 bit 0 is a 1 and bit 1 and bit 2 are both zeros.

Hint 1: The output is always odd, so this affects bit 0 quite simply.

Example 1: The output bit 1 is only high (a '1') when input bits 0 and 1 are EITHER 1 or 0, but NOT BOTH a 1 AND a 0. This means bit 1 can be generated with a two input exclusive OR gate.

You should examine the other bits in the same way and you should find simple gates to generate the desired results.

Overall the problem can be solved using a maximum of three common logic gates.

 

[nafri]

ok ı see but how can ı think with truth table of this circuit and ı have 3 input but ı have lots of output when we think x=4 our f(x)=21 and our output for 4 is like a 10101how can we use this at truth table and karnough map

 

[KeepItSimpleStupid]

remember that you have 3 bits as input with 16 one bit outputs. You may be able to consider the values of 5,6 and 7 as don't cares.

You can try writing the equations for each output, then collect the common terms in each equation. The don't cares could further minimize the design. eg 5,6 and 7 could have a 0 or 1 output arbitrarily.

 

[KeepItSimpleStupid]

bit 0 out = to bit 0 in by inspection. It probably forces the output for 5 and 7 to be 1 defining your first dont care condtion.

 

[MrAl]

ok ı see but how can ı think with truth table of this circuit and ı have 3 input but ı have lots of output when we think x=4 our f(x)=21 and our output for 4 is like a 10101how can we use this at truth table and karnough map

Hi again,

You first have to write out the truth table:

000  00001
001  00011
010  00111
011  01101
100  10101

and i'll label the bits:

210  43210 (input and output bit enumerations)
000  00001
001  00011
010  00111
011  01101
100  10101

From the above you can see we have an extremely small entropy, which probably means a very simple solution.
The easiest way to think about this is in terms of each output bit, taken alone without the other output bits. The reason for this is because the decision making for any bit will required one decision making element such as a gate, or possibly even simpler.

Lets start by looking at ONLY the zeroth bit of the output:

210  0 (bit enumerations)
000  1
001  1
010  1
011  1
100  1

From the above, we see that the zeroth bit of the output is ALWAYS a '1', regardless what the input is. This means we dont even need a gate for bit 0, we can wire that directly to the high logic level supply voltage (in theory). Thus the zeroth output bit becomes simply a wire to the supply voltage and no gate is required.

Now lets do the next output bit, the bit 1 of the output:

210  1 (bit enumerations)
000  0
001  1
010  1
011  0
100  0

From the above we can see that the output (bit 1) is a '1' ONLY when either bit 1 is a '1' and bit 0 is a '0', or vice versa, and is a '0' only when either bit 1 and bit 0 are both 1's or both 0's, and that function is accomplished by use of an exclusive OR gate, and that completely characterizes that one bit perfectly without the need to consider any other input bits. So now we've done bit 0 and bit 1 of the output. You would do the other bits the same way.

We'll skip now to the last bit (bit 4) of the output and you can do the other bits yourself...

210  4 (bit enumerations)
000  0
001  0
010  0
011  0
100  1

From the above we can see that the only time we get a '1' for the output is when the bit 2 of the input is high (a '1'), and that is enough to completely characterize the output bit 4 without considering any other bits. Thus, we wire bit 2 of the input directly to bit 4 of the output (or if you prefer, through a buffer). This also does not required a logic gate (unless you want a buffer).

So already we've reduced two of the bits to a direct wiring, and the other three bits required logic gates one of which we've already figured out, so now you should be able to figure out the other two required logic gates by following the same method as shown for the other output bit that needed a logic gate.

See if you can take it from here.

 

[KeepItSimpleStupid]

Sorry about the bit 0 thing. I based it on what was said earlier, not what is now verified as incorrect.

 

[kubeek]

hi every one ı want to design f(x)=x^2+x+1 and x values between 0 to 4 with logic gates. how can ı design this

Is this supposed to be done in whole numbers, modular arithemetics, one bit binary or something else?
For example 3^2+3+1=13, but in modulo 4 arithmetics it equals 1. This will change how to calculate the result.