Edward W. Veitch

Edward W. Veitch (November 4, 1924 – December 23, 2013) was 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

Recently Veitch wrote about the development of the Veitch diagram and its interpretation, These comments are summarized here.

• The problem is how to depict a Boolean function of n variables so the human eye can easily 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.

Years later (1999) Veitch discovered that Wikipedia 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 points on the corners of an n-dimensional cube. 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 Sudoku 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. Veitch died on December 23, 2013.^[1]

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.