The problem of retrieving an ordered list of k words that satisfy a given search condition from an associative memory of m words of n bits each is addressed. A fast ordered retrieval algorithm is proposed, along with a logic design for a cellular associative memory which mechanizes the algorithm. The algorithm is of time complexity O(n+k). By contrast, the fastest previously known algorithms, by M.H. Lewis (see RCA Rev., vol.23, p.215-29 (1962)) and C.V. Ramamoorthy, J.L. Turner, and B.W. Wah (see ibid., vol.27, no.9, p.800-15 (1978)), are of time complexities O(k*log n) and O(k*n), respectively.>

A new scheme for constructing search algorithms for bit-parallel associative memories of m n-bit words is described. The resulting equivalence searches, threshold searches, and double-limit searches achieve the time bound of O(log n), compared to O(n), the recent result of Ramamoorthy et al. [12]. The extremum search algorithm by Frei and Goldberg [2] is modified and generalized so that the number of memory interrogations is reduced by 30 percent over the initial algorithm in the average case.

This correspondence is concerned with the detection of permanent faults in redundant combinational networks. Fault masking in such networks is examined. A method for determining an optimal test set that will detect all detectable faults is given.

The problem of how to determine minimal sets of tests for single and multiple faults in irredundant combinational circuits is dealt with. It is shown that the "Equivalent Sum of Products" form of the given network contains all the information necessary to derive a min; mal test set. A simple procedure which generates a minimal test set Ts for single faults is described. Fault masking is then studied and it is shown how to find the multiple faults undetected by Ts. Finally a method which derives a nearly minimal multiple fault test set Tm where Ts [mi][/mi] Tm is given.

This note is concerned with the realization of sequential machines without logic, i. e., using delay elements only. The other approach to the problem deals with only the next-state behavior and tends to be rather long. A new approach is presented for not only the next-state behavior, but also for the complete behavior. Beginning with the output partitions, the predecessors are found until the process terminates with an input partition, a trivial partition, a previously found partition, or a nontrivial function of input and internal states. Whenever the latter occurs, the machine requires logic. With respect to the next-state behavior, it is first shown that a permutation machine is logic-free if and only if it is autonomous. Then since the next-state behavior of a feedback-free machine is realizable without logic, a machine is logic-free realizable if and only if M, is autonomous.

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 of the 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.

This correspondence presents a logical design procedure for feedback shift registers, which permits the gating of a common clock signal.

Abstract—This paper considers the problem of determining whether a sequential machine, given by its flow table, can be realized in the form of a single binary shift register. One-to-one and many-to-one assignments are considered. Binary partitions are introduced, and shift registers are characterized in terms of binary partitions. An algorithm is given for the determination of the required partitions for a shift-register assignment. Binary set systems are introduced and shift registers are characterized in terms of binary set systems. It is proven that there exists a sequential machine that cannot be realized by a single binary shift register of finite length. Methods for determining the set systems necessary for a single shift-register assignment are given. For machines where every state has two distinct next states, a method is presented whereby a number of machines can be easily eliminated as being not fsr realizable. It is then shown how this can be extended to all machines.

This paper presents an approach to the problem of assigning binary input codes so that the combinatorial circuits necessary to realize the given output functions may be minimized. The approach is based on binary partitions and binary set systems, which provide a natural language for dealing with the problem. First, a lower bound is established for the realization of each output function, with the assumption that the function will not be realized directly. Then, the output partitions determined by the output functions are found and those output partitions that can be used together in a valid assignment are established. This provides a number of assignment schemes which, in turn, can be evaluated in terms of a lower bound for the realization cost. For the scheme with the smallest lower bound, the actual realization cost is established. This provides a measure by which a number of schemes can be eliminated, since it is necessary to consider only those schemes having a lower bound smaller than the least actual cost already obtained. Using set systems, the method is extended to include output functions containing don't cares. It is also shown how the method can be applied to the minimization of combinatorial circuits in sequential machines.

This paper presents a method for determining, from the flow table of a sequential machine, whether the machine is linearly realizable using the minimum number of unit delay elements. The method is an extension of a previously presented method for autonomous machines. A linearity algorithm is presented for each of two cases: 1) where the output is given and is to be linear, and 2) where the output is either not given or may be nonlinear. The method is simple, straightforward, and, in general, provides a ready solution to the linearity problem.

This paper presents a method of determining, from the flow table of an autonomous sequential machine, whether the machine can be realized by a linear circuit which uses the minimum possible number of secondary variables. The method is based on a class of binary partitions of states, which are used to find a minimal assignment of the secondary variables such that the next state and output functions are linear. The partitions are examined in detail and the properties necessary to produce a valid assignment are developed.