Delay line synthesis of sequential machines

[摘要] 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: ifa 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 realizea 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.

[发布机构] Rice University