# Request name of a 2-1 AOI gate F=A or ( A and B)

Discussion in 'Homework Help' started by cj3, Mar 9, 2012.

1. ### cj3 Thread Starter New Member

Mar 9, 2012
11
0
Request name of a 2-1 AOI gate F' = A or ( A and B).
Also, how many transistors to implement this?

Derivation:
F = A or ( B and C);
LET A = p, B = p, C = q
F = p OR ( p AND q)
LET p = A, q = B
F' = A or ( A and B)

F' is effectively the 4-bit logical connective known as Right Projection.

2. ### bertus Administrator

Apr 5, 2008
15,805
2,389
Hello,

I found this post in "the completed projects collection" forum.
In "the completed projects collection" forum posts will stay invisible.
I think this is more like a homework assignment, so I moved it here and made it visible.

Bertus

3. ### cj3 Thread Starter New Member

Mar 9, 2012
11
0
Please replace my question in a more noticeable place.

I am a mathematical logician, not a Double-E, so the question is not really a homework assignment but a question arising from from a research project.

Thank you.

4. ### Georacer Moderator

Nov 25, 2009
5,151
1,266
What do you mean by the phrase: "request name"? Can you elaborate?

I suggest you first simplify the expression using a Karnaugh map. You will discover that there is a redundancy in arguments.

5. ### cj3 Thread Starter New Member

Mar 9, 2012
11
0
"Request name" means an answer something such as AOI 1-1-2 and a name such as "AO" for "And-Or" (?).

What does the Karnaugh map look like? While a Kranaugh map is a truth or proof table, it is unclear what this particular one should look like.

Of course there is redundancy in the expression. Please simplify and give the resulting circuit or gate a name .

The second part of the question is how many transistors to effect the gate / circuit.

Note bene: this is not a homework assignment, so non definitive answers beg the questilon. Hence if you are not willing to answer the questions, then please allow another reader do so for the press of time.

Thank you.

Last edited: Mar 10, 2012
6. ### Ron H AAC Fanatic!

Apr 14, 2005
7,050
657
Does F' imply inversion? AOI implies inversion.
If there is no inversion, then a good name would be "wire".

7. ### cj3 Thread Starter New Member

Mar 9, 2012
11
0
F is the "F" in the double-e literature. It does not imply inversion to me. If the name is now "wire", then so what?

F = ( A and B) or A
F = ( A * B) + A = ??

8. ### Ron H AAC Fanatic!

Apr 14, 2005
7,050
657
F=A.
You say you are a mathematical logician. Did you not study Boolean logic?

9. ### Georacer Moderator

Nov 25, 2009
5,151
1,266
It might be the language barrier, but I still can't understand what you seek.

Some remarks:

In the electronics world, the ' mark denotes a logical inversion. So F' is equivalent to NOT(F).

You are not consistent to your notation: You write both F'=A or (A and B) and F=A or (A and B). Clarify which one is valid.

As RonH said, F=A' (according to the first line of your first post). Therefore you need to only build a CMOS inverter (2 transistors) to implement this expression. Can you handle that?

10. ### thatoneguy AAC Fanatic!

Feb 19, 2009
6,357
718
Both cases can be written as below in C programming language:

F=(A&B)|A

The result is logical OR of these two equations:
F=A&B
F=A

Roughly speaking, for masking several bits:
OR Masks bits to True
AND Masks bits to False

Truth Table ends up as so:

 A B X Reason 0 0 0 Nothing True 0 1 0 AND results in 0, and A is False 1 0 1 A&B=0, but "OR A" Masks result to True 1 1 1 Both statements are True

Invert X for F' (aka !F)

11. ### cj3 Thread Starter New Member

Mar 9, 2012
11
0
For F' [F-sharp or F-prime] read F. That was a typo.

12. ### cj3 Thread Starter New Member

Mar 9, 2012
11
0
Of course, G = A or ( A and B) = A, ie, the "wire" name is correct.

The expression of interest was mistaken, and the question was mis-stated for this forum. The question should read as:

What are the names for these two circuits, if any; and

How many transistors in which to implement, respectively, the following two different truth tables, with "a" as row major and "b" as column minor:

Truth table known as "c21":

ab 00 01 10 11
00 00 01 00 01
01 00 01 00 01
10 00 01 10 11
11 00 01 10 11

Truth table known as "c53":

ab 00 01 10 11
00 00 01 00 01
01 00 01 00 01
10 10 11 10 11
11 10 11 10 11

Thank you in advance.

Last edited: Mar 11, 2012
13. ### Georacer Moderator

Nov 25, 2009
5,151
1,266
I 'm not familiar with this truth table notation.

I recognize the A and B columns as input, but I don't understand what the next 8 columns represent. Why is there the binary count used as column numbering?

The norm I 'm used to is this one:

Of course, the output can be many bits long.

Ron H likes this.
14. ### cj3 Thread Starter New Member

Mar 9, 2012
11
0
In this bi-valent context, truth table = proof table = look up table (LUT).

Truth table known as "c21":

ab 00 01 10 11
00 00 01 00 01
01 00 01 00 01
10 00 01 10 11
11 00 01 10 11

This is read row major, column minor where in the logical expression "a" is the precedent term and "b" is the antecedent term", such as "a c21 b = result", eg, 10 c21 01 = 01.
Similarly, 11 c21 00 = 00

Truth table known as "c53":

ab 00 01 10 11
00 00 01 00 01
01 00 01 00 01
10 10 11 10 11
11 10 11 10 11

