Design Methods for Digital Systems

This book constitutes an introduction to the theory of binary switch­ ing networks (binary logic circuits) such as are encountered in industrial automatic systems, in communications networks and, more particularly, in digital computers. These logic circuits, with or without memory, (sequential circuits, combinational circuits) play an increasing part in many sectors of in­ dustry. They are, naturally, to be found in digital computers where, by means of an assembly (often complex) of elerpentary circuits, the func­ tions of computation and decision which are basic to the treatment of information, are performed. In their turn these computers form the heart of an increasing number of digital systems to which they are coupled by interface units which, themselves, fulfil complex functions of information processing. Thus the digital techniques penetrate ever more deeply into industrial and scientific activities in the form of systems with varying degrees of specialization, from the wired-in device with fixed structure to those systems centered on a general-purpose programmable com­ puter. In addition, the present possibility of mass producing microminiaturi­ sed logic circuits (integrated circuits, etc. ) gives a foretaste of the intro­ duction of these techniques into the more familiar aspects of everyday life. The present work is devoted to an exposition of the algebraic techni­ ques nesessary for the study and synthesis of such logic networks. No previous knowledge of this field of activity is necessary: any technician or engineer possessing an elementary knowledge of mathematics and electronics can undertake its reading.

1 General Concepts.- 1.1 Digital Systems.- 1.2 Sets.- 1.2.1 The Concept of a Set.- 1.2.2 Equality of Two Sets.- 1.2.3 Subsets. Inclusion Relation.- 1.2.4 Complement of a Set.- 1.2.5 Union and Intersection of Sets.- 1.2.5.1 Union.- 1.2.5.2 Intersection.- 1.2.6 Empty Set. Universal Set.- 1.2.7 Set of Subsets.- 1.2.8 Cover of a Set.- 1.2.9 Partition of a Set.- 1.2.10 Cartesian Product of Sets.- 1.2.11 Application. Counting the Elements of a Set.- 1.3 Relations.- 1.3.1 Relations between the Elements of a Number of Sets.- 1.3.2 Notation.- 1.3.3 Graphical Representation of a Binary Relation.- 1.3.4 Some Properties of Binary Relations.- 1.3.4.1 Reflexivity.- 1.3.4.2 Symmetry.- 1.3.4.3 Transitivity.- 1.3.5 Equivalence Relations.- 1.3.6 Equivalence Classes.- 1.4 Univocal Relations or Functions.- 1.5 Concept of an Algebraic Structure.- 2 Numeration Systems. Binary Numeration.- 2.1 Numbers and Numeration Systems.- 2.2 Decimal System of Numeration.- 2.3 Numeration System on an Integer Positive Base.- 2.4 Binary Numeration System.- 2.4.1 Binary Numeration.- 2.4.2 Binary Addition and Subtraction.- 2.4.2.1 Addition.- 2.4.2.2 Subtraction.- 2.4.3 Binary Multiplication and Division.- 2.4.3.1 Multiplication.- 2.4.3.2 Division.- 2.4.4 Systems to the Base 2P (p ? 1).- 2.5 Passage from One Numeration System to Another.- 2.5.1 First Method.- 2.5.2 Second Method.- 2.6 Decimal-Binary and Binary-Decimal Conversions.- 2.6.1 Conversion of a Decimal Number to a Binary Number.- 2.6.2 Conversion of a Binary Number to a Decimal Number.- 2.6.3 Other Conversion Methods.- 2.6.3.1 Successive Subtraction Method.- 2.6.3.2 Mixed Method (Binary-Octal-Decimal).- 2.6.3.3 Mixed Method (Binary-Hexadecimal).- 3 Codes.- 3.1 Codes.- 3.2 The Coding of Numbers.- 3.2.1 Pure Binary Coding.- 3.2.2 Binary Coded Decimal Codes (BCD Codes).- 3.2.2.1 Principle.- 3.2.2.2 The Number of 4-Positions BCD Codes.- 3.2.2.3 4-Bit Weighted BCD Codes.- 3.2.2.4 Non-Weighted 4-Bit BCD Codes.- 3.2.2.5 BCD Codes Having More than 4 Positions.- 3.3 Unit Distance Codes.- 3.3.1 Definition (Binary Case).- 3.3.2 Reflected Code (Gray Code, Cyclic Code).- 3.3.2.1 Construction of a Reflected Code with n Binary Digits.- 3.3.2.2 Conversion Formulae.- 3.3.3 The Usefulness of Unit Distance Codes.- 3.4 Residue checks.- 3.4.1 Residue Checks.- 3.4.2 Residue Checks Computation.- 3.4.2.1 Modulo m Residues of the Powers of an Integer.- 3.4.2.2 Examples.- 3.4.3 Examples of Congruence.- 3.4.3.1 Problem.- 3.4.3.2 Counters.- 3.4.3.3 True Complement.- 3.5 The Choice of a Code.- 3.5.1 Adaptation to Input-Output Operations.- 3.5.2 Adaptation to Digital Operations.- 3.5.3 Aptitude for the Automatic Detection or Correction of Errors.- 4 Algebra of Contacts.- 4.1 Electromagnetic Contact Relays.- 4.2 Binary Variables Associated with a Relay.- 4.3 Complement of a Variable.- 4.4. Transmission Function of a Dipole Contact Network.- 4.4.1 Transmission of a Contact.- 4.4.2 Transmission of a Dipole Comprising 2 Contacts in Series.- 4.4.3 Transmission of a Dipole Consisting 2 Contacts in Parallel.- 4.5 Operations on Dipoles.- 4.5.1 Complementation.- 4.5.2 Connections in Series.- 4.5.3 Connections in Parallel.- 4.5.4 Properties of Operations ?, and +.- 4.5.5 2 Variable Functions.- 4.5.6 Examples of Application.- 5 Algebra of Classes. Algebra of Logic.- 5.1 Algebra of Classes.- 5.2 Algebra of Logic (Calculus of Propositions).- 5.2.1 Propositions. Logic Values of a Proposition.- 5.2.2 Operations on Propositions.- 5.2.2.1 Operation AND (Logical Product).- 5.2.2.2 Operation OR (Or-Inclusive).- 5.2.2.3 Negation of a Proposition.- 5.2.3 Compound Propositions and Functions of Logic.- 5.2.4 Numeric Notation of Logic Values.- 5.2.5 Other Logic Functions.- 5.2.5.1 2 Variable Functions.- 5.2.5.2 Function “Exclusive-OR” (P ? Q).- 5.2.5.3 Equivalence (P ? Q).- 5.2.5.4 Implication (P? Q).- 5.2.5.5 Sheffer Functions (P/Q) (“Function NAND”).- 5.2.5.6 Peirce Function (P j Q) ?(“Function NOR”).- 5.2.6 Tautologies. Contradictions.- 5.2.7 Some Properties of the Functions AND, OR and Negation.- 5.2.8 Examples and Applications.- 5.2.9 Algebra of Logic (Propositional Calculus).- 5.2.10 Functional Logic.- 5.2.10.1 Propositional Functions.- 5.2.10.2 Operations on Propositional Functions.- 5.2.10.3 Quantifiers.- 5.2.11 Binary Relations and Associated Propositions.- 5.2.12 Classes Associated with a Property or with a Relationship.- 5.2.13 Operations on Propositions and on Classes.- 5.3 Algebra of Contacts and Algebra of Logic.- 5.4 Algebra of Classes and Algebra of Contacts.- 5.5 Concept of Boolean Algebra.- 6 Boolean Algebra.- 6.1 General. Axiomatic Definitions.- 6.2 Boolean Algebra.- 6.2.1 Set. Operations.- 6.2.2 Axioms for a Boolean Algebra.- 6.3 Fundamental Relations in Boolean Algebra.- 6.4 Dual Expressions. Principle of Duality.- 6.4.1 Dual Expressions.- 6.4.2 Principle of Duality.- 6.4.3 Notation.- 6.5 Examples of Boolean Algebra.- 6.5.1 2-Element Algebra.- 6.5.2 Algebra of Classes.- 6.5.3 Algebra of Propositions.- 6.5.4 Algebra of n-Dimensional Binary Vectors.- 6.6 Boolean Variables and Expressions.- 6.6.1 Boolean Variables.- 6.6.2 Boolean Expressions.- 6.6.3 Values for a Boolean Expression. Function Generated by an Expression.- 6.6.4 Equality of 2 Boolean Expressions.- 6.6.5 Canonical Forms Equal to an Algebraic Expression.- 6.6.5.1 Expressions Having 1 Variable.- 6.6.5.2 Expressions Having n Variables.- 6.6.5.3 Dual Expressions.- 6.6.6 A Practical Method for the Determination of a Complement.- 6.6.7 Reduction to one Level of the Complementations Contained in an Expression.- 6.6.8 Relationship between a Dual Expression and its Complement.- 7 Boolean Functions.- 7.1 Binary Variables.- 7.2 Boolean Functions.- 7.2.1 Definition.- 7.2.2 Truth Table for a Boolean Function of n-Variables.- 7.2.3 Other Means of Defining a Boolean Function.- 7.2.3.1 Characteristic Vector.- 7.2.3.2 Decimal Representations.- 7.2.4 Number of Boolean Functions Having n Variables.- 7.3 Operations on Boolean Functions.- 7.3.1 Sum of two Functions f + g.- 7.3.2 Product of two Functions f · g.- 7.3.3 Complement of a Function f.- 7.3.4 Identically Null Function (0).- 7.3.5 Function Identically Equal to 1 (1).- 7.4 The Algebra of Boolean Functions of n Variables.- 7.5 Boolean Expressions and Boolean Functions.- 7.5.1 Boolean Expressions.- 7.5.2 Function Generrated by a Boolean Expression.- 7.5.3 Equality of 2 Expressions.- 7.5.4 Algebraic Expressions for a Boolean Function.- 7.5.4.1 Fundamental Product.- 7.5.4.2 Disjunctive Canonical Form of a Function with n Variables.- 7.5.4.3 Fundamental Sums.- 7.5.4.4 Conjunctive Canonical Form of a Function with n Variables.- 7.5.4.5 Some Abridged Notations.- 7.5.4.6 Partial Expansions of a Boolean Function.- 7.6 Dual Functions.- 7.6.1 Dual of a Dual Function.- 7.6.2 Dual of a Sum.- 7.6.3 Dual of a Product.- 7.6.4 Dual of a Complement.- 7.6.5 Dual of a Constant Function.- 7.7 Some Distinguished Functions.- 7.7.1 n-Variables AND Function.- 7.7.2 n-Variables OR Function.- 7.7.3 Peirce Function of n-Variables (OR-INV-NOR).- 7.7.4 Sheffer Function in n-Variables (AND-INV-NAND).- 7.7.5 Some Properties of the Operations ? and/. Sheffer Algebra.- 7.7.5.1 Expressions by Means of Operations (+),(.),(?).- 7.7.5.2 Properties of Duality for ? and /.- 7.7.5.3 Sheffer Algebrae.- 7.7.5.4 Expressions for the Operations ., +, and ? with the aid of the Operations ? and / (n-Variables).- 7.7.5.5 Canonical Forms.- 7.7.5.6 Some General Properties of the Sheffer and Peirce Operators.- 7.7.6 Operation ?.- 7.8 Threshold Functions.- 7.8.1 Definition.- 7.8.2 Geometrical Interpretation.- 7.8.3 Particular Case: Majority Function.- 7.9 Functionally Complete Set of Operators.- 7.10 Determination of Canonical Forms.- 7.11 Some Operations on the Canonical Forms.- 7.11.1 Passage from one Canonical Form to Another.- 7.11.2 Complement of a Function f Given in Canonical Form.- 7.12 Incompletely Specified Functions.- 7.13 Characteristic Function for a Set.- 7.14 Characteristic Set for a Function.- 8 Geometric Representations of Boolean Functions.- 8.1 The n-Dimensional Cube.- 8.1.1 Example: — 2-Variable Functions.- 8.1.2 3-Variables Functions.- 8.1.3 Functions of n-Variables (any n).- 8.1.3.1 Sets (E1) and E2).- 8.1.3.2 Relation of Adjacency between 2 Vertices.- 8.1.3.3 Geometric Representation.- 8.1.4 Other Representations and Definitions.- 8.1.4.1 The n-Dimensional Cube.- 8.1.4.2 The k-Dimensional Sub-Cube of an n-Dimensional Cube (0?k?n).- 8.1.4.3 Distance of 2 Vertices of an n-Dimensional Cube.- 8.2 Venn Diagrams.- 8.3 The Karnaugh Diagram.- 8.3.1 The Case of 4 Variables (or less).- 8.3.2 Karnaugh Diagrams in 5 and 6 Variables.- 8.3.2.1 The 5-Variable Case.- 8.3.2.2 The Case of 6-Variables.- 8.3.3 Decimal Notation.- 8.3.4 The Karnaugh Diagram and the Representation of Functions in Practice.- 8.3.4.1 Notations.- 8.3.4.2 Derivation of a Karnaugh Diagram.- 8.4 The Simplification of Algebraic Expressions by the Karnaugh Diagram Method.- 8.4.1 Karnaugh Diagram Interpretations for the Sum, Product and Complementation Operations.- 8.4.1.1 Sum.- 8.4.1.2 Product.- 8.4.1.3 Complement.- 8.4.2 Representation of Certain Remarkable Functions.- 8.4.2.1 Variables.- 8.4.2.2 Product of k Variables (k > 1).- 8.4.2.3 Fundamental Sums.- 8.4.3 The Use of the Karnaugh Diagram for the Proof of Algebraic Identities.- 9 Applications and Examples.- 9.1 Switching Networks. Switching Elements.- 9.2 Electronic Logic Circuits. Gates.- 9.2.1 Gates.- 9.2.2 Logics.- 9.2.3 Logic Conventions.- 9.2.4 Diode Logic.- 9.2.5 Direct Coupled Transistor Logic (DCTL).- 9.2.6 Diode-Transistor Logic (DTL).- 9.3 Combinational Networks. Function and Performance. Expressions and Structure.- 9.4 Examples.- 9.4.1 An Identity.- 9.4.2 Binary Adder and Subtractor.- 9.4.2.1 Addition.- 9.4.2.2 Subtraction.- 9.4.3 Restricted Complement of a Number (Complement to ‘1’).- 9.4.4 True Complement of a Number.- 9.4.5 Even Parity Check.- 9.4.6 Addition of 2 Numbers Having Even Parity Digits.- 9.4.7 Comparison of 2 Binary Numbers.- 9.4.8 V-Scan Encoder Errors.- 9.4.8.1 Error Pattern.- 9.4.8.2 Principle of the V-Scan Encoder.- 9.4.8.3 Relation between the Value Available at a Brush and the Digits of the Number x to be Read Out.- 9.4.8.4 Error Caused by the Failure of a Single Brush.- 9.4.8.5 The length of an Error Burst.- 9.4.8.6 Numerical Value of the Error e = y ? x.- 9.4.8.7 Examples.- 9.4.9 Errors of a Reflected Binary Code Encoder.- 9.4.10 Detector of Illicit Combinations in the Excess-3 Code.- 10 The Simplification of Combinational Networks.- 10.1 General.- 10.2 Simplification Criterion. Cost Function.- 10.3 General Methods for Simplification.- 10.3.1 Algebraic Method.- 10.3.2 Karnaugh Diagram Method.- 10.3.3 Quine-McCluskey Algorithm.- 10.3.4 Functional Decomposition Method (Ashenhurst, Curtis, Povarov).- 10.4 The Quine-McCluskey Algorithm.- 10.4.1 Single-Output Networks.- 10.4.1.1 Statement of the Problem.- 10.4.1.2 Geometrical Interpretation of the Minimisation Problem.- 10.4.1.3 n-Dimensional Cube and Sub-Cubes.- 10.4.1.4 Maximal k-Cubes.- 10.4.1.5 Statement of the Problem of Minimisation.- 10.4.1.6 Properties of the Minimal Cover.- 10.4.1.7 Essential Maximal k-Cubes.- 10.4.1.8 Quine-McCluskey Algorithm (Geometrical Interpretation).- 10.4.1.9 Incompletely Specified Functions.- 10.4.1.10 Product of Sums.- 10.4.2 Multi-Output Circuits.- 10.5 Functional Decompositions.- 10.5.1 Simple Disjoint Decompositions.- 10.5.1.1 Definition.- 10.5.1.2 Number of Partitions (YZ) of Variables.- 10.5.1.3 Necessary and Sufficient Condition for the Existence of a Simple Disjoint Decomposition.- 10.5.1.4 Other form of Criterion of Decomposability. Column Criteria.- 10.5.1.5 Theorem.- 10.5.1.6 Theorem.- 10.5.1.7 Theorem.- 10.5.1.8 Theorem.- 10.5.1.9 Theorem.- 10.5.2 Simple Disjoint Decompositions and Maximal Cubes.- 10.5.3 Simple Non-Disjoint Decompositions.- 11 Concept of the Sequential Network.- 11.1 Elementary Example. The Ferrite Core.- 11.1.1 Read-Out.- 11.1.2 Writing.- 11.2 Ecoles-Jordan Flip-Flop.- 11.2.1 Type S-R Flip-Flop (Elementary Register).- 11.2.2 Type T Flip-Flop (Elementary Counter, Symmetric Flip-Flop).- 11.3 Dynamic Type Flip-Flop.- 11.3.1 Type S-R Flip-Flop.- 11.3.2 Type T Flip-Flop.- 11.4 Some Elementary Counters.- 11.4.1 Dynamic Type Flip-Flop Pure Binary Counter.- 11.4.2 Gray Code Counter with Eccles-Jordan Type T Flip-Flops.- 11.4.3 Gray Code Continuous Level Counter.- 11.4.4 Random Impulse Counter.- 12 Sequential Networks. Definitions and Representations.- 12.1 Quantization of Physical Parameters and Time in Sequential Logic Networks.- 12.1.1 Discrete Time.- 12.1.2 Operating Phases. Timing Signals.- 12.1.2.1 Synchronous Systems.- 12.1.2.2 Asynchronous Systems.- 12.2 Binary Sequential Networks. General Model.- 12.2.1 Inputs.- 12.2.2 Outputs.- 12.2.3 Internal States.- 12.2.4 Operation.- 12.2.5 Present and Future States. Total State. Transitions.- 12.2.6 Concept of a Finite Automaton.- 12.2.7 Synchronous and Asynchronous Sequential Networks.- 12.2.7.1 Synchronous Sequential Networks.- 12.2.7.2 Asynchronous Sequential Networks.- 12.3 Sequential Networks and Associated Representations.- 12.3.1 Logic Diagrams.- 12.3.2 Equations and Truth Tables.- 12.3.3 Structural Representations.- 12.3.3.1 Alphabets.- 12.3.3.2 Words, Sequences, Sequence Lengths.- 12.3.3.3 Transitions. Transition and Output Functions.- 12.3.3.4 Successors. Direct Successors Indirect Successors.- 12.3.3.5 Transition Table. Table of Outputs.- 12.3.3.6 Graphical Representation of a Sequential Network.- 12.3.3.7 Connection Matrix.- 12.3.4 Representations as a Function of Time.- 12.3.4.1 Literal Representation.- 12.3.4.2 Sequence Diagram.- 12.4 Study of the Operation of Sequential Networks.- 12.4.1 Synchronous Circuits.- 12.4.2 Asynchronous Networks.- 12.4.2.1 Sequential Network Diagram.- 12.4.2.2 Equations.- 12.4.2.3 Truth Tables.- 12.4.2.4 Differential Truth Table.- 12.4.2.5 Stable States.- 12.4.2.6 Table of Transitions and Outputs. Graph.- 12.4.2.7 Cycles with Constant Input.- 12.4.2.8 Hazards.- 12.4.2.9 Races.- 12.4.2.10 Phase Diagram (Huffmann).- 12.5 Adaptation of the Theoretical Model to the Physical Circuit.- 12.6 Some Supplementary Physical Considerations.- 12.6.1 Synchronous Networks.- 12.6.2 Asynchronous Networks.- 12.6.3 Physical Duration of States.- 12.6.4 Delay Elements.- 12.6.5 Synchronisation.- 12.6.6 State Stability.- 12.6.7 Memory.- 12.6.8 Synchronous and Asynchronous Viewpoints.- 12.7 Incompletely Specified Circuits.- 12.8 Sequential Networks and Combinatorial Networks.- 13 Regular Expressions and Regular Events.- 13.1 Events.- 13.1.1 Definition.- 13.1.2 Empty Sequence ?.- 13.1.3 Empty Set of Sequences ø.- 13.2 Regular Expressions. Regular Events.- 13.2.1 Regular Operations.- 13.2.1.1 Union of A and B (A?B).- 13.2.1.2 Product (Concatenation) of A and B (A.B).- 13.2.1.3 Iteration of an Event A (A*).- 13.2.2 Function ?(A).- 13.2.3 Properties of Regular Operations.- 13.2.4 Generalised Regular Operations.- 13.2.4.1 Intersection of 2 Events A and B (A?B).- 13.2.4.2 Complement of an Event A (?).- 13.2.4.3 Boolean Expression E(A,B).- 13.2.4.4 Event E1 = (t)t?pE.- 13.2.4.5 Event E2= (Et)t?pE.- 13.2.5 Regular Expressions.- 13.2.6 Regular Events.- 13.2.7 Set Derived from a Regular Event. Derivation of a Regular Expression.- 13.2.7.1 Derivatives with Respect to a Sequence of Length 1.- 13.2.7.2 Derivatives with Respect to a Sequence of Length >1.- 13.2.8 Properties of Derivatives.- 13.2.8.1 Examples of the Determination of Derivatives.- 13.3 Regular Expressions Associated with a States Diagram.- 13.3.1 Moore Diagram.- 13.3.2 Mealy Diagram.- 13.3.3 Example: Series Adder.- 14 The Simplification of Sequential Networks and Minimisation of Transition Tables.- 14.1 Introduction.- 14.1.1 Performance.- 14.1.1.1 Completely Specified Circuits.- 14.1.1.2 Incompletely Specified Circuits.- 14.1.2 Cost Function.- 14.2 Minimisation of the Number of States for a Completely Specified Table.- 14.2.1 Some Preliminary Considerations.- 1...