R70-43 Lattice Functions, Pair Algebras, and Finite-State Machines
This paper is yet another solution for finding linear internal state assignments for the next-state behavior of a sequential machine. A state assignment is said to be linear if and only if the resulting next-state variables are linear combinations ofthe present-state and input variables. Consequently, the next-state behavior of a sequential machine is said to be linear if and only if there exists a one-to-one assignment which is linear. The problem of finding linear assignments has received considerable attention, probably due to their inherent mathematical structure, and hopefully to further illuminate the theory of sequential machines in general. The prime contribution of this paper is a refinement of a previously presented algorithm [1] for finding linear assignments. In this algorithm an assignment is found for a single column, as an autonomous machine, and it is then checked for validity with the remaining columns. The problem, of course, is to be able to restrict the choice of possible assignments so that the number that has to be checked for validity is sufficiently small to keep the process from becoming an exhaustive search. This the author has managed to do, with reasonable success. The author does go into considerable detail in explaining the background and individual steps of the algorithm. While all of the detail may be useful, it does make the paper significantly longer than it needs to be. The prime criticism of the paper is not in the algorithm itself, but in what the author purports that it will do. In the first instance, it is stated that the algorithm is very effective even when the number of states is large. If the matrix A is not unique, then it is necessary to try each possible A in the subsequent steps of the algorithm. In such circumstances, an algorithm can hardly be termed effective. Furthermore, the method requires the graph of the matrix A, which is no easy task for large n (the order of A). As an example, if the cycle length is 19, then the order ofA is 18 and the graph contains 218 = 262 144 vectors of length 18, and yet a next-state table with 19 states is not at all unreasonable. It is therefore concluded that while the algorithm will work, it may become exceedingly tedious for some cases. In the second instance, the author restricts his algorithm to a realization oforder n, where the number of states is q, and 2n' < q< 2'. As an example, the following machine (machine l) has ten states and hence, following the author, n= 4. In contradiction, however, when the algorithm is applied, n =6. Obviously the restriction is fallacious and it is only necessary for q< 2'. The author has omitted a few rather important references [2]-[4], not all of which were available at the time of writing; however, they are mentioned for completeness.
Identification and synthesis of linear sequential machines
This paper considers the identification and synthesis of linear sequential machines from their state transition tables. Necessary and sufficient conditions for linearity are derived which form the basis of identification tests. A sufficient condition leads to a method for coding the system's state vectors in a fashion consistent with linearity but which does not entail trial and error. The coding process is analytic in nature and allows the coding of state vectors independently of the coding or linearity of the output table. Both the Moore and Mealy models are considered in deriving coding procedures for the input and output vectors.
A Study of Feedback and Errors in Sequential Machines
The object of this paper is to study feedback in sequential machines, to classify (according to their seriousness) and analyze errors which arise in the state transitions of machines, and to establish some relations between feedback and errors. It is shown that the previously developed algebraic methods1,2 supply the necessary tools and a rigorous basis for this theory, and relate these new results to previously obtained results about the structure of sequential machines. For example, this work yields the necessary methods to detect the existence of a decomposition of machines into component machines so that the most ``serious'' errors of the computation can occur only in an isolated component machine. This leads to the possibility of imposing selectively different reliability conditions on the component machines to achieve high over-all reliability of the realizations.