Search

Concept of n-width and extremal subspaces, first introduced by Kolmogorov, plays an important part in mathematical problems of approximation of classes of functions and in engineering problems of signal representation and reconstruction. In this short paper, explicit expressions for n-width and extremal subspaces are obtained for a class which is of some engineering importance.

This paper examines a M -ary sequential orthogonal (OM) communications system. A similar M -ary sequential pulse-amplitude modulation (PAM) problem was previously considered by Hecht and Schwartz [10], and by the author. We examine the following problem: given that one of them signals is repetitively sent over an additive Gaussian channel successive intervals of time, determine the optimum sequential procedure to follow at the receiver to pick the correct signal with a probability of wrong selection no greater than \varepsilon . The optimum procedure is defined to be one that minimizes the expected number of transmissions (sample size) before a decision is reached. This paper extends the works of Viterbi [1] and Kramer [2] who proposed two ad hoc test procedures for this OM problem. From the results of Simons [3] and Hoeffding [4], a lower bound on the expected sample size is found for any sequential test procedure for the proposed OM system. Both the maximum a posteriori probability (MAP) and the simultaneous tests are shown to achieve this lower bound in the limit as \epsilon \rightarrow 0 . Viterbi [1] computed the expected sample size for the MAP test procedure when M = 2 . For the case where M \geq 3 , this paper derives approximations of the expected sample sizes for both the MAP and the simultaneous test procedures when \varepsilon \rightarrow 0 . Computer simulation shows that the derived expected sample size gives accurate estimation of the actual sample size when M \epsilon . These sequential procedures offer 1 to 2 dB more power saving than the test procedures of Viterbi [1] and Kramer [2] if \epsilon > 10^{-7} .

This paper presents an extension of the concept of linear separation to generate a wider class of Boolean functions. This generalization is affected by modifying the requirements for separation to allow both true and false assignments to reside on the same hyperplane (pseudoseparation) or within the same neighborhood of a hyperplane (marginal separation). Boolean functions which can be separated in either of these ways are called partially separable functions. This paper is divided into two parts. The first deals with pseudoseparable functions and the second deals with marginally separable functions. Some of the theoretical algebraic properties of partially separable functions are investigated, and the relationship between these and the corresponding properties for separable functions is explored. Necessary and sufflcient conditions for each type of separation are also discussed, A parameter which shows whether a given Boolean function is separable, pseudoseparable, or marginally separable is introduced.

This paper deals with the relations between the structure matrices of electric networks which are n-port equivalent to a given network composed of passive linear time-invariant bilateral two-terminal elements, whose associated linear graph is connected and has no self-loops. The n -ports are defined as (i) ports created by cutting designated links of a cotree, or (ii) ports created by connecting to designated branches of a tree. Matrix representations for the electromagnetic, topological, and port structures of networks are described. It is found that the structures of equivalent networks can be formally represented by means of a pair of square matrices, one of which describes the change of electromagnetic structure, and the other the change of topological and port structures. The principal result of the paper is the determination of necessary and sufficient conditions on these matrices for n-port immittance equivalence. This result opens the possibility of directly specifying the electromagnetic, topological, or port structures of an equivalent network, and then formally solving for the remaining information. This is in contrast to existing methods, based on W. Cauer's linear transformation of port variables, in which the effect on the three structures is "mixed" in a single matrix of transformation.

In this paper, we obtain upper and lower bounds on the designed and actual distances of any sequence of extended primitive BCH codes of increasing lengths n and fixed rate R . The results of this paper are based on [1, ch. 12], which gives an exact expression for the rates of any sequence of extended primitive BCH codes of increasing length and fixed ratio of distance/length.

Cyclically permutable codes have error-correcting properties which are invariant under arbitrary cyclic permutation of any of their code words. This paper summarizes the results of an empirical investigation of certain of these codes, which have parameters not covered by a previous paper of E. N. Gilbert. ^{1} These codes are thought to be nearly optimal. Estimates of the obtainable number of code words are given. The codes may be suitable for use in certain asynchronous multiplex communication systems.

