Periodic Decomposition of Sequential Machines

ABSTRACT

Given a minimal sequential machine M and a positive integer T, it is desired to partition the state set of M into T classes, say S0, S1, · · ·, ST-1, such that all states in S1, under all possible inputs, pass into states in Si+1 (mod T). If such a T-partition exists, M can be realized by means of periodically-varying logic, which often results in the saving of memory elements. The period of M is defined as the greatest common divisor of all cycle lengths of M—a quantity which can be readily evaluated since it depends only on a finite set of independent loops exhibited by the state graph. The main result is that a T-partition exists for M if and only if T is a divisor of the period of M. For every such T, an algorithm is given for constructing the corresponding partition. If M is not required to be minimal, it is shown (constructively) that a T-partition exists for every T.

REFERENCES

• 1: GILL, A. Time-varying sequential machines. J . Franklin Inst. 276 (1963), 519-539.
• 2: SESHU, S., hen REED, M. B. Linear Graphs and Electrical Networks. Addison Wesley, Reading, Mass., 1961, p. 24.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Performance, Theory, Verification