Search

An analytical method of designing recognition functions in self-organizing systems is discussed in this paper. A mathematical model is defined which embodies recognition and learning processes based on past experiences. The ``desired function'' is introduced as the most faithful expression of recognition functions based on past experiences, and it is shown how to design the recognition function whose mean-square error from the desired function is minimized. The desired function makes it possible to utilize the orthonormal relationship between certain functions of inputs, and this gives a very simple design procedure for recognition functions. Also, since the desired function is a probability function of past experiences, the problems of learning and education can be discussed on a quantitative basis. Two concepts, forced education and statistical classification, are used in combination with the minimization technique of the mean-square error, and this gives a simple design procedure to improve the approximation abilities. The approximation abilities of linear recognition functions are studied in this paper for all linearly separable Boolean functions with two through six inputs.

The purpose of this paper is to give an over-all view of the FORMAC language. FORMAC is an experimental programming system designed to permit the manipulation of mathematical expressions. The paper includes a brief description of the FORMAC language and samples of complete FORMAC programs. It should be noted that FORMAC is an experimental program, and that at the present time IBM has no intention of releasing it to their customers.

This paper considers a class of information sources consisting of text and pictures. The text is English language text appearing in scientific and technical documents. The picture sources are the largely schematic pictures that occur in the same class of documents. However, the discussion is broadened slightly to include other picture sources. For a tiny fragment of English, the paper shows how the syntactic structure of text may be described, and then goes on to suggest that a similar analysis may be performed on the class of pictures under study. The description of these two kinds of information sources with a single class of descriptive techniques is suggested as an alternative to the synthetic approach in which artificial languages are specified and then learned and used. The major reason for doing syntactical analysis of such sources discussed here is that several information processing operations, amounting to the interpretation of the information sources looked upon as languages, can be done by the technique of syntax direction which uses the results of syntactic analysis to mediate subsequent processes for manipulating the information tokens. The paper concludes with an illustration of an algorithm for matching the sentences given by a simple grammar against the class of simple pictures which these sentences purport to describe.

Error analysis in the computer simulation of dynamic systems is fundamentally a variational problem. The computing errors are small variations of the computed solutions with respect to the exact solution of the differential equations being integrated. It is not surprising, therefore, that many of the mathematical tools used to perform error analysis in the computer simulation of dynamic systems are similar to those used in the variational or perturbational analysis of those systems themselves. Fundamental papers in this direction have been published previously [8], [9], [13]. The present paper, however derives the error-propagation equations in a more basic form, which makes it easier to apply such variational mathematical tools as Liapunoff's second method to analyze error stability, and Pontryagin's maximum principle to study ``worst-case'' errors in computation.

In engineering and scientific problems one of the most commonly used tools is Fourier analysis. With the increasing availability of analog, hybrid, and digital computers, it is useful to examine special techniques applicable to these machines. This paper presents: 1) methods for evaluating the required integrals on either a digital or an analog computer and 2) an analysis which results in guidelines for choosing the sampling interval when the problem is done digitally. Parts of the material presented in this paper can be found in other sources although there are some refinements included here that make the implementation of the theory considerably easier. The theory is valid for any machine, but minor modifications may have to be made in hybrid computer patching or in the digital program to conform with equipment restrictions.

Several papers have been written and published on various aspects of the SOLOMON computer. This paper describes the final design of the computer, from a total system viewpoint. The paper consists of three major portions: a brief description of the system organization, a description of the functional capabilities of the computer, i.e., the instruction set, and a description of the physical system, i.e., type of circuitry and packaging techniques utilized.

This paper discusses certain concepts and sample results in the techniques of system effectiveness analysis with particular attention to availability. It turns out that the contemporary concept of system effectiveness can be usefully viewed as a generalization of prior concepts relating to system availability. Central to the paper's approach is a presentation of the need for redefinition of system availability. While on the one hand some 18 definitions are available in the literature, this latter concept is not broad enough for complex systems; the implied binary situation of a system being either UP or DOWN is not an accurate enough model for such systems. System effectiveness, which has been evolved to replace availability, arises from attempts to unify treatment of the statistics of system state behavior and transition behavior, of the performance capability associated with these states and transitions, and of the interaction of the performance statistics within the conditions of the problem. The analytic techniques developed are of particular power when dealing with redundant and modular systems. A comparative effectiveness evaluation of 10 alternative computer system designs, all having the same basic performance, is exhibited; this analysis was performed with respect to a given sample functional requirement.

