The building blocks of the MUX Universal System are 3-Multiplexer gates (MUX, for short) and NOT (inverters). And with these two types of building blocks we can design any kind of logic circuit. As a simple example, here's a MUX circuit for the XOR function:
XOR(x,y)= MUX((!(x)),(!(y)),y)
The Go MUX Grammar of GeneXproTools defines not just the XOR function but all the 258 built-in logical functions in terms of MUX gates and NOT. This means that we can automatically convert all kinds of logic circuits to MUX circuits with this grammar.
MUX circuits are very popular, and the reason for their popularity is their compactness. In the remainder of this post I'll show you some simple examples to illustrate this claim.
For this exercise I had to choose a very simple function – the 3-Majority function – otherwise we would get huge circuits for some of the Universal Logical Systems I'll be using to make comparisons, namely, the NAND System and the NOR System.
Furthermore, I also decided on a very simple architecture of only 1 gene so that we could make more meaningful comparisons between the logical systems.
So let's start by designing a minimal logic circuit for the 3-Majority function using just NOT, AND, and OR:
func gepModel(d []bool) bool {
y := false
y = (((d[2] || d[1]) && d[0]) || (d[2] && d[1]))
return y
}
And now let's repeat the exercise separately for NAND and NOR gates:
The minimal NAND circuit:
func gepModel(d []bool) bool {
y := false
y = gepNand(gepNand(d[2],d[1]),gepNand(d[0],gepNand(gepNand(d[0],d[1]),
gepNand(d[2],d[0]))))
return y
}
func gepNand(x, y bool) bool {
return (!(x && y))
}
And the minimal NOR circuit:
func gepModel(d []bool) bool {
y := false
y = gepNor(gepNor(d[2],gepNor(gepNor(d[0],d[2]),gepNor(d[2],d[1]))),
gepNor(d[1],d[0]))
return y
}
func gepNor(x, y bool) bool {
return (!(x || y))
}
And finally, the minimal MUX circuit:
func gepModel(d []bool) bool {
y := false
y = gepMux(gepMux(d[0],d[2],d[1]),d[2],d[1])
return y
}
func gepMux(x, y, z bool) bool {
return (((!(x)) && y) || (x && z))
}
As you can see, compared to the NAND and NOR circuits, the MUX circuit is very compact with only 5 literals (in this case, it's the same number of literals we got for the NOT-AND-OR circuit).
This is of course just a simple exercise using a simple function and we are bound to get some variation with different functions, but overall the MUX System is considerably more compact than the NAND System and the NOR System. And we can further illustrate this with a different exercise by using the built-in universal systems of GeneXproTools (the NAND, NOR, and MUX systems) to automatically convert NOT-AND-OR circuits into NAND, NOR, or MUX circuits.
As an illustration let's use the minimal NOT-AND-OR circuit presented above with only 5 literals.
And now let's convert this circuit to NAND gates using the NAND Grammar of GeneXproTools:
func gepModel(d []bool) bool {
y := false
y = gepNand(gepNand(gepNand(gepNand(gepNand(gepNand(d[2],d[2]),
gepNand(d[1],d[1])),d[0]),gepNand(gepNand(gepNand(d[2],d[2]),
gepNand(d[1],d[1])),d[0])),gepNand(gepNand(gepNand(gepNand(d[2],d[2]),
gepNand(d[1],d[1])),d[0]),gepNand(gepNand(gepNand(d[2],d[2]),
gepNand(d[1],d[1])),d[0]))),gepNand(gepNand(gepNand(d[2],d[1]),
gepNand(d[2],d[1])),gepNand(gepNand(d[2],d[1]),gepNand(d[2],d[1]))))
return y
}
func gepNand(x, y bool) bool {
return (!(x && y))
}
As you can see, the NAND code explodes unceremoniously, going from 5 literals to 28.
And the same is true for the NOR System:
func gepModel(d []bool) bool {
y := false
y = gepNor(gepNor(gepNor(gepNor(gepNor(gepNor(d[2],d[1]),
gepNor(d[2],d[1])),gepNor(gepNor(d[2],d[1]),gepNor(d[2],d[1]))),
gepNor(d[0],d[0])),gepNor(gepNor(d[2],d[2]),gepNor(d[1],d[1]))),
gepNor(gepNor(gepNor(gepNor(gepNor(d[2],d[1]),gepNor(d[2],d[1])),
gepNor(gepNor(d[2],d[1]),gepNor(d[2],d[1]))),gepNor(d[0],d[0])),
gepNor(gepNor(d[2],d[2]),gepNor(d[1],d[1]))))
return y
}
func gepNor(x, y bool) bool {
return (!(x || y))
}
In this case we also ended up with 28 literals.
For the MUX System we get considerably shorter circuits (17 literals in this case):
func gepModel(d []bool) bool {
y := false
y = gepMux(gepMux(gepMux(d[2],d[1],d[2]),
gepMux(d[2],d[1],d[2]),d[0]),gepMux(d[2],d[2],d[1]),
gepMux(gepMux(d[2],d[1],d[2]),gepMux(d[2],d[1],d[2]),d[0]))
return y
}
func gepMux(x, y, z bool) bool {
return (((!(x)) && y) || (x && z))
}
In the next post I'll talk about yet another Universal Logical System – the popular and compact Reed-Muller System.
Comments
There are currently no comments on this article.
Comment
your_ip_is_blacklisted_by sbl.spamhaus.org