ECE 120 Introduction to Computing Department of Electrical and Computer Engineering University of Illinois at Urbana Champaign 2000 2022 Steven S Lumetta All rights reserved ii 2000 2022 Steven S Lumetta All rights reserved The bulk of these notes was developed for the ECE 120 class at the University of Illinois at Urbana Champaign but some material was taken from my previous lecture notes for ECE 290 written around 2000 ECE 190 written around 2004 and ECE 391 written around 2004 Doug Jones was my co conspirator in developing the new design and both he and Geo rey Herman o ered frequent and helpful feedback on early drafts for which I am grateful Numerous other instructors have also given me feedback over the years including but not limited to Volodymyr Kindratenko Wen mei W Hwu Suma Bhat Juan Jos e Jaramillo David Varodayan Donna Brown Ujjal Bhowmik and Kirill Levchenko Where the notes are more easily read thanks are due to them Remaining mistakes should be attributed to me As part of ECE Illinois determination to make our curricula more inclusive I have also decided to consciously identify and eliminate any non inclusive and potentially o ensive terminology from our course materials In the rare cases in which I feel that students may encounter such terms in their careers I may mention their previous use I also encourage you to report any remaining instances to me directly 2000 2022 Steven S Lumetta All rights reserved Contents 1 1 The Halting Problem 1 1 1 Universal Computing Machines 1 1 2 The Halting Problem 1 2 The 2 s Complement Representation 1 2 1 Review of Bits and the Unsigned Representation 1 2 2 Picking a Good Representation 1 2 3 The Unsigned Add Unit 1 2 4 Deriving 2 s Complement 1 2 5 An Algebraic Approach 1 2 6 Negating 2 s Complement Numbers 1 3 Over ow Conditions 1 3 1 Implication and Mathematical Notation 1 3 2 Over ow for Unsigned Addition 1 3 3 Over ow for 2 s Complement Addition 1 4 Logic Operations 1 4 1 Truth Tables 1 4 2 Boolean Logic Operations 1 4 3 Over ow as Logic Expressions 1 4 4 Logical Completeness 1 4 5 Implications of Logical Completeness 1 4 6 Examples and a Generalization 1 5 Programming Concepts and the C Language 1 5 1 The C Programming Language 1 5 2 Data Types 1 5 3 Variable Declarations 1 5 4 Expressions and Operators 1 5 5 Basic I O 1 5 6 Types of Statements in C 1 5 7 Program Execution 1 5 8 Compilation and Interpretation 1 5 9 The C Preprocessor 1 5 10 Changing Types in C 1 6 Summary of Part 1 of the Course 2 1 Optimizing Logic Expressions 2 1 1 De ning Optimality iii 1 1 1 3 3 3 3 4 5 6 7 7 7 8 11 11 11 13 14 16 16 18 18 19 21 21 22 24 25 27 28 28 30 33 33 iv CONTENTS 2 1 2 Terminology 2 1 3 Veitch Charts and Karnaugh Maps 2 1 4 Canonical Forms 2 1 5 Two Level Logic 2 1 6 Multi Metric Optimization 2 2 Boolean Properties and Don t Care Simpli cation 2 2 1 Logic Properties 2 2 2 Choosing the Best Function 2 2 3 Caring about Don t Cares 2 2 4 Generalizations and Applications 2 3 Example Bit Sliced Addition 2 3 1 One Bit at a Time 2 3 2 Abstracting the Human Process 2 3 3 Designing the Logic 2 3 4 Adders and Word Size 2 4 Example Bit Sliced Comparison 2 4 1 Comparing Two Numbers 2 4 2 An Abstract Model 2 4 3 A Representation and the First Bit 2 4 4 Optimizing Our Design 2 4 5 Extending to 2 s Complement 2 4 6 Further Optimization 2 5 Using Abstraction to Simplify Problems 2 5 1 Subtraction 2 5 2 Checking ASCII for Upper case Letters 2 5 3 Checking ASCII for Lower case Letters 2 5 4 The Multiplexer 2 6 Sequential Logic 2 6 1 Storing One Bit 2 6 2 The Clock Abstraction 2 6 3 Static Hazards Causes and Cures 2 6 4 Dynamic Hazards 2 6 5 Essential Hazards 2 6 6 Proof Outline for Clocked Synchronous Design 2 7 Registers 2 7 1 Registers 35 36 40 40 41 44 44 44 45 48 49 49 49 50 51 53 53 53 54 56 57 58 59 59 60 62 63 65 65 67 69 70 71 72 73 73 CONTENTS v 74 76 79 79 80 82 84 86 87 87 89 89 90 90 91 92 93 94 94 95 97 99 2 7 2 Shift Registers 2 8 Summary of Part 2 of the Course 3 1 Serialization and Finite State Machines 3 1 1 Serialization General Strategy 3 1 2 Serialization Comparator Example 3 1 3 Finite State Machines 3 1 4 Synchronous Counters 3 1 5 Ripple Counters 3 1 6 Timing Issues 3 1 7 Machine Models 3 2 Finite State Machine Design Examples Part I 3 2 1 Steps in the Design Process 3 2 2 Example A Two Bit Gray Code Counter 3 2 3 Example A Three Bit Gray Code Counter 3 2 4 Example A Color Sequencer 3 2 5 Identifying an Initial State 3 2 6 Developing an Abstract Model 3 2 7 Specifying I O Behavior 3 2 8 Completing the Speci cation 3 2 9 Choosing a State Representation 3 2 10 Abstracting Design Symmetries 3 2 11 Impact of the State Representation 3 3 Design of the Finite State Machine for the Lab 100 3 3 1 Physical Design Sensors and Timing 100 3 3 2 An Abstract Model 101 3 3 3 Picking the Representation 102 3 3 4 Testing the Design 103 3 4 Extending Keyless Entry with a Timeout 105 3 5 Finite State Machine Design Examples Part II 107 3 5 1 Design of a Vending Machine 107 3 5 2 Encoders and Decoders 109 3 5 3 Vending Machine Implementation 111 3 5 4 Design of a Game Controller 113 3 5 5 Analysis of a Stoplight Controller 115 3 6 Random Access Memories 118 3 6 1 Memory 118 vi CONTENTS 3 6 2 Static Random Access Memory 119 3 6 3 Tri State Bu ers and Combining Chips 122 3 6 4 Dynamic Random Access Memory 123 3 7 From FSM to Computer 126 3 7 1 Specifying the Problem 126 3 7 2 Choosing Components and Identifying States 127 3 7 3 Laying Out Components 129 3 7 4 Control and Data 130 3 7 5 State Representation and Logic Expressions 131 3 8 Summary of Part 3 of the Course 132 4 1 Control Unit Design 135 4 1 1 LC 3 Datapath Control Signals 135 4 1 2 Example Control Word ADD 137 4 1 3 Example Control Word LDR 138 4 1 4 Hardwired Control 139 4 1 5 Using a Memory for Logic Functions 140 …
View Full Document
Unlocking...