This paper concerns the application of a result of Arden and Arthurs to a particular finite-state machine, the accumulator. Arden and Arthurs have shown that given a complete set of devices for some fixed sequence rate, any finite-state machine may be constructed from these devices to operate at this maximum rate. In this paper we consider the construction of a good representation (in terms of overall delay) of the m-bit accumulator, operating at the maximum rate. Examples are presented using state-of-the-art devices which illustrate the construction and give measures of usefulness and cost Of this accumulator.

This paper studies a class of switching networks which are constructed by cascading two-input, single-output completely flexible binary logical cells. It is assumed that each cell can be adjusted at will in order that any one of the sixteen possible switching functions of its two binary inputs may be obtained at its single output lead. An n-input cascaded network is composed of n-l, two-input, single output logical cells. The inputs to a typical cell Ai consist of a signal variable Xi and the output ai from the preceding cell Ai-1. For the end cell A1 the inputs are the signal variables X0 and X1. The output is derived from the terminal cell An-1. In view of the growing interest in the area of ``self-organizing'' or ``adaptive'' switching networks, the study of the type of network just discussed seems to be pertinent. The results presented here are pertinent to typical n-input cascaded structures, and consist of characterization and enumeration of the class of all n-place realizable switching functions, test procedure for the determination of the realizability of arbitrary n-place switching functions, and finally determination of all possible cascaded structures for synthesis of realizable n-place switching functions. The paper develops some new techniques especially suited to the present study. These techniques may also hopefully find applications in other types of logic synthesis.

The paper presents a factual account of the trip of the 1959 U. S. technical delegation in computers to the Soviet Union. It includes the itinerary, descriptions of specific Soviet computers, descriptions of certain computing centers, a discussion of Soviet computer-oriented education, and a description of current circuit and component development. In appendices are given the instruction repertoire of the URAL-I and the URAL-II machines, and an analysis of some magnetic cores. The paper is extensively illustrated and contains a bibliography of relevant Soviet documents.

The networks considered in this paper consist of n identical combinational logic cells connected in cascade through bi-directional discrete information channels. All switching is done synchronously with unit time delay through each cell. Three classes of networks are formed according to whether or not information flow in one direction along the cascade is dependent upon that in the other. Steady-state behavioral relationships between the three classes are discussed, and the class having mutually dependent information flow is shown to be the only one which can exhibit steady-state memory properties. The main object of the paper is to derive several theorems concerning these memory properties. The last section interprets some previous results of Hennie as a start on the transients and cycling problems.

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.

Coincident-current techniques, usually associated with parallel ferrite-core stores, may also be used for the operation of serio-parallel or purely serial memories. After outlining, in block diagram form, one possible physical realization of a serial system, the paper examines the conditions under which such a store is economically justified. The distinguishing feature of the system discussed is that coincidence is established in the memory matrix between two currents representing an address signal and a time signal, respectively. Studies of the characteristics and economics of serio-parallel devices are however not reported in detail. It is shown how the properties of the time-controlled serial store may lead to the adoption of a word-asynchronous design for serial digital computers. In such a machine, timing is not controlled or determined by limited store access. As examples, the paper indicates how the serial techniques facilitate the incorporation into small serial computers, of autonomous transfers, automatic floating point operations, high speed multiplication, division and shift orders and asynchronous transfers between, say, a high speed store and a magnetic drum.

Many papers have been written about the reflected binary system and it is well known in the computer field for analog-to-digital conversion. The method used in creating this system may be extended to systems of bases other than two. It is the purpose of this paper to carry this extension to its logical conclusion. The author describes how reflected systems of different bases may be composed. The equations for translating between the conventional and reflected systems are then derived. It is also demonstrated how the reflected binary system is a special case of reflected number systems and how the general case simplifies for the reflected binary case.