This paper deals with a t h e o r e t i c a l c i r c u i t analysis of a single-ended push-pull audio amplifier. Linear tube characteristics and small signals are assumed. The problem of impedance matching is first discussed. The properties and the requirements of a s a t i s f a c t o r y d r i v e r s t a g e are analyzed, and an output stage using an impedance matching output transformer is discussed. The effects of the plate-to-ground capacitance of t h e d r i v e r stage on the frequency-gain characteristic and of the choice of the tube and circuit parameters are analyzed. The paper concludes with some experimental results indicative of the inherent properties of the amplifier. In a r e c e n t a r t i c l e by Peterson and Sinclair,l special c i r c u i t s have been suggested by which a high fidelity, low d i s t o r t i o n audio amplifier can be constructed without using output transformers or i n which the requimrnents of an output transformer can be greatly simplified, The present a r t i c l e will give a t h e o r e t i c a l analysis of the b a s i c c i r c u i t used by Peterson and Sinclair. It will be observed that many desirable characte r i s t i c s of t h i s a m p l i f i e r c i r c u i t can be deduced from this analysis.

This paper generalizes Cover's results on broadcast channels with two binary symmetric channels (BSC) to the class of degraded channels with N components. A random code, and its associated decoding scheme, is shown to have expected probability of error going to zero for all components simultaneously as the codeword length goes to infinity, if the point representing the rates to the various receivers falls in the set of achievable rates described by this paper. A procedure to expurgate a good random broadcast code is given, leading to a bound on the maximum probability of error. Binary symmetric broadcast channels always fall in the class of degraded broadcast channels. The results of the paper are applied to this class of channels of potential practical importance.

The evaluation of characteristic numbers for trees has been done either by drawing the graph trees or by setting up a "primitive node-pair connection matrix." In this paper a new algorithm called the foldant is proposed. This is an algebraic method equivalent to the drawing of the graph trees. When a node, say node n , is superposed upon another node, say node 1, any branch ni , where i is any third node, is now parallel to the branch li . This geometrical transformation can be described by the algorithm of the foldant. As a direct application, Maxwell's rule of the driving point admittance which is described in the Appendix of his classic book. can be rewritten in terms of the foldant. Thus, as far as the computation of driving point admittance is concerned, it is no longer necessary to write down a set of node or loop equations nor to remember the lengthy statement of Maxwell's original rule. In this paper, pertinent theorems are given, together with proofs. Examples are given to clarify the method of computation.

In this paper some properties of unimodular (or E -) and paramount (or M -) matrices are discussed. The paper deals with matrices K which may be decomposed in a congruence ADA \prime where A is a rectangular unimodular- and D a diagonal- matrix with constant, positive and real diagonal elements. It is shown that such a decomposition, if at all possible, is essentially unique and a direct algebraic procedure is given which results either in finding the pair of matrices A and D or in a proof that such decomposition is impossible. Since the admittance matrices of n -ports described on pure resistance networks (or RLC networks for positive, real values of the complex frequency) with n + 1 nodes, or dually the impedance matrices of n -ports inscribed into R -networks with exactly n independent links belong to the Class of ADA \prime matrices the paper defines a method of decomposition of such matrices into the product ADA . The synthesis of the corresponding n -port may then be realized by known methods.

—Finding simple or "canonical representations" for regular events is one of the important problems concerning finite automata. The present paper is an attempt to find concatenative canonical decompositions for regular events. Five different decomposition types of regular events are defined, imustrated by examples, and their properties investigated. The main tool in our investigations is the notion of a decomposition set; it is a generalization of the notion of a decomposition state, introduced by the authors in a previous paper.[7]Let A =(S, M, s 0 , F) be a finite automaton; a subset S⊂S is a decomposition set if A goes through a state of S whenever it accepts a tape. In order to determine whether a given subset S⊂S is a decomposition set one has to check only tapes whose length is not greater than |S|-|S|-1, where |S| and |S| are the number of states in S and S, respectively. Thus, one can deternine all decomposition sets of A. The knowledge of the decomposition sets of A enables one to determine whether and in what form T(A), the set of tapes accepted by A, is decomposable.

