Go Language: Reed-Muller System

Posted
Comments None

The Reed-Muller System is yet another popular and compact Universal Logical System (see the previous post "Go Language: MUX System" about another compact logical system) that uses exclusively NOT, AND, and XOR in the design of electronic circuits.

GeneXproTools implements the Reed-Muller System for all supported programming languages and here we'll take a look at the Reed-Muller Grammar for the Go language.

The Reed-Muller Grammar allows us to convert automatically any logic circuit into NOT-AND-XOR gates. And this is possible because GeneXproTools maps all its 258 built-in logical functions into NOT-AND-XOR. For example, we can create a Reed-Muller circuit for the 3-Majority function:

package gepModel

func gepModel(d []bool) bool {
    y := false

    y = ((d[1] && (d[0] != d[2])) != (d[0] && d[2]))

    return y
}

Now compare this minimal logic circuit with the minimal circuits that we designed for the other universal systems – the Boolean NOT-AND-OR System, the NAND System, the NOR System and the MUX System (they are all shown in the previous post).

As you can see, the NOT-AND-XOR circuit is among the most compact with just 5 literals (the same number of literals as the NOT-AND-OR System and MUX System).

And if we repeat the same exercise that we did in the previous post and convert the minimal Boolean NOT-AND-OR circuit to the Reed-Muller System using our new Go Reed-Muller Grammar, we get:

package gepModel

func gepModel(d []bool) bool {
    y := false

    y = (((((d[2] && (!(d[1]))) != d[1]) && d[0]) &&
        (!((d[2] && d[1])))) != (d[2] && d[1]))

    return y
}

This circuit is also very compact with just 8 literals (although this should not come as a surprise as we are only mapping the OR gate, which of course favors immensely this system; as a comparison, the NAND and NOR circuits both use 28 literals and the MUX circuit uses 17).

So, like we showed for the MUX System in the previous post, the Reed-Muller System is indeed very well suited for designing extremely compact logic circuits.

This ends our journey into Universal Logical Systems and the Go language. Next I'll talk briefly about the Boolean Grammars for the R language as we will be adding them to GeneXproTools with this mini-release "New Project: Cross-Validation, Var Importance & More".

Author

Comments

There are currently no comments on this article.

Comment

Enter your comment below. Fields marked * are required. You must preview your comment first before finally posting.





← Older Newer →