Some digital functions can be difficult to optimize if they are represented in the conventional sum-of-products or product-of-sums forms, 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 as illustrated in Figure 1 (note that it's common to use '^' characters in logical equations to indicate XOR functions; see also the related article on Karnaugh Maps).

Figure 1. A 2-input function suitable for Reed-Müller implementation.

Since the truth table shown in Figure 1 is easily recognizable as being that for an XOR function, it comes as no great surprise to find that implementing it as a single XOR gate is preferable to an implementation based on multiple AND, OR and NOT gates. A similar checkerboard pattern may apply to a three-input function as illustrated in Figure 2.

Figure 2. A 3-input function suitable for Reed-Müller implementation.

As XORs are both commutative [for example, (a ^ b) = (b ^ a)] and associative [ for example, (a ^ b) ^ c = a ^ (b ^ c)], it doesn’t matter which combinations of inputs are applied to the individual gates. The checkerboard pattern for a four-input function continues the theme as illustrated in Figure 3.

Figure 3. A 4-input function suitable for Reed-Müller implementation.

Larger checkerboard patterns involving groups of 0s and 1s also indicate functions suitable for a Reed-Müller implementation as illustrated in Figure 4.

Figure 4. Example functions suitable for Reed-Müller implementations.

Once you have recognized a checkerboard pattern, there is a quick “rule of thumb” for determining the variables to be used in the Reed-Müller implementation. Select any group of 0s or 1s and identify the significant and redundant variables, and then simply XOR the significant variables together (the significant variables are those whose values are the same for all of the boxes forming the group, while the redundant variables are those whose values vary between boxes).

Although we don’t bother entering logic 0 values into our Karnaugh maps, we know that any empty squares really contain 0s. As all of the checkerboard patterns we've considered this far include a logic 0 in the box in the upper left corner (corresponding to all of the inputs being logic 0), the resulting Reed-Müller implementations can be realized using only XORs. Having said this, any pair of XORs may be replaced with XNORs, the only requirement being that there is an even number of XNORs.

Alternatively, if the checkerboard pattern includes a logic 1 in the box in the upper left corner, the Reed-Müller implementation must contain an odd number of XNORs. Once again, it does not matter which combinations of inputs are applied to the individual XORs and XNORs as illustrated in Figure 5.

Figure 5. Example Reed-Müller implementations requiring XNOR gates.

Although these examples provide a very limited introduction to the concept of Reed-Müller logic, checkerboard Karnaugh Map patterns are easy to recognize and appear surprisingly often. Reed-Müller implementations are often appropriate for circuits performing arithmetic or encoding functions. (Note that example encoding and decoding functions suitable for Reed-Müller implementation are presented in the related article on Gray Codes.)

Note: See also my articles on Assertion-Level Logic and Positive vs Negative Logic.