Design Feature: April 11, 1996

"Pure" Reed-Muller logic lets you implement certain functions using only XOR and XNOR gates (see "Hug an XOR gate today," EDN, March 1, 1996, pg 175). I have created a simple program that can examine truth tables, determine if they are suitable for a pure Reed-Muller implementation, and, if so, generate the appropriate Reed-Muller expression. This article examines this program and references areas in which you might wish to consider making improvements. (I wrote the program in C, and it should be compatible with any ANSI-standard C compiler.)

Consider the way the program "sees" the world. When inputting a truth table, the program first visualizes that table's contents in the form of a Karnaugh map and then projects those contents into an array of characters, called "workspace." One way to envision this projection is to imagine grabbing the upper corners of the Karnaugh map and pulling them out to the left and right, thereby unfolding the map like a concertina (Figure 1).

You use a standard binary index to address the elements of the workspace array, but you can also visualize them as having an alternative set of Karnaugh map addresses. This approach entails performing an address translation whenever you load data into or retrieve data from the array. Although this technique may seem cumbersome, the structure is actually quite cunning, because, in addition to facilitating the data processing, it also accommodates the fact that each truth table can support a number of alternative Karnaugh map representations. The beauty of that structure is that, regardless of how you visualize the Karnaugh map, its contents always map into exactly the same locations in the workspace. For example, you can view a three-input truth table as having a 234 or 432 Karnaugh map (Figure 2).

Gzins and gzouts

To use this program, which, by some strange quirk of fate is called "max_prog," you should first know what the program actually does. First, you create a text-file representation of one or more truth tables that you would like to examine, and then you run the program using this file as its input. In return, the program determines which truth tables are suitable for Reed-Muller implementations and returns the appropriate expressions. For example, consider the truth tables in Figure 3.

As you will see, the part of the program that reads the input file is rather simple; hence, the file's somewhat minimalist look. When you've created the input file, you run the program from the operating system's command line as follows:

As truth tables 1 and 2 are obviously those for an AND and an XOR, respectively, the results the program returns should come as no surprise. The program assumes that the inputs to the truth tables are named a, b, c, etc and that the output is named y. This version of the program can handle truth tables with as many as 10 inputs but only one output. You can easily increase the number of inputs and outputs if necessary.

The first part of the program simply declares anything that the program is going to use:

The program then declares the function that controls everything:

The variable num_tt, which keeps track of the number of the truth table being processed, is initialized with zero, and then the function load_lookup_tables() is called to initialize the look-up tables. The program then enters a loop.

The function get_truth_tables() loads the outputs from the first truth table into the working area. This function also returns the number of inputs for the truth table and assigns the value to the variable num_in. When get_truth_tables() returns a value of zero for the number of inputs, then all of the truth tables in the input file have been processed, and the program terminates. Otherwise, the first action in the loop is to increment num_tt, which keeps track of the number of the truth table that is being analyzed.

Once a truth table has been loaded, the function test_reed_muller() examines the table to determine if it has a Reed-Muller solution. If such a solution exists, then the function extract_reed_muller() determines which of the truth table's inputs are significant. The information on the significant inputs appears as a bit mask, which is assigned to the variable mask. Finally, the function output_reed_muller() displays the Reed-Muller equation. If only everything in life could be so simple. Two utility functions are called occasionally. One is as follows:

The get_binary_value() function accepts a pointer to a string of characters, such as 1001, which have been read from the input file and which represent a set of input values associated with a line from one of the truth tables. The function converts this string into the numerical value that they represent; for example, 1001=9. You also use the function to process a single 0 or 1 character representing an output value associated with a line in a truth table and to convert that value to its numerical 0 or 1 equivalent.

Loading look-up tables

The first interesting action that the main controlling routine performs is to call the function load_look-up_tables(), and it doesn't take a rocket scientist to guess what this one does.

The load_look-up_tables() function revolves around a loop, in which the variable bin is incremented from zero to the maximum number of elements in the tables. For each value of bin, its equivalent gray code is generated and assigned to the variable gray. Finally, the element in the bin_to_gray look-up table pointed to by bin is loaded with the value in gray, and the element in the gray_to_bin look-up table pointed to by gray is loaded with the value in bin. The statement "gray=bin (bin >>1)" is the software equivalent of a binary-to-gray-code converter, as the previous article discusses. (Note that "" "" is the XOR operator in C.)

Throughout the rest of this program, you can easily perform binary-to-gray-code and gray-code-to-binary conversions by accessing the appropriate value in the bin_to_gray and gray_to_bin look-up tables, respectively. For example, assume that you have already assigned an integer variable called "index" the equivalent of the binary value 11002:

Loading truth tables

After declaring everything and initializing the look-up tables, the program is ready to rock 'n' roll. The first function of any significance is get_truth_tables(), which loads the truth tables, one at a time, from the input file:

Functions that read in and write out data are generally rather boring, and this one is no exception. On the other hand, even though it is mean and lean, get_truth_tables() permits a reasonable amount of latitude, and it's worth taking the time to note its main features and limitations:

When you consider the size of this function, you can't really ask for too much more: What do you want for nothing—your money back? The function processes each line of a truth table and loads the output value associated with that line into the working area workspace[]. When the function detects a blank line indicating the end of the truth table, the function terminates and returns the number of inputs associated with this table to the main controlling loop.

The statement of most interest is "workspace [gray_to_bin[address]]=data;," which loads the output value into the workspace[]. This statement uses the gray-code-to-binary look-up table to transpose the address representing the truth table's input values into an address the computer uses to point to the working area and to load the output value from the truth table into the element in the working area pointed to by this transposed address. The organization of the working area is the key to the way in which the rest of the program works.