This is read row major, column minor where in the logical expression "a" is the precedent term and "b" is the antecedent term", such as"a c53 b = result", eg, 10 c53 01 = 11.
Similarly, 11 c53 00 = 10

The logical connectives c21 and c53 are not synmetrical (such as are AND, OR) but rather produce different results depending on the left- (Sinistro) or right-(Dextro) bit being processed.

For example, with 00 c21 10 = 00, ie ,the Sinistro bit 0y c21 1y = 0y.
However, with 00 c21 11 = 01, ie, the Dextro bit x0 c21 x1 = x1.
The Sinstro bit 0y c21 1y produces a zero 0y, but
the Dextro bit x0 c21 x1 produces a one x1.
This means the logical connective c21 is not symmetrical for left- and right-bit processing.

By contrast, a symmetrical logical connective such as AND is decimal 17 or binary 0001.0001 in the symmetrical form of xxxY.xxxY, but a nonsymmetrical logical connective such as c21 is decimal 21 or binary 0001.0101 in the nonsymmetrical form of xxxY.xYxY.

(The eight bits with a period as separator are derived for any of the 256 8-bit connectives from the template expression of "0011.0011 [put connective name here] 0101.0101 = result". This evaluates all left- and right-bit possibilities, and from the binary expression, the proof table or LUT may be numerically calculated on the fly or held in computer cache memory as a static look up table.)

Last edited: Mar 15, 2012
15. ### Georacer Moderator

Nov 25, 2009
5,151
1,266
I understand what you want to do now. My first answer to your question "How many transistors do I need" is: Many.

Binary circuits don't work with two-dimensional two tables. You have to first convert it to the form I presented in post #13.
You effectively have four bits of input and two bits of output. Is that clear why? Disregard the two numbers you have and treat your input as four, equivalent bits.

You have to build a truth table as the one I showed you that has 2^{input bits}=2^4=16 rows. Each row corresponds to a different combination of input bits.
At the right of each row, you will mark your output. The output is extracted from the function tables you provided.

At this point you will want to implement your functions. You have several options. You can use transistors, logic gates or a ROM.

For the first option, you first need to read the following:
The output has two bits. That means that you need two Boolean functions with four input variables to construct the output. You might know about Boolean logic already. You need to reduce the expression of those functions as much as possible.
One easy way is by using Karnaugh maps. You can Google them, or read a bit here: http://www.allaboutcircuits.com/vol_4/chpt_8/index.html

Next, you need to implement the actual CMOS circuit. I highly suggest the book CMOS VLSI by Weste/Harris, which describes this procedure very well. I might be able to dig up some other resources, if you can't find it in a library.

If you opt to use logic gate ICs, then you should identify the ones you need through the Boolean expression of the output.
For example, the function F=A OR (B AND C) requires one 2-input AND gate and one 2-input OR gate.

Finally, for the ROM implementation, which is very scalable, you can write the multi-bit result of your function into the corresponding address of the memory.
For example for the operation 01 c21 11 = 01, you should write the data "01" in the address "0111". Thus, each time you access that address, the correct result will be returned.

That's all I had to say, trying to keep it short.

If you want to proceed, I suggest you complete each step and post your work, so that we can check you as you go.

16. ### cj3 Thread Starter New Member

Mar 9, 2012
11
0
Thanks for taking the time to reply.

The three approaches suggested were:

1. Transistors: well, ultimately storing results via the transistors of an FPGA; CMOS is 4-transistors respectively for an AND and OR gate (AO); in a Vertix-7, 8-trans per AO means space for 8.5 * 10^8 such AOs.

2. Logic gates: I read are slower by a factor of 3 than ROM

3. ROM: I now plan to implement in the LUTs of an FPGA. On the high end, Vertex-7 has 8 * 6-LUTs. Because a 4-input LUT (4-LUT) is fracturable into two 2-input LUTs (2-LUT), the Vertix-7 arguably accommodates 24 such 2-LUTs. We only need one 2-LUT. Smaller FPGAs are cheaper, and the prototype in Vertex-5 should work as a scale down. We may use NI's costly LabVIEW, but it does not emit portable VHDL code, verily, VHDL code is suppressed altogether, which is not what we would like as Ada95 pro-jammers

We can be reached off-line from this forum at <snip> (no index page yet).

Last edited by a moderator: Mar 19, 2012
17. ### Georacer Moderator

Nov 25, 2009
5,151
1,266
Generally, help is encouraged to take place in a public forum, where future members can visit and others can cross-check results. We cannot stop you from exchanging PMs with other members, but the community isn't obliged or even motivated to help you in private.

18. ### cj3 Thread Starter New Member

Mar 9, 2012
11
0
Thank you for censoring my last post. I regret wasting your time, and especially mine.

19. ### Wendy Moderator

Mar 24, 2008
20,772
2,540
You may have notice we don't have advertisements here. This is not a coincidence. Professional spammers are dealt with promptly, and are banned for life. Many cases their IP is also banned.

So when we remove what is a different kind of spam, we ask your understanding. This site is here to use, not abuse. It isn't just about you.

Ditto on homework, we are not doing anyone a service being a homework service. This site is about teaching, which is helping you learn how to solve problems for yourself, not giving you the answers.

Every single person here is a volunteer. If you want a private tutor you will have to pay for the service. We do not do private tutoring here.

Judging from your comment when you reported this as abuse, you have missed many points of this site. It is open source, emphasis on open. You wish to learn, we want to teach, but it is done on our terms. Other people will be allowed to benefit from your experience, though this thread is yours, and yours alone. Politeness is a must though, when you expect help from strangers.