This article shows more universal gates than the NAND and NOR that are usually discussed. Are any Hacker News users knowledgeable about the topic? Because I was wondering why I never heard about these universal gates before. Almost always, only NAND and NOR are discussed.
Universal Logic Gates (2015)
11–20 of 38 posts
Re: Universal Logic Gates (2015)
#12Earlier quoted context omitted.
Personally, I don't find them that interesting. AND, OR, NAND, and NOR are all non-linear. However, you can implement any logic function with XOR and AND, which is essentially modulo-2 addition and multiply. So the whole world of GF(2) algebra applies, and that is how error correction and encryption are analyzed. Goest thou, and study GF(2).
Xors are slow and expensive . That’s why all you see is nand and nor. This article doesn’t really make much sense. Nobody designs at this level except for understanding and abstraction.
Re: Universal Logic Gates (2015)
#13This article shows more universal gates than the NAND and NOR that are usually discussed. Are any Hacker News users knowledgeable about the topic? Because I was wondering why I never heard about these universal gates before. Almost always, only NAND and NOR are discussed.
Re: Universal Logic Gates (2015)
#14This article shows more universal gates than the NAND and NOR that are usually discussed. Are any Hacker News users knowledgeable about the topic? Because I was wondering why I never heard about these universal gates before. Almost always, only NAND and NOR are discussed.
I would guess that NAND and NOR might better lend themselves to practical physical implementation. Also: If you don't limit yourself to 2-input/1-output gates, there's loads more universal gates. Many 3-in/3-out reversible gates are universal [1]. I really have a soft spot for the Fredkin, it just seems so elegant. [1] http://www.thefullwiki.org/Three-input_universal_logic_gate
Re: Universal Logic Gates (2015)
#15This article shows more universal gates than the NAND and NOR that are usually discussed. Are any Hacker News users knowledgeable about the topic? Because I was wondering why I never heard about these universal gates before. Almost always, only NAND and NOR are discussed.
I would guess that NAND and NOR might better lend themselves to practical physical implementation. Also: If you don't limit yourself to 2-input/1-output gates, there's loads more universal gates. Many 3-in/3-out reversible gates are universal [1]. I really have a soft spot for the Fredkin, it just seems so elegant. [1] http://www.thefullwiki.org/Three-input_universal_logic_gate
I agree. It’s so simple, yet it easily leads to other seeminly-more-complicated gates, simply by ignoring some of the inputs or outputs.
Plus it has the feature that the # of on inputs always equals the # of on outputs. And the feature that it’s reversible. Really a cool gate all around.
Re: Universal Logic Gates (2015)
#16Earlier quoted context omitted.
Personally, I don't find them that interesting. AND, OR, NAND, and NOR are all non-linear. However, you can implement any logic function with XOR and AND, which is essentially modulo-2 addition and multiply. So the whole world of GF(2) algebra applies, and that is how error correction and encryption are analyzed. Goest thou, and study GF(2).
Xors are slow and expensive . That’s why all you see is nand and nor. This article doesn’t really make much sense. Nobody designs at this level except for understanding and abstraction.
Even if in theory you can make any logic gate from a combination of NAND or NOR gates, the XOR gate is almost never done so.
In most logic circuit families, including in the most popular families, i.e. TTL and CMOS, there are special circuits for implementing XOR, which are better than a NAND or NOR combination.
Also, in most logic circuit families, including in the most popular families, i.e. TTL and CMOS, even if you can implement NAND with NOR and NOR with NAND, this is not done so, but there are distinct circuits for NAND and NOR.
In conclusion, in most logic circuit families you do not implement everything with a single kind of universal gate, but you have 3 kinds of basic blocks, NAND, NOR and XOR.
In certain logic families you have extra basic blocks, which can be implemented in a better way than the equivalent schematic made of universal gates.
Moreover, even if TTL circuits are usually presented as being composed of NAND gates, it is more useful to view the NAND TTL or DTL gate as an AND gate (a minimum-computing circuit made with diodes) followed by an inverter made with a transistor (which can be expanded to a NOR gate by adding parallel transistors).
So the real basic blocks of TTL circuits are AND, NOR and XOR (the NOR being not the same as the NOR from the NAND+NOR+XOR description, but a sub-circuit of that), but these simpler AND and NOR blocks cannot be used by themselves, because the AND does not have TTL output levels and the NOR does not have TTL input levels, so you always must have an AND (possibly reduced to a repeater) followed by a NOR (possibly reduced to an inverter), to make a complete TTL gate.
My point is that while it is useful to know that any gate can be implemented using only a single kind of universal gate, such implementations are not efficient and you must use a small number of basic blocks, not only one.
On the other hand, when you want to understand the theory of logic gates, basing them on one kind of universal gate is also no useful.
You can better understand logic operations when you see them as based on minimum (or the equivalent maximum) and on inversion (for values between 0 and 1 inversion is 1-x, for values between -1 and 1 inversion is -x). These 2 operations are also valid when applied to non-binary logic values. The physical implementation of these 2 operations can actually work with real-valued inputs and outputs.
An alternative view for the binary logic case is that mentioned by someone above, of having addition & multiplication modulo 2 as the basic operations.
Either the minimum/inversion view or the addition/multiplication view give much more insight than reasoning about NAND or NOR, which just combine the 2 basic operations in such a way that a cascade of the combinations can recover each of the basic operations, so they provide an alternative.
Re: Universal Logic Gates (2015)
#17Re: Universal Logic Gates (2015)
#18Earlier quoted context omitted.
Personally, I don't find them that interesting. AND, OR, NAND, and NOR are all non-linear. However, you can implement any logic function with XOR and AND, which is essentially modulo-2 addition and multiply. So the whole world of GF(2) algebra applies, and that is how error correction and encryption are analyzed. Goest thou, and study GF(2).
You don't need XOR and AND. You ONLY need NAND (or NOR). NAND/NOR are universal in that they can single handedly construct all other gates. XOR and AND is not a minimal construction. This is well below the level of understanding to get to GF(2).
Re: Universal Logic Gates (2015)
#19Earlier quoted context omitted.
Personally, I don't find them that interesting. AND, OR, NAND, and NOR are all non-linear. However, you can implement any logic function with XOR and AND, which is essentially modulo-2 addition and multiply. So the whole world of GF(2) algebra applies, and that is how error correction and encryption are analyzed. Goest thou, and study GF(2).
You don't need XOR and AND. You ONLY need NAND (or NOR). NAND/NOR are universal in that they can single handedly construct all other gates. XOR and AND is not a minimal construction. This is well below the level of understanding to get to GF(2).
The following 4 sets of logic operations (and many others) are minimal: 1. AND, NOT 2. AND, XOR 3. NAND 4. NOR
So AND + XOR is a minimal set, because you can make NOT from a XOR where one input is true.
Re: Universal Logic Gates (2015)
#20Earlier quoted context omitted.
You don't need XOR and AND. You ONLY need NAND (or NOR). NAND/NOR are universal in that they can single handedly construct all other gates. XOR and AND is not a minimal construction. This is well below the level of understanding to get to GF(2).
See my answer above. Even if a single universal gate is enough if you disregard speed and cost (area and power consumption) when you implement physical logic circuits speed and cost are essential so you cannot use a single type of universal gate but you must use a small number of basic gates, because each of them has a better implementation from diodes and transistors than an implementation made as a cascade of a sin…
They're entirely different levels of abstraction.
https://en.wikipedia.org/wiki/Functional_completeness This line in particular: "In digital electronics terminology, the binary NAND gate and the binary NOR gate are the only binary universal logic gates."
Saying that insight isn't useful (that you can reduce any Boolean equation to a single universal gate) - when it is a cornerstone in modern equivalence checking, Boolean SAT solving, and minimization of combinatorial equations) is really, really missing some very key things...
It is the kind of fundamental cornerstone that allows modern digital computers to even exist.