Given two implicants of a Boolean function, we can, by performing their consensus, find a third implicant. This operation has been used for finding the prime implicants of a Boolean function. In this paper, the consensus is extended from two to any number of terms. A property of these generalized consensus relations leads to a systematic way of finding them. It is shown that any prime implicant of a Boolean function is a generalized consensus; therefore the algorithm for the determination of the consensus relations can be used for finding the prime implicants. This new method is simpler than the usual process of iterative consensus. It is also shown in this paper that consensus theory can be used for finding the minimal sums of a Boolean function. The methods are applicable for any Boolean function, with or without don't care conditions, with a single or a multiple output.

In this paper the problem of realization of a resistive n -port network from its paramount admittance matrix Y is considered from a geometric point of view. Augmentation of the set of n ports to a linear 2n - 1 tree on a complete graph with 2n vertices leads to a system of n(n + 1) equations in q = n (2n - 1) unknowns. All the real solutions of this system correspond to equivalent n ports. They may be looked on as points of a manifold L in the q -space E^{q} . The realization of Y in the conventional sense being constrained to non-negative resistor values is equivalent to finding a point of intersection of L and the non-negative orthant P of E^{q} . In this paper the theory of equivalence is studied and some properties of L are defined. Similarly to the known method of the decomposition of the admittance matrix Y of a resistive n -port network with n + 1 vertices into a unimodular congruence Y = CGC' , this paper proposes a decomposition of a general admittance matrix Y into a subunimodular congruence Y = CGC' .

In this paper a new decoding scheme for random convolutional codes is described. This scheme is different from other effective decoding schemes, such as sequential decoding [1] and low-density parity check codes [2]. The new scheme yields (for a certain region of information rates) an upper bound on the average number of computations which is {\em independent} of the coding constraint length. Furthermore, unlike sequential decoding, a bound on the total number of computations (rather than just on the "incorrect subset") is derived in this paper.

Recurrent codes for burst-error correction are defined to be a type B1 code. A type B1 code is capable of correcting all the single burst errors of length l or less. A type B2 code is a subclass of a type B1 code with the restriction that the single burst error of length l or less occurs within r consecutive blocks (it is assumed that l is divisible by b and l = rb ). In this paper, the author will present a class of q -nary recurrent codes--both type B1 and B2 codes--for burst-error correction. The construction procedures for this class of codes are simple and systematic. An interesting relation exists between a type B1 and a type B2 code. If a code is type B2 (with block length b , burst-error-correction capability l = rb ), then by reducing the block length by one symbol, the type B2 code becomes a type B1 code, while the burst-error-correction capability remains the same. Both types of codes can be used for the correction of binary burst errors. The correction of binary burst errors will be briefly discussed in this paper.

This paper examines the distribution of the mantissas of floating point numbers and shows how the arithmetic operations of a computer transform various distributions toward the limiting distribution $r(x) = {1 \over x \ln b} \quad (1/b \leqq x \leqq 1)$ (where b is the base of the number system). The paper also gives a number of applications to hardware, software, and general computing which show that this distribution is not merely an amusing curiosity. A brief examination of the distribution of exponents is included.

In a recent series of papers, [2]-[4] Schalkwijk and Kailath have proposed a block coding scheme for transmission over the additive white Gaussian noise channel with one-sided spectral density N_{0} using a noiseless delayless feedback link. The signals have bandwidth W (W \leq \infty) and average power \bar{P} . They show how to communicate at rates R , the channel capacity, with error probability P_{e} = \exp \{-e^{2(C-R)T+o(T)}\} (where T is the coding delay), a "double exponential" decay. In their scheme the signal energy (in a T -second transmission) is a random variable with only its expectation constrained to be \bar{P}T . In this paper we consider the effect of imposing a peak energy constraint on the transmitter such that whenever the Schalkwijk-Kailath scheme requires energy exceeding a \bar{P}T (where a > 1 is a fixed parameter) transmission stops and an error is declared. We show that the error probability is degraded to a "single exponential" form P_{e} = e^{-E(a)T+o(T)} and find the exponent E(a) . In the case W = \infty , E(a) = (a - 1)^{2}/4a C . For finite W, E(a) is given by a more complicated expression.

