On the Number of Distinct State Assignments for Synchronous Sequential Machines

In an early paper [1], McCluskey and Unger counted the number of distinct state assignments for synchronous sequential machines. Their formula, however, does not account for all distinct state assignments when the memory function in a realization is performed by delay elements alone. This note amends their formula by establishing the conditions for its validity and by deriving the appropriate expression under other conditions. An example illustrating the effect of using the McCluskey-Unger formula in a case where it does not apply can be found in a recent paper by Dolotta and McCluskey [2]. In their paper, a procedure is proposed for selecting a state assignment that has an associated economical realization. Their method implicitly restricts the memory units to be delay elements, and some distinct state assignments are not considered. Consequently, a number of realizations are over-looked. A minor modification in the Dolotta-McCluskey algorithm is suggested so that all distinct state assignments are taken into account. In some cases this revised procedure results in a more economical realization than the unmodified one.