Switching Machines : Volume 1: Combinational Systems Introduction to Sequential Systems

We shall begin this brief section with what we consider to be its objective. It will be followed by the main outline and then concluded by a few notes as to how this work should be used. Although logical systems have been manufactured for some time, the theory behind them is quite recent. Without going into historical digressions, we simply remark that the first comprehensive ideas on the application of Boolean algebra to logical systems appeared in the 1930's. These systems appeared in telephone exchanges and were realized with relays. It is only around 1955 that many articles and books trying to systematize the study of such automata, appeared. Since then, the theory has advanced regularly, but not in a way which satisfies those concerned with practical applications. What is serious, is that aside the books by Caldwell (which dates already from 1958), Marcus, and P. Naslin (in France), few works have been published which try to gather and unify results which can be used by the practis­ ing engineer; this is the objective of the present volumes.

1/Boolean Algebra.- 1.1. Introduction.- 1.2. Binary number systems—codes.- 1.3. Postulates and theorems of Boolean algebra.- 1.3.1. Postulates.- 1.3.2. Other relations.- 1.4. Boolean functions.- 1.4.1. Truth tables.- 1.4.1.1. Generalities.- 1.4.1.2. Some particular functions.- 1.4.2. The designation number of a Boolean function.- 1.5. Reduction of Boolean functions—Map representation.- 1.5.1. Veitch maps.- 1.5.2. Karnaugh maps.- 1.6. Reduction of Boolean functions (continued)—McCluskey-Quine method.- 1.7. Reduction of functions containing ‘don’t care’ terms.- 1.8. Factorization of Boolean functions.- 1.8.1. Basic notions of Boolean matrices.- 1.8.2. Matrix representation of a Boolean function.- 1.8.3. Aspect of the problem of decomposition of a Boolean function.- 1.8.3.1. Example of decomposition.- 1.8.3.2. Matrix analysis of the decomposition.- 1.8.3.3. Determination of matrix T.- 1.8.4. Properties of matrix T.- 1.8.4.1. Number of ‘1’s’ of matrix T.- 1.8.4.2. Construction of matrix[T].- 1.8.4.3. Multiplication of a Boolean matrix on the right by a pseudo-unitary matrix.- 1.8.5. Application to the solution of the two types of decomposition problems.- 1.8.5.1. Problem of the 1st type.- 1.8.5.2. Problem of the 2nd type.- 1.8.6. Case of a non-solvable problem of the 1st type.- 1.8.6.1. Antecedent and consequent solution.- 1.8.6.2. Decomposition using an antecedent solution.- 1.8.6.3. Decomposition using the consequent solution.- 1.9. Conclusions.- Appendixes.- 1.A.1. Transposition of two variables in the designation number of a function.- 1.A.3. Consensus method.- 1.A.4. Minimal conjunctive form—Minimal disjunctive form.- 1.A.5. Quine-McCluskey algorithm—Generalizations.- 1.A.5.1. Lagrange’s function.- 1.A.5.2. Canonical forms of a Boolean function of n variables.- 1.A.5.3. General expression for the normal form of a Boolean function.- 1.A.5.4. Quine-McCluskey minimization algorithm.- 1. A.5.5. Application of the Quine-McCluskey method.- 1.A.5.6. Choice of prime implicants.- l.A.5.7. Practical application of the Quine-McCluskey method.- Exercises.- 2/Practical Realization of Logical Functions.- 2.1. Introduction.- 2.2. Elementary notions.- 2.3. The relay.- 2.3.1. Memory mounting.- 2.3.2. Special relays.- 2.4. Electronic circuits—Positive and negative logics.- 2.5. Diode circuits.- 2.5.1. Diode gates.- 2.6. Transistor circuits.- 2.6.1. Transistor-resistor gates.- 2.6.2. Transistor-diode gates.- 2.6.3. Directly coupled transistors.- 2.6.4. Note on vacuum tube circuits.- 2.7. Flip-flop and memory transistorized logics.- 2.7.1. Utilization of pulses.- 2.7.2. Memory.- 2.7.3. Application to input-output rectification.- 2.7.4. Flip-flops.- 2.8. Tunnel Diodes.- 2.9. Magnetic circuits.- 2.10. Cryotrons.- 2.11. Fluidic logic.- 2.11.1. Fluidic logical devices using mechanical displacement.- a. Flapper valve obturation networks.- b. Spool valve networks.- c. Ball systems.- 2.11.2. Logical fluidic devices without mechanical displacement.- a. Amplifiers.- b. Jet interaction networks.- c. Boundary layer control.- 2.12. Integrated circuits.- 2.13. Logical simulators.- Exercises.- 3/Combinational Systems.- 3.1. Introduction.- 3.2. Boolean algebra and technology.- 3.2.1. The algebra of relay circuits.- 3.2.2. Diode circuit algebra.- 3.2.3. Transistor circuit algebra.- 3.3. Combinational systems.- 3.4. Combinational dipoles.- 3.4.1. Combinational dipole analysis.- 3.4.2. Combinational dipole synthesis.- 3.4.2.1. Cost of a circuit.- 3.4.2.2. Karnaugh and Quine-McCluskey methods.- 3.4.2.3. Utilization of Boolean matrices for the realization of dipoles.- 3.5. Study of combinational multipoles.- 3.5.1. Analysis of combinational multipoles.- 3.5.2. Synthesis of a combinational multipole.- 3.5.2.1. Extension of the McCluskey method.- 3.5.2.2. Utilization of Boolean matrices in multipole design.- 3.6. Matrix analysis of combinational relay systems.- 3.6.1. Introduction to the method.- 3.6.2. Connection matrix.- 3.6.2.2. Properties of the connection matrix.- 3.6.3. Application of connection matrices to combinational multipoles.- 3.6.3.1 Node removal or addition in a network.- 3.6.3.2 Addition of supplementary nodes to a circuit.- 3.6.4. Elimination of redundant terms.- 3.6.4.1 Type one.- 3.6.4.2 Type two of series redundant terms.- 3.6.4.3 Type 3 redundant terms.- 3.6.5. Example of a multipole synthesis.- 3.6.6. Partial equivalence of combinational multipoles.- 3.6.6.1 Definition.- 3.6.6.2 Application to combinational dipoles.- 3.6.6.3 Application to combinational multipoles.- 3.6.6.4 Example.- 3.6.6.5 Comments.- 3.6.7. Graph of a circuit-matrix associated with the graph.- 3.6.8. Properties of a circuit’s topological matrix.- 3.6.8.1 Determination of the number of loops in a circuit.- 3.6.8.2 Determination of paths of a given length.- 3.7. Comparison between the general simplification method of Boolean functions and the matrix analysis method in relay systems.- 3.A.1. Symmetric functions.- 3.A.2. Elementary symmetric functions.- 3.A.3. Properties of the symmetric functions.- 3.A.4. Realization of the symmetric functions.- 3.A.5. Iterative circuits.- Exercises.- 4/Introduction to Sequential Systems.- 4.1. Review of the general properties of transient phenomena in combinational Systems.- 4.1.1. Equation and graph of combinational systems.- 4.1.2. Transients in combinational systems.- 4.2. Sequential systems—Analysis.- 4.2.1. Single loop systems.- 4.2.1.1. Method of study.- 4.2.1.2. Validity of the method.- 4.2.1.3. First series of conclusions.- 4.2.2. Systems having several loops.- 4.2.2.1. Relays systems.- 4.2.2.2. Type 2 systems.- 4.2.3. Equations and representation of a sequential system.- 4.2.4. Internal variables of a type 2 sequential system.- 4.2.4.1. Search for internal variables.- 4.2.4.2. Determination of the sufficient number of internal variables.- 4.2.4.3. Determination of the minimal number of internal variables.- 4.2.5. Performance of a sequential system.- 4.3. Synthesis problems—Definitions of the internal state.- 4.4. Internal state—Technological state.- 4.5. Conclusion.- Appendix—Physical interpretation of the choice of internal variables.- Exercises.- 5/Representation and Classification of Sequential Systems.- 5.1. Introduction.- 5.2. Flow table of a sequential system.- 5.2.1. Necessity of the flow table.- 5.2.2. Construction of the flow table.- 5.2.3. Utilization of the flow table.- 5.2.4. Flow table—excitation and output matrices.- 5.3. Asynchronous and synchronous machines.- 5.3.1. Introduction.- 5.3.2. Example of an asynchronous machine.- 5.3.3. Definition of synchronous machines.- 5.3.4. Comparison between the different realizations.- 5.3.5. Realization of the synchronous system.- 5.4. Moore, Mealy, and Huffman machines.- 5.4.1. Mealy and Moore machines.- 5.4.2. Asynchronous machines—representation by Huffman flow table.- 5.4.3. Correspondence between the Huffman flow table and the flow table.- 5.4.3.1. Mealy transform of a Huffman flow table.- 5.4.3.2, Mealy tables associated with Huffman flow tables.- 5.5. Complementary notions.- 5.5.1. Flow diagram.- 5.5.1.1. Flow diagram of a Mealy machine.- 5.5.1.2. Flow diagram of Moore machines.- 5.5.1.3. Some characteristics of sequential machines.- 5.5.2. Transition matrix.- 5.5.2.2. Properties of the transition matrix.- 5.A.1. Representation of the asynchronous machines by sequence charts.- 5.A.2. Moore’s machine and Mealy’s machine.- 5.A.2.1. Introduction: passage from a Moore machine to an equivalent Mealy machine.- 5.A.2.2. First proof of the existence of a Moore machine equivalent to a given Mealy machine.- 5.A.2.3. Second proof.- 5.A.2.4. Utilization of the transition matrix.- 5.A.2.5. Comparison of the methods.- Exercises.- 6/Analysis of Sequential Systems Hazards in Sequential and Combinational Systems.- 6.1. Analysis of asynchronous sequential systems.- 6.1.1. Asynchronous relay systems.- 6.1.1.1. Construction of the flow table.- 6.1.1.2. Construction of the Huffman flow table.- 6.1.1.3. Construction of the flow diagram.- 6.1.1.4. Graph of performance of an asynchronous system.- 6.1.1.5. Construction of the transition table.- 6.1.1.6. Construction of the transition matrix.- 6.1.2. Characteristic properties of asynchronous sequential systems.- 6.1.2.1. Cycles.- 6.1.2.2. Races.- 6.1.2.3. Examples of a critical race.- 6.1.2.4. Example of a non-critical race.- 6.1.2.5. Example of a critical race on primary variables.- 6.1.2.6. Example of non-critical races of primary variables.- 6.1.2.7. Adjacency condition in an asynchronous sequential system.- 6.1.3. Electronic asynchronous systems.- 6.2. Analysis of synchronous sequential systems.- 6.2.1. Synchronized asynchronous systems.- 6.6.2. Pulsed systems.- 6.2.2.1. Symmetric flip-flop circuits.- 6.2.2.2. SR flip-flop circuits.- 6.3. Hazards in combinational and sequential systems.- 6.3.1. Nature of the problem.- 6.3.2. Static hazards.- 6.3.2.1. Definition.- 6.3.2.2. Static hazards and technology.- 6.3.2.3. Notions of cut-sets and tie-sets.- 6.3.2.4. Search for static hazards.- 6.3.2.5. Elimination of static hazards.- 6.3.3. Dynamic hazards.- 6.3.3.1. Definition.- 6.3.3.2. Search for dynamic hazards.- 6.3.3.3. Dynamic hazard and technology.- 6.3.3.4. Elimination of dynamic hazards.- 6.3.4. Multiple input change hazards.- 6.3.4.1. Definition.- 6.3.4.2. Elimination of the race hazard.- 6.3.5. Superposition of static and dynamic hazards.- 6.3.5.1. Analysis.- 6.3.5.2. Synthesis.- 6.4. Hazards in asynchronous sequential systems.- 6.4.1. Change-over hazards in sequential systems.- 6.4.1.1. Relays systems.- 6.4.1.2. Electronic systems.- 6.4.2. Propagation hazards in electronic systems.- 6.4.2.1. Analysis of a sequential system by means of graphs.- 6.4.2.2. Definition of propagation hazards.- 6.4.2.3. Elimination of the propagation hazard.- 6.4.3. Transient hazards in electronic circuits driven by switches and using NOR, OR operators.- 6.4.3.1. Cause of transient hazards in electronic circuits.- 6.4.3.2. Analysis of hazards due to the inputs in electronic circuits.- 6.4.4. Simulation of a propagation hazard.- 6.4.5. Propagation delay in the loops.- 6.5. Hazards in synchronous systems.- 6.5.1. Many input gate.- 6.5.2. Minimal input width.- 6.5.3. Hazards due for pulse width.- 6.5.4. Half-pulse hazards.- 6.5.5. Hazards at outputs.- Exercises.