Design Methods for Digital Systems

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.- 14.2.2 Equivalent States.- 14.2.2.1 States in the Same Table T.- 14.2.2.2 State Appertaining to 2 Tables T and T?.- 14.2.3 Covering of Table T by T?.- 14.2.4 Successor to a Set of States.- 14.2.5 Reduction of a Table. Successive Partitions Pk.- 14.2.6 Algorithm for the Minimum Number of Internal States and its Practical Application.- 14.2.7 Example.- 14.3 Minimisation of the Number of Internal States for an Incompletely Specified Table.- 14.3.1 Interpretation of Unspecified Variables.- 14.3.2 Applicable Input Sequences.- 14.3.3 Compatibility of 2 Partially Specified Output Sequences.- 14.3.4 Compatibility of 2 States qi and qi.- 14.3.5 Compatibility of a Set of n States (n > 2).- 14.3.6 Compatibility of States and Simplification of Tables.- 14.3.6.1 Covering of a Sequence Z by a Sequence Z?.- 14.3.6.2 Covering of a State qi of a Table T by a State q?i of a Tabled T.- 14.3.6.3 Covering of a Table T by a Table T?.- 14.3.7 Properties of Compatibles.- 14.3.8 Determination of Compatibles.- 14.3.8.1 Compatible Pairs.- 14.3.8.2 Compatibles of the Order ? 2. Maximal Compatibles.- 14.3.9 Determination of a Table T' Covering T, Based on a Closed Set of Compatibles.- 14.3.10 Determination of a Minimal Table T.- 14.3.11 Another Example of Minimisation.- 15 The Synthesis of Synchronous Sequential Networks.- 15.1 General.- 15.1.1 The Direct Method.- 15.1.2 The State Diagram Method.- 15.2 Direct Method. Examples.- 15.3 State Diagram Method.- 15.4 Diagrams Associated with a Regular Expression.- 15.4.1 Development of a Regular Expression from a Base.- 15.4.2 Interpretation in Terms of Derivatives.- 15.4.3 Algorithm for the Synthesis of a Moore Machine.- 15.4.4 Algorithm for the Construction of a Mealy Machine.- 15.4.5 Examples of Synthesis.- 15.4.6 Networks Having Several Binary Outputs.- 15.5 Coding of Initial States. Memory Control Circuits.- 16 counters.- 16.1 Introduction.- 16.2 Pure Binary Counters.- 16.2.1 Up-Counting and Down-Counting in Pure Binary Code.- 16.2.1.1 Up-Counting.- 16.2.1.2 Down-Counting.- 16.2.1.3 Counting in Pure Binary: Other Formulae.- 16.3 Decimal Counters.- 16.4 Reflected Binary Code Counters.- 16.4.1 Recurrence Relations in Gray Code Counting.- 16.4.2 Down-Counting.- 16.4.3 Examples of Counters.