Since it is not clear, in general, how an automaton should best be characterized, one of the purposes of this paper is to find ways to go from one characterization to another. In doing so, we hare not been completely impartial — the programming approach has been emphasized more than the others. There are perhaps two reasons for this emphasis: First and the more obvious one is the closeness between theoretical programming discussed here and programming of digital computers. Secondly, the programming approach has provided a way of looking at automata that seems to make certain ideas less obscure — the construction of a universal program in Section. III of this paper is one such example. In the theory of finite automata, Theorem 3 is an attempt to unify the ideas of complete and partial automata, which have generally been treated separately in the past.

Starting from the definition of a determinant and using a few of its elementary properties, this paper gives an independent derivation of the optimum formula for the gain of a flow graph. Thus, a simpler path is shown to Coates' important result. This paper is self-contained, so that no previous knowledge of flow graphs is required. For motivation, the reader is referred to some well kmown papers and books.

In an asymmetric binary channel, it may be sufficient to correct single O-errors and detect double 0-errors, for example, while correcting double 1-errors and detecting quadruple 1-errors. (A double 1-error is said to occur when two of the l's of an input code character are delivered as O's at the output of the channel.) Minimum distance requirements are given for pairs of code characters of a code which corrects k -tuple 1-errors, detects (k+a) -tuple 1-errors, corrects j -tuple 0-errors, and detects (j+b) -tuple O-errors (k,a,j , and b , are non-negative integers with k > j and a \geq b ). These requirements are weaker than those for a symmetrical k -tuple error correcting, (k+a) -tuple error detecting, code and hence may be used to generally obtain more code characters for a given character length than are obtainable in the k, (k+a) -case. If the channel is highly asymmetric, it may be sufficient to detect and correct only one type of error. An earlier paper considered the case of single 1-error correction and showed that it was always possible to obtain more code characters than exist in known single error correcting codes of equivalent character length except in cases where the symmetric code is "close-packed." In this paper codes are developed for k -tuple 1-error correction which also yield more code characters than symmetrical k -tuple error correcting codes of the same length. The correction scheme is generally symbol-correcting, but may require message-correction of binary sequences whose length is approximately (k+l)^{-1} that of the code characters. A double 1-error correcting code is discussed in some detail and examples of code generation and correction are included.

Boolean algebra is the algebra of classes or sets of objects. It consists essentially of systematic rules for the use of the fundamental connectives "or," "and," "not." The relevance of Boolean algebra to the information-handling field stems from the fact that, in digital systems, information can be represented only by means of sets of discrete physical states of the machinery involved. This paper has been prepared principally to present an adequate mathematical basis for the application of Boolean algebra to the study of information-handling systems. An important purpose of this application is the minimization of the physical elements required in information-handling (or computing) circuits. Consequently, some fundamental methods of simplifying Boolean functions are explained in detail. These methods make possible the unconditional minimization of what are called here "elementary" functions, but of these functions only. Because much of the symbolism and many of the methods in use at the present time are far from uniform, another purpose of this paper has been to put into use an adequate and consistent symbolism, to provide needed fundamental definitions and to derive all theorems and propositions required from the basic postulates. The treatment is essentially an algebraic one. The methods are those of abstract algebra rather than of mathematical logic. The dualization laws have been systematically used to derive fundamental principles which cannot conveniently be obtained in any other way. The application of Boolean algebra to the design of computer circuits is illustrated by actual examples.

The relationship between multivalued switching algebra and Boolean algebra is presented by introducing different definitions for the complements of multivalued variables. For every definition introduced, the paper points out which Boolean algebra theorems are valid for multivalued cases, which are invalid, and gives proofs to substantiate the claim. It is shown that DeMorgan's theorem holds for all four definitions of complement given in this paper. One definition allows us to map the multivalued variables into binary variables. Under this definition, all axioms and theorems of Boolean algebra are satisfied and can be used for minimization of any multivalued switching function f. Illustrative examples for minimizing f and its complement f are given.

Part I of this paper contributes methods, theorems, formulas and graphs to meet a previously unfilled need in dealing with certain types of two-dimensional probability problems — especially those relating to alternating current transmission systems and networks, in which the variables occur naturally in complex form and thus are two-dimensional. The paper is concerned particularly with “normal” probability functions (distribution functions) in two dimensions, which are analogous to the familiar “ normal” probability functions in one-dimensional probability problems. It supplies a comprehensive set of graphs for the probability that a “normal” complex chance-variable deviates from its mean value by an amount whose magnitude (absolute value) exceeds any stated value; in other words, the probability that the chance-variable lies without any specified circle centered at the mean value in the plane of its “scatter-diagram,” that is, in the complex plane of the chance-variable. It gives a comprehensive treatment of the distribution-parameters of the “normal” complex chance-variable, and convenient formulas for the necessary evaluation of these parameters. For use in various portions of the paper, as well as for various possible outside uses, it supplies a considerable number of formulas and theorems on “mean values” (“expected values”) of complex chance-variables.

