Synthesis of linear sequential machines

The synthesis problem for linear sequential machines which are defined over Boolean rings is considered. A theory is developed for realizing one sequential machine utilizing another lower-order one in combination with delay elements and Boolean adders. Included in the development is a necessary condition for the existence of a synthesis, and an investigation of two natural structures which can be employed in such syntheses. The concepts of minimal and good realizations are introduced, and exploited to produce an efficient synthesis algorithm. The latter, which is illustrated via an example, involves only the operations of sorting and of determining greatest common divisors of certain sets of non-negative integers.