Misplaced Pages

This is an old revision of this page, as edited by Afveitch (talk | contribs) at 09:15, 8 October 2012. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

This is the user sandbox of Afveitch. A user sandbox is a subpage of the user's user page. It serves as a testing spot and page development space for the user and is not an encyclopedia article. Create or edit your own sandbox here. Other sandboxes: Main sandbox | Template sandbox Finished writing a draft article? Are you ready to request review of it by an experienced editor for possible inclusion in Misplaced Pages? Submit your draft for review!

Edward W. Veitch is an American computer scientist. He graduated from Harvard University in 1946 with a degree in Physics, followed by graduate degrees from Harvard in Physics and Applied Physics in 1948 and 1949 respectively. In his 1952 paper "A Chart Method for Simplifying Truth Functions", Veitch described a graphical procedure for the optimization of logic circuits, a year later (1953) refined in a paper by Maurice Karnaugh into what is now known as the Karnaugh map method.

Recent Comments on Design

The problem was how to depict a Boolean function of n variables in such a way as to make it easy for the human eye to see how to simplify the function. A function of four variables has sixteen input combinations and the diagram has sixteen different squares to be filled from the truth table that defines the function. The primary difference between the Veitch and Karnaugh versions is that the Veitch diagram presents the data in the binary sequence used in the truth table while the Karnaugh map interchanges the third and fourth rows and the third and fourth columns. The general digital computer community chose the Karnaugh approach. Veitch accepted this decision, even though in early 1952, before his presentation, he had almost changed to that approach but decided against it. A few years later several textbooks described the K-map, a few of them designating it a Veitch diagram.

Two score and seven years later (1999) Veitch discovered that Misplaced Pages had an article on the K-map. He read it and reread his 1952 paper. He realized that his old paper did not describe his method for finding simplification patterns. He now believes that the readers of his paper believed that he found simplifications by looking at the column and row labels while the K-map user found the simplification groups from a set of rules and then used the labels only to identify the groups.

Veitch also believes that a change he made in his diagram just before his presentation made it more difficult for the reader to realize his rules for finding simplification groups.

The Original Veitch diagram

It was known that one way to represent the function was as specified points on the corners of an n-dimensional cube, with each variable representing a different dimension of the cube. Three variables would be expressed through a 3-dimensional cube, or a normal cube with eight corners. Two adjacent corners such as the two on the upper right could be defined as the upper right corners and the four corners on the front of the cube could be defined as the front corners. For four, five, or six variables the problem becomes more complicated.

How do we depict the multi-dimensional cube on a flat diagram that makes it easy to see these relationships? For three dimensions, Veitch drew a 2x2 set of squares for the top of the cube and a second set for the bottom of the cube with a small space between the two sets of squares. Within the 2x2 set on the top the simplification groups are any horizontal or vertical pair or all of the four cells. The only adjacencies between the top and bottom sets are a one-to-one connection between each square of the top set and corresponding cell of the bottom set. A similar rule applies to the four variable cases, which is sometimes drawn as a cube inside of another cube with corresponding corners all connected. The four variable Veitch diagram would then be four 2x2 sets in a larger square with a small space between each pair of sets. Thus a horizontal pair in the top left set can combine with a matching pair in the bottom left set or with the top right set or possibly with all four sets to make an eight cell group. For five variables or six variables the same rule applies. The five variable diagram consists of two four variable diagrams drawn next to each other with a larger space between them. Matches between the two four variable diagrams are between cells that are next to each other when one map is overlaid over the other.

In a last minute change before his presentation Veitch removed the spacing between the 2x2 cell groups. This was a poor decision because it made it more difficult for the user to grasp the overall structure of the function, as well as the rules Veitch used in recognizing simplifications. Veitch learned recently from solving Suduko puzzles that spaces or heavy lines between groups of boxes can be very helpful especially if one has poor eyesight, such as Veitch now has.

References

• Edward W. Veitch, 1952, "A Chart Method for Simplifying Truth Functions", Transactions of the 1952 ACM Annual Meeting, ACM Annual Conference/Annual Meeting "Pittsburgh", ACM, NY, pp. 127–133.

• Maurice Karnaugh, November 1953, The Map Method for Synthesis of Combinational Logic Circuits, AIEE Committee on Technical Operations for presentation at the AIEE summer General Meeting, Atlantic City, N. J., June 15–19, 1953, pp. 593–599.

Template:Persondata

Category:American computer scientists Category:Living people Category:1924 births

• v
• t
• e

de:Edward W. Veitch pt:Edward Veitch