The paper describes a proposed microprogrammed interface computer, ``Intergraphic,'' which will link many (initially 13; potentially more than 50) general-purpose graphical terminals to a central processor. Intergraphic will generate new images once only, at high speed (10-MHz incremental plotting rates) on one of several small, electrostatically deflected, precision CRT's. The images will be generated on a 1024 by 1024 grid in incremental and random-point display modes by fast microcode sequences which interpret display lists from the central processor. The centrally generated images will be scan converted to standard television video signals and recorded on a multitrack video disk(s), each track refreshing a low-cost standard television terminal. User feedback will be via raster coordinates, determined by a light-pen (``raster-pen'') and simple counting circuits at each terminal. The paper concentrates on the digital interface structure which is versatile and fast (3-5 ns integrated circuits and 100-ns cycle-time READ-only memory). The description centers on display generation, although the structure is largely general purpose. The proposed operating system is outlined only since it is in an early stage of development. Also, the order-code accompanying data from the central processor is incomplete. However, new orders can be readily interpreted by adding microprograms to the READ-only memory (i.e., ``firmware,'' not hardware extensions); thus, the interface will also be a useful medium for experimentation in graphical structures and communication.

The purpose of this paper is to present a simple template-matching pattern recognition technique by using any general-purpose associative memory. The input patterns for recognition may have wide variations, provided that the distinct features of individual pattern classes can be extracted. Each pattern class is allowed to have deviations in size, style, orientation, etc. within certain limits. This pattern recognition technique is extremely efficient in handwritten character recognition, which is used for illustration in this paper. Because each input pattern is processed with all the pattern classes simultaneously, the speed of this pattern recognition technique is very high. It is found that most input patterns are recognized within first comparison process and no input patterns require more than two comparison processes for their recognition.

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

This paper presents the results of an attempt to automate part of a formalized method of system design. Basic to this method are two languages, Boolean algebra and a register transfer language. From a Boolean algebra description a digital system can be constructed while the second language can be used in a step by step description of the execution of each instruction. To illustrate, a register transfer language is used to give a description of an adder considered as part of a digital system. This description is then translated into a set of Boolean equations. Next, the automation of this translation by using a syntax-directed compiler is explained. The compiler requires a syntactic description of register transfers. This description is given using a meta-language called Backus normal form. A Backus normal form description of Boolean equations that is used for translating Boolean equations into register transfers is also given; this translation process is called analysis. The feasibility of computer-aided design and analysis is thereby demonstrated. The computer-aided design method described in this paper, besides eliminating drudgery and error, would permit several system designs to be attempted and evaluated; a permanent record of the chosen system would also be available for future modifications, maintenance, and simulation. The analysis programs could be used to check the effect on the system of any changes made in the Boolean equations (or equivalently the logical diagrams) and the effect of any unused operation codes.

A bibliography containing 63 references to papers dealing with NOR and NAND gate design and application composes this paper. References are primarily taken from journals published in the United States. They are mainly presented as an aid to those interested in this area of computer circuitry rather than as a listing of credit to those who have done work in NOR and NAND logic and related fields. A one or two sentence summary is given for each reference.

In this study, an investigation was made to discover methods of storing more bits on a Williams tube than can be stored by conventional methods. Read-around was ignored because the object was to explore the Williams tube as a secondary memory for non-random access operations. Proceeding on this basis, it was found that a four-fold increase in packing is possible with established techniques, and an even greater increase with other methods described in this paper. Such a memory is more versatile than a magnetic drum, as shown by the example of machine organization presented in this paper.

This paper presents a synthesis method of ternary digital systems by means of a threshold algebra. The method is based on the fact that the K operations of any ternary function can be expressed as threshold operations on a set of functions called midterms. Such midterms can be easily generated from the outputs of the ternary multivibrators described by the authors in a previous paper [4]. The Quine method is extended to the minimization of ternary threshold normal forms. RTL circuits implementing the operations are described, and the threshold design of a fast carry propagation ternary adder is outlined in order to illustrate the method.

In an early paper [1], McCluskey and Unger counted the number of distinct state assignments for synchronous sequential machines. Their formula, however, does not account for all distinct state assignments when the memory function in a realization is performed by delay elements alone. This note amends their formula by establishing the conditions for its validity and by deriving the appropriate expression under other conditions. An example illustrating the effect of using the McCluskey-Unger formula in a case where it does not apply can be found in a recent paper by Dolotta and McCluskey [2]. In their paper, a procedure is proposed for selecting a state assignment that has an associated economical realization. Their method implicitly restricts the memory units to be delay elements, and some distinct state assignments are not considered. Consequently, a number of realizations are over-looked. A minor modification in the Dolotta-McCluskey algorithm is suggested so that all distinct state assignments are taken into account. In some cases this revised procedure results in a more economical realization than the unmodified one.

