Bebop to the Boolean Boogie, 3rd Edition

Appendix C. Reed-Müller Logic

“But That’s Not Logical, Captain!”

Some digital functions can be difficult to optimize if they are represented in the conventional sum-of-products or product-of-sums forms,^[1] which are based on ANDs, ORs, NANDs, NORs, and NOTs. In certain cases it may be more appropriate to implement a function in a form known as Reed-Müller logic, which is based on XORs and XNORs. One indication as to whether a function is suitable for the Reed-Müller form of implementation is if that function’s Karnaugh Map displays a checkerboard pattern of 0s and 1s. Consider a familiar two-input function (Figure C.1).

¹ The concepts of sum-of-products and product-of-sums were introduced in Chapter 9: Boolean Algebra.

Figure C.1. 2-input ...