The change-making problem (assemble a total of C cents using the least number of coins) is representative of a frequently encountered class of optimization problems.A recursive algorithm is developed for solving that problem.A much simpler--but not universally applicable--algorithm is also presented, and a procedure is described for testing its validity for any specified set of parameters.

This paper is concerned with the transformation of a single-channel (series-operated) finite-state machine into a multichannel (parallel-operated) machine, and conversely. It is shown that every single-channel machine has a multichannel analog with the same number of states. A multichannel machine has a single-channel analog if and only if a so-called "prefix condition" is satisfied. Algorithms are given for constructing both types of analogs with the minimum number of states.

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 S 0 , S 1 , · · ·, S T -1 , such that all states in S 1, under all possible inputs, pass into states in S i +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 .

This paper deals with the synthesis of sequential machines (without a distinguished initial state) which satisfies a specified list of input sequences and corresponding output sequences. Readily testable necessary and sufficient conditions are given for such a list to result in a realizable machine, and an algorithm is formulated for constructing the machine when these conditions are fulfilled.

In a recent paper,1Hsiao and Sih proposed a method for transforming binary linear feedback shift registers (initially cleared) into a binary linear circuit with f input terminals and f output terminals which operates f times faster. In this manner, the availability of f channels, rather than one, can be exploited to process (and, in particular, encode and decode) data at a rate proportional to f. In this paper, a method of transformation is formulated which is applicable to arbitrary linear sequential circuits defined over an arbitrary modular field and subject to an arbitrary initial state.

article Free Access Share on Analysis and Synthesis of Stable Linear Sequential Circuits Author: Arthur Gill Department of Electrical Engineering, University of California, Berkeley Department of Electrical Engineering, University of California, BerkeleyView Profile Authors Info & Claims Journal of the ACMVolume 12Issue 1Jan. 1965 pp 141–149https://doi.org/10.1145/321250.321263Published:01 January 1965Publication History 13citation385DownloadsMetricsTotal Citations13Total Downloads385Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Following Moore [1], consider a sequential machine (discrete, synchronius automata) having n states or less, m inputs, and p-possible outputs. The state that the machine is in at a given time depends only on the state at the previous time and the previous input. The output at a given time depends only on the current state. In addition the machine is strongly connected. That is to say, it is possible to take it from any state to any other state by means of some sequence of inputs. Finally, the machine is in reduced form, which may be taken to mean that it is not possible to design a sequential machine having fewer states whose behavior, in so far as its inputs and outputs are concerned, is identical with the behavior of the original machine. As a gedanken experiment, one may attempt to determine the table of state transitions and outputs of this machine (to within a renaming of its states) by applying inputs and observing the corresponding outputs. It is assumed that one does not just open up the machine and trace its circuits. What will be the length of this gedanken experiment? That is, how many inputs are needed?

In this paper the group-theoretical concept of ``confluence sets'' is introduced as a valuable tool in the analysis of linear sequential circuits (LSC's). Using this concept, a scheme is formulated for producing state graphs of autonomous LSC's which, in the ``singular'' case, is superior to currently known schemes. Singular LSC's, which are of potential interest in error correction systems, are studied in detail. Properties of their state graphs are derived, culminating in a unique characterization of such graphs in terms of representative ``cycles'' and ``trees.'' Together with known results on nonsingular circuits, the results in this paper offer a description of the autonomous behavior of the general linear sequential circuit.

This paper is concerned with the design of a discrete stochastic generator (such as needed for implementing Monte Carlo programs or for simulating probabilistic finite-state machines), realized by feeding a deterministic finite-memory sequential neCwork from an arbitrary random source.It is shown that the problem of designing such a generator in an optimal fashion, or subject to some accuracy criterion, is equivalent to a weight distribution problem arising in various transportation and scheduling tasks.A number of procedures are presented for solving this problem, and the implications of these procedures on the logical design of the generator network are pointed out.

In this paper, networks of finite-state machines, rather than individual machines, are discussed. The investigation centers around cascade networks, where the output of one machine serves as an input to another. It is shown how, by means of connection matrices, the characteristics of such a network can be obtained from those of the component machines, and how a specified machine can be decomposed into a number of cascaded components. The advantages of such a decomposition, as well as some of the problems that remain to be solved in this area, are discussed.

The assignment of prime numbers to the branches of directed or non-directed nets, enables one to construct transition matrices in a numerical, rather than a symbolic, form. The numerical form greatly facilitates the construction of higher-order transition matrices, needed for the topological analysis of a given net. The proposed method is especially useful for the mechanical determination of the non-repeating paths and cycles in the net.

This paper is concerned with the optimal compilation of programs whose function is to transfer words of information from one location in a serial memory to another. The most important optimization tool is the ``timing schedule,'' which facilitates the analysis of various transfer schemes and the determination of the fastest one. The procedure described for optimizing serial transfers is readily programmable for computer execution, and is directly applicable to a general class of transportation problems.

The characteristics of a discrete automaton with a finite memory can be determined by an experiment of a finite length. This paper discusses the properties of such experiments, and presents methods for their optimal construction. Specific results are given for binary-input automata with the memory ranges 0, 1, 2, 3 and 4.

The usefulness of large-capacity digital differential analyzers (DDA's) is severely hampered by the complexity of the scaling process. The scales needed for programming a DDA have to be compatible with the so-called ``equilibrium,'' ``topological,'' and ``boundary'' constraints, imposed by the construction of the analyzer and the nature of the problem at hand. Simultaneous trial-and-error satisfaction of all these constraints, to achieve optimal range and accuracy of computation, is practically impossible for any problem involving more than a few integrators. The paper shows how the scaling constraints can be organized in a matrix form, and how optimal scales can be produced in a systematic manner. The proposed scheme, which can be programmed for automatic execution, is adaptable for DDA's operating in conjunction with general-purpose digital computers.

Speedier and simpler pattern-recognition systems can be realized when provided with a minimum-scan reading device. For the idealized case, where the input set of patterns is finite, binary and errorless, a theorem is proved which enables the designer to predict the efficiency range of the contemplated reading device. A constructive method, which can be readily programmed for computer processing, is proposed for finding the shortest scanning path realizable for any given set. In the case of noise, scanning paths are sought which maintain a prescribed minimal "distance'' between the patterns, and hence yield a prescribed level of error-detecting capability. The theorem previously proved is extended for this case, and a constructive method is proposed for finding the shortest path consistent with any specified minimal distance, for any given set of patterns.