USA: +1(669)289-8683 
Sign in
Purpose
The purpose of this project is to use a digital logic simulator and build a moderate circuit with a sequential sub-circuit and a combinational sub-circuit.
Project Description
We will build a 4-bit counter with two Hex Digit displays to show the corresponding decimal values 0 ~ 15 (and back to 0). The circuit uses a counter sub-circuit (step 1) to generate BCD code automatically. The output of the counter sub-circuit will then be fed to a second sub-circuit (step 2) and connected to two Hex Digit displays.
Step 1
Build the counting-up counter described in Fig 10-17 (ch10.5) of the Tarnoff textbook in Logisim. This is a sequential circuit.
The clock signal is in the Wiring folder [of Logisim].
Use one D flip-flop for each of the four latches and set their trigger attribute to “Rising Edge”. Be aware that the pins of the D flip-flop component in Logisim are ordered differently from the D latch graphic symbol in our textbook. Hover your mouse over each pin of the D flip-flop to know what that pin is for. Use Help menu > Library Reference.
Step 2
Now design and build a combinational circuit to convert BCD code (4-bit input) to its decimal value expressed in two sets of BCD codes (8-bit output Y7 ~ Y0). Even though it has 8 outputs, this circuit is simpler than the project we built in the previous unit.
The truth table is provided below. The intention is to convert input ABCD (0000 ~ 1111) to outputs Y7~Y0 which represent decimal values 0 ~ 15. The decimal values will be expressed in two sets of BCD codes, Y7~Y4 for the ten’s digit and Y3~Y0 for the one’s digit.
Provide a simplified expression for each of the 8 outputs Y7 ~ Y0. You may use whatever simplification method you like, but show your work with steps (such as k-maps). Hint: Y7, Y6, and Y5 will be the same and end up being 0.
Create a new circuit in Logisim to implement these simplified functions. Only use AND, OR, and NOT gates. Label items (every input/output pin and every AND/OR gate) in your circuit.
Add your name, Park ID, and date to your circuit using the Text tool. Save your circuit as Unit4_YourLastName_Step2.circ. Test your circuit to make sure it works properly before proceeding to the next step. Document your testing in the project document.
Step 3
Save a copy of your counter circuit from Step 1 as Unit4_YourLastName_Step3.circ (i.e. don’t destroy your Step 1 file). We will work in this file to combine our Step 1 and Step 2 circuits.
Load your Step 2 circuit (BCD to 2-digit decimal) into this Step 3 file. First, make sure your Step 2 circuit file is in the same folder on your computer as this Step 3 file. Next use Project menu -> Load Library -> Logisim Library … to add your Step 2 circuit. The loaded circuit will become a new folder under the Explorer Pane, as shown in Figure 1. Click open that folder and add the main component to the current file (the same way you add a built-in component). It will be displayed as a black box with four input pins and 8 output pins. We’ll use the loaded circuit like a Logisim component, the same way a circuit chip can be used anywhere with proper wiring. Figure 1. The loaded circuit in the Explorer Pane
Connect each of the four outputs of your Step 1 counter to the corresponding input pin of the black box (your step 2 circuit). Make sure they’re paired correctly. The Step 1 MSB output should be connected to the MSB input pin of the black box. Do not delete the output pins. Just add additional wire before each output of your Step 1 counter circuit.
Add two Hex Digit Displays to the right side of the black box and align them side by side (Figure 2). The Hex Digit Display component is listed under the Input/Output folder. Be sure to use the “Hex Digit Display”, not the 7-seg display we used last week.
Figure 2. Two Hex Digit Displays Side by Side Showing an Output of 15.
A Hex display takes a single input line carrying 4 bits, not 4 lines of 1-bit input. Because of that, we need to combine Y7~Y0 into two 4-bit lines before connecting the outputs of the black box to the two Hex displays. We will use two splitters. Splitter is the first component listed under the Wiring folder. Figure 3 shows how a splitter combines four 1-bit lines into a 4-bit line for a Hex Digit Display. If it helps, build a test circuit as in Figure 3 to understand the connection before adding splitters to your Step 3 circuit. Use the following attributes for the splitter:
Facing: NorthFan Out: 4Bit Width In: 4
Now add two splitters to your Step 3 circuit between the black box and the two Hex displays. One splitter will combine Y7~Y4 into a 4-bit line before sending them to the Hex display on the left (for the ten’s digit). The other splitter will combine Y3~Y0 for the Hex display on the right (for the one’s digit).
Save your circuit and test it. Document your testing in the project document.
Step 4
What’s the hardest part of this project for you? Please explain.
How’s your understanding of combinational circuits and sequential circuits after this project? Please explain. Feel free to comment on other aspects of this project.
In Logisim, a wire carrying 1 bit should only be light green (1) or dark green (0). See Help > Logisim References > Wire bundles > Wire colors.
Use one AND gate for each ANDed term no matter how many variables the term uses. Use one OR gate to OR terms at the same level. Edit the number of input pins an AND/OR gate has to match the number of inputs the gate needs. It can help you track your work, not missing any input connections or adding extra ones.
COMPUTER ORGANIZATION AND
DESIGN FUNDAMENTALS
Examining Computer Hardware from the Bottom to the Top
David Tarnoff
Revised First Edition
Computer Organization and Design Fundamentals
by David Tarnoff
Copyright © 2005-2007 by David L. Tarnoff. All rights reserved.
Published with the assistance of Lulu.com
This book was written by David L. Tarnoff who is also responsible for
the creation of all figures contained herein.
Cover design by David L. Tarnoff
Cover cartoons created by Neal Kegley
Printing History:
July 2005:
January 2006:
July 2007:
First edition.
Minor corrections to first edition.
Added text on Gray code, DRAM technologies,
Mealy machines, XOR boolean rules, signed
BCD, and hard drive access times. Also made
minor corrections.
Legal Notice:
The 3Com® name is a registered trademark of the 3Com Corporation.
The Apple® name and iTunes® name are registered trademarks of
Apple Computer, Inc.
The Dell® name is a registered trademark of Dell, Inc.
The Intel® name, Pentium® 4 Processor Extreme Edition, HyperThreading Technology™, and Hyper-Pipelined Technology™ are
registered trademarks of the Intel Corporation.
PowerPC® is a registered trademark of International Business Machines
Corporation.
The Microsoft® name is a registered trademark of the Microsoft
Corporation.
While every precaution has been taken to ensure that the material
contained in this book is accurate, the author assumes no responsibility
for errors or omissions, or for damage incurred as a result of using the
information contained in this book.
Please report any errors found to the author at tarnoff@etsu.edu. In
addition, suggestions concerning improvements or additions to the text
are encouraged. Please direct such correspondence to the author.
This book is dedicated to
my wife and our son.
I love you both with all my heart.
TABLE OF CONTENTS
Preface…………………………………………………………………………………… xxi
Chapter One: Digital Signals and Systems …………………………………. 1
1.1 Should Software Engineers Worry About Hardware?…………… 1
1.2 Non-Digital Signals………………………………………………………….. 3
1.3 Digital Signals…………………………………………………………………. 4
1.4 Conversion Systems…………………………………………………………. 6
1.5 Representation of Digital Signals ………………………………………. 7
1.6 Types of Digital Signals……………………………………………………. 9
1.6.1 Edges ……………………………………………………………………… 9
1.6.2 Pulses……………………………………………………………………… 9
1.6.3 Non-Periodic Pulse Trains ………………………………………. 10
1.6.4 Periodic Pulse Trains………………………………………………. 11
1.6.5 Pulse-Width Modulation …………………………………………. 13
1.7 Unit Prefixes …………………………………………………………………. 15
1.8 What’s Next? …………………………………………………………………. 16
Problems…………………………………………………………………………….. 16
Chapter Two: Numbering Systems ………………………………………….. 17
2.1 Unsigned Binary Counting………………………………………………. 17
2.2 Binary Terminology……………………………………………………….. 20
2.3 Unsigned Binary to Decimal Conversion ………………………….. 20
2.4 Decimal to Unsigned Binary Conversion ………………………….. 23
2.5 Binary Representation of Analog Values…………………………… 25
2.6 Sampling Theory……………………………………………………………. 31
2.7 Hexadecimal Representation……………………………………………. 34
2.8 Binary Coded Decimal……………………………………………………. 36
2.9 Gray Codes……………………………………………………………………. 37
2.10 What’s Next? ……………………………………………………………….. 40
Problems…………………………………………………………………………….. 41
Chapter Three: Binary Math and Signed Representations ……….. 43
3.1 Binary Addition……………………………………………………………… 43
3.2 Binary Subtraction …………………………………………………………. 45
3.3 Binary Complements………………………………………………………. 46
3.3.1 One’s Complement …………………………………………………. 46
3.3.2 Two’s Complement…………………………………………………. 47
3.3.3 Most Significant Bit as a Sign Indicator ……………………. 50
3.3.4 Signed Magnitude ………………………………………………….. 51
v
vi Computer Organization and Design Fundamentals
3.3.5 MSB and Number of Bits………………………………………… 51
3.3.6 Issues Surrounding the Conversion of Binary Numbers. 52
3.3.7 Minimums and Maximums ……………………………………… 55
3.4 Floating Point Binary……………………………………………………… 57
3.5 Hexadecimal Addition ……………………………………………………. 61
3.6 BCD Addition ……………………………………………………………….. 64
3.7 Multiplication and Division by Powers of Two………………….. 65
3.8 Easy Decimal to Binary Conversion Trick ………………………… 67
3.9 Arithmetic Overflow………………………………………………………. 67
3.10 What’s Next? ……………………………………………………………….. 69
Problems ……………………………………………………………………………. 69
Chapter Four: Logic Functions and Gates……………………………….. 71
4.1 Logic Gate Basics ………………………………………………………….. 71
4.1.1 NOT Gate……………………………………………………………… 72
4.1.2 AND Gate …………………………………………………………….. 72
4.1.3 OR Gate………………………………………………………………… 73
4.1.4 Exclusive-OR (XOR) Gate ……………………………………… 74
4.2 Truth Tables………………………………………………………………….. 75
4.3 Timing Diagrams for Gates …………………………………………….. 79
4.4 Combinational Logic ……………………………………………………… 80
4.5 Truth Tables for Combinational Logic ……………………………… 83
4.6 What’s Next? …………………………………………………………………. 86
Problems ……………………………………………………………………………. 87
Chapter Five: Boolean Algebra ……………………………………………….. 89
5.1 Need for Boolean Expressions…………………………………………. 89
5.2 Symbols of Boolean Algebra…………………………………………… 90
5.3 Boolean Expressions of Combinational Logic …………………… 92
5.4 Laws of Boolean Algebra ……………………………………………….. 95
5.5 Rules of Boolean Algebra……………………………………………….. 96
5.5.1 NOT Rule……………………………………………………………… 96
5.5.2 OR Rules ………………………………………………………………. 96
5.5.3 AND Rules……………………………………………………………. 97
5.5.4 XOR Rules ……………………………………………………………. 98
5.5.5 Derivation of Other Rules ……………………………………….. 99
5.6 Simplification………………………………………………………………. 101
5.7 DeMorgan’s Theorem …………………………………………………… 103
5.8 What’s Next? ……………………………………………………………….. 106
Problems ………………………………………………………………………….. 107
Table of Contents vii
Chapter Six: Standard Boolean Expression Formats………………. 109
6.1 Sum-of-Products ………………………………………………………….. 109
6.2 Converting an SOP Expression to a Truth Table………………. 110
6.3 Converting a Truth Table to an SOP Expression………………. 112
6.4 Product-of-Sums ………………………………………………………….. 114
6.5 Converting POS to Truth Table ……………………………………… 115
6.6 Converting a Truth Table to a POS Expression………………… 118
6.7 NAND-NAND Logic……………………………………………………. 119
6.8 What’s Next? ……………………………………………………………….. 122
Problems…………………………………………………………………………… 123
Chapter Seven: Karnaugh Maps ……………………………………………. 125
7.1 The Karnaugh Map ………………………………………………………. 125
7.2 Using Karnaugh Maps ………………………………………………….. 129
7.3 “Don’t Care” Conditions in a Karnaugh Map……………………. 137
7.4 What’s Next? ……………………………………………………………….. 138
Problems…………………………………………………………………………… 139
Chapter Eight: Combinational Logic Applications …………………. 141
8.1 Adders ………………………………………………………………………… 141
8.2 Seven-Segment Displays……………………………………………….. 147
8.3 Active-Low Signals………………………………………………………. 151
8.4 Decoders……………………………………………………………………… 152
8.5 Multiplexers ………………………………………………………………… 155
8.6 Demultiplexers …………………………………………………………….. 157
8.7 Integrated Circuits………………………………………………………… 159
8.8 What’s Next? ……………………………………………………………….. 163
Problems…………………………………………………………………………… 164
Chapter Nine: Binary Operation Applications ……………………….. 165
9.1 Bitwise Operations……………………………………………………….. 165
9.1.1 Clearing/Masking Bits ………………………………………….. 167
9.1.2 Setting Bits ………………………………………………………….. 171
9.1.3 Toggling Bits……………………………………………………….. 171
9.2 Comparing Bits with XOR…………………………………………….. 173
9.3 Parity ………………………………………………………………………….. 174
9.4 Checksum……………………………………………………………………. 175
9.5 Cyclic Redundancy Check …………………………………………….. 179
9.5.1 CRC Process………………………………………………………… 185
9.5.2 CRC Implementation ……………………………………………. 187
9.6 Hamming Code ……………………………………………………………. 188
viii Computer Organization and Design Fundamentals
9.7 What’s Next? ……………………………………………………………….. 199
Problems ………………………………………………………………………….. 199
Chapter Ten: Memory Cells ………………………………………………….. 203
10.1 New Truth Table Symbols …………………………………………… 203
10.1.1 Edges/Transitions……………………………………………….. 203
10.1.2 Previously Stored Values …………………………………….. 204
10.1.3 Undefined Values……………………………………………….. 204
10.2 The S-R Latch……………………………………………………………. 205
10.3 The D Latch ………………………………………………………………. 209
10.4 Divide-By-Two Circuit……………………………………………….. 212
10.5 Counter……………………………………………………………………… 213
10.6 Parallel Data Output……………………………………………………. 214
10.7 What’s Next? ……………………………………………………………… 215
Problems ………………………………………………………………………….. 216
Chapter Eleven: State Machines ……………………………………………. 217
11.1 Introduction to State Machines …………………………………….. 217
11.1.1 States ………………………………………………………………… 217
11.1.2 State Diagrams …………………………………………………… 218
11.1.3 Errors in State Diagrams ……………………………………… 222
11.1.4 Basic Circuit Organization…………………………………… 222
11.2 State Machine Design Process……………………………………… 225
11.3 Another State Machine Design: Pattern Detection ………….. 234
11.4 Mealy Versus Moore State Machines……………………………. 237
11.5 What’s Next? ……………………………………………………………… 238
Problems ………………………………………………………………………….. 239
Chapter Twelve: Memory Organization ………………………………… 241
12.1 Early Memory ……………………………………………………………. 241
12.2 Organization of Memory Device ………………………………….. 242
12.3 Interfacing Memory to a Processor……………………………….. 244
12.3.1 Buses ………………………………………………………………… 244
12.3.2 Memory Maps ……………………………………………………. 248
12.3.3 Address Decoding ………………………………………………. 250
12.3.4 Chip Select Hardware …………………………………………. 255
12.4 Memory Mapped Input/Output…………………………………….. 259
12.5 Memory Terminology…………………………………………………. 260
12.5.1 Random Access Memory …………………………………….. 260
12.5.2 Read Only Memory…………………………………………….. 261
12.5.3 Static RAM versus Dynamic RAM ………………………. 261
Table of Contents ix
12.5.4 Types of DRAM and Their Timing ………………………. 263
12.5.5 Asynchronous vs. Synchronous Memory ………………. 266
12.6 What’s Next? ……………………………………………………………… 267
Problems…………………………………………………………………………… 267
Chapter Thirteen: Memory Hierarchy …………………………………… 269
13.1 Characteristics of the Memory Hierarchy………………………. 269
13.2 Physical Characteristics of a Hard Drive ……………………….. 269
13.2.1 Hard Drive Read/Write Head……………………………….. 270
13.2.2 Data Encoding……………………………………………………. 272
13.2.3 Hard Drive Access Time ……………………………………… 275
13.2.4 S.M.A.R.T. ………………………………………………………… 278
13.3 Organization of Data on a Hard Drive …………………………… 279
13.4 Cache RAM……………………………………………………………….. 284
13.4.1 Cache Organization …………………………………………….. 286
13.4.2 Dividing Memory into Blocks ……………………………… 287
13.4.3 Cache Operation…………………………………………………. 289
13.4.4 Cache Characteristics ………………………………………….. 290
13.4.5 Cache Mapping Functions……………………………………. 290
13.4.6 Cache Write Policy …………………………………………….. 299
13.5 Registers……………………………………………………………………. 300
13.6 What’s Next? ……………………………………………………………… 300
Problems…………………………………………………………………………… 301
Chapter Fourteen: Serial Protocol Basics……………………………….. 303
14.1 OSI Seven-Layer Network Model ………………………………… 303
14.2 Serial versus Parallel Data Transmission……………………….. 304
14.3 Anatomy of a Frame or Packet …………………………………….. 306
14.4 Sample Protocol: IEEE 802.3 Ethernet………………………….. 308
14.5 Sample Protocol: Internet Protocol ……………………………….. 310
14.6 Sample Protocol: Transmission Control Protocol……………. 313
14.7 Dissecting a Frame……………………………………………………… 317
14.8 Additional Resources ………………………………………………….. 320
14.9 What’s Next? ……………………………………………………………… 322
Problems…………………………………………………………………………… 322
Chapter Fifteen: Introduction to Processor Architecture………… 325
15.1 Organization versus Architecture………………………………….. 325
15.2 Components ………………………………………………………………. 325
15.2.1 Bus……………………………………………………………………. 325
15.2.2 Registers……………………………………………………………. 326
x Computer Organization and Design Fundamentals
15.2.3 Flags …………………………………………………………………. 327
15.2.4 Buffers………………………………………………………………. 328
15.2.5 The Stack…………………………………………………………… 329
15.2.6 I/O Ports ……………………………………………………………. 331
15.3 Processor Level………………………………………………………….. 332
15.4 CPU Level…………………………………………………………………. 333
15.5 Simple Example of CPU Operation………………………………. 334
15.6 Assembly and Machine Language ………………………………… 338
15.7 Big-Endian/Little-Endian…………………………………………….. 345
15.8 Pipelined Architectures……………………………………………….. 346
15.9 Passing Data To and From Peripherals………………………….. 350
15.9.1 Memory-Mapped I/O ………………………………………….. 351
15.9.2 Polling ………………………………………………………………. 353
15.9.3 Interrupts …………………………………………………………… 354
15.9.4 Direct Memory Access………………………………………… 355
15.9.5 I/O Channels and Processors………………………………… 356
15.10 What’s Next? ……………………………………………………………. 357
Problems ………………………………………………………………………….. 357
Chapter Sixteen: Intel 80×86 Base Architecture……………………… 359
16.1 Why Study the 80×86?………………………………………………… 359
16.2 Execution Unit …………………………………………………………… 360
16.2.1 General Purpose Registers …………………………………… 361
16.2.2 Address Registers……………………………………………….. 362
16.2.3 Flags …………………………………………………………………. 363
16.2.4 Internal Buses…………………………………………………….. 365
16.3 Bus Interface Unit………………………………………………………. 365
16.3.1 Segment Addressing …………………………………………… 366
16.3.2 Instruction Queue……………………………………………….. 370
16.4 Memory versus I/O Ports…………………………………………….. 371
16.5 What’s Next? ……………………………………………………………… 372
Problems ………………………………………………………………………….. 373
Chapter Seventeen: Intel 80×86 Assembly Language………………. 375
17.1 Assemblers versus Compilers………………………………………. 375
17.2 Components of a Line of Assembly Language……………….. 376
17.3 Assembly Language Directives ……………………………………. 378
17.3.1 SEGMENT Directive………………………………………….. 378
17.3.2 .MODEL, .STACK, .DATA, and .CODE Directives . 380
17.3.3 PROC Directive …………………………………………………. 381
Table of Contents xi
17.3.4 END Directive……………………………………………………. 382
17.3.5 Data Definition Directives …………………………………… 382
17.3.6 EQU Directive……………………………………………………. 383
17.4 80×86 Opcodes…………………………………………………………… 385
17.4.1 Data Transfer……………………………………………………… 385
17.4.2 Data Manipulation………………………………………………. 386
17.4.3 Program Control…………………………………………………. 387
17.4.4 Special Operations ……………………………………………… 390
17.5 Addressing Modes………………………………………………………. 391
17.5.1 Register Addressing ……………………………………………. 391
17.5.2 Immediate Addressing…………………………………………. 392
17.5.3 Pointer Addressing ……………………………………………… 392
17.6 Sample 80×86 Assembly Language Programs………………… 393
17.7 Additional 80×86 Programming Resources ……………………. 397
17.8 What’s Next? ……………………………………………………………… 398
Problems…………………………………………………………………………… 398
Index …………………………………………………………………………………….. 401
TABLE OF FIGURES
1-1
1-2
1-3
1-4
1-5
1-6
1-7
1-8
1-9
1-10
1-11
1-12
1-13
1-14
1-15
1-16
Sample Digital System ……………………………………………………… 3
Continuous Analog Signal with Infinite Resolution ……………… 4
Sample of Discrete Measurements Taken Every 0.1 Sec……….. 4
Samples Taken of an Analog Signal …………………………………… 5
Slow Sampling Rate Missed an Anomaly……………………………. 5
Poor Resolution Resulting in an Inaccurate Measurement …….. 5
Block Diagram of a System to Capture Analog Data ……………. 6
Representation of a Single Binary Signal ……………………………. 8
Representation of Multiple Digital Signals………………………….. 8
Alternate Representation of Multiple Digital Signals ……………. 9
Digital Transition Definitions ………………………………………….. 10
Pulse Waveforms …………………………………………………………… 10
Non-Periodic Pulse Train ………………………………………………… 10
Periodic Pulse Train ……………………………………………………….. 11
Periodic Pulse Train with Different Pulse Widths ………………. 11
Periodic Pulse Train with 25% Duty Cycle ……………………….. 13
2-1
Counting in Decimal ………………………………………………………. 17
xii Computer Organization and Design Fundamentals
2-2
2-3
2-4
2-5
2-6
2-7
2-8
2-9
2-10
2-11
2-12
Counting in Binary…………………………………………………………. 18
Binary-Decimal Equivalents from 0 to 17 …………………………. 19
Values Represented By Each of the First 8 Bit Positions …….. 21
Sample Conversion of 101101002 to Decimal……………………. 21
Decimal to Unsigned Binary Conversion Flow Chart …………. 24
Sample Analog Signal of Sound ………………………………………. 26
Effects of Number of Bits on Roundoff Error ……………………. 32
Aliasing Effects Due to Slow Sampling Rate …………………….. 33
Eight Binary Values Identifying Rotating Shaft Position…….. 38
Example of a Position Encoder………………………………………… 38
Conversion from Unsigned Binary to Gray Code……………….. 39
3-1
3-2
3-3
3-4
3-5
3-6
Four Possible Results of Adding Two Bits………………………… 44
Four Possible Results of Adding Two Bits with Carry………… 44
Two’s Complement Short-Cut………………………………………….. 49
Converting a Two’s Complement Number to a Decimal ……… 53
IEEE Standard 754 Floating-Point Formats……………………….. 59
Duplicate MSB for Right Shift of 2’s Complement Values….. 66
4-1
4-2
4-3
4-4
4-5
4-6
4-7
4-8
4-9
4-10
4-11
4-12
4-13
4-14
4-15
4-16
4-17
4-18
4-19
4-20
4-21
Basic Format of a Logic Gate ………………………………………….. 71
Basic Logic Symbols ……………………………………………………… 72
Operation of the NOT Gate……………………………………………… 72
Operation of a Two-Input AND Gate ……………………………….. 73
Operation of a Two-Input OR Gate ………………………………….. 74
Operation of a Two-Input XOR Gate ……………………………….. 74
Sample Three-Input Truth Table………………………………………. 75
Listing All Bit Patterns for a Four-Input Truth Table………….. 76
Inverter Truth Table ……………………………………………………….. 77
Two-Input AND Gate Truth Table …………………………………… 77
Two-Input OR Gate Truth Table ……………………………………… 77
Two-Input XOR Gate Truth Table……………………………………. 78
Three-Input AND Gate Truth Table With Don’t Cares ……….. 78
Sample Timing Diagram for a Three-Input AND Gate ……….. 79
Sample Timing Diagram for a Three-Input OR Gate ………….. 79
Sample Timing Diagram for a Three-Input XOR Gate ……….. 79
Sample Combinational Logic…………………………………………… 80
Combinational Logic for a Simple Security System……………. 80
Truth Table for Simple Security System of Figure 4-18 ……… 81
“NOT” Circuits ……………………………………………………………… 82
Schematic “Short-Hand” for Inverted Inputs ……………………… 82
Table of Contents xiii
4-22
4-23
4-24
4-25
4-26
4-27
4-28
4-29
Sample of Multi-Level Combinational Logic …………………….. 83
Process of Passing Inputs Through Combinational Logic ……. 83
Steps That Inputs Pass Through in Combinational Logic…….. 84
All Combinations of Ones and Zeros for Three Inputs………… 84
Step (a) in Sample Truth Table Creation …………………………… 85
Step (b) in Sample Truth Table Creation …………………………… 85
Step (c) in Sample Truth Table Creation …………………………… 86
Step (d) in Sample Truth Table Creation …………………………… 86
5-1
5-2
5-3
5-4
5-5
5-6
5-7
5-8
5-9
5-10
5-11
5-12
5-13
5-14
Schematic and Truth Table of Combinational Logic …………… 89
Boolean Expression for the AND Function ……………………….. 90
Boolean Expression for the OR Function ………………………….. 91
Boolean Expression for the NOT Function………………………… 91
Circuit Representation of the Boolean Expression 1+0+1……. 91
Sample of Multi-Level Combinational Logic …………………….. 92
Creating Boolean Expression from Combinational Logic ……. 93
Examples of the Precedence of the NOT Function …………….. 93
Example of a Conversion from a Boolean Expression ………… 94
Commutative Law for Two Variables OR’ed Together ……….. 95
Schematic Form of NOT Rule …………………………………………. 96
Rules of Boolean Algebra ……………………………………………… 101
Application of DeMorgan’s Theorem………………………………. 105
Schematic Application of DeMorgan’s Theorem………………. 106
6-1
6-2
6-3
6-4
6-5
6-6
6-7
6-8
6-9
6-10
6-11
6-12
6-13
6-14
6-15
Sample Sum-of-Products Binary Circuit …………………………. 110
Samples of Single Product (AND) Truth Tables ………………. 111
Sample of a Sum-of-Products Truth Table ………………………. 111
Conversion of an SOP Expression to a Truth Table ………….. 112
Sample Product-of-Sums Binary Circuit …………………………. 115
Samples of Single Sum (OR) Truth Tables………………………. 115
Sample of a Product-of-Sums Truth Table ………………………. 116
Sample Sums With Multiple Zero Outputs ………………………. 117
Conversion of a POS Expression to a Truth Table ……………. 118
Circuit Depiction of DeMorgan’s Theorem………………………. 120
OR Gate Equals a NAND Gate With Inverted Inputs………… 120
OR-to-NAND Equivalency Expanded to Four Inputs ……….. 120
Sample SOP Circuit ……………………………………………………… 121
Sample SOP Circuit with Output OR Gate Replaced ………… 121
Sample SOP Circuit Implemented With NAND Gates………. 122
7-1
2-by-2 Karnaugh Map Used with Two Inputs ………………….. 126
xiv Computer Organization and Design Fundamentals
7-2
7-3
7-4
7-5
7-6
7-7
7-8
7-9
Mapping a 2-Input Truth Table to Its Karnaugh Map ……….. 126
Three-Input Karnaugh Map …………………………………………… 127
Four-Input Karnaugh Map …………………………………………….. 127
Identifying the Products in a Karnaugh Map ……………………. 130
Karnaugh Map with Four Adjacent Cells Containing ‘1’ ……. 130
Sample Rectangle in a Three-Input Karnaugh Map…………… 133
Karnaugh Map with a “Don’t Care” Elements ………………….. 138
Karnaugh Map with a “Don’t Care” Elements Assigned ……. 138
8-1
8-2
8-3
8-4
8-5
8-6
8-7
8-8
8-9
8-10
8-11
8-12
8-13
8-14
8-15
8-16
8-17
8-18
8-19
8-20
8-21
8-22
8-23
8-24
8-25
8-26
8-27
8-28
8-29
8-30
8-31
Four Possible Results of Adding Two Bits………………………. 141
Block Diagram of a Half Adder……………………………………… 142
Four Possible States of a Half Adder ………………………………. 142
Logic Circuit for a Half Adder……………………………………….. 143
Block Diagram of a Multi-bit Adder……………………………….. 144
Block Diagram of a Full Adder………………………………………. 144
Sum and Carryout Karnaugh Maps for a Full Adder…………. 145
Logic Circuit for a Full Adder ……………………………………….. 146
Seven-Segment Display ………………………………………………… 147
Displaying a ‘1’ with a 7-Segment Display ………………………. 147
A Seven-Segment Display Displaying a Decimal ‘2’…………. 148
Block Diagram of a Seven-Segment Display Driver …………. 148
Segment Patterns for all Hexadecimal Digits …………………… 149
Seven Segment Display Truth Table ………………………………. 149
Karnaugh Map for Segment ‘e’……………………………………….. 150
Karnaugh Map for Segment ‘e’ with Rectangles ……………….. 150
Logic Circuit for Segment e of 7-Segment Display…………… 151
Labeling Conventions for Active-Low Signals ………………… 152
Sample Circuit for Enabling a Microwave ………………………. 153
Sample Circuit for Delivering a Soda ……………………………… 153
Truth Table to Enable a Device for A=1, B=1, & C=0………. 154
Digital Circuit for a 1-of-4 Decoder ……………………………….. 154
Digital Circuit for an Active-Low 1-of-4 Decoder ……………. 155
Truth Table for an Active-Low 1-of-8 Decoder ……………….. 155
Block Diagram of an Eight Channel Multiplexer ……………… 156
Truth Table for an Eight Channel Multiplexer …………………. 156
Logic Circuit for a 1-Line-to-4-Line Demultiplexer………….. 158
Truth Table for a 1-Line-to-4-Line Demultiplexer ……………. 159
Examples of Integrated Circuits……………………………………… 159
Pin-out of a Quad Dual-Input NAND Gate IC (7400)……….. 160
Sample Pin 1 Identifications ………………………………………….. 160
Table of Contents xv
8-32
8-33
8-34
8-35
8-36
8-37
Generic Protoboard ………………………………………………………. 161
Generic Protoboard Internal Connections ………………………… 161
Sample Circuit Wired on a Protoboard ……………………………. 162
Schematic Symbol of a Light-Emitting Diode (LED) ……….. 162
LED Circuit ………………………………………………………………… 163
Switch Circuit………………………………………………………………. 163
9-1
9-2
9-3
9-4
9-5
9-6
9-7
9-8
9-9
9-10
9-11
9-12
9-13
9-14
9-15
Graphic of a Bitwise Operation Performed on LSB ………….. 166
Bitwise AND of 011010112 and 110110102 …………………….. 166
Three Sample Bitwise ANDs …………………………………………. 168
Possible Output from a Motion Detector …………………………. 173
A Difference in Output Indicates an Error ……………………….. 173
Simple Error Detection with an XOR Gate………………………. 174
Sample Block of Data with Accompanying Datasums ………. 176
Small Changes in Data Canceling in Checksum……………….. 179
Example of Long Division in Binary ………………………………. 181
Example of Long Division Using XOR Subtraction………….. 182
Sample Code for Calculating CRC Checksums………………… 189
Venn Diagram Representation of Hamming Code ……………. 192
Example Single-Bit Errors in Venn Diagram …………………… 192
Example of a Two-Bit Error ………………………………………….. 193
Using Parity to Check for Double-Bit Errors……………………. 194
10-1 Symbols for Rising Edge and Falling Edge Transitions …….. 204
10-2 Sample Truth Table Using Undefined Output ………………….. 204
10-3 Primitive Feedback Circuit using Inverters………………………. 205
10-4 Operation of a NAND Gate with One Input Tied High ……… 206
10-5 Primitive Feedback Circuit Redrawn with NAND Gates …… 206
10-6 Only Two Possible States of Circuit in Figure 10-5 ………….. 206
10-7 Operation of a Simple Memory Cell ……………………………….. 207
10-8 Operation of a Simple Memory Cell (continued)………………. 208
10-9 S-R Latch ……………………………………………………………………. 209
10-10 S-R Latch Truth Table ………………………………………………….. 209
10-11 Block Diagram of the D Latch ……………………………………….. 209
10-12 Edge-Triggered D Latch Truth Tables …………………………….. 211
10-13 Transparent D Latch Truth Tables ………………………………….. 211
10-14 Divide-By-Two Circuit …………………………………………………. 212
10-15 Clock and Output Timing in a Divide-By-Two Circuit ……… 212
10-16 Cascading Four Divide-By-Two Circuits ………………………… 213
10-17 Counter Implemented with Divide-By-Two Circuits ………… 213
xvi Computer Organization and Design Fundamentals
10-18 Output of Binary Counter Circuit …………………………………… 214
10-19 Output Port Data Latch Circuitry……………………………………. 215
11-1 Adding Memory to a Digital Logic Circuit ……………………… 217
11-2 States of a Traffic Signal System……………………………………. 218
11-3 States of a Light Bulb……………………………………………………. 218
11-4 State Diagram for Light Bulb State Machine……………………. 218
11-5 Complete State Diagram for Light Bulb State Machine …….. 219
11-6 Block Diagram of an Up-Down Binary Counter ………………. 220
11-7 State Diagram for a 3-Bit Up-Down Binary Counter ………… 221
11-8 Sample of a Reset Indication in a State Diagram………………. 221
11-9 Block Diagram of a State Machine …………………………………. 223
11-10 Initial State of the Push Button Light Control ………………….. 226
11-11 Transitions from State 0 of Push Button Circuit……………….. 226
11-12 B=0 Transition from State 0 of Push Button Circuit …………. 227
11-13 B=1 Transition from State 0 of Push Button Circuit …………. 227
11-14 B=0 Transition from State 1 of Push Button Circuit …………. 227
11-15 B=1 Transition from State 1 of Push Button Circuit …………. 228
11-16 Transitions from State 2 of Push Button Circuit……………….. 228
11-17 Final State Diagram for Push Button Circuit ……………………. 229
11-18 Block Diagram for Push Button Circuit…………………………… 230
11-19 K-Maps for S1′, S0′, and L of Push Button Circuit …………….. 232
11-20 Finished Push Button Circuit …………………………………………. 232
11-21 Revised Truth Table and K Map for Push Button Circuit ….. 233
11-22 Identifying the Bit Pattern “101” in a Bit Stream ……………… 234
11-23 State Diagram for Identifying the Bit Pattern “101”………….. 235
11-24 Next State and Output Truth Tables for Pattern Detect ……… 236
11-25 K-Maps for S1′, S0′, and P of Pattern Detect Circuit ………….. 237
11-26 Final Circuit to Identify the Bit Pattern “101” ………………….. 237
11-27 Basic Configuration of a Mealy Machine ………………………… 238
11-28 Sample State Diagram of a Mealy Machine …………………….. 238
11-29 Output Truth Table for Sample Mealy Machine……………….. 239
12-1
12-2
12-3
12-4
12-5
12-6
12-7
Diagram of a Section of Core Memory……………………………. 241
Basic Organization of a Memory Device…………………………. 243
Basic Processor to Memory Device Interface…………………… 245
Two Memory Devices Sharing a Bus ……………………………… 246
Three Buffers Trying to Drive the Same Output ………………. 248
Sample Memory Maps ………………………………………………….. 249
Full Address with Enable Bits and Device Address Bits……. 251
Table of Contents xvii
12-8 IPv4 Address Divided into Subnet and Host IDs………………. 254
12-9 Sample Chip Select Circuit for a Memory Device…………….. 256
12-10 Some Types of Memory Mapped I/O Configurations ……….. 260
12-11 Basic Addressing Process for a DRAM …………………………… 264
12-12 Organization of DRAM…………………………………………………. 265
12-13 Example of an FPM Transfer …………………………………………. 265
12-14 Example of an EDO Transfer…………………………………………. 266
13-1 Block Diagram of a Standard Memory Hierarchy …………….. 269
13-2 Configuration of a Hard Drive Write Head………………………. 271
13-3 Sample FM Magnetic Encoding……………………………………… 273
13-4 Sample MFM Magnetic Encoding ………………………………….. 274
13-5 RLL Relation between Bit Patterns and Polarity Changes …. 274
13-6 Sample RLL Magnetic Encoding……………………………………. 275
13-7 Components of Disk Access Time ………………………………….. 277
13-8 Relation between Read/Write Head and Tracks ……………….. 279
13-9 Organization of Hard Disk Platter…………………………………… 280
13-10 Illustration of a Hard Drive Cylinder ………………………………. 281
13-11 Equal Number of Bits per Track versus Equal Sized Bits ….. 282
13-12 Comparison of Sector Organizations ………………………………. 282
13-13 Cache Placement between Main Memory and Processor …… 285
13-14 L1 and L2 Cache Placement…………………………………………… 285
13-15 Split Cache Organization ………………………………………………. 286
13-16 Organization of Cache into Lines …………………………………… 287
13-17 Division of Memory into Blocks…………………………………….. 288
13-18 Organization of Address Identifying Block and Offset ……… 289
13-19 Direct Mapping of Main Memory to Cache……………………… 291
13-20 Direct Mapping Partitioning of Memory Address …………….. 292
13-21 Fully Associative Partitioning of Memory Address…………… 295
13-22 Set Associative Mapping of Main Memory to Cache ………… 297
13-23 Effect of Cache Set Size on Address Partitioning……………… 298
14-1
14-2
14-3
14-4
14-5
14-6
14-7
Sample Protocol Stack using TCP, IP, and Ethernet …………. 307
Layout of an IEEE 802.3 Ethernet Frame ………………………… 308
Layout of an IP Packet Header……………………………………….. 311
Layout of a TCP Packet Header……………………………………… 314
Position and Purpose of TCP Control Flags …………………….. 315
Layout of a TCP Pseudo Header …………………………………….. 316
Simulated Raw Data Capture of an Ethernet Frame ………….. 317
15-1
Sample Code Using Conditional Statements ……………………. 328
xviii Computer Organization and Design Fundamentals
15-2 Block Diagram of a System Incorporating a Buffer ………….. 329
15-3 Generic Block Diagram of a Processor System ………………… 332
15-4 Generic Block Diagram of Processor Internals…………………. 333
15-5 Generic Block Diagram of a Typical CPU ………………………. 334
15-6 Decoded Assembly Language from Table 15-6 ……………….. 343
15-7 Non-Pipelined Execution of Five Instructions………………….. 348
15-8 Pipelined Execution of Five Instructions …………………………. 348
15-9 Sample Memory Mapped Device Circuit ………………………… 352
15-10 Basic Operation of an ISR …………………………………………….. 355
16-1
16-2
16-3
Block Diagram of 80×86 Execution Unit (EU) ………………… 360
Block Diagram of 80×86 Bus Interface Unit (BIU)…………… 366
Segment/Pointer Relation in the 80×86 Memory Map ………. 368
17-1 Format of a Line of Assembly Language Code ………………… 377
17-2 Format and Parameters Used to Define a Segment……………. 379
17-3 Format of the .MODEL Directive…………………………………… 380
17-4 Format and Parameters Used to Define a Procedure …………. 381
17-5 Format and Parameters of Some Define Directives…………… 383
17-6 Example Uses of Define Directives ………………………………… 384
17-7 Format and Parameters of the EQU Directive ………………….. 384
17-8 Sample Code with and without the EQU Directive …………… 384
17-9 Format and Parameters of the MOV Opcode……………………. 385
17-10 Format and Parameters of the IN and OUT Opcodes ………… 385
17-11 Format and Parameters of the ADD Opcode ……………………. 386
17-12 Format and Parameters of NEG, NOT, DEC, and INC ……… 386
17-13 Format and Parameters of SAR, SHR, SAL, and SHL………. 387
17-14 Example of a JMP Instruction………………………………………… 387
17-15 Example of a LOOP Instruction……………………………………… 389
17-16 Sample Organization of a Procedure Call………………………… 390
17-17 Examples of Register Addressing …………………………………… 392
17-18 Examples of Immediate Addressing ……………………………….. 392
17-19 Examples of an Address being used as an Operand…………… 393
17-20 Skeleton Code for a Simple Assembly Program……………….. 393
17-21 Code to Assign Data Segment Address to DS Register……… 394
17-22 Code to Inform O/S that Program is Terminated………………. 395
17-23 Skeleton Code with Code Added for O/S Support ……………. 395
17-24 Data Defining Directives for Example Code ……………………. 396
17-25 Step-by-Step Example Operation Converted to Code ……….. 396
17-26 Final Code for Example Assembly Language Program……… 397
Table of Contents xix
TABLE OF TABLES
1-1
Unit Prefixes………………………………………………………………….. 15
2-1
2-2
2-3
Converting Binary to Decimal and Hexadecimal ……………….. 35
Converting BCD to Decimal ……………………………………………. 36
Derivation of the Four-Bit Gray Code ………………………………. 40
3-1
3-2
3-3
Representation Comparison for 8-bit Binary Numbers ……….. 57
Hexadecimal to Decimal Conversion Table……………………….. 62
Multiplying the Binary Value 10012 by Powers of Two………. 65
8-1
8-2
Addition Results Based on Inputs of a Full Adder ……………. 144
Sum and Carryout Truth Tables for a Full Adder ……………… 145
9-1
9-2
9-3
9-4
9-5
9-6
9-7
9-8
9-9
9-10
Truth Table for a Two-Input XOR Gate ………………………….. 172
Addition and Subtraction Without Carries or Borrows………. 181
Reconstructing the Dividend Using XORs ………………………. 183
Second Example of Reconstructing the Dividend……………… 184
Data Groupings and Parity for the Nibble 10112 ………………. 190
Data Groupings with a Data Bit in Error …………………………. 190
Data Groupings with a Parity Bit in Error ……………………….. 191
Identifying Errors in a Nibble with Three Parity Bits………… 191
Parity Bits Required for a Specific Number of Data Bits …… 195
Membership of Data and Parity Bits in Parity Groups ………. 197
11-1
11-2
11-3
11-4
11-5
List of States for Push Button Circuit ……………………………… 230
Next State Truth Table for Push Button Circuit………………… 231
Output Truth Table for Push Button Circuit …………………….. 231
Revised List of States for Push Button Circuit …………………. 233
List of States for Bit Pattern Detection Circuit …………………. 236
12-1
12-2
The Allowable Settings of Four Chip Selects …………………… 247
Sample Memory Sizes versus Required Address Lines……… 251
15-1
15-2
15-3
15-4
15-5
15-6
15-7
15-8
Conditional Jumps to be Placed After a Compare …………….. 337
Conditional Jumps to be Placed After an Operation ………….. 338
Numbered Instructions for Imaginary Processor ………………. 340
Assembly Language for Imaginary Processor ………………….. 340
Operand Requirements for Imaginary Processor ………………. 341
A Simple Program Stored at Memory Address 100016 ………. 342
Signal Values for Sample I/O Device ……………………………… 351
Control Signal Levels for I/O and Memory Transactions…… 353
xx Computer Organization and Design Fundamentals
16-1
16-2
Summary of Intel 80×86 Bus Characteristics …………………… 360
Summary of the 80×86 Read and Write Control Signals……. 372
17-1
17-2
17-3
Memory Models Available for use with .MODEL ……………. 381
Summary of 80×86 Conditional Jumps……………………………. 388
80×86 Instructions for Modifying Flags ………………………….. 390
PREFACE
When I first taught computer organization to computer science
majors here at East Tennessee State University, I was not sure where to
begin. My training as an electrical engineer provided me with a
background in DC and AC electrical theory, electronics, and circuit
design. Was this where I needed to start? Do computer science majors
really need to understand computers at the transistor level?
The textbook used by my predecessors assumed the reader had had
some experience with electronics. The author went so far as to use
screen captures from oscilloscopes and other test equipment to describe
circuit properties. I soon found that this was a bad assumption to make
when it came to students of computer science.
To provide a lifeline to my floundering students, I began writing
supplementary notes and posting them to my course web site. Over the
years, the notes matured until eventually students stopped buying the
course textbook. When the on-line notes were discovered by search
engines, I began receiving messages from other instructors asking if
they could link to my notes. The answer was obvious: of course!
The on-line notes provided a wonderful opportunity. Instead of
requiring a textbook for my course, I could ask my students to purchase
hardware or software to supplement the university’s laboratory
equipment. This could include anything from external hard drives to
circuit components. By enhancing the hands-on portion of the course, I
hope that I have improved each student’s chance to learn and retain the
material.1
In April of 2004, I became aware of recent advances in selfpublishing with services such as Lulu.com. In an effort to reduce the
costs paid by students who were printing the course notes from the
web, I decided to compile my web notes into a book. For years, I had
been receiving comments from students about dried up printer
cartridges. I once found a student searching the recycled paper bin for
scrap paper on which to print my notes. Even our campus technology
group had begun to suggest I was one of the causes for the overuse of
campus printers.
1
Korwin, Anthony R., Jones, Ronald E., “Do Hands-On, Technology-Based
Activities Enhance Learning by Reinforcing Cognitive Knowledge and Retention?”
Journal of Technology Education, Vol. 1, No. 2, Spring 1990. Online. Internet.
Available WWW: http://scholar.lib.vt.edu/ejournals/JTE/v1n2/pdf/jones.pdf
xxi
xxii Computer Organization and Design Fundamentals
So here it is, a textbook open to anyone with a simple desire to learn
about the digital concepts of a computer. I’ve tried to address topics
such as analog to digital conversion, CRC’s, and memory organization
using practical terms and examples instead of the purely theoretical or
technical approaches favored by engineers. Hopefully I’ve succeeded.
I do not pretend to believe that this book alone will provide the
reader with the background necessary to begin designing and building
contemporary computer circuits. I do, however, believe that reading it
will give people the tools to become better developers of software and
computer systems by understanding the tools for logic design and the
organization of the computer’s internals.
The design concepts used for hardware are just as applicable to
software. In addition, an understanding of hardware can be applied to
software design allowing for improved system performance. This book
can be used as a springboard to topics such as advanced computer
architecture, embedded system design, network design, compiler
design, or microprocessor design. The possibilities are endless.
Organization of This Book
The material in this book is presented in three stages. The first stage,
Chapters 1 through 7, discusses the mathematical foundation and
design tools that address the digital nature of computers. The discussion
begins in Chapters 1, 2, and 3 where the reader is introduced to the
differences between the physical world and the digital world. These
chapters show how the differences affect the way the computer
represents and manipulates data. Chapter 4 introduces digital logic and
logic gates followed by Chapters 5, 6, and 7 where the tools of design
are introduced.
The second stage, Chapters 8 through 11, applies the fundamentals
of the first seven chapters to standard digital designs such as binary
adders and counters, checksums and cyclic redundancy checks,
network addressing, storage devices, and state machines.
The last stage, Chapters 12 through 17, presents the top-level view
of the computer. It begins with the organization of addressable memory
in Chapter 12. This is followed in Chapter 13 with a discussion of the
memory hierarchy starting with the physical construction of hard drives
and ending with the organization of cache memory and processor
registers. Chapter 14 brings the reader through the concepts of serial
protocols ending with descriptions of the IEEE 802.3 Ethernet, TCP,
Preface
xxiii
and IP protocols. Chapter 15 presents the theories of computer
architecture while Chapters 16 and 17 use the Intel 80×86 family as a
means of example.
Each chapter concludes with a short section titled “What’s Next?”
describing where the next chapter will take the reader. This is followed
by a set of questions that the reader may use to evaluate his or her
understanding of the topic.
Acknowledgments
I would like to begin by thanking my department chair, Dr. Terry
Countermine, for the support and guidance with which he provided me.
At first I thought that this project would simply be a matter of
converting my existing web notes into a refined manuscript. This was
not the case, and Dr. Countermine’s support and understanding were
critical to my success.
I would also like to thank my computer organization students who
tolerated being the test bed of this textbook. Many of them provided
suggestions that strengthened the book, and I am grateful to them all.
Most of all, I would like to thank my wife, Karen, who has always
encouraged and supported me in each of my endeavors. You provide
the foundation of my success.
Lastly, even self-published books cannot be realized without some
support. I would like to thank those who participate as contributors and
moderators on the Lulu.com forums. In addition, I would like to thank
Lulu.com directly for providing me with a quality outlet for my work.
Disclaimer
The information in this book is based on the personal knowledge
collected by David Tarnoff through years of study in the field of
electrical engineering and his work as an embedded system designer.
While he believes this information is correct, he accepts no
responsibility or liability whatsoever with regard to the application of
any of the material presented in this book.
In addition, the design tools presented here are meant to act as a
foundation to future learning. David Tarnoff offers no warranty or
guarantee toward products used or developed with material from this
book. He also denies any liability arising out of the application of any
tool or product discussed in this book. If the reader chooses to use the
material in this book to implement a product, he or she shall indemnify
xxiv Computer Organization and Design Fundamentals
and hold the author and any party involved in the publication of this
book harmless against all claims, costs, or damages arising out of the
direct or indirect application of the material.
David L. Tarnoff
Johnson City, Tennessee
USA
May 11, 2005
tarnoff@etsu.edu
Note About Third Printing
Over the past two years, a number of small issues have been
revealed to me about this work. A few topics needed elaboration and a
few errors that had slipped through the self-editing process needed
correction. There were not enough issues to require the release of a
second edition, but readers of this book should be aware that changes
have been made in this the third printing of the book.
The new topics now included in this book are Gray codes, signed
BCD, XOR boolean rules, Mealy state machines (the first printing only
addressed Moore state machines), DRAM technologies, and hard drive
access times. If any reader feels that additional topics should be
included in future printings or editions, please feel free to e-mail me at
tarnoff@etsu.edu.
David L. Tarnoff
July 6, 2007
CHAPTER ONE
Digital Signals and Systems
1.1 Should Software Engineers Worry About Hardware?
Some students of computer and information sciences look at
computer hardware the same way many drivers look at their cars: the
use of a car doesn’t require the knowledge of how to build one.
Knowing how to design and build a computer may not be vital to the
computer professional, but it goes a long way toward improving their
skills, i.e., making them better drivers. For anyone going into a career
involving computer programming, computer system design, or the
installation and maintenance of computer systems, the principles of
computer organization provide tools to create better designs. These
include:
•
•
•
•
•
System design tools – The same design theories used at the lowest
level of system design are also applied at higher levels. For
example, the same methods a circuit board designer uses to create
the interface between a processor and its memory chips are used to
design the addressing scheme of an IP network.
Software design tools – The same procedures used to optimize
digital circuits can be used for the logic portions of software.
Complex blocks of if-statements, for example, can be simplified or
made to run faster using these tools.
Improved troubleshooting skills – A clear understanding of the
inner workings of a computer gives the technician servicing it the
tools to isolate a problem quicker and with greater accuracy.
Interconnectivity – Hardware is needed to connect the real world to
a computer’s inputs and outputs. Writing software to control a
system such as an automotive air bag could produce catastrophic
results without a clear understanding of the architecture and
hardware of a microprocessor.
Marketability – Embedded system design puts microprocessors into
task-specific applications such as manufacturing, communications,
and automotive control. As processors become cheaper and more
powerful, the same tools used for desktop software design are being
applied to embedded system design. This means that the software
1
2 Computer Organization and Design Fundamentals
engineer with experience in hardware design has a significant
advantage over hardware engineers in this market.
If that doesn’t convince you, take a look at what Shigeki Ishizuka,
the head of Sony’s digital camera division, says about understanding
hardware. “When you control parts design, you can integrate the whole
package much more elegantly.” In other words, today’s business
environment of low cost and rapid market response, success may
depend on how well you control the hardware of your system.
Think of the myriad of systems around you such as your car, cell
phone, and PlayStation® that rely on a programmer’s understanding of
hardware. A computer mouse, for example, sends digital information
into the computer’s mouse port. In order for the software to respond
properly to the movement or button presses of the mouse, the software
designer must be able to interpret the digital signal.
On a much greater scale, consider a construction company with
projects scattered across a large region that wants to monitor its
equipment from a central location such as its corporate offices. A
system such as this could be used for inventory control allowing a
remote user to locate each piece of equipment from their Internetenabled desktop computer. E-mail alerts could be sent predicting
possible failures when conditions such as overheating or excessive
vibration are detected. The system could deliver e-mails or messages to
pagers in cases of theft or notify maintenance that periodic service is
needed. Here again, the link between software and hardware is critical.
An embedded processor inside the equipment communicates with
sensors that monitor conditions such as temperature, vibration, or oil
pressure. The processor is capable of transmitting this information to
the remote user via a cellular link either when prompted or as an
emergency notification. In addition, the processor may be capable of
using GPS to determine its geographic location. If the equipment is
moved outside of a specified range, a message can be sent indicating a
possible theft.
The design of a system such as this raises many questions including:
•
•
What physical values do the digital values that are read from the
sensors represent in the real world?
How can useful information be pulled from the data stream being
received by the processors?
Chapter 1: Digital Signals and Systems
•
•
3
How should the data be formatted for optimal storage, searching,
and retrieval?
Is it possible that using a slower data rate might actually mean
shorter connect times over expensive cellular links?
Figure 1-1 Sample Digital System
Computer organization theories answer these and many other questions.
1.2 Non-Digital Signals
The real world is analog. What does that mean? Well, an analog
value is equivalent to a floating-point number with an infinite number
of places to the right of the decimal point. For example, temperatures
do not take on distinct values such as 75°, 76°, 77°, 78°, etc. They take
values like 75.434535… In fact, between the temperatures 75.435° and
75.436°, there are an infinite number of possible values. A man doesn’t
weigh exactly 178 pounds. Add an atom, and his weight changes.
When values such as temperature or weight change over time, they
follow what is called a continuous curve. Between any two values on
the curve, an infinite number of values take place over an infinite
number of points in time.
Okay, so these are ridiculous examples. We can get by without
knowing the weight of a man plus or minus an atom. Heck, if we
4 Computer Organization and Design Fundamentals
measured to that level of accuracy, his weight would be changing every
second. (Time is also an analog value.) It is sufficient to say that analog
values represent a continuous signal with infinitesimal resolution.
Figure 1-2 Continuous Analog Signal with Infinite Resolution
1.3 Digital Signals
There is such a thing as an analog computer, a computer that
processes information using analog levels of electricity or the positions
of mechanical devices. The overwhelming majority of today’s
computers do not do this, however. Instead, they represent an analog
value by converting it to a number with a fixed resolution, i.e., a fixed
number of digits to the right of the decimal point. This measurement is
referred to as a digital value. If the value is changing with respect to
time, then a sequence of measurements can be taken, the period
between the measurements typically remaining fixed.
Time
(seconds)
0.00
0.10
0.20
0.30
0.40
Measurement
0.1987
0.2955
0.3894
0.4794
0.5646
Figure 1-3 Sample of Discrete Measurements Taken Every 0.1 Sec
Since computers look at the world with a fixed resolution in both
time and magnitude, when the computer records an analog signal such
as the sound waves from music, it does it by taking a sequence of snapshots. For example, assume Figure 1-2 is an analog “real world” signal
Chapter 1: Digital Signals and Systems
5
such as a sound wave. The computer can only measure the signal at
intervals. Each measurement is called a sample. The rate at which these
samples are taken is called the sampling rate. The X’s in Figure 1-4
represent these measurements.
Figure 1-4 Samples Taken of an Analog Signal
Two problems arise from this process: information can be lost
between the measurements and information can be lost due to the
rounding of the measurement. First, if the sampling rate is too slow,
then some details of the signal may be missed.
Missed
Anomaly
Figure 1-5 Slow Sampling Rate Missed an Anomaly
Second, if the computer does not record with enough accuracy (i.e.,
enough digits after the decimal point) an error may be introduced
between the actual measurement and the recorded value.
Accuracy of
computer allows
only these levels
of measurement
Analog Signal
Figure 1-6 Poor Resolution Resulting in an Inaccurate Measurement
6 Computer Organization and Design Fundamentals
These effects can be reduced by increasing the resolution of the
measurement and increasing the sampling rate. A discussion of this can
be found in Chapter 2 in the section titled “Sampling Theory”.
1.4 Conversion Systems
The typical system used to convert an external condition such as
pressure, temperature, or light intensity to a format usable by a digital
system is shown in the block diagram in Figure 1-7.
Sensor
Weak, noisy
analog signal
Signal
conditioning
Analog
to digital
converter
Strong, clean
analog signal
Digital
measurements
of analog signal
0.3238
0.3254
0.3312
0.3240
0.3221
Figure 1-7 Block Diagram of a System to Capture Analog Data
The interface between the external condition and the electronics of
the system is the sensor. This device converts the environmental
conditions into a signal readable by analog electronics. Often, this
signal is weak and is easily distorted by noise. Therefore, the output of
the sensor is usually amplified and cleaned up before being converted
to digital values by the Analog-to-Digital Converter (ADC).
Continuous operation of this system results in a sequence of digital
measurements or samples that are stored in the computer where it can
be viewed much like the table of numbers in a spreadsheet.
There are benefits to using data in a digital format rather than
analog. First, if an analog signal is transmitted over long distances,
noise attaches itself to the signal. To keep the signal strong enough to
reach its destination, it must be amplified. All of the noise that attached
itself to the signal, however, is amplified along with the original signal
Chapter 1: Digital Signals and Systems
7
resulting in distortion. For example, before the advent of digital phone
networks, long distance phone calls over analog lines were often full of
static and interference that made understanding people who were
physically farther away more difficult.
Noise cannot attach itself to a digital signal. Once an analog signal
has been converted to a sequence of numbers, the signal’s
characteristics remain the same as long as the numbers don’t change.
Therefore, digital systems such as the contemporary long-distance
phone system do not suffer from degradation over long distances.
A second benefit is that once a signal is turned into a sequence of
numbers, mathematical algorithms can be used to operate on the data.
Disciplines such as Digital Signal Processing (DSP) and the study of
wavelets allow for much more accurate processing of signals than
analog systems were ever able to achieve.
A sequence of digital numbers can also be stored more compactly
than an analog signal. The data compression behind the MP3
technology is not remotely possible with analog technology. In
addition, supplementary data can be stored along with the samples for
information such as digital watermarking for security or codes for error
checking or error correction.
These advantages come at a price, however. As mentioned earlier, if
the samples are taken too slowly, details of the analog input are missed.
If the resolution of the samples is not fine enough, the signal may not
be precisely represented with the digital values. Last of all, additional
hardware is required to convert the signal from analog to digital.
1.5 Representation of Digital Signals
Digital systems do not store numbers the way humans do. A human
can remember the number 4.5 and understand that it represents a
quantity. The digital system does not have this capability. Instead,
digital systems work with numbers using millions of tiny switches
called transistors. Each transistor can remember only one of two
possible values, on or off. This is referred to as a binary system.
The values represented by the transistors of a binary system can be
interpreted as needed by the application. On and off can just as easily
mean 1 or 0, yes or no, true or false, up or down, or high or low. At this
point, it is immaterial what the two values represent. What matters is
that there are only two possible values per transistor. The complexity of
the computer comes in how the millions of transistors are designed to
8 Computer Organization and Design Fundamentals
work together. For the purpose of this discussion, the two values of a
transistor will be referred to as logic 1 and logic 0.
Now let’s examine some of the methods used to represent binary
data by first looking at a single binary signal. Assume we are recording
the binary values present on a single wire controlling a light bulb.
Excluding lights controlled by dimmer switches, a light bulb circuit
is a binary system; the light is either on or off, a logic 1 or a logic 0
respectively. Over time, the state of the light bulb changes following
the position of the switch. The top portion of Figure 1-8 represents the
waveform of the binary signal controlling the light bulb based on the
changes in the switch position shown in the lower half of the figure.
Figure 1-8 Representation of a Single Binary Signal
This representation is much like a mathematical x-y plot where the
x-axis represents time and the y-axis identifies either logic 1 or 0.
Sometimes, two or more binary lines are grouped together to
perform a single function. For example, the overall lighting in a room
may be controlled by three different switches controlling independent
banks of lights. This circumstance may be represented with a diagram
such as the one shown in Figure 1-9.
Switch A
Switch B
Switch C
Figure 1-9 Representation of Multiple Digital Signals
Chapter 1: Digital Signals and Systems
9
Alternatively, multiple lines can be combined into a more abstract
representation such as the one shown in Figure 1-10.
During these periods, the data
signals do not change
Valid data
Valid data
Data is in
transition
Invalid or
undefined data
Valid data
No data
is available
Figure 1-10 Alternate Representation of Multiple Digital Signals
Two horizontal lines, one at a logic 1 level and one at a logic 0 level
indicate constant signals from all of the lines represented. A single
horizontal line running approximately between logic 1 and logic 0
means that the signals are not sending any data. This is different from
an “off” or logic 0 in that a logic 0 indicates a number while no data
means that the device transmitting the data is not available. Hash marks
indicate invalid or changing data. This could mean that one or all of the
signals are changing their values, or that due to the nature of the
electronics, the values of the data signals cannot be predicted. In the
later case, the system may need to wait to allow the signals to stabilize.
1.6 Types of Digital Signals
1.6.1 Edges
A single binary signal can have one of two possible transitions as
shown in Figure 1-11. The first one, a transition from a logic 0 to a
logic 1, is called a rising edge transition. The second one, a transition
from a logic 1 to a logic 0 is called a falling edge transition.
1.6.2 Pulses
A binary pulse occurs when a signal changes from one value to the
other for a short period, then returns to its original value. Examples of
this type of signal might be the power-on or reset buttons on a
10 Computer Organization and Design Fundamentals
computer (momentarily pressed, then released) or the button used to
initialize synchronization between a PDA and a computer.
Logic 1
Logic 1
Logic 0
Logic 0
a.) Rising Edge
b.) Falling Edge
Figure 1-11 Digital Transition Definitions
There are two types of pulses. The first is called a positive-going
pulse, and it has an idle state of logic 0 with a short pulse to logic 1.
The other one, a negative-going pulse, has an idle state of logic 1 with
a short pulse to logic 0. Both of these signals are shown in Figure 1-12.
Logic 1
Logic 1
Logic 0
Logic 0
a.) Positive-going
b.) Negative-going
Figure 1-12 Pulse Waveforms
1.6.3 Non-Periodic Pulse Trains
Some digital signals such as the data wires of an Ethernet link or the
data and address lines of a memory interface do not have a
characteristic pattern in their changes between logic 1 and logic 0.
These are called non-periodic pulse trains.
Figure 1-13 Non-Periodic Pulse Train
Like music, the duration of the notes or the spaces between the notes
can be longer or shorter. On the page, they do not look meaningful, but
once the reader is given the tools to interpret the signal, the data they
contain becomes clear.
Chapter 1: Digital Signals and Systems
11
1.6.4 Periodic Pulse Trains
Some signals act as the heartbeat to a digital system. For example, a
signal might tell a system, “Every 1/100th of a second, you need to
____.” The output from a car’s processor to control the engine’s spark
plug is such a signal. These signals are referred to as periodic pulse
trains. Like the drum beat to a song, a periodic pulse train is meant to
synchronize events or keep processes moving.
The defining characteristic of this type of waveform is that all
measurements between any two subsequent, identical parts of the
waveform produce the same value. This value is referred to as the
period, T, and it has units of seconds/cycle (read seconds per cycle).
Figure 1-14 identifies the measurement of a period in a typical periodic
Pulse Train.
t
w
Period = T
Period = T
Figure 1-14 Periodic Pulse Train
The measurement of the period does not fully describe a periodic
pulse train, however; a second measurement, the width of the pulse, tw,
is needed. For example, the two signals in Figure 1-15 have the same
period. Their pulse widths, however, are not the same. In signal a, tw is
about one-fourth of the signal’s period while tw of signal b is about onehalf of the signal’s period.
a)
b)
Figure 1-15 Periodic Pulse Train with Different Pulse Widths
The units of tw is seconds. Its value will always be greater than zero
and less than the period. A tw of zero implies the signal has no pulses,
and if tw equaled the period, then the signal would never go low.
12 Computer Organization and Design Fundamentals
It is also common to represent the rate of the pulses in a periodic
pulse train with the inverse measurement of the period. This
measurement, called the frequency of the periodic pulse train has units
of cycles/second, otherwise known as Hertz (Hz).
To determine the frequency of a periodic pulse train from the period,
invert the measurement for the period.
1
Frequency =
Period in seconds
(1.1)
Example
If it takes 0.1 seconds for a periodic pulse train to make a complete
cycle or period, what is that waveform’s frequency?
Solution
Frequency =
1
Period in seconds
Frequency =
1
0.1 seconds
Frequency = 10 Hz
Example
If a computer’s system clock is 2 Gigahertz (2,000,000,000 Hz),
what is the duration of its system clock’s period?
Solution
Inverting Equation 1.1 gives us the equation used to determine the
period from the frequency.
Period =
1
Frequency
Substituting 2,000,000,000 Hz for the frequency in this new equation
gives us the following solution.
Chapter 1: Digital Signals and Systems
Period =
13
1
2,000,000,000 Hz
Period = 0.0000000005 seconds = 0.5 nanoseconds
1.6.5 Pulse-Width Modulation
The last measurement of a periodic waveform is the duty cycle. The
duty cycle represents the percentage of time that a periodic signal is a
logic ‘1’. For example, Figure 1-16 represents a periodic pulse train
where tw is about one-quarter or 25% of the duration of the period.
Therefore, the duty cycle of this signal is 25%.
Logic 1
Logic 0
T
¼T
Figure 1-16 Periodic Pulse Train with 25% Duty Cycle
Equation 1.2 represents the formula used to calculate the duty cycle
where both tw and T have units of seconds.
Duty Cycle =
logic 1 pulse duration (tw)
Period (T)
x 100%
(1.2)
Since the range of tw is from 0 to T, then the duty cycle has a range
from 0% (a constant logic 0) to 100% (a constant logic 1).
Example
The typical human eye cannot detect a light flashing on and off at
frequencies above 40 Hz. For example, fluorescent lights flicker at a
low frequency, around 60 Hz, which most people cannot see. (Some
people can detect higher frequencies and are sensitive to what they
correctly perceive as the flashing of fluorescent lights.)
For higher frequencies, a periodic pulse train sent to a light appears
to the human eye to simply be dimmer than the same light sent a
constant logic 1. This technique can be used to dim light emitting
diodes (LEDs), devices that respond to only logic 1’s or logic 0’s. The
14 Computer Organization and Design Fundamentals
brightness of the LED with respect to the full on state is equivalent to
the duty cycle. For example, to make an LED shine half as bright as it
would with a constant logic 1 sent to it, the duty cycle should be 50%.
The frequency is irrelevant as long as it is higher than the human eye
can detect.
Example
Assume that a 1 kHz (1,000 Hz) periodic pulse train is sent to an
LED. What should the pulse width (tw) be to make the light emitted
from the LED one-third of its full capability?
Solution
Examining equation 1.2 shows that to determine the pulse width, we
must first get the values for the period and the duty cycle.
The duty cycle is equal to the level of intensity that the LED is to be
lit, i.e., one-third or 33%. The period, T, is equal to one over the
frequency.
1
Period =
Frequency
Period =
1
1,000 Hz
Period = 0.001 seconds
To determine the pulse width, solve equation 1.2 for tw, then
substitute the values for the period and the duty cycle.
Duty Cycle =
tw =
tw
T
x 100%
T x (Duty Cycle)
100%
tw = 0.001 seconds x 0.33
tw = 0.00033 seconds = 330 microseconds
Chapter 1: Digital Signals and Systems
15
1.7 Unit Prefixes
You may have noticed that in some of our examples, a prefix was
used with the units of seconds or Hertz. This is done to reduce the
number of leading zeros between a decimal point and a magnitude or to
reduce the number of trailing zeros in a very large magnitude.
A prefix replaces a power of 10 multiplier. For example, the
measurement 5,000 hertz is equivalent to 5 x 103 hertz. The multiplier
103 can be replaced with the prefix “kilo” giving us 5 kilohertz. Each
prefix has a single-letter abbreviation that can be used with the
abbreviation of the units. For example, to use kilo with the abbreviation
Hz, the single letter “k” would be used giving us kHz.
Throughout this book, many prefixes will be used to describe the
measurements being discussed. These are presented in the table in
Table 1-1. Note that there are prefixes well beyond those presented in
this table. They will not be used in this book.
Table 1-1 Unit Prefixes
Prefix
zetta
exa
peta
tera
giga
mega
kilo
milli
micro
nano
pico
Symbol
Z
E
P
T
G
M
k
m
μ or u
n
p
Power of 10
1021
1018
1015
1012
109
106
103
10-3
10-6
10-9
10-12
To use the table, just substitute the prefix for its power of ten. For
example, substitute 10-6 for the prefix “μ” in the value 15.6 μS. This
would give us 15.6 x 10-6 seconds, which in turn equals 0.0000156
seconds.
16 Computer Organization and Design Fundamentals
1.8 What’s Next?
In this chapter, we’ve seen how the methods that a computer uses to
store and interpret values are different from the ways in which those
values appear in the real world. We’ve also seen some of the methods
used to measure and represent these digital signals.
In Chapter 2 we will see how digital values are used to represent
integers. This is the first major step toward understanding some of the
idiosyncrasies of computing systems such as why a compiler might
restrict the values of a data type from –32,768 to 32,767. In addition, it
shows how some bugs occur in programs due to the misuse of data
types.
Problems
1.
Define the term “sample” as it applies to digital systems.
2.
Define the term “sampling rate” as it applies to digital systems.
3.
What are the two primary problems that sampling could cause?
4.
Name the three parts of the system used to input an analog signal
into a digital system and describe their purpose.
5.
Name four benefits of a digital system over an analog system.
6.
Name three drawbacks of a digital system over an analog system.
7.
True or False: Since non-periodic pulse trains do not have a
predictable format, there are no defining measurements of the
signal.
8.
If a computer runs at 12.8 GHz, what is the period of its clock
signal?
9.
If the period of a periodic pulse train is 125 nanoseconds, what is
the signal’s frequency?
10. If the period of a periodic pulse train is 50 microseconds, what
should the pulse width, tw, be to achieve a duty cycle of 15%?
11. True or False: A signal’s frequency can be calculated from its duty
cycle alone.
CHAPTER TWO
Numbering Systems
Chapter one discussed how computers remember numbers using
transistors, tiny devices that act like switches with only two positions,
on or off. A single transistor, therefore, can only remember one of two
possible numbers, a one or a zero. This isn’t useful for anything more
complex than controlling a light bulb, so for larger values, transistors
are grouped together so that their combination of ones and zeros can be
used to represent larger numbers.
This chapter discusses some of the methods that are used to
represent numbers with groups of transistors or bits. The reader will
also be given methods for calculating the minimum and maximum
values of each representation based on the number of bits in the group.
2.1 Unsigned Binary Counting
The simplest form of numeric representation with bits is unsigned
binary. When we count upward through the positive integers using
decimal, we start with a 0 in the one’s place and increment that value
until we reach the upper limit of a single digit, i.e., 9. At that point,
we’ve run out of the “symbols” we use to count, and we need to
increment the next digit, the ten’s place. We then reset the one’s place to
zero, and start the cycle again.
Ten’s
place
1
One’s
place
0
1
2
3
:
8
9
0
Figure 2-1 Counting in Decimal
Since computers do not have an infinite number of transistors, the
number of digits that can be used to represent a number is limited. This
17
18 Computer Organization and Design Fundamentals
would be like saying we could only use the hundreds, tens, and ones
place when counting in decimal.
This has two results. First, it limits the number of values we can
represent. For our example where we are only allowed to count up to
the hundreds place in decimal, we would be limited to the range of
values from 0 to 999.
Second, we need a way to show others that we are limiting the
number of digits. This is usually done by adding leading zeros to the
number to fill up any unused places. For example, a decimal 18 would
be written 018 if we were limited to three decimal digits.
Counting with bits, hereafter referred to as counting in binary, is
subject to these same issues. The only difference is that decimal uses
ten symbols (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9) while binary only uses two
symbols (0 and 1).
To begin with, Figure 2-2 shows that when counting in binary, we
run out of symbols quickly requiring the addition of another “place”
after only the second increment.
Another digit is added when we run
out of symbols for the first column.
Another digit is added when we run out
of symbols for the second column.
0
1
10
11
100
101
Figure 2-2 Counting in Binary
If we were counting using four bits, then the sequence would look
like: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001,
1010, 1011, 1100, 1101, 1110, and 1111. Notice that when restricted to
four bits, we reach our limit at 1111, which happens to be the fifteenth
value. It should also be noted that we ended up with 2 x 2 x 2 x 2 = 16
different values. With two symbols for each bit, we have 2n possible
combinations of symbols where n represents the number of bits.
In decimal, we know what each digit represents: ones, tens,
hundreds, thousands, etc. How do we figure out what the different
digits in binary represent? If we go back to decimal, we see that each
place can contain one of ten digits. After the ones digit counts from 0 to
Chapter 2: Numbering Systems
9, we need to increment the tens place. Subsequently, the third place is
incremented after 9 tens and 9 ones, i.e., 99 increments, have been
counted. This makes it the hundreds place.
In binary, the rightmost place is considered the ones place just like
decimal. The next place is incremented after the ones place reaches 1.
This means that the second place in binary represents the value after 1,
i.e., a decimal 2. The third place is incremented after a 1 is in both the
ones place and the twos place, i.e., we’ve counted to a decimal 3.
Therefore, the third place represents a decimal 4. Continuing this
process shows us that each place in binary represents a successive
power of two.
Figure 2-3 uses 5 bits to count up to a decimal 17. Examine each
row where a single one is present in the binary number. This reveals
what that position represents. For example, a binary 01000 is shown to
be equivalent to a decimal 8. Therefore, the fourth bit position from the
right is the 8’s position.
Decimal
value
0
1
2
3
4
5
6
7
8
Binary
value
00000
00001
00010
00011
00100
00101
00110
00111
01000
Decimal
value
9
10
11
12
13
14
15
16
17
Binary
value
01001
01010
01011
01100
01101
01110
01111
10000
10001
Figure 2-3 Binary-Decimal Equivalents from 0 to 17
This information will help us develop a method for converting
unsigned binary numbers to decimal and back to unsigned binary.
Some of you may recognize this as “base-2” math. This gives us a
method for indicating which representation is being used when writing
a number down on paper. For example, does the number 100 represent
a decimal value or a binary value? Since binary is base-2 and decimal
is base-10, a subscript “2” is placed at the end of all binary numbers in
19
20 Computer Organization and Design Fundamentals
this book and a subscript “10” is placed at the end of all decimal
numbers. This means a binary 100 should be written as 1002 and a
decimal 100 should be written as 10010.
2.2 Binary Terminology
When writing values in decimal, it is common to separate the places
or positions of large numbers in groups of three digits separated by
commas. For example, 34532374510 is typically written 345,323,74510
showing that there are 345 millions, 323 thousands, and 745 ones. This
practice makes it easier to read and comprehend the magnitude of the
numbers. Binary numbers are also divided into components depending
on their application. Each binary grouping has been given a name.
To begin with, a single place or position in a binary number is called
a bit, short for binary digit. For example, the binary number 01102 is
made up of four bits. The rightmost bit, the one that represents the ones
place, is called the Least Significant Bit or LSB. The leftmost bit, the
one that represents the highest power of two for that number, is called
the Most Significant Bit or MSB. Note that the MSB represents a bit
position. It doesn’t mean that a ‘1’ must exist in that position.
The next four terms describe how bits might be grouped together.
•
•
•
•
Nibble – A four bit binary number
Byte – A unit of storage for a single character, typically an eight
bit (2 nibble) binary number (short for binary term)
Word – Typically a sixteen bit (2 byte) binary number
Double Word – A thirty-two bit (2 word) binary number
The following are some examples of each type of binary number.
Bit
Nibble
Byte
Word
Double Word
12
10102
101001012
10100101111100002
101001011111000011001110111011012
2.3 Unsigned Binary to Decimal Conversion
As shown in section 2.1, each place or position in a binary number
corresponds to a specific power of 2 starting with the rightmost bit
Chapter 2: Numbering Systems
which represents 20=1. It is through this organization of the bits that we
will convert binary numbers to their decimal equivalent. Figure 2-4
shows the bit positions and the corresponding powers of two for each
bit in positions 0 through 7.
Numbered bit
7
position
Corresponding
27
power of 2
Decimal equivalent
128
of power of 2
6
5
4
3
2
1
0
26
25
24
23
22
21
20
64
32
16
8
4
2
1
Figure 2-4 Values Represented By Each of the First 8 Bit Positions
To begin converting an unsigned binary number to decimal, identify
each bit position that contains a 1. It is important to note that we
number the bit positions starting with 0 identifying the rightmost bit.
Next, add the powers of 2 for each position containing a 1. This sum
is the decimal equivalent of the binary value. An example of this
process is shown in Figure 2-5 where the binary number 101101002 is
converted to its decimal equivalent.
Bit Position
Binary Value
7
1
6
0
5
1
4
1
3
0
2
1
1
0
0
0
101101002 = 27 + 25 + 24 + 22
= 12810 + 3210 + 1610 + 410
= 18010
Figure 2-5 Sample Conversion of 101101002 to Decimal
This brings up an important issue when representing numbers with a
computer. Note that when a computer stores a number, it uses a limited
number of transistors. If, for example, we are limited to eight
transistors, each transistor storing a single bit, then we have an upper
limit to the size of the decimal value we can store.
21
22 Computer Organization and Design Fundamentals
The largest unsigned eight bit number we can store has a 1 in all
eight positions, i.e., 111111112. This number cannot be incremented
without forcing an overflow to the next highest bit. Therefore, the
largest decimal value that 8 bits can represent in unsigned binary is the
sum of all powers of two from 0 to 7.
111111112 = 27 + 26 + 25 + 24 + 23 + 22 + 21 + 20
= 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1
= 25510
If you add one to this value, the result is 256 which is 28, the power
of two for the next bit position. This makes sense because if you add 1
to 111111112, then beginning with the first column, 1 is added to 1
giving us a result of 0 with a 1 carry to the next column. This
propagates to the MSB where a final carry is passed to the ninth bit.
The final value is then 1000000002 = 25610.
111111112 + 1 = 1000000002 = 25610 = 28
Therefore, the maximum value that can be represented with 8 bits in
unsigned binary is 28 – 1 = 255.
It turns out that the same result is found for any number of bits. The
maximum value that can be represented with n bits in unsigned binary
is 2n – 1.
Max unsigned binary value represented with n bits = 2n – 1
(2.1)
We can look at this another way. Each digit of a binary number can
take on 2 possible values, 0 and 1. Since there are two possible values
for the first digit, two possible values for the second digit, two for the
third, and so on until you reach the n-th bit, then we can find the total
number of possible combinations of 1’s and 0’s for n-bits by
multiplying 2 n-times, i.e., 2n.
How does this fit with our upper limit of 2n-1? Where does the “-1”
come from? Remember that counting using unsigned binary integers
begins at 0, not 1. Giving 0 one of the bit patterns takes one away from
the maximum value.
Chapter 2: Numbering Systems
2.4 Decimal to Unsigned Binary Conversion
Converting from decimal to unsigned binary is a little more
complicated, but it still isn’t too difficult. Once again, there is a welldefined process.
To begin with, it is helpful to remember the powers of 2 that
correspond to each bit position in the binary numbering system. These
were presented in Figure 2-4 for the powers of 20 up to 27.
What we need to do is separate the decimal value into its power of 2
components. The easiest way to begin is to find the largest power of 2
that is less than or equal to our decimal value. For example if we were
converting 7510 to binary, the largest power of 2 less than or equal to
7510 is 26 = 64.
The next step is to place a 1 in the location corresponding to that
power of 2 to indicate that this power of 2 is a component of our
original decimal value.
Next, subtract this first power of 2 from the original decimal value.
In our example, that would give us 7510 – 6410 = 1110. If the result is not
equal to zero, go back to the first step where we found the largest
power of 2 less than or equal to the new decimal value. In the case of
our example, we would be looking for the largest power of 2 less than
or equal to 1110 which would be 23 = 8.
When the result of the subtraction reaches zero, and it eventually
will, then the conversion is complete. Simply place 0’s in the bit
positions that do not contain 1’s. Figure 2-6 illustrates this process
using a flowchart.
If you get all of the way to bit position zero and still have a non-zero
result, then one of two things has happened. Either there was an error in
one of your subtractions or you did not start off with a large enough
number of bits. Remember that a fixed number of bits, n, can only
represent an integer value up to 2n – 1. For example, if you are trying to
convert 31210 to unsigned binary, eight bits will not be enough because
the highest value eight bits can represent is 28 – 1 = 25510. Nine bits,
however, will work because its maximum unsigned value is 29 – 1 =
51110.
23
24 Computer Organization and Design Fundamentals
Start
Find the largest power of 2
less than or equal to the
decimal value being converted
Place a 1 in the bit
position corresponding to
that power of 2
Subtract that power of 2 from
the decimal value. This will
be the new decimal value.
Is new
decimal value equal
to zero?
Yes
End
No
Figure 2-6 Decimal to Unsigned Binary Conversion Flow Chart
Example
Convert the decimal value 13310 to an 8 bit unsigned binary number.
Solution
Since 13310 is less than 28 – 1 = 255, 8 bits will be sufficient for this
conversion. Using Figure 2-4, we see that the largest power of 2 less
than or equal to 13310 is 27 = 128. Therefore, we place a 1 in bit
position 7 and subtract 128 from 133.
Bit position
7
1
6
5
4
133 – 128 = 5
3
2
1
0
Chapter 2: Numbering Systems
Our new decimal value is 5. Since this is a non-zero value, our next
step is to find the largest power of 2 less than or equal to 5. That would
be 22 = 4. So we place a 1 in the bit position 2 and subtract 4 from 5.
Bit position
7
1
6
5
4
3
2
1
1
0
5–4=1
Our new decimal value is 1, so find the largest power of 2 less than
or equal to 1. That would be 20 = 1. So we place a 1 in the bit position 0
and subtract 1 from 1.
Bit position
7
1
6
5
4
3
2
1
1
0
1
1–1=0
Since the result of our last subtraction is 0, the conversion is
complete. Place zeros in the empty bit positions.
Bit position
7
1
6
0
5
0
4
0
3
0
2
1
1
0
0
1
And the result is:
13310 = 100001012
2.5 Binary Representation of Analog Values
Converting unsigned (positive) integers to binary is only one of the
many ways that computers represent values using binary bits. This
chapter still has two more to cover, and Chapter 3 will cover even
more.
This section focuses on the problems and solutions of trying to map
real world values such as temperature or weight from a specified range
to a binary integer. For example, a computer that uses 8 bits to
represent an integer is capable of representing 256 individual values
from 0 to 255. Temperature, however, is a floating-point value with
25
26 Computer Organization and Design Fundamentals
unrealistic upper and lower limits. Can we get a computer to represent a
temperature using eight bits? The answer is yes, but it will cost us in
the areas of resolution and range.
Another example of analog values is the pattern of sound waves
such as that from music. Figure 2-7 represents such a signal.
Figure 2-7 Sample Analog Signal of Sound
Remember that a single binary bit can be set to only one of two
values: logic 1 or logic 0. Combining many bits together allows for a
range of integers, but these are still discrete values. The real world is
analog, values represented with floating-point measurements capable of
infinite resolution. To use an n-bit binary number to represent analog,
we need to put some restrictions on what is being measured.
First, an n-bit binary number has a limited range. We saw this when
converting unsigned positive integers to binary. In this case, the lower
limit was 0 and the upper limit was 2n-1. To use n-bits to represent an
analog value, we need to restrict the allowable range of analog
measurements. This doesn’t need to be a problem.
For example, does the typical bathroom scale need to measure
values above 400 pounds? If not, then a digital system could use a 10bit binary number mapped to a range from zero to 400 pounds. A
binary 00000000002 could represent zero pounds while 11111111112
could represent 400 pounds.
What is needed next is a method to map the values inside the range
zero to 400 pounds to the binary integers in the range 00000000002 to
11111111112. To do this, we need a linear function defining a one-toone mapping between each binary integer and the analog value it
represents. To do this, we turn to the basic math expression for a linear
function.
y = mx + b
Chapter 2: Numbering Systems
This function defines m as the rate of the change in y with respect to
changes in x and b as the value y is set to when x equals 0. We can use
this expression to map a binary integer x to an analog value y.
The slope of this function, m, can be calculated by dividing the
range of analog values by the number of intervals defined by the n-bit
binary integer. The number of intervals defined by the n-bit binary
integer is equal to the upper limit of that binary number if it were being
used as an unsigned integer, i.e., 2n-1.
m=
Range of analog values
Number of intervals of binary integer
m=
Max analog value – Min analog value
2n – 1
(2.2)
Let’s go back to our example of the kitchen scale where the
maximum analog value is 400 pounds while the minimum is zero
pounds. If a 10-bit binary value is used to represent this analog value,
then the number of intervals of the binary integer is 210 – 1 = 1023.
This gives us a slope of:
m=
400 pounds – 0 pounds
1023 binary increments
= 0.391 pounds/binary increment
That means that each time the binary number increments, e.g.,
01101100102 goes to 01101100112, it represents an increment in the
analog value of 0.391 pounds. Since a binary value of 00000000002
represents an analog value of 0 pounds, then 00000000012 represents
0.391 pounds, 00000000102 represents 2 × 0.391 = 0.782 pounds,
00000000112 represents 3 × 0.391 = 1.173 pounds, and so on.
In some cases, the lower limit might be something other than 0. This
is important especially if better accuracy is required. For example, a
kitchen oven may have an upper limit of 600oF. If zero were used as the
lower limit, then the temperature range 600oF – 0oF = 600oF would
need to …
