This paper proposes a method, termed antiparallel control logic, for the control and efficient utilization of computer networks that exhibit substantial propagation delays on the lines interconnecting the logical elements, as well as in the elements themselves. The discussion encompasses the basic behavior of antiparallel stages that realize this method of control, including their logical realization and their extension to other useful network logic structures. In a strictly feedforward line, where the stored data are indexed forward by control pulses moving in a direction away from the data source, the existence of time variations in the delays of successive stages implies a nonzero probability that two successive control pulses will eventually appear at the inputs to a given stage so closely spaced that the basic reaction time of the stage is violated. The result is a failure of the transfer mechanism and a consequent loss of information. If feedback control is provided such that control pulses move in a direction opposite to the flow of information, that is, if the control and information flows are antiparallel, then the failure of the transfer mechanism does not cause an overlap in the information stored on the line, but rather leaves a void, or hole, which does not imply necessary information loss nor physically unrealizable storage requirements on the individual stages.

The run measure of a switching function has arisen in several contexts as an indication of the complexity, or cost, of a realization of the function. The run measure of a function can be defined in terms of its conventional truth-table representation. The output column of the truth table is an ordered sequence of zeros and ones that are disposed in runs; i.e., groups of like digits, of various lengths. The run measure of the function is simply the number of runs in this output sequence. It is often convenient to consider two functions to be equivalent if one can be obtained from the other by some permutation or complementation of the input variables. In this context, the cost of a function can be taken as the minimum value of the run measure over the equivalence class that contains the function. This paper derives a firm upper bound on the run measure for arbitrary n-variable switching functions when arbitrary permutations and complementations of the input variables are permitted. It is also shown that this bound is attained only in the case of the parity functions and that, hence in this sense, all other functions are less complex.

Using the contact network as a representative of the class of combinational branch-type networks, various realization techniques are examined for their applicability or adaptability to the particular class of complementary-output networks, that is, two-output networks which have exactly one active output for each combination of the independent variables. Some elementary structural characteristics are developed and a particular class of functions which are minimally realized in separate parts is discussed. Upper and lower bounds are derived for the the number of contacts required to realize an arbitrary n-variable specification. Rudin's interconnection rules are extended to the non-series-parallel case and examples are given of their application. Trees are discussed in terms of a specific procedure proposed for their realization. Finally, Calingaert's reduction of the general multi-output problem to a single-output problem is reviewed in terms of the specific class of networks of interest here, and results, in conjunction with Moore's tables of minimal four-variable networks, in a table of minimal three-variable complementary-output networks.

A detailed study has been made of a certain class of systematic binary error-correcting codes that will correct the error bursts typical of some digital channels. These codes--generalizations of codes discovered by Abramson and Melas--are cyclic codes designed to correct any single burst of errors pern-digit word provided that the width of the burst (regarded cyclically) does not exceed a certain number of digits,b. Moreover, these codes are optimum in the sense that they employ the minimum number of redundant digits theoretically possible for a cyclic code with given values ofnandb. A cyclic code is completely characterized by its generator polynomialg(x), hence, the properties of the code can be determined by analysis of the correspondingg(x). Necessary and sufficient conditions ong(x)have been formulated for the corresponding cyclic code to be an optimum burst-bcorrecting code. These conditions have been formulated into a series of tests that can be carried out (in principle) on anyg(x). All optimum burst-bcyclic codes withn < 2^{12}andb < 6have been found in this way and their generators are tabulated in the paper. In all, 98 codes are listed (not counting reciprocals) forb = 3andb = 4; it was shown that no optimum codes exist forb = 5within the limits stated. Practical codes forb \geq 6will probably be nonoptimum codes because of the extreme word lengths required for optimum ones.