Preface iv
1 Welcome Aboard 1
1.1 What We Will Tryto Do 1
1.2 How We Will Get There 1
1.3 Two Recurring Themes 3
1.3.1 The Notion of Abstraction 3
1.3.2 Hardware vs. Software 5
1.4 A Computer System 7
1.4.1 A (Very) Little History for a(Lot) Better Perspective 8
1.4.2 The Parts of a Computer System 10
1.5 Two Very Important Ideas 11
1.6 Computersas Universal Computational Devices 12
1.7 How Do We Getthe Electrons to Do the Work? 14
1.7.1 The Statement of the Problem 14
1.7.2 The Algorithm 16
1.7.3 The Program 16
1.7.4 The ISA 17
1.7.5 The Microarchitecture 18
1.7.6 The Logic Circuit 19
1.7.7 The Devices 19
Exercises 20
2 Bits, Data Types, and Operations 25
2.1 Bits and Data Types 25
2.1.1 The Bitas the Unit of Information 25
2.1.2 Data Types 26
2.2 Integer Data Types 26
2.2.1 Unsigned Integers 26
2.2.2 Signed Integers 27
2.3 2��s Complement Integers 29
2.4 Conversion Between Binary and Decimal 31
2.4.1 Binary to Decimal Conversion 31
2.4.2 Decimal to Binary Conversion 32
2.4.3 Extending Conversion to Numbers with Fractional Parts 33
2.5 Operations on Bits��Part I: Arithmetic 34
2.5.1 Addition and Subtraction 34
2.5.2 Sign-Extension 36
2.5.3 Overflow 36
2.6 Operations on Bits��Part II:Logical Operations 38
2.6.1 ALogical Variable 38
2.6.2 The AND Function 38
2.6.3 The OR Function 39
2.6.4 The NOT Function 40
2.6.5 The Exclusive-OR Function 40
2.6.6 De Morgan��s Laws 41
2.6.7 The Bit Vector 42
2.7 Other Representations 43
2.7.1 Floating Point Data Type (Greater Range, Less Precision) 43
2.7.2 ASCII Codes 47
2.7.3 Hexadecimal Notation 48
Exercises 49
3 Digital Logic Structures 59
3.1 The Transistor 59
3.2 Logic Gates 61
3.2.1 The NOT Gate (Inverter) 61
3.2.2 OR and NOR Gates 62
3.2.3 Why We Can��t Simply Connect P-Type to Ground 64
3.2.4 AND and NAND Gates 65
3.2.5 Gates with More Than Two Inputs 66
3.3 Combinational Logic Circuits 67
3.3.1 Decoder 67
3.3.2 Mux 68
3.3.3 A One-Bit Adder (a.k.a.a Full Adder) 69
3.3.4 The Programmable Logic Array(PLA)71
3.3.5 Logical Completeness 72
3.4 Basic Storage Elements 73
3.4.1 The R-S Latch 73
3.4.2 The Gated D Latch 74
3.5 The Concept of Memory 75
3.5.1 Address Space 75
3.5.2 Addressability 76
3.5.3 A22-by-3-Bit Memory 76
3.6 Sequential Logic Circuits 78
3.6.1 A Simple Example: The Combination Lock 79
3.6.2 The Concept of State 80
3.6.3 The Finite State Machine and Its State Diagram 82
3.6.4 The Synchronous Finite State Machine 85
3.6.5 The Clock 86
3.6.6 Example: A Danger Sign 87
3.7 Preview of Coming Attractions: The Data Path of the LC-3 93
Exercises 95
4 The von Neumann Model 121
4.1 Basic Components 121
4.1.1 Memory 122
4.1.2 Processing Unit123
4.1.3 Inputand Output 124
4.1.4 Control Unit 125
4.2 The LC-3: An Examplevon Neumann Machine 125
4.3 Instruction Processing 127
4.3.1 The Instruction 127
4.3.2 The Instruction Cycle (NOT the Clock Cycle!) 130
4.3.3 Changing the Sequence of Execution 132
4.3.4 Control of the Instruction Cycle 134
4.3.5 Halting the Computer (the TRAP Instruction) 136
4.4 Our First Program: A Multiplication Algorithm 137
Exercises 139
5 The LC-3 145
5.1 The ISA: Overview 145
5.1.1 Memory Organization 146
5.1.2 Registers 146
5.1.3 The Instruction Set147
5.1.4 Opcodes 149
5.1.5 Data Types 149
5.1.6 Addressing Modes 150
5.1.7 Condition Codes 150
5.2 Operate Instructions 151
5.2.1 ADD, AND, and NOT 151
5.2.2 Immediates 152
5.2.3 The LEA Instruction (Although Not Really an Operate) 154
5.3 Data Movement Instructions 155
5.3.1 PC-Relative Mode 156
5.3.2 Indirect Mode158
5.3.3 Base+offset Mode 159
5.3.4 An Example 160
5.4 Control Instructions 161
5.4.1 Conditional Branches162
5.4.2 Two Methods of Loop Control165
5.4.3 The JMP Instruction 169
5.4.4 The TRAP Instruction 169
5.5 Another Example: Counting Occurrences of a Character 170
5.6 The Data Path Revisited 173
5.6.1 Basic Components of the Data Path 175
5.6.2 The Instruction Cycle Specificto the LC-3 176
Exercises 177
6 Programming 203
6.1 Problem Solving 203
6.1.1 Systematic Decomposition