Development and comparison of algorithms for generating a scan sequence for a random access scanner

Many data acquisition systems incorporate high speed scanners to convert analog signals into digital format for further processing. Some systems multiplex many channels into a single scanner. A random access scanner whose scan sequence is specified by a table in random access memory will permit different scan rates on different channels. Generation of this scan table can be a tedious manual task when there are a large number of channels (e.g. 50), more than a few scan rates (e.g. 5), and/or the ratio of the highest scan rate to the lowest scan rate becomes large (e.g. 100:1). This study developes an algorithm which will generate these scan sequences for the random access scanner and implements the algorithm on a digital computer.

Application of number theory to the mathematical statement of the problem led to development of several algorithms which were implemented in FORTRAN. The most efficient of these algorithms operate by partitioning the problem into a set of subproblems. Through recursion they solve each subproblem by partitioning it repeatedly into even smaller parts, continuing until a set of simple problems is created. From this process, a pictorial representation or "wheel diagram" of the problem can be constructed. From the wheel diagram and a description of the original problem, a scan table can be constructed. In additon, the wheel diagram can be used as a method of storing the scan sequence in a smaller amount of memory.

The most efficient partitioning algorithm solved most scan table problems in less than a second of CPU time. Some types of problems, however, required as much as a few minutes of cpu time.