Testing for Reed-Muller

After all of the data from a truth table has been loaded into the working area, the function test_reed_muller() is called to determine whether this truth table has a Reed-Muller solution, as follows:

The test_reed_muller() function performs a series of actions (Figure 4).

In the case of a two-input truth table, the main loop first initializes bottom and top to point at locations 0 and 3, respectively, in the working area. The first actions are to perform an exclusive-OR of the contents of the working area pointed to by bottom and top and to store the result in the variable look_for. It doesn't matter whether the result stored in look_for is a 0 or a 1; whatever it is, that's what you're looking for. The values of bottom and top are then incremented and decremented, respectively, an exclusive-OR is performed on the contents of the working area that they are now pointing to, and the result is compared to the value stored in look_for.

If the result of this exclusive-OR is not the same as the value stored in look_for, then a Reed-Muller solution does not exist, and test_reed_muller() returns a 0 and terminates. But, if the result is the same as the value stored in look_for, then the function continues. In the case of a two-input truth table, all of the tests have been performed, so the function would return a 1 indicating that there is a Reed-Muller solution.

In the case of a three-input truth table, the first series of tests are exactly the same as for the two-input truth table. Assuming that the table passes these tests, the main loop reinitializes bottom and top to point at locations 0 and 7, respectively, in the working area. Again, the first action in this iteration of the loop is to perform an exclusive-OR of the contents of the working area pointed to by bottom and top and to store the result in look_for. Again, it doesn't matter whether the result stored in look_for is a 0 or a 1; whatever it is, that's what you're looking for this time.

The values of bottom and top are then incremented and decremented respectively, an exclusive-OR is performed on the contents of the working area that they are now pointing to, and the result is compared to the value stored in look_for. This procedure continues until it is determined that there is no Reed-Muller solution or until bottom and top meet in the middle, in which case there is a solution.

Similarly, in the case of a four-input truth table, the first series of tests would be the same as for a two-input table, and the second series of tests would be the same as for a three-input table. Assuming that the table passes these tests, the main loop would commence a third series of tests by reinitializing bottom and top to point at locations 0 and 15, respectively, in the working area.

On the positive side, if a Reed-Muller solution does not exist, then this function usually finds out quickly. If a solution does exist, then the function can take a lot of tests to prove it. In fact, an n-input truth table requires (2ⁿ-2) tests if the table has a solution. This situation is not ideal, but there does not appear to be a better way, unless you can think of one.

Assuming that a Reed-Muller solution exists, then you use the extract_reed_muller() function to determine the significant inputs.

The extract_reed_muller() function is the hardest to follow, but it is a good exercise in reverse-logic-lateral-thinking, which will keep your brain in peak mental fitness. Figure 5 shows the easiest way to visualize the east-west-south-north searches for the Karnaugh map associated with a four-input truth table.

The extract_reed_muller() function is reasonably efficient. One of the rules for a Reed-Muller solution is that there must be the same number of ones stored in the Karnaugh map boxes as there are zeros. This requirement means that the largest possible block of ones or zeros can occupy only half the boxes, which, in turn, means that this function performs relatively few tests. For a four-input truth table, this function always performs a maximum of only four tests (excluding the tests that determine whether any further tests are necessary).

Now it only remains to output the equation for the Reed-Muller implementation.

You can modify or extend this program in many ways. For example, you can easily modify the input function get_truth_tables() to accept truth tables with multiple outputs. Alternatively, you could augment the function to accept the textual equivalent of Karnaugh maps. A more interesting exercise would be to modify the program to accept don't-care values, which you represent with question marks, on the inputs. For those who enjoy a challenge, modify the program to cope with don't-cares on the outputs.

Another interesting area would be the test_reed_muller() function. Assuming that the table has a Reed-Muller solution, an n-input truth table requires (2ⁿ-2) tests. You may be able to discover a more efficient technique to determine whether the table has a solution. If you do, please let me know.

A question arises about why the maximum number of truth table inputs is set as high as 10. After all, this would equate to a truth table with 1024 lines, and there is little chance that anyone would take the time to type these in and even less chance of doing so without errors. However, one way in which you could modify the program would be to have it read in simple Boolean equations. If you start processing equations in this form, you can easily reach the 10-input limit.

Extending the program to accept Boolean equations is a large stride into the arena of logic synthesis. Many commercially available logic-synthesis utilities use a technique called binary decision diagrams (BDDs) to represent the data internally. In this method, equations are stored as decision trees. I have a back-burner project to see whether you can modify this program to "stroll around" a BDD and detect functions that would be amenable to "partial" Reed-Muller implementations. (Note that partial Reed-Muller implementations were discussed in the previous article.)

Please feel free to use this program in your own projects, and let me know if you come up with anything interesting. If you would like to play with this program, you can download the source code from my Web pages. Simply wander over to http://ro.com/~bebopbb and then root around under the area marked "free synthesis software and other goodies."

Author's biography

Clive "Max" Maxfield is a member of the technical staff at Intergraph Computer Systems, Huntsville, AL, where he gets to play with the company's high-performance graphics workstations (phone (800) 763-0242). In addition to writing numerous technical articles and papers, Maxfield is also the author of Bebop to the Boolean Boogie: An Unconventional Guide to Electronics (ISBN 1-878707-22-1). To order, phone (800) 247-6553. You can reach Maxfield via e-mail at crmaxfie@ingr.com.