Switching Machines

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.