This paper presents a synthesis method of ternary digital systems by means of a threshold algebra. The method is based on the fact that the K operations of any ternary function can be expressed as threshold operations on a set of functions called midterms. Such midterms can be easily generated from the outputs of the ternary multivibrators described by the authors in a previous paper [4].

Two corrections are presented: (1) The authors of the paper "An Algorithm for Linear Inequalities and Applications," which appeared on pages 683-688 of the October, 1965, issue of these Transactions, has called the following to the attention of the Editor. It was established in this paper that the algorithm converges to the solution (if one exists) in a finite number of steps and that the convergence is exponential. We would like to point out that, for any finite algorithm, exponential convergence is superfluous since it is always possible to find an exponential trajectory which dominates any strictly decreasing and finite trajectory. The particular proof for exponential convergence in the paper is, however, erroneous. Nevertheless, this fact "will not disturb any of the results, theoretical or experimental, mentioned in the paper. We would like to thank C.C. Blaydon for this correction and Prof. T.M. Cover for his suggestions during the review of the paper. Correction (2): The author of the short note "Logical Design of Analog-to-Digital Converters," which appeared on pages 740-741 of the October, 1965, issue of these Transactions, has called the following to the attention of the Editor. On page 740, column 2, the next to the last line, there is a comma after "the most significant bit" which should be deleted.

The fast Fourier transform algorithm, reported by Cooley and Tukey, results in substantial computational savings and permits a considerable amount of parallel computation. By making use of these features, estimates of the spectral components of a time function can be calculated by a special-purpose digital machine while the function is being sampled. In this paper, two digital machine organizations are suggested which use the algorithm for the case of N (the number of samples analyzed) being a power of 2 and the case of N being the product of two integers. The first machine consists of shift registers and arithmetic units organized in stages which perform calculations in parallel. It can be used when N is a power of 2 and can accept signals being sampled at a rate exceeding 500 000 samples per second. The second machine requires fewer shift registers and only one arithmetic unit but cannot operate in a continuous manner. This means that either a dead time between adjacent records of data must be allowed or a time compression unit must be used. In the first case the obtainable sampling rate depends upon the dead time which can be allowed between adjacent records of data. In the second case sampling rates up to 8000 samples per second are feasible. For this analyzer, N is required to be expressible as the product of two integers.

A method of monitoring the program execution in a digital computer on the basis of the flow diagram of the computing program has been devised. A comparatively low-cost equipment for monitoring a maximum of 64 boxes in a flow diagram has been constructed. The monitoring method is flexible and convenient in its application. It can be used in connection with relative or symbolic addresses, compilers, etc. The user must provide only a flow diagram drawn on translucent paper in a certain form and the information to correlate this diagram with the computing program. A subroutine modifies the computing program as needed for the monitoring purpose and restores it to its original form when the user so desires. The monitoring introduces only a very small increase in computing time, requiring for each call-up of a box in the flow diagram only a time amounting to that needed for two simple unconditional jumps. The monitor can be used to present during the computation a visual dynamic picture of the progress of the program and to register, on occurrence, the whereabouts of an interruption, thus facilitating the tracing of the error. The principle of the monitoring method and the subroutine program, and the essentials of the constructed monitor equipment, are described in detail.

The object of this paper is to study feedback in sequential machines, to classify (according to their seriousness) and analyze errors which arise in the state transitions of machines, and to establish some relations between feedback and errors. It is shown that the previously developed algebraic methods1,2 supply the necessary tools and a rigorous basis for this theory, and relate these new results to previously obtained results about the structure of sequential machines. For example, this work yields the necessary methods to detect the existence of a decomposition of machines into component machines so that the most ``serious'' errors of the computation can occur only in an isolated component machine. This leads to the possibility of imposing selectively different reliability conditions on the component machines to achieve high over-all reliability of the realizations.