##### Example.0.3Analog-to-digital Conversion

A common problem encountered in engineering is that of analog-to-digital (a-d) conversion, where the reading on a dial, for example, must be converted to a numerical value. In order for this conversion to be done reliably and quickly, one must solve an interesting problem in graph theory. Before this problem is posed, we will make the connection between a-d conversion and the graph problem using a simple example. Suppose a dial in a video game can be turned in any direction, and that the positions will be converted to one of the numbers zero through seven in the following way. As depicted in Figure .0.4, the angles from 0 to 360 are divided into eight equal parts, and each part is assigned a number starting with 0 and increasing clockwise. If the dial points in any of these sectors the conversion is to the number of that sector. If the dial is on the boundary, then we will be satisfied with the conversion to either of the numbers in the bordering sectors. This conversion can be thought of as giving an approximate angle of the dial, for if the dial is in sector \textit{k}, then the angle that the dial makes with east is approximately \({45k}^{\circ}\).

Now that the desired conversion has been identified, we will describe a “solution” that has one major error in it, and then identify how this problem can be rectified. All digital computers represent numbers in binary form, as a sequence of 0's and 1's called bits, short for binary digits. The binary representations of numbers 0 through 7 are: \begin{equation*}\begin{array}{c} 0= {000}_{two} = 0 \cdot 4 + 0 \cdot 2 + 0 \cdot 1\\ 1= {001}_{two} = 0 \cdot 4 + 0 \cdot 2 + 1 \cdot 1\\ 2= {010}_{two} = 0 \cdot 4 + 1 \cdot 2 + 0 \cdot 1\\ 3= {011}_{two} = 0 \cdot 4 + 1 \cdot 2 + 1 \cdot 1\\ 4= {100}_{two} = 1 \cdot 4 + 0 \cdot 2 + 0 \cdot 1\\ 5= {101}_{two} = 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1\\ 6= {110}_{two} = 1 \cdot 4 + 1 \cdot 2 + 0 \cdot 1\\ 7= {111}_{two} = 1 \cdot 4 + 1 \cdot 2 + 1 \cdot 1\\ \end{array} \end{equation*}

We will discuss the binary number system in Section 1.4. The way that we could send those bits to a computer is by coating parts of the back of the dial with a metallic substance, as in Figure .0.5. For each of the three concentric circles on the dial there is a small magnet. If a magnet lies under a part of the dial that has been coated with metal, then it will turn a switch ON, whereas the switch stays OFF when no metal is detected above a magnet. Notice how every ON/OFF combination of the three switches is possible given the way the back of the dial is coated.

If the dial is placed so that the magnets are in the middle of a sector, we expect this method to work well. There is a problem on certain boundaries, however. If the dial is turned so that the magnets are between sectors three and four, for example, then it is unclear what the result will be. This is due to the fact that each magnet will have only a fraction of the required metal above it to turn its switch ON. Due to expected irregularities in the coating of the dial, we can be safe in saying that for each switch either ON or OFF could be the result, and so if the dial is between sectors three and four, any number could be indicated. This problem does not occur between every sector. For example, between sectors 0 and 1, there is only one switch that cannot be predicted. No matter what the outcome is for the units switch in this case, the indicated sector must be either 0 or 1, which is consistent with the original objective that a positioning of the dial on a boundary of two sectors should produce the number of either sector.

Is there a way to coat the sectors on the back of the dial so that each of the eight patterns corresponding to the numbers 0 to 7 appears once, and so that between any two adjacent sectors there is only one switch that will have a questionable setting? One way of trying to answer this question is by using an undirected graph called the 3-cube (Figure .0.6). In general, an undirected graph consists of vertices (the circled 0's and 1's in the 3-cube) and the edges, which are lines that connect certain pairs of vertices. Two vertices in the 3-cube are connected by an edge if the sequences of the three bits differ in exactly one position. If one could draw a path along the edges in the 3-cube that starts at any vertex, passes through every other vertex once, and returns to the start, then that sequence of bit patterns can be used to coat the back of the dial so that between every sector there is only one questionable switch. Such a path is not difficult to find; so we will leave it to you to find one, starting at 000 and drawing the sequence in which the dial would be coated.

Many A-D conversion problems require many more sectors and switches than this example, and the same kinds of problems can occur. The solution would be to find a path within a much larger yet similar graph. For example, there might be 1,024 sectors with 10 switches, resulting in a graph with 1,024 vertices. One of the objectives of this text will be to train you to understand the thought processes that are needed to attack such large problems. In Chapter 9 we will take a closer look at graph theory and discuss some of its applications.

One question might come to mind at this point. If the coating of the dial is no longer as it is in Figure .0.5, how would you interpret the patterns that are on the back of the dial as numbers from 0 to 7? In Chapter 14 we will see that if a certain path is used, this “decoding” is quite easy.

The 3-cube and its generalization, the \(n\)-cube, play a role in the design of a multiprocessor called a hypercube. A multiprocessor is a computer that consists of several independent processors that can operate simultaneously and are connected to one another by a network of connections. In a hypercube with \(M=2^n\) processors, the processors are numbered 0 to \(M-1\). Two processors are connected if their binary representations differ in exactly one bit. The hypercube has proven to be the best possible network for certain problems requiring the use of a “supercomputer.” Denning's article in the May-June 1987 issue of “American Scientist” provides an excellent survey of this topic.