Universal Logic Gates (2015)
allaboutcircuits.com
Universal Logic Gates (2015)
1–10 of 38 posts
Re: Universal Logic Gates (2015)
#2This 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)
#3This 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)
#4This 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'd recommend reading Matrix Logic, by August Stern. It's an approach to logic using vectors, aka matrices. This article doesn't answer why the math works out such that some gates are universal, but Matrix Logic does.
Re: Universal Logic Gates (2015)
#5Of the 16 possible 2-input/1-output gates:
* 8 of them are linear, in that the output is A xor (B and X) xor (C and Y). Any combination of these can only ever generate linear combinations of their inputs, thus they cannot be universal.
* 6 of them are monotonic, in that X op Y * 4 gates (0, X, Y, 1) are both linear and monotonic.
* The 6 gates which are neither linear nor monotonic are universal.
Re: Universal Logic Gates (2015)
#6This 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
The monotone, linear, etc. functions are called clones and the clones form a lattice called Post's Lattice
https://en.wikipedia.org/wiki/Post%27s_lattice
Given several logic gates, if their most recent common ancestor in the lattice is the clone of all boolean functions, then that set is universal. This provides a convenient prescription for deciding universality for a new k-input gate.
Re: Universal Logic Gates (2015)
#7This 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.
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).
Re: Universal Logic Gates (2015)
#8This 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.
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)
#9This 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.
There's tons of universal logic gates outside of the 2 -> 1 domain.
Re: Universal Logic Gates (2015)
#10This 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.
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).