Tell me more ×
Electrical Engineering Stack Exchange is a question and answer site for electronics and electrical engineering professionals, students, and enthusiasts. It's 100% free, no registration required.
up vote 6 down vote favorite
1

I know how to simplify digital circuits using Karnaugh maps. However, the resulting circuits always consist of only not, and and or gates (basic Boolean algebra operators).

Often, by using other gates (xor, nor, xnor, nand, etc) you can get a simpler circuit.

What techniques can be used for this simplification?

share|improve this question
4  
So you want algorithm which is used by logic synthesising software. This topic is deadly complex and deadly expensive :-) You really want to start digging here : en.wikipedia.org/wiki/Logic_synthesis – BarsMonster Jun 24 '11 at 11:48
I didn't even think to question why we reduced them to what was easily comprehend-able by our brains. I wish I could upvote this more than once! This is a fantastic question. – Joel B Jun 24 '11 at 19:42
You can massage the output of the K-map to give NOR and NAND functions, using De Morgan – clabacchio♦ Apr 26 '12 at 15:29

3 Answers

up vote 4 down vote

If you want to go all the way down to transistor level to get a simpler circuit, there are more ways to simplify the circuit. For instance, using NMOS instead of CMOS lets you use a resistor instead of 2 PMOS transistors for a NAND gate, which might be worthwhile if you don't need a strong 1 and you're using discrete components.

Also, floating gate MOSFETs with multiple gate signals can be used to implement logic gates, and even multiple value logic, with very few devices.

You probably don't care about transistor level right now, but it's something you want to consider as some point. NOT, NAND, and NOR are the easiest (fewest transistors) to make in CMOS, so other gates are usually composed of these.

Side note: simplest isn't necessarily the best - you might want to even out path times to avoid glitching.

share|improve this answer
Thanks for the insight at the lower level! However, I wish logic gates were 'ideal' and not composed out of transistors :-). So your point could be rephrased as: before you know the IC technology (custom/semi-custom ASIC, FPGA, CPLD...) you don't have criteria for simplification :-) – Halst Jun 24 '11 at 14:16
@Halst, sometimes you have to roll with school and such to learn the concept of how things really work. Then they will make you use it at a real level. – Kortuk♦ Jun 25 '11 at 8:59
-1 doesn't address OP's actual question. – CyberMen Apr 26 '12 at 17:29
up vote 1 down vote

The basic unit of the logic circuit is the NAND gate. Most (if not all) programmable logic circuits use NAND gates internally. All the other gates can be made up of purely NAND gates:

  • A NOT gate is a NAND gate with all inputs tied together.
  • An AND gate is 2 NAND gates - 1 configured as NOT to invert the output
  • An OR gate is 3 NAND gates - 2 set configured as NOT to invert the inputs

NOR, XOR, etc use more gates and are often avoided as they're a 'less efficient use of resources'.

So really it depends on what you mean by a 'simpler' circuit. Is a simpler circuit one which uses less individual gates, or one which uses less types of gates? 100% efficiency could either be a single gate that does all you want, or it could be lots and lots and lots of just one type of gate.

share|improve this answer
1  
@Matt - "use more gates and are often avoided". I don't quite agree. If you want to compare two binary values for equality you simply need an XOR, there simply is no other solution. That's 4 NAND gates, yes, but there's nothing you can do about it. – stevenvh Jun 24 '11 at 12:59
3  
what you refer to is called 'universal gates', they are nand and nor. However it is a big misconception that most digital circuits are build on them. Real circuits always use whatever logic gates they need to have less of them. – Halst Jun 24 '11 at 13:53
1  
so, to be explicit, your answer is completely wrong in every point. – Halst Jun 24 '11 at 13:57
2  
@Matt, that is also wrong. FPGAs are based on Logic Elements (See altera.com/literature/hb/cyc3/cyc3_ciii51002.pdf) which usually consist of a register and a look-up-table that is basically a memory cell with 4 inputs and 1 output, which is used to create any logic gate (or several of them). – Halst Jun 24 '11 at 14:02
1  
@Matt, you are actually correct in spirit, but many are being lost in words. In most ICs and even building from discrete components, either NAND or NOR on their own are functionally complete. If you use just a NAND gate, which is 4 transistors, you can build an circuit. In reality, it all breaks down to transistors though and for every 2 transistors you can add a bit more "thought" to a gate. This is often done directly. Anyway, thought I would say something as you are not "wrong" and I think your point is worth thinking about. – Kortuk♦ Jun 25 '11 at 9:08
show 6 more comments
up vote 0 down vote

There are two things you are talking about:

1) xor gates are actually a simplification of a more sophisticated circuit. if you draw the K-map for xor logic you should get Xor = A'B + AB' at the transistor level, its a way its implemented. (+ is or, multiplication is and and ' is not)

2) To use nor/nand/xnor gates you need to use DeMorgans law.

Which states:

A'B' = (A+B)'

A'+B' = (AB)'

essentially: If you not a logic and/or it will either split or fuse (and turns to or) and the individual components are not-ed.

share|improve this answer
Your equation doesn't look right. (A+B)'A' + B' would always be true if B is false. But A'B' is only true if B is false and A is false. – The Photon Apr 26 '12 at 16:58
@ThePhoton Stackexchange sucks. Enter doesnt make proper line break. – CyberMen Apr 26 '12 at 17:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.