previous | contents | next

The device is to take a fixed number of 8-bit analog samples, here 512. The samples are first stored in a fast memory and then punched on paper tape with an 8-bit identifying number preceding the samples. This number, the Sample Identification, is supplied from an external source.

1. Design a system in which the analog input is multiplexed for eight inputs.

2. Modify your system so that the identifying number has four 8-bit characters.

3. What is the maximum sampling rate that might be accomplished using the same a-to-d converter, and memory? What would such a design look like?

4. There is no way to tell if the data punched is the same as that sampled and read. Paper tape systems of this type have been known to make errors (e.g., 1 character in 10^6 punched is not unheard of). Design a scheme for detecting whether an error has been transmitted in the data which was punched. Design a scheme that assumes 1 character has been erroneously punched with a single bit error. Add enough information so that the error can be corrected.

5. Assuming the analog-to-digital converter samples are variable from 8 to 12 bits, modify the design to accommodate the variable sample accuracy.

KEYWORDS: State, symbol, tape, transport, Turing machine

In 1936 A. M. Turing in a paper on the theory of computability, defined a class of abstract machines which we now call Turing machines. These machines have both theoretical and pedagogical applications in the study of the nature of computation. Turing machines provide an effective method for expressing a computational procedure; these model initial, terminal and looping conditions as well as the basic computational steps of the procedure. A Turing machine has a finite number of states (resembling a conventional controller) and is coupled by a single read-write head to a tape (resembling a magnetic tape) which is infinitely long and consists of squares which may have symbols from a finite alphabet written on them. The Turing machine executes three basic functions:

2. Write - write a symbol on the square of the tape under the head.

3. Move - move the read head one square to the left or right on the tape.

The operation of the Turing machine proceeds as follows:

• 1. Read a symbol from the tape.

2. Using the current machine state and symbol read as parameters, compute:

• a. a symbol to write on the tape (possible the same symbol as was read);

b. a new machine state (possibly the same as the current state);

c. a direction to move along the tape (left or right).

3. Loop to step 1.

The functions for computing new machine states, symbols, and directions are usually expressed in tabular form. Each combination of machine state and symbol has an associated triple which indicates the new machine state, symbol to write, and direction of movement resulting from that combination of parameters; the complete entry is referred to as a quintuple. The table format is shown in Figure TUR-1.

A parity counter will be developed as an example of a particular Turing machine. The purpose of the parity counter is to count the number of l's, modulo 2, that are on a tape of 0's and l's, i.e., detect an odd or even number of

260

previous | contents | next