In recent years a number of nonlinear codes have been discovered which have better error-correcting capabilities than any known linear codes. However, very little is known about the properties of such codes. In this paper we study the most basic property, the weight enumerator. The weight of a codeword is the number of its nonzero components; the weight enumerator gives the number of codewords of each weight, and is fundamental for obtaining the error probability when the code is used for error-correction on a noisy channel. In 1963 one of us showed that the weight enumerator of a linear code is related in a simple way to that of the dual code (Jessie MacWilliams, “A Theorem on the Distribution of Weights in a Systematic Code,” Bell System Technical Journal, 42, No. 1 (January 1963), pp. 79–94). In the present paper, which is a sequel, we show that the same relationship holds for the weight enumerator of a nonlinear code. Furthermore, a definition is given for the dual α⊥ of a nonlinear binary code α which satisfies (α⊥)⊥ = α provided α contains the zero codeword.

This paper presents a method for the realization of a given nth order node conductance (or capacitance or reciprocal inductance) matrix as an (n + 1) -node network with all positive elements and no ideal transformers. The first part establishes simple relations between branch conductances and elements in the given matrix which are assumed to be based upon a linear tree. These relations are analogous to the well-known ones pertinent to a so-called "dominant" matrix based upon the starlike tree. In an analysis problem they enable one to compute a single driving-point or transfer impedance with a minimum of computations. The second part of the paper develops a method whereby one can readily determine whether a given G matrix is based upon a tree (the necessary condition for its realization) and find the pertinent geometrical tree configuration when one exists. Once the latter is established, realization is simple and straightforward. The entire process requires no repeated trials and proceeds toward the desired goal with a minimum of effort.

The purpose of this paper is to demonstrate that it is possible to communicate over a memoryless channel of capacity C at any rate R with a probability of error less than 2^{-E(R)\nu},E(R)>0 , per block of a length approximately proportional to \nu^{2} and with a computational decoding complexity which is asymptotically proportional to \nu^{2} when \nu is large. The decoding scheme presented in this paper is based on a two-cycle iteration of a decoding procedure which has been described in an earlier paper [1 ].

Graph theoretic techniques provide a convenient tool for the investigation of the vulnerability of a communication network to either natural or enemy-induced damage. In this paper, the communication network is represented by a nonoriented linear graph, and the problem of synthesizing networks to provide optimal. protection against damage is investigated. Damage is associated with the removal of a set of nodes that disconnects the graph or by the removal of a set of edges that disconnects the graph. It is assumed that fixed cost for edges may be envisioned as prescribing the total number of edges allowed to connect a given number of nodes. A class of graphs that provides optimum damage protection for a fixed cost is then derived. Bipartite graphs are investigated in detail. It is shown that the complete bipartite graph is also an optimal damage-resistant net and that it can be decomposed into Hamiltonian cycles to yield optimal graphs of lower order. Another possible criterion of optimality is introduced and studied. This new measure is the minimum number of edges that must be deleted in order to isolate a given number of nodes. It is then shown that the complete bipartite graph is also optimal with respect to this alternative measure of vulnerability. This paper also contains proofs of several new and interesting graph theoretic results.

This paper presents a method of synthesizing a circuit to obtain a transfer function whose poles lie on the negative real axis and whose zeros lie anywhere in the complex frequency plane including the positive real axis by means of two parallel resistance-capacitance (R-C) ladders and an ideal transformer. The polynomial in the numerator of the given transfer function is first resolved into the difference of two component polynomials whose zeros are all negative real numbers. The method of resolution is based on conditions for collinearity of points that represent nth degree polynomials (with real coefficients) in n-dimensional space. The two component polynomial fractions for the given transfer function are then synthesized into two R-C ladders and the resulting network is the parallel combination of these two ladders through an ideal transformer and terminated by another R-C ladder. The method applies to more generalized cases and usually gives a network that contains less resistive and capacitive elements than any of the other methods available. If the resolution of the numerator polynomial is as a sum of polynomials instead of a difference, more than two components may be required. An expression for the upper bound to the least number of such components is also included in the paper.

