This paper is concerned with the problem of mechanizing synchronous sequential machines with the least number of shift registers. An algorithm, suitable for programming on a digital computer, is developed which starts with the state table of the given machine and yields mechanizations having the least possible number of shift registers. The algorithm is based on the fact that there is a one-to-one correspondence between shift registers and certain partitions of the set of states of the machine. These partitions are called shift-register partitions (SRP's), and it is shown that every SRP can be generated from two special partitions called the column partition (πc) and the row partition (πr). States are grouped together in πcif they have transitions into common states and are grouped together in πrif they have transitions from common states.

The problem of assigning codes to the output states of a multiple-output combinational circuit is considered. It is assumed that if the circuit has n inputs, then the 2nfundamental products, i.e., input states, are to be partitioned into disjoint groups, such that all members of the same group produce the same output state. The problem of coding the output states is studied here. Two algorithms for making the assignments are considered. The first gives those encodings for which the sum of the costs of all the output functions is minimum; the second minimizes the variable dependency of the output functions. In problems where reduced variable dependency is possible it has been found that the second algorithm yields minimum or near-minimum cost networks. Since this algorithm is easily applied it is useful for finding economical networks in situations where a large number of variables are involved since in such cases the first algorithm becomes lengthy. Attention is also directed to the problem of determining the optimum number of output variables to use for an encoding. An upper bound is derived and an example is presented which requires this bound.