Logic 101 - Part 3 - Reed-Muller Logic

Part 1 – Assertion-Level Logic
Part 2 – Positive vs Negative Logic
Part 3 – Reed-Müller Logic
Part 4 – Gray Codes

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 shown in Fig 1 (note that '&' represents a logical AND, '|' a logical OR, '^' an XOR, and '!' a negation or NOT function).

1. Two-input function suitable for a Reed-Müller implementation.

Since the above truth table 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 may be preferable to an implementation based on multiple AND, OR and NOT gates. A similar checkerboard pattern may apply to a three-input function (Fig 2).

2. Three-input function suitable for a 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 (Fig 3).

3. Four-input function suitable for a Reed-Müller implementation.

Larger checkerboard patterns involving groups of 0s and 1s also indicate functions suitable for a Reed-Müller implementation (Fig 4).

4. Additional functions suitable for a Reed-Müller implementation.

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).

As all of the checkerboard patterns shown in the above illustrations 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. However, 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.

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 (see also Part 4 of this mini-series).

Clive "Max" Maxfield is president of TechBites Interactive, a marketing consultancy firm specializing in high technology. Max is the author and co-author of a number of books, including Bebop to the Boolean Boogie (An Unconventional Guide to Electronics), The Design Warrior's Guide to FPGAs (Devices, Tools, and Flows), and How Computers Do Math featuring the pedagogical and phantasmagorical virtual DIY Calculator.

Widely regarded as being an expert in all aspects of computing and electronics (at least by his mother), Max was once referred to as "an industry notable" and a "semiconductor design expert" by someone famous who wasn't prompted, coerced, or remunerated in any way. Max can be reached at max@techbites.com.