The Visual Optimization of Circuitry

BC: CS092 / PS392 / FA294

Paul Kennedy, 9 Dec 2008

An Introduction:
This project encompasses several aspects of the Computer Science world, with traditions dating back prior to the inventions of computers themselves. The theory of Boolean algebra, which is the basis for all computing, dates back to George Boole in the 1830's. (1, p32) Boolean algebra is study of true - false statements based on a limited number of inputs. While Boolean algebra originally looked much like algebra using normal base 10 numbers which had had the operations replaced with boolean operators, today it is also often represented as a logic diagram, or what most people would recognize as a circuit. In the standard course of study, a student will learn Boolean algebra as a precursor to any kind of Computer Organization or Computer Architecture course (in essence the study of the low level hardware in a computer.) Thus, any individual studying logic diagrams will be doing so with a firm base in the use of Boolean algebra. This equivalence between boolean algrebra and its physical representation on a circuit board, is in essence the basis of all Computer Science.

The Two Problems:
During my study of Boolean Algebra and more specifically its application to logic diagrams, I came across two problems that would require visual solutions, or optimizations.
1.) First, I almost immediately noticed that the symbols used in the logic diagrams were hardly intuitively associated with their counterparts in Boolean algebra. While the AND symbol in a logic diagram may appear neat and be easy to draw, there is no relation to the concatenation symbol used to represent the same operation on paper. The same applies for all the other Logic symbols used in the diagrams. While the symbols can all be learned one has to force the brain to make the connections between the logic diagram symbols and their equivalents until it becomes second nature. However, it could be much better. While optimizing several aspects of each symbol, it would also be possible to make the symbol reminiscent of its algebra equivalent.
2.) Secondly, once a student begins to deal with more complicated circuits, it becomes difficult to trace a logic diagram from output to inputs. Often times, it can require substantial amount of time to trace the logic diagram in order to determine what precisely it is generating. If it were easier to follow what is happening in a logic diagram, then it would significantly cut down on the interpretation time of both debugging and general reading of a logic diagram.
Both of these issues require visual optimizations of the current format to be rectified.

1.) The Basis for the New Symbols
When I started the process of creating a better set of symbols for the logic diagrams, the first step was to set out what conditions to try and have the symbols meet. There were 5 guidelines for my design process. First, the symbols should recall a similarity to the Boolean operations. Second, they should also strike a resemblance to the Verilog or HDL symbology. Third, the symbols should be distinct and easily recognizable at a moments glance. Fourth, the symbols should be easy and quick to draw for when the Logic Diagrams are being written out by hand. Finally, the symbols should create a clear segmentation of the immediate surroundings. (i.e. The symbol should have a clear distinction about which side is which.)

The Design Process
Once I actually started the design process, I attempted to maximize each of those rules in order to create several initial sets of symbols. I created symbols which were close mirrors of the boolean and Verilog logic, as well as creating sets that focused on distinct shapes and ease of drawing. These initial sets are shown here:

After surveying these sets of symbols, I immediately found that the triangular symbols in general seemed to stand out the best. A sideways triangles lends itself well to an imput - output format, and highlights the contents of the triangle. In order to follow through with the original plan, I drew several more intermediate steps of the triangular shapes. After many attempts at creating the symbols using variations of the triangle outline, I settled upon a set that was very easy to draw quickly, and very clearly mirrored a mix of the Boolean and Verilog symbols. Immediately upon looking at the symbols with very little intial clarification, a Boolean Algebra educated individual should be able to discern the symbols meaning. This final hand written set is shown here:

This set of symbols provides a very clean simplified look to the logic diagram. The consistent shape of the triangle provides a connection between the symbols, however due to the distinct contents of each triangle, the symbols are definitely unique. Additionally, the symbols in general are paired, AND with NAND. Since the triangle provides a direction to the symbol, this set uses that to simplify the differentiation between the two. The symbols are quite clearly the inverse of each other (as in boolean algebra.) The triangle that points forward shows a regular operation, while the backwards triangles show a negated operation or reversed output. This set covers all the areas of optimization that this project was supposed to focus on with regards to the symbols. Therefore, I created a computer generated set of symbols (using Adobe Photoshop) with a much cleaner look as you might see in a Hardware Design Software Suite.

In order to test whether or not the new symbols were actually an improvement, I replaced the old symbols in several different situations with this new set of symbols. I surveyed a few individuals (fellow Computer Organization students) to determine my success rate. While not a large enough test group to signify any sort of statistical signicance, they all in general preferred the new symbols to the old ones. Here is the test environment in which the new symbols were simulated. The original was made in Xilinx. I also used two pages from our Computer Organization text book for more examples of using the new symbols in teaching. They follow the complicated circuit diagram. In the test case I have included the old symbols first, followed by the same image with the new symbols in place.

Test 1

Here are the pages from the text book. I found these two pages to be particularly strong reinforcement on the ease with which this new set of symbols could be incorporated into the teaching curriculum.

(1, p45) (1, 83)

2.) Logic Tracing

This second portion of the project focused on an aspect which any hardware designer will be able to appreciate. The debugging process of a hardware schematic. The abundance of lines and information on any schematic can make it challenging to trace a logical route and determine where a missed connection may be. However, I developed a rudimentary wire color algorithim which could be used to show connections between logic gates as well as highlight logical paths. Since logical diagrams tend to be developed in 'layers' of logic gates as seen in the test example above, this creates some seperation which allows my algorithim to work. Each gate in each level of the logic diagram is assigned one of the 6 'complete' colors based on the R-G-B scale. A complete color is one where the values of RGB are either 255 or 0. This allows for 6 colors (excluding black and white.) Then for each wire connecting two logic gates, the average of each of the R G B values between the two logic gates is used to color the wire. Only the first two logic gates on a connection base the wire colors off of each other. Otherwise, if there is a third logic gate that connects to that wire, it takes the average of the R G B values in that wire and in the third logic gate.
This alogirithim makes it much easier to trace wires through a logic diagram and would also help to distinguish where a missed connection is. It would be able to highlight a missed connection, because the wire would only be the color of the gate it is connected to, not the average of the two gates. This algorithim, if used by a Hardware Design Suite like Xilinx would make schematic debugging immensely less time consuming.
Taking the test diagram from above, I applied the algorithim by hand to demontrate the drastic difference it would make.

In hindsight, I would have dimmed the saturation of the colors used in the algorithim in order to make the circuit a little more subtle. However, as can be seen in the image, wires have become very easy to trace since you can ensure that the wire you are tracing is the same color as the one you started on.
In summary, the two portions of my project would both make significant improvements to both the ability of new students to learn the Computer Organization language and for general debugging purposes. The new set of symbols would make a much more logical representation of the boolean alegbra happening behind the scenes. They are easier to read, and more quickly and intuitively convey their meaning. Additionally, when the wire color algorithim is added in, significant improvements should be seen in total time taken to create a new circuit schematic or logic diagram.

Bibliography

1. Mano, M. Morris and Kime, Charles R., "Logic and Computer Design Fundamentals, Fourth Edition", 2008, Pearson Education, Inc