A greatly simplified configuration is proposed for the array that performs summation in a cellular logic module. Such modules realize arbitrary, multioutput, combinational switching behavior as sums of products (or sums of other terms). Special cases of these modules are random-access and associative memories (conventional or READ-ONLY). The simplifications are achieved by taking advantage of the symmetries among the product (or term) buses and symmetries among the output lines, as well as the fact that extensive sharing of terms among output functions does not normally occur in practice. In many cases of interest, the simplified memory array can be reduced to a single column of cells.

An algorithm is derived for multiprobe testing for shorts, opens, and wiring errors in any multiterminal wiring network, such as a printed circuit board, wiring harness, multiconductor cable, or backplane wiring board. For behavioral testing the minimum number of tests required, always achievable, is equal to p - 1 + [log2q], where p is the number of terminals in the largest interconnected cluster in the network, and q is the total number of clusters, including isolated terminals. For structural testing the number of tests required is less, and can be as small as [log2q] + 1 depending upon the assumptions made regarding the types of faults that can occur.

A design is presented for an augmented content-addressed memory (ACAM) that can realize arbitrary combinational and sequential logic as well as a repertoire of simultaneously executed but varying word-organized operations.The ACAM array is offered as a useful and efficient module that is highly compatible with large-scale-integrated (LSI) device technology, and which can be used to construct a central processor, certain related peripheral subsystems, and possibly for general digital applications as well.An ACAM is a rectangular cellular array in which all cells are identical and each cell contains both storage and combinational logic.Data words are stored along rows of the array, and all operations are parallel (single-clock).Horizontal operations include shifting, column entry and readout, and several types of tests--equality, size (~_ and >), binary inclusion, zero, and overflow.In the vertical direction, one may perform vertical shifting (whole words at a time), entry, readout, logical and Boolean addition, full binary addition, complementation, and masking.Within certain limitations, word operations are selected independently for separate words in the array, and most operations may be masked on certain digits of all words or on certain words in all digit positions or both.The basic cell has a complexity of about 40 NOR-gates.In addition to its general-purpose parallel-processing capability, the ACAM array may also be utilized for many special purposes, such as a pushdown memory, a queue (buffer) memory, a bank of index registers, a scratchpad memory, a sorting memory (which keeps in order all words inserted in it), a conventionally addressed memory, and a list memory (based on any of a variety of data structures).By virtue of its combinational capability, the array may be employed as a data encoder or decoder, a permutation array (like a crossbar switch), a correlator for binary signal sequences, or a microprogram control matrix.

A cellular-logic approach is used to generate a family of multiple-output combinational switching circuits containing closed loops ( of the type that normally generate sequential behavior) and composed of simple gates. These networks contain fewer gates than any loop-free realizations. Some members of the family are oscillatory, while others are stable with multiple stable states, but the outputs remain quiescent in both cases. This result appears to have repercussions on some of the well-known optimality results of switching theory.

Faults can be circumvented in one-dimensional cellular arrays simply by switching out (bypassing) the defective cells in the cascade. In this note, the problem is solved of finding the minimal network of switches capable of bypassing up to q possibly defective cells from an n-celled array. The cells may be combinational or sequential, unilateral or bilateral, and may employ digital or continuous signals. It is shown that the minimum number N(n, q) of switches required equals ½(q+1)(2n-q+2) for the case when added internal circuit nodes are disallowed, or when q=1, and equals 3n otherwise.

A new unit-distance counting code (similar to the Gray code but having error-checking properties) that offers distinct advantages in the simplicity of the digital equipment required for encoding and decoding is described. This code has application in several special areas of information processing. It is generated by a particular generalization of the family of Gray codes, which has no error- checking features, but shares with the Gray code a simple conversion relationship to the conventional binary counting code. The new code is derived, and its error-checking and code conversion properties are proven by simple combinatorial arguments. The code has a total of K(m)= 2.2m/2code words of m digits each (m any even integer). It may be employed for correction of single errors or for the detection of double errors.

As a direct consequence of large-scale integration, many advantages in the design, fabrication, testing, and use of digital circuitry can be achieved if the circuits can be arranged in a two-dimensional iterative, or cellular, array of identical elementary networks, or cells. When a small amount of storage is included in each cell, the same array may be regarded either as a logically enhanced memory array, or as a logic array whose elementary gates and connections can be "programmed" to realize a desired logical behavior.

Dr. Dwyer's first three comments appear to be correct observations on the general subject of testing and diagnosis, although the initial statement in his second comment is incorrect (see [1], first paragraph of Section II-A, page 353).

Described in this report are the results of a comprehensive technical survey of all published Soviet literature in coding theory and its applications--over400papers and books appearing before March 1967. The purpose of this report is to draw attention to this important collection of technical results, which are not well known in the West, and to summarize the significant contributions. Particular emphasis is placed upon those results that fill gaps in the body of knowledge about coding theory and practice as familiar to non-Soviet The most noteworthy Soviet contributions have occurred in those areas that deal with codes for the noiseless channel, codes that correct asymmetric errors, decoding for cyclic codes, randomcoding bounds on the amount of computation required, and various application criteria--that is, when to use which code, and how well it performs. Other important but isolated results have been reported on the construction of optimal low-rate codes, bounds on nonrandom codes, linear (continuous) coding, codes for checking arithmetic operations, properties of code polynomials, linear transformations of codes, multiple-burst-correcting codes, special synchronization codes, and certain broad generalizations of the conventional coding problem. Little or no significant work has been done on pseudorandom sequences, unit-distance codes (with one exception), the application of codes to the design of redundant computers and memories, the search for good cyclic codes, and the physical realization of sequential decoding algorithms. Section II of this report is directed to the nonspecialist, and describes the status of the field of coding theory in the Soviet Union, summarizes the major technical results, and compares these with corresponding work in the West. Section III discusses in detail for the coding specialist new theoretical results, details of coding procedures, and analytical tools described in the Soviet literature. A complete bibliography is included.

