6

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?

Kevin Vermeer
  • 19,989
  • 8
  • 57
  • 102
Halst
  • 240
  • 2
  • 7
  • 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
  • 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 : http://en.wikipedia.org/wiki/Logic_synthesis – BarsMonster Jun 24 '11 at 11:48
  • 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 Answers3

4

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.

Aphaea
  • 251
  • 1
  • 5
  • 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 08:59
  • -1 doesn't address OP's actual question. – CyberMen Apr 26 '12 at 17:29
1

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.

Majenko
  • 55,955
  • 9
  • 105
  • 187
  • 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
  • @stevenvh hence 'often avoided' and not 'always avoided' – Majenko 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
  • @Halst I said ***programmable*** logic - FPGAs, etc. These rely on the genericicity (?) of the NAND (or NOR) gates to function. – Majenko Jun 24 '11 at 13:58
  • 2
    @Matt, that is also wrong. FPGAs are based on Logic Elements (See http://www.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
  • @halst hmmm.. things may have changed since I was trained then. I have dug out my old college text book - First published 1979, reprinted 1989... 74 logic was the big thing then ;) – Majenko Jun 24 '11 at 14:05
  • NOR is the exact same complexity as NAND. AND, OR, XOR do require more transistors. Even PALs (programmable array logic and PLA -- programmable logic array -- the simplest and earliest field-programmable devices) used a matrix of AND followed by a matrix of OR. And what's this "both" inputs. There's no rule limiting a NAND or NOR gate to just two inputs. – Ben Voigt Jun 24 '11 at 20:52
  • All right, pedant. I should rename you to Which Tyler. s/both/all/g – Majenko Jun 24 '11 at 20:54
  • 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 09:08
  • There is actually a distinction between AND and OR: the former uses a series of nMOS, while the latter uses a series of pMOS. Hence, because of the better performance of nMOS, NAND is usually more performant. – clabacchio Apr 26 '12 at 15:28
0

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.

CyberMen
  • 858
  • 9
  • 16