Delay line synthesis of sequential machines
Marathe, Shreehari Ganesh
Jump, J. Robert
Master of Science
This thesis deals with the problem of realizing state sequential machines with delay line networks which are a special case of shift register networks. A formal definition of delay line networks is given with an algebraic model in terms of the following four parameters: the input set I, the number of delay lines m, the length of delay line 1, and the logic function f. With the help of this model, the concept of a state being in a cycle of length c is defined and it is shown that such a state is periodic with period c. The following result concerning the periodicity of doubly periodic finite sequence is proved: if a finite sequence is periodic with periods u and v and if the length of the sequence is greater than or equal to u+v-g where g is the greatest common division of u and v, then the sequence is periodic with period g. These results are related by proving that if a state is in two cycles of length u and v, then the length of the delay line must be less than u+v-g. A method is developed to derive bounds for the length and number of delay lines for a delay line network to realize a given machine. A constructive synthesis algorithm is given to find a delay line realisation of given machine in the above bounds if such an assignment exists. This algorithm utilizes a state assignment procedure to assign the states of a given machine to the states of a specific delay line network.