A cellular array is a logical network of identical or almost identical cells, each of which contains a small amount of logic and storage, and, except for a few buses to the edge of the array, is connected only to its immediate neighbors. The cellular approach offers special advantages for realization by the forthcoming large-scale-integrated (LSI) technology. Such arrays are shown to be applicable for the encoding and decoding of binary error-correcting codes, and also for identifying the possibilities of tradeoffs between decoding time and equipment complexity. Arrays are presented for the decoding of single errors, burst errors, and erasures; the decoding of erasures is accomplished by the equation-solution approach, and it is shown for several code families that the Gauss elimination procedure is not required.

Abstract—he problem of designing test schedules for the testing or diagnosis of a small number of nontransient faults in combinational digital circuits (switching networks) is considered in detail. By testing and diagnosis we mean the following: 1) detection of a fault, 2) location of a fault, and 3) location of a fault within the confines of a prescribed package or module. It is shown that minimal test schedules can be readily derived–using procedures already worked out for solving certain problems in pattern recognition and switching theory–under the assumption that the selection of the test inputs in the schedule is independent of the response of the circuit under test. When this assumption is not made, it is shown that much shorter test schedules are sometimes possible, and procedures are offered for obtaining good ones. Finally, the general status of diagnostics for digital circuits is reviewed and evaluated, and specific problems remaining to be solved are described.

Abstract—A class of networks is described that has the capability of permuting in an arbitrary manner a set of n digital input lines onto a set of n digital output lines. The circuitry of the networks is arranged in cellular form, i. e., in a two-dimensional iterative pattern with mainly local intercell connections, where the basic cell behaves as a reversing switch with a single memory flip-flop. Various network forms are described, differing in the number of cells needed, in the shape of the array, and in the length and regularity of intercell connections. Also discussed are some ways of setting up the array to achieve a desired permutation.

The purpose of this paper is to describe the design of an all-digital cellular threshold array that is well adapted to realization by large-scale integrated semiconductor technology. A set of these arrays may be interconnected to realize arbitrary combinational or sequential logic, or may be stacked to form a multilevel adaptive pattern classification machine.

A comprehensive technical survey of Soviet switching theory and its applications to the logical design of digital systems reveals that, despite considerable activity (763 papers and books), the average state of the art in the U.S.S.R. is somewhat behind that in the U.S. However, there are a large number of noteworthy contributions, particularly in those aspects of the field dealing with complexity estimates of switching networks, synthesis of multiterminal circuits, the selection of logical primitives (building blocks), and certain minimization problems. This paper evaluates the Soviet position through June, 1964, compares it with that in the West, and summarizes the significant Soviet technical contributions. Recommendations are offered for initiating research in the United States in several special problem areas in switching theory.

A new family of codes is described for representing serial binary data, subject to constraints on the maximum separation between successive changes in value(0 \rightarrow 1, 1 \rightarrow, or both), or between successive like digits (0's,1's, or both). These codes have application to the recording or transmission of digital data without an accompanying clock. In such cases, the clock must be regenerated during reading (receiving, decoding), and its accuracy controlled directly from the data itself. The codes developed for this type of synchronization are shown to be optimal, and to require a very small amount of redundancy. Their encoders and decoders are not unreasonably complex, and they can be easily extended to include simple error detection or correction for almost the same additional cost as is required for arbitrary data.

A family of single-error-correcting codes is described for the protection of binary data words of fixed lengthk, each of which has the same numberwof1's. The code family is shown to be valid for all integerskandw(where0 < w < k). Some other related codes, based upon conventional Hamming codes, Latin squares, and block designs are also developed, and some of these are more efficient for certain values ofwandk.

A binary superimposed code consists of a set of code words whose digit-by-digit Boolean sums(1 + 1 = 1)enjoy a prescribed level of distinguishability. These codes find their main application in the representation of document attributes within an information retrieval system, but might also be used as a basis for channel assignments to relieve congestion in crowded communications bands. In this paper some basic properties of nonrandom codes of this family are presented, and formulas and bounds relating the principal code parameters are derived. Finally, there are described several such code families based upon (1)q-nary conventional error-correcting codes, (2) combinatorial arrangements, such as block designs and Latin squares, (3) a graphical construction, and (4) the parity-check matrices of standard binary error-correcting codes.

The problem of synthesizing switching networks out of linear-input (threshold) elements is studied for the class of symmetric switching functions. Tight bounds are derived for the number of elements required in a minimal realization, and a method of synthesis is presented which yields economical networks. Minimal networks result for all symmetric functions of no more than about twelve variables, and for several other cases. In particular, it is shown how the parity function of any number n of variables can be realized with about log2(n) elements.

A class of counters is described in which the number of 1's in the flip-flops or register stages composing the counter remains constant as the counter advances from state to state. Simple digital circuit arrangements are described for the design of such counters, which may be used with a particular type of decoding tree as economical ring-type counters, to provide a separate output lead for each state. Some interesting theoretical questions concerning the minimization of these decoding trees are raised and partially answered. Finally, the costs of these counters are compared with one another, and with those of other types of counters, over a continuous range of values of the flip-flop/gate-input cost ratio.