Comp Architecture, Karnaugh Maps : Mark me!

Emerson

Hey, well.. here I am repeating some of my exams and I'm trying to teach myself for the summer.
The maths forum seems to be the closest thing that relates to this so here goes:

Here's a question from my paper, I've followed it with my attempt at answering it.





So, anything wrong with what i've done? I haven't got any 5 variable K.map examples to compare it to..
Any suggestions welcome!

thx

cerebus

Looks like you've got your truth table (and resulting Karnaugh map) slightly wrong.

Here's what I work out as being the truth table for the function (A or xor (B and C):

A  B  C    X
0  0  0    0
0  0  1    0
0  1  0    1
0  1  1    0
1  0  0    1
1  0  1    1
1  1  0    1
1  1  1    0

As you can see, it is a slightly different to what you got. Lets take a look at the logical expression you are evaluating:

X is only true if either (A or or (B and C) are exclusively true. As an example, consider what we both got for 011 - you evaluated X to be 1, while I evaluated it to be 0.

In this case, (A or is true as A = 0, B = 1, so (A or = 1. (B and C) is also true as B = 1 and C = 1. As both (A or and (B and C) are true, X must be false (don't forget it is an exclusive-OR). The same is true for 110 - we get different answers there as well.

Secondly, your Karnaugh map is a little bit too complex. Don't forget you are working on an expression with three variables - A, B and C. The variables D and E are two things you are using yourself as 'helpers' to show you what (A + and (B and C) evaluate to. They should not show up in your Karnaugh map.

The Karnaugh map for the function should look like this

           AB
        \ 00  01  11  10
     C 0   0   1   1   1
       1   0   0   0   1

So by grouping into two sets you can work out that (here's hoping my code comes out right - expression should read (B and notC) or (A and notB))

      _     _
X = B.C + A.B

You can play around and try to reduce this down to something more simple if you feel like it. Already it has one advantage - there is no longer any XOR, which is a pretty expensive function in terms of transistors.

Just one aside on your answer to section (e) - don't forget, in your solution you still have to generate D and E from somewhere. You don't get them for free.

[size=-2]
[disclaimer] Any mistakes are intentional to see if you are paying attention [/disclaimer]
[/size]

Emerson

cerebus, you're a legend!
In future I will write "and" above . and "or" above +
I automatically get them mixed up no matter how many times I tell myself as + logically connects with the word and in my head

Fixed the truth table, keeping our imaginary D & E throughputs for clarity and dumped them in the Karnaugh Map (my god, the trouble I went to, trying to figure out a 5 input one!) and I got
_ _
X = B.C + A.B as you had calculated.

Interesting to read that XOR components are more expensive, will note that.

I'll use this thread if I encounter any more difficulties revising from now until the exam next month..

Yay.. really satisfied now. Really appreciate your help, thanks!

cerebus

Originally posted by Emerson
Interesting to read that XOR components are more expensive, will note that.

Actually, let me qualify that.

In standard CMOS logic XORs are expensive. For example, in a typical standard cell library that I have handy a 2-input low-drive XOR gate has 14 MOS devices. 2-input NAND/NOR gates in the same library have 4 transistors.

It is possible to build XORs with much fewer devices using pass transistors (and other funky circuit design styles), but in regular bog-standard logic they are expensive.

As an aside, it could be an idea to move this to the engineering forum rather than maths as it might be more suited.

Capt'n Midnight

You should also take into account propogation delay.
eg: if your XOR gates are made from other gates the circuit will be slower. - Always found it amazing that the carry look ahead adder can add two n-bit numbers with just four layers of gates

Not really applicable in this case but for larger diagrams you can use overlaps to reduce glitchs due to state changes.