A general analytical technique described in this paper permits the extension of Z -transform methods to sampled-data systems containing synchronized switches which do not operate with the same sampling rate. Sampling periods of each switch are first expressed in the form T/p_{1} ... T/p_{n} (where p_{1} ... p_{n} are integers not equal to zero) and then it is shown that each switch with a period T/p can be replaced by a system of switches and advance and delay elements where each switch operates with a sampling period T . In this way, the original sampled-data system can be represented by an equivalent system containing switches operating with the same sampling rate. The general solution of such equivalent systems is outlined in this paper.

In this paper we make a beginning in the hitherto unexplored problem of finding absolute minimal expressions of Boolean functions. We shall adhere to the notations and terminology introduced in our previous paper,1 which will be referred to as S. In the present paper, we shall find absolute minimals for Boolean functions whose point set complex consists of either one or two points. The case of one point is in Theorem 1, Section I. The case when the two points form a 1-cell is covered by Theorem 4, Section I which discusses an arbitrary dimensional cell. The case when the cell complex consists of two isolated points, the main theme of this paper, is dealt with in Section II.

This paper contains some applications of an elementary study of unate truth functions. One application is a method of deciding when a truth function is linearly separated, i. e., is expressible as a linear polynomial inequality in its arguments (letting 1 represent truth and 0 represent falsity). Other applications are to contact nets and to rectifier nets. Much of the material of this paper, although not in print, is well known to some logicians and switching theorists. Nothing from the first three sections is original.

This paper examines the following M -level pulse-amplitude modulation (PAM) sequential communication system. Given that one of the M signals is repetitively sent over an additive Gaussian channel during successive intervals of time, what is the optimum sequential procedure to follow at the receiver in order to pick the correct signal with a probability of wrong selection no greater than \epsilon? The optimum procedure is defined to be one that minimizes the expected number of transmissions (sample size) before a decision is reached. The paper extends the results of Hecht for the "simultaneous" test procedure (also obtained independently by the author). This paper shows the following. 1) The maximum a posteriori (MAP) test procedure is shown to be comparable in performance with the simultaneous test. 2) MAP test with a threshold 1 - e does not yield error probabilities equal to e if M \geq 3 . 3) Lower bounds on the expected sample sizes for any test procedure for the M -level PAM are obtained with the results from Hoeffding and Simons. 4) Both the simultaneous and the MAP tests are shown to achieve the lower bound when \epsilon \rightarrow 0 . 5) Approximations used by Hecht for the simultaneous test are made rigorous and slightly tighter expressions of error probability than the ones given by Hecht are obtained for some cases. 6) Energy savings of both the MAP and the simultaneous tests over the nonsequential scheme are presented for different values of M .

Analysis and synthesis techniques for a class of sequential discrete-state networks are discussed. These networks, made up of arbitrary interconnections of unit-delay elements (or of trigger flip-flops), modulo-p adders, and scalar multipliers (modulo \alpha , prime p ), are of importance in unconventional radar and communication systems, in automatic error-correction circuits, and in the control circuits of digital computers. In addition, these networks are of theoretical significance to the study of more general sequential networks. The basic problem with which this paper is concerned is that of finding economical realizations of such networks for prescribed autonomous (excitation-free) behavior. To this end, an analytical-algebraic model is described which permits the investigation of the relation between network logical structure and state-sequential behavior. This relation is studied in detail for nonsingular networks (those with purely cyclic behavior). Among the results of this investigation is the establishment of relations between the state diagram of the network and a characteristic polynomial derived from its logical structure, An operation of multiplication of state diagrams is shown to correspond to multiplication of the corresponding polynomials. A criterion is established for the realizability of prescribed cyclic behavior by means of linear autonomous sequential networks. An effective procedure for the economical realization of such networks is described, and it is shown that linear feedback shift registers constitute a canonical class of realizations. Examples are given of the realization procedure. The problem of synthesis with only one-cycle length specified is also discussed. A partial solution is obtained to this "don't care" problem. Some special families of feedback shift registers are investigated in detail, and the state-diagram structures are obtained for an arbitrary number of stages and an arbitrary (prime) modulus. Mathematical appendixes are included which summarize the pertinent results in Galois field theory and in the factorization of cyclotomic polynomials into irreducible factors over a modular field. The relation of the theory developed in this paper to Huffman's description of linear sequence transducers in terms of the D operator is discussed, as well as unsolved problems and directions for further generalization.

