|
Abstract
comKarnaugh is a Java program which is meant to calculate the coordinates of an input Boolean expression on a Karnaugh Map by presenting the correct function to the user. This paper presents the calculator functions, design limitations, the previous work available in boolean calculators, and future design and functional values for the calculator itself.
Students of logic and computer architecture often have presented to them problems in boolean algebra. Such problems can be difficult for students to learn to solve. Of notice is the lack of boolean calculators, that is, software that can take as an input an expression in boolean algebra and return a truth table on that expression. This is especially odd as all binary computers can be described by boolean algebra, so a class on architecture is, in some sense, a class on creating manipulations of boolean algebra.
1
A boolean calculator is much simpler than a standard calculator in a number of ways. First, boolean expressions can be broken down into only two values, true and false. Second, all boolean operators are equally weighted, there are no precedence rules. Operators are evaluated from left to right, although expressions within parentheses must be evaluated as blocks. Finally, there are fewer operators in boolean algebra.
However, there are ways in which a boolean calculator is more complicated than a standard calculator. First, there is the flexibility of input. A boolean calculator accepts abstract symbols, such as ‘A' or ‘X' and assigns to them true/false values, which it operates on. A typical calculator, implemented in software, takes as input symbols numbers, and operates on numbers. Second, a mathematical function takes an input and returns a single output. A boolean calculator takes a function as an input and returns all possible values for a function of that form, given all possible values for its member symbols.
The Karnaugh map, or K-map is a graphical interpretation of the truth table for a Boolean function. Given a range of truth values, the Karnaugh map presents those values in way that allows for simple reduction to a cardinal expression with that truth table. Karnaugh maps are useful as ways to reduce a boolean function to the minimum expression necessary to express a desired truth table.
There is therefore some utility in an application that could, given a particular truth table, produce the corresponding K-Map for that truth table. This is done by mapping a truth table to a two dimensional grid and marking the minterms where the function is true. The next figure shows a K-Map in 2 terms. Such a map provides the user with a quick way to simplify Boolean expressions to their basic forms.
The comKarnaugh application does not produce K-Maps, although that is in its implementation future. Instead, it is used to produce the ∑functions that can be used to generate K-Maps. In forming this crucial step between a Boolean expression and the corresponding K-Map, comKarnaugh provides a valuable tool for working with Boolean expressions.
The application is written in Java and broken down into three classes, the Karnaugh calculator, the Karnaugh parser, and the front end GUI. The calculator class receives a string from the GUI and passes it to the parser. The parser checks the string for well-formedness, and generates a postfix string from the original string.
For example, the following string S, (A*B!)+(B*C!) is a
well formed string. The ! operator is used after the operand it is meant to
modify, and all operations must be explicitly declared, AB will not be
received as a well formed string, but A*B will. If Karnaugh calculator
receives string S, it will first check whether it is well formed.
Finding that it is a well formed string, the parser will generate a postfix
string S': AB!*BC!*+. Other information extracted from
S by the parser includes the number of unique operands in the
string, and a hash table which places them in order. In this case, the hash
table would map A:0, B:1, C:2.
The calculator takes the number of keys, k and generates a table
size from them by calculating 2k. This integer forms the
upper bound of an iterative function call which generates a true/false value
based on a row of a truth table and the string S'. The true of this
function call is placed into a vector, in our example the function
runCalc(i) would be called 8 times and return true on calls 2,
4, 5, & 6, so the vector would contain {2,4,5,6}.
When the runCalc call is made, the number i is used to generate
an appropriate truth table row. In the example with 3 input variables, each
call to FindTruth returns an array of 3 boolean values, indexed
to match the values in the hash table from the parser. The calculator can
therefore easily map from the string input to boolean values, regardless of
which symbols are input into the calculator-any value from a-Z can be used
as an operand, and there is technically support for functions of up to 52
variables. The GUI does not have presentation space for more than 5 variable
output strings, however.
From the user perspective, a well formed string in input into the text box, a button is clicked, and an appropriate function produced.
As far as a test series of inputs has been able to reveal, the calculator is stable and accurate. Illegal strings are recognized and rejected, and legal strings produce the correct ∑functions. The major problems with the Karnaugh calculator are limitations of functionality and presentation.
First, the output panel is not independently resizable, leading to limits in the number of input parameters that can usefully be evaluated. Although technically the calculator can take inputs of up to 52 variables, it can only display about 5. Second, the calculator should produce actual K-Maps, rather than just the functions. This would meet all the design goals for the first generation program.
The Karnaugh calculator will be released as an open source project under the Gnu Public License (or a creative commons equivalent), along with instructions for use and an object description within the next few months. Enhancements that would improve the calculator immensely would be a simplification function that identifies groups in the K-Map and suggests a simplified boolean function, and also an ability to show both K-Maps and a simplified function in both sum-of-products and product-of-sums forms. These functions should be relatively simple to add to the calculator as an outgrowth of the necessary work on the GUI prior to release.
As a future project, it would be interesting to incorporate some boolean algebra simplification rules into the calculator, to address inputs where the K-Map itself is too large to produce useful information. This would add a function to the calculator. However, it would probably be simplest to still reduce the equation to sum-of-products form, so that the form of the equation to be reduced would be known ahead of time. This would greatly simplify writing the rules for reducing the equation further. This would also leverage the existing parser and calculator.
Modifying the parser to accept a wider range of logic functions would also be interesting. Design questions here are whether it is simpler to convert NAND and NOR functions to !, *, and + in the parser, or add those functions to the calculator. And while NAND and NOR gates present little real trouble to the design of the calculator, the interpretation of exclusive-or and exclusive-nor functions might represent a real change in operation that would present a significant challenge.
Because any single output circuit can be represented by a boolean expression, the core classes, the calculator and the parser, represent an excellent platform for future development of simulators of such simple circuits. Because the calculator function itself also takes a truth table row as an input, it implicitly will take as an input a set 1/0 inputs into a virtual circuit of arbitrary complexity.
In order to extend the calculator to more advanced use, a number of changes would have to be made. If the level of abstraction is very high, that is, the user is conceptualizing the circuits from text input, the only changes that would be required would be to have an additional input field for the values that the user wishes to test against. At a lower level of abstraction, the creation of a GUI allowing the visual construction of circuits and input values would be needed. However, once these items were in place, the calculator could easily be used to show equivalence between various circuits and input functions, and even to simplify circuits.
Working from that level, a logical next step would be to create the ability to establish multiple outputs, in effect, reversing the calculator from its current use of multiple input values into a single circuit, and instead calculating single input values into multiple, or complex, circuits.
If the latter stage could be combined with the ability to save and abstract such constructions, than the calculator could be used to build quite complex circuits. There is no particular reason it should not be able to mimic a simple mechanical calculator, given multiple inputs and outputs, it should be quite possible, if extremely tedious, to construct a circuit which multiplies two numbers together.
If the system were modified slightly at this point to allow blocks to save their previous state, so that hitting the return key mimics the ticking of the system clock, the user becomes capable of constructing a complete virtual computer using the boolean calculator as its primary means of calculation. Add to this the ability to save diagrams and load initial conditions, and the k-Map builder becomes a rich, open source platform for the construction of virtual circuits and instruction sets and might be of real value in the pedagogy of computer architecture.
For example, if we can build blocks that retain state out of arbitrary boolean functions, then we can construct flip-flops. The state is easily represented as an additional truth value to be input into the block. A multiplexer can be constructed from NOT, AND, and OR gates. A register can be constructed from flip-flops, and a bus system built from registers and multiplexers.
2 So we can build a bus system using the modified calculator.
The primary advantage of this open-K platform would be that instead of being a virtual computer, it would be a real computer built out of virtual circuits. That is, in theory, the behavior of a computer built on this platform would be identical to the behavior of a computer built using the circuit diagram at the core of the simulated computer. Students would have the opportunity to build circuits from the ground up or examine the inner workings of circuits that had been built by others in the past, for example “zooming in” to a multiplexer to see how it works. And while their are many projects that examine particular issues in computer architecture, such as animations of memory access, none of them are modeled on a real machine, so none of them allow the user to determine what level of the computer they are interested in, or allow the user to alter the workings of the simulation.
The open-K architecture would solve that problem, providing a single platform for addressing issues from the extremely simple, such as the construction of a single J/K flip-flop, to the very complex, such as the construction of a floating point co-processor for an existing architecture. In todays academic environment, it would be as close a student could get to burning their own circuit boards.
Created 15 January 2006