In this paper, the cyclic nature of AN codes is defined after a brief summary of previous work in this area is given. New results are shown in the determination of the range for single-error-correcting AN codes when A is the product of two odd primes p_1 and p_2 , given the orders of 2 modulo p_1 and modulo p_2 . The second part of the paper treats a more practical class of arithmetic codes known as separate codes. A generalized separate code, called a multiresidue code, is one in which a number N is represented as \begin{equation} [N, \mid N \mid _ {m1}, \mid N \mid _{m2}, \cdots , \mid N \mid _{mk}] \end{equation} where m_i are pairwise relatively prime integers. For each AN code, where A is composite, a multiresidue code can be derived having error-correction properties analogous to those of the AN code. Under certain natural constraints, multiresidue codes of large distance and large range (i.e., large values of N ) can be implemented. This leads to possible realization of practical single and/or multiple-error-correcting arithmetic units.

In this paper an efficient method of generating separating sets of a given graph with the use of a newly defined concept-a cutset graph-is discussed. The cut-set graph of a given graph G is defined such that each edge of the graph corresponds to a pair of basic branch cut-sets of G having the relation that the ring sum of these cut-sets coincides with an incident cut-set with respect to a vertex in G . The present paper shows that the cut-set graph is a useful tool for solution of the problem of generating all of the basic vertex cut-sets and the basic mixed cut-sets of a given graph.

This paper considers necessary and sufficient conditions for the canonic realization of a reactance function Z(s) in terms of cascaded nonsymmetric LC lattice sections defined in the paper. These conditions are stated in terms of the requirement that if Z'(s) is the derivative of Z(s) with respect to s , then j\omega^{2} Z'(j\omega) Z'(\omega) = Z (\omega) Z(j\omega) must have a real positive root \omega = \omega_0 . Extensions of these conditions to one-port, RLC networks are also considered.

The linear graph, after a delay of about a hundred years from its conception by Kirchhoff, is today rapidly assuming a dominant position in the foundation of electric network theory. This paper is a presentation, by definition and properties deducible therefrom, of a new class of subgraphs (segs) which includes stars and cut sets as special cases. The matrix associated with the seg can be shown to be the general coefficient matrix of the Kirchhoff current equations. Hence, in addition to adding to the structure of linear graph theory, the results in this paper broaden the base of knowledge of currents in electric networks. This broadened base has already permitted the opening of a new phase of network theory and can certainly be expected to open others.

The n-station communication net, when used as a channel in a larger net, can be used in n^{2} - n different ways. These ways are considered in an interesting series of papers concerning the relations among the n^{2}- n utilizations. The present paper continues the series by completely solving this terminal capacity realizability problem in the domain of generalized nets which admit negative channel capacities. The procedure is then to attack the problem of equivalence between (generalized) nets and communication nets. Although the equivalence theory developed here is not yet complete, the present work shows it to be a promising avenue for further exploration; and the incomplete theory itself has already produced one important new result in the theory of communication nets proper: a necessary and sufficient realizability condition for terminal capacity specifications which demand the maximum possible number of distinct terminal capacities.

A numerical method for evaluating the complex integral I = \frac{1}{2\pij} \oint \frac{B(z)B(z^{-1})}{A(z)A(z^{-1})} \frac{dz}{z} along the unit circle in a positive direction (where A and B are polynomials with real coefficients), is presented in this paper. The method developed in this paper is shown to be obtainable as a FORTRAN program as well as a table form. The results achieved represent significant reduction of the computations compared to other existing methods.

This paper continues the series based on the use of matrices in the design of switching networks. To avoid redundancy within the series, all previous papers on matrix logic are considered as prerequisite, in particular, references 1 and 2. This paper establishes a general classification scheme for logical functions, as follows: 1. General symmetric functions, which are the sum of ordinary symmetric functions. 2. Trivial and redundant functions. 3. Universal functions, which are capable of performing any logical functions by appropriate iterations.

A review of various papers dealing with p-n-p-n device characteristics shows essentially different interpretations of 1) the condition for switching and 2) the operating state defined by \alpha_{p}+ \alpha_{N} = 1 . The present paper attempts to show the relationship between these various papers and to clarify the conditions which exist at the switching point and holding point.

This paper presents the general concept of a weighted directed graph which we call a net. Illustrative examples leading up to the definition of a net indicate its applicability to a wide variety of problems in communication and network theory. A number of theorems concerning the proper paths of a net are established. A non-arithmetic matrix calculus is developed to facilitate computations and formalize proofs. In later papers, the techniques presented here will be exploited in the study of the theory of sequential machines.

In an effort to relate various existent schools of thought, this paper describes four models of probabilistic finite-state systems, giving necessary and sufficient conditions for reciprocal describability. An algorithm for the realization (synthesis) of a stochastic sequential machine by a deterministic machine and additive noise is presented. Different definitions of equivalence are listed and related by theorems, the most important of which states that "behavioral equivalence" with the same cutpoints for sequence recognizers is identical to "stochastic equivalence" (indistinguishability) for sequence transducers. Corollaries show the import of these results to the state minimization problem. The paper composes a strong case in favor of the adoption of J. W. Carlyle's model as a unifying one.

This paper disproves Darlington's conjecture that every RC -grounded two-port is equivalent to a series-parallel two-port. The proof depends upon the construction of a counterexample. This counterexample is a six-node RC -grounded two-port, whose admittance functions Y_{11} = N_{11}/D, -Y_{12} = N_{12}/D, Y_{22} = N_{22}/D, written without common factors, have compact poles at the zeros of D and for which N_{12} has a negative coefficient. In accordance with properties of RC series-parallel networks derived in an earlier paper, the network of the counterexample cannot be equivalent to any RC series-parallel two-port.

The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.

In an earlier paper the author proved a conjecture of Vowels: if f/g is a positive function, so is f'/g' , i.e., the positive property is preserved on differentiating the numerator and denominator. This paper generalizes this transformation process by the use of certain classes, of linear operators, both for general positive functions and for 2-element-type network functions, for which characterization theorems are first established.

A class of binary encoding algorithms called Harper codes has been studied previously as a means of encoding numbers for transmission over an idealized binary channel. This paper considers a more general and practical transmission system model. For any Harper code, it presents a technique for obtaining the expression for the average absolute numerical error that occurs during transmission. It shows that all Harper codes do not exhibit the same average absolute numerical error for all transmission systems that satisfy the model. However, there is a subset of Harper codes such that all codes in the subset give identical performance. The paper defines the subset and presents an expression for the average absolute numerical error for any Harper code in the subset. The subset is important because it includes the natural binary representation, the Gray code, and the folded binary code.

In a classic paper by Guillemin,[ E. A. Guillemin, "New methods of driving-point and transfer impedance synthesis," Proc. of Symp. on Modern Network Synthesis, Polytechnic Inst. of Brooklyn, N. Y., vol. 5, p. 119; 1955.] the synthesis of a dissipationless LC "zero-section" filter which has quadruplet zeros of transmission was demonstrated. Guillemin's procedure involved the factorization of (1) below. In this paper an alternate process for the realization of such a zero section is presented. The computational processes involved in this method are simpler than those required in Guillemin's method because factorization of (1) is not required.

This paper is concerned with the synthesis of the voltage transfer function of an unterminated RC ladder network. Given A (p) = \frac{V_2}{V_1} = K \frac{N(p)}{D(p)} the constraint on N and D is well known and the realization procedure is straightforward. However, for many applications, it is important to realize the maximum possible gain ( K \max ) associated with a given transfer function. This paper presents a method of determining K_{\max} from the given A(p) . Furthermore, it is shown that if the maximum gain occurs at dc or at infinite frequency, K_{\max} can be realized exactly. If the maximum gain occurs at a finite frequency, K_{\max} can be approached arbitrarily closely.