Computer Organization and Design Fundamentals Study Guide and Chapter Summaries – David Tarnoff (Revised 1st Edition) BSCS / BSIT

BSCS and BSIT students can use this guide to study the complete textbook “Computer Organization and Design Fundamentals” by David L. Tarnoff of East Tennessee State University. The author offers the book free of charge, chapter by chapter and as one full file, and it covers the ground of a first Digital Logic Design course and the start of Computer Organization and Assembly Language (COAL).

The book builds from the bottom up, as its subtitle says: Examining Computer Hardware from the Bottom to the Top. It starts with signals and binary numbers, moves through gates, Boolean algebra, Karnaugh maps, adders, latches and state machines, and finishes with memory, caches, serial protocols and a first look at the Intel 80×86 and its assembly language. Every chapter ends with a short What’s Next? section and a set of problems, so it works as a semester textbook and as revision material before a paper.

Book Overview

Chapter List

Chapter 1: Digital Signals and Systems

Stage 1: Foundations · Difficulty: Easy · Key topics: analog vs digital, sampling, ADC, logic levels, edges, pulse trains, duty cycle, PWM, unit prefixes

The chapter begins by asking why software people should care about hardware, and answers with five benefits: better design tools, troubleshooting, interconnectivity, marketability and software that runs faster. It then contrasts the analog real world, where a value can have infinitely many decimal places, with digital values captured as samples taken at a sampling rate. A capture system needs a sensor, signal conditioning and an analog-to-digital converter. Digital signals are drawn as logic 1 and logic 0 waveforms, and the chapter defines edges, pulses, periodic pulse trains, period, frequency, duty cycle and pulse-width modulation, finishing with unit prefixes.

Key Points:

• A sample is one measurement of a changing value; the sampling rate is how often samples are taken.
• An analog input chain has three parts: sensor, signal conditioning and an analog-to-digital converter (ADC).
• Noise cannot attach itself to a digital signal, so digital data survives long distances; the costs are missed detail, limited resolution and extra conversion hardware.
• A rising edge is a 0-to-1 transition and a falling edge is 1-to-0.
• Frequency is the inverse of the period: a 0.1 s period is 10 Hz, and a 2 GHz clock has a 0.5 ns period.
• Duty cycle = pulse width / period x 100%; a 50% duty cycle drives an LED at half brightness.

Memory Tip: Frequency and period are two ways of saying the same thing, so convert by flipping the number: 1 kHz means a 1 ms period, and a 1 ms period means 1 kHz.

Common Mistake: Thinking a lower duty cycle means a slower signal. The frequency stays the same; only the fraction of each cycle spent at logic 1 changes.

Important Questions:

• What is the difference between a sample and the sampling rate? A sample is a single measurement of a changing value; the sampling rate is the number of samples taken per second.
• How are frequency and period related? Frequency is 1 divided by the period, so a signal with a 125 ns period has a frequency of 8 MHz.

Chapter 2: Numbering Systems

Stage 1: Foundations · Difficulty: Easy · Key topics: unsigned binary, bit, nibble, byte, word, conversions, analog mapping, resolution, Nyquist theorem, hexadecimal, BCD, Gray code

Transistors store one bit each, so this chapter shows how groups of bits represent numbers. It starts with unsigned binary counting, where n bits give 2^n values, and with the vocabulary of LSB, MSB, nibble, byte and word. Conversion is taught both ways, using the subtraction of powers of two for decimal to binary. The chapter then maps analog values such as a bathroom scale reading or an oven temperature onto binary using a slope equation and a resolution formula, explains aliasing and the Nyquist theorem, and ends with three special codes: hexadecimal, binary coded decimal and Gray code.

Key Points:

• n bits give 2^n combinations, and the largest unsigned value is 2^n – 1 (255 for 8 bits).
• A nibble is 4 bits, a byte is typically 8, a word is typically 16 and a double word is 32.
• Resolution = analog range / (2^n – 1); more bits mean a finer step.
• Nyquist theorem: sample at more than twice the highest frequency you want to keep. Audio CDs use 44,100 samples per second, which allows frequencies up to 22,050 Hz.
• Hexadecimal gives one symbol per nibble; computers use binary and only humans use hex.
• BCD stores each decimal digit in its own nibble, and the patterns 1010 to 1111 are invalid as digits.
• Gray code changes exactly one bit between neighbouring values: 000, 001, 011, 010, 110, 111, 101, 100.

Memory Tip: For decimal to binary, write 128 64 32 16 8 4 2 1 above eight empty boxes, then tick off each power of two that fits into what is left.

Common Mistake: Using 2^n instead of 2^n – 1 for the maximum value. Counting starts at zero, so 8 bits top out at 255, not 256.

Important Questions:

• How many bits are needed to store 768 in unsigned binary? Ten bits. Nine bits reach only 511, while ten bits reach 1023.
• What sampling rate is needed to capture frequencies up to 155 kHz? More than twice the highest frequency, so more than 310 kHz, according to the Nyquist theorem.

Chapter 3: Binary Math and Signed Representations

Stage 1: Foundations · Difficulty: Medium · Key topics: binary addition and subtraction, one’s complement, two’s complement, signed magnitude, IEEE 754, BCD addition, shifting, overflow

This chapter explains how a processor does arithmetic and why its answers sometimes go wrong. Addition and subtraction work column by column with carries and borrows. Negative numbers come next: one’s complement flips every bit, two’s complement flips and adds 1, and signed magnitude uses the MSB as a sign. The same pattern, 10100110, can mean 166, -90 or -38 depending on the interpretation. The chapter then covers fractional binary and IEEE 754 floating point, hexadecimal and BCD addition, shifting as fast multiplication and division by powers of two, and finally how to detect arithmetic overflow.

Key Points:

• Two’s complement = invert all bits, then add 1. Shortcut: copy bits from the right up to and including the first 1, then invert the rest.
• For n bits: unsigned 0 to 2^n – 1; two’s complement -2^(n-1) to 2^(n-1) – 1; signed magnitude -(2^(n-1) – 1) to 2^(n-1) – 1.
• Signed magnitude has two zeros (00000000 and 10000000), so it wastes one value.
• IEEE 754 single precision uses 1 sign bit, 8 exponent bits and 23 fraction bits; double precision uses 1, 11 and 52.
• In BCD addition, add 6 to any nibble that is invalid or produced a carry.
• A left shift multiplies by 2 and a right shift divides by 2; a right shift of a negative two’s complement number must copy the MSB to keep the sign.
• Unsigned overflow shows as a carry out of the MSB; two’s complement overflow happens only when two operands of the same sign give a result of the opposite sign.

Memory Tip: Treat the MSB of a two’s complement number as worth minus 2^(n-1). Then 10010100 is -128 + 16 + 4 = -108, with no need to invert anything.

Common Mistake: Reading a bit pattern without knowing its type and width. The same 10010100 is -108 as 8-bit two’s complement but 148 when it is a 10-bit number with leading zeros.

Important Questions:

• What is the 8-bit two’s complement of 10 (00001010)? Invert to get 11110101 and add 1 to get 11110110, which represents -10.
• How do you detect overflow when adding two’s complement numbers? Only operands with the same sign can overflow, and it is detected when the result has the opposite sign. For example 99 + 53 in 8 bits gives 10011000, which reads as -104.

Chapter 4: Logic Functions and Gates

Stage 1: Foundations · Difficulty: Easy · Key topics: NOT, AND, OR, XOR, NAND, NOR, XNOR, truth tables, timing diagrams, combinational logic

Chapter 4 introduces the first real hardware building blocks. A logic gate takes one or more binary inputs and produces a single output bit by a fixed rule. The four primary gates are NOT, AND, OR and XOR, each shown with a real-world example such as headlight sensors, lamp switches and alarm sensors. The chapter teaches how to build a truth table with 2^n rows, how to use a don’t care symbol, and how to read timing diagrams. It then connects gates into combinational circuits, adds NAND, NOR and XNOR, and shows a column-by-column method for finding the truth table of any multi-level circuit.

Key Points:

• NOT flips its single input; AND outputs 1 only if all inputs are 1; OR outputs 0 only if all inputs are 0.
• XOR outputs 1 when an odd number of inputs are 1, which makes it a natural error checker.
• A circuit with n inputs has a truth table of 2^n rows; a wrong row count means a pattern is missing or duplicated.
• NAND outputs 1 if any input is 0, and every digital circuit can be built from NAND gates alone.
• A don’t care (X) lets one row stand for several when an input cannot change the output.
• For a multi-level circuit, add one truth table column per gate, in signal order; the last column is the output.

Memory Tip: Read the problem statement for the words “and” and “or”. Each one points straight at an AND or OR gate in the circuit.

Common Mistake: Treating a three-input XOR as “exactly one input is 1”. It outputs 1 for any odd number of ones, so inputs 1, 1, 1 also give 1.

Important Questions:

• How many rows does a four-input truth table have? Sixteen, because 2^4 = 16.
• What does a NAND gate output, and why is it important? It outputs 0 only when all inputs are 1. It is one of the fastest gates, and any digital circuit can be built from NAND gates alone.

Chapter 5: Boolean Algebra

Stage 1: Foundations · Difficulty: Medium · Key topics: Boolean expressions, precedence, commutative, associative and distributive laws, NOT, OR, AND and XOR rules, simplification, DeMorgan’s theorem

Schematics and truth tables get unwieldy for large circuits, so this chapter introduces Boolean expressions. AND is written like multiplication, OR like addition, NOT as a bar and XOR as the function that is true when its inputs differ. Precedence matters: a bar over one variable first, then AND, then OR, with parentheses overriding everything. The chapter converts circuits to expressions and back, lists the commutative, associative and distributive laws, and presents the rules for each gate, including derived rules proved with truth tables and the FOIL expansion. Worked simplifications show fewer gates for the same output, and DeMorgan’s theorem lets inverters move across AND and OR.

Key Points:

• AND is written A · B, OR is A + B and NOT is a bar over the variable.
• AND is evaluated before OR unless parentheses say otherwise.
• Distributive law: A(B + C) = AB + AC; the commutative and associative laws hold for both AND and OR.
• OR rules: A + 0 = A, A + 1 = 1, A + A = A and A + NOT A = 1. AND rules: A · 0 = 0, A · 1 = A, A · A = A and A · NOT A = 0.
• Derived rules: A + AB = A and (A + B)(A + C) = A + BC.
• DeMorgan: an inverter on the output of an AND gate can be pushed to the inputs if the AND becomes an OR, and the reverse also holds.
• A simpler expression means fewer gates, a cheaper and smaller board and lower power; in software it can mean faster code or less memory.

Memory Tip: For DeMorgan, remember “break the bar, change the sign”: splitting a bar that covers several variables turns AND into OR and OR into AND.

Common Mistake: Treating 1 + 1 as 2. In Boolean algebra the plus sign means OR, so 1 + 1 = 1 and A + A = A.

Important Questions:

• What does DeMorgan’s theorem say? The inverse of an AND equals the OR of the inverted inputs, and the inverse of an OR equals the AND of the inverted inputs. It lets you remove logic layers by moving inverters back to the inputs.
• Why simplify a Boolean expression? The same output can be produced with fewer gates, which lowers cost, board size and power use, and in software can speed up conditions.

Chapter 6: Standard Boolean Expression Formats

Stage 1: Foundations · Difficulty: Medium · Key topics: sum-of-products, product-of-sums, truth table conversion, NAND-NAND logic, two-level circuits

Standards let independently designed parts work together, and this chapter gives two standard shapes for combinational logic. A sum-of-products (SOP) expression is an OR of AND terms, so a signal crosses at most an inverter, an AND gate and an OR gate. The chapter shows how to turn an SOP into a truth table, where each product lights up one row, and how to turn a truth table back into SOP by writing one product for every row with output 1. Product-of-sums (POS) is the mirror image, built from the rows with output 0. The last section uses DeMorgan to build any SOP circuit from NAND gates only.

Key Points:

• SOP is an OR of AND terms; POS is an AND of OR terms. Neither allows parentheses or a bar over more than one variable.
• Truth table to SOP: one product per row whose output is 1, each product containing every variable.
• Truth table to POS: one sum per row whose output is 0, inverting the inputs that are 1 in that row.
• A product that leaves out a variable is 1 in two rows; each missing variable doubles the rows.
• NAND-NAND logic replaces the AND-OR structure with NAND gates only, so one gate type builds the whole system.
• NAND is the fastest gate in most technologies, which makes the NAND-NAND form quicker than AND-OR.

Memory Tip: SOP hunts for the ones and POS hunts for the zeros. If you can say which output value you are reading, you know which form to write.

Common Mistake: In POS, copying the row’s inputs as they are. For the zero row 101 the sum must use the inverted inputs, so that every term in the sum is 0 in that row.

Important Questions:

• What is the difference between SOP and POS? SOP is an OR of ANDed product terms built from the output-1 rows; POS is an AND of ORed sum terms built from the output-0 rows.
• Why is NAND-NAND preferred over AND-OR? Every gate is the same type, and NAND is typically the fastest gate, so the circuit is simpler to build and quicker.

Chapter 7: Karnaugh Maps

Stage 1: Foundations · Difficulty: Medium · Key topics: Karnaugh map, Gray code ordering, rectangles, minimum SOP, wrap-around, don’t care conditions

An SOP taken straight from a truth table is correct but rarely minimal. The Karnaugh map rearranges the truth table into a grid with one cell per row, so that neighbouring cells differ in exactly one input and that input can be dropped. Two-input maps are 2×2, three-input maps are 2×4 and four-input maps are 4×4, with rows and columns in Gray code order; five inputs no longer fit on a flat map. The chapter gives the rules for valid rectangles and works a four-input example where eight ones reduce to three terms. It ends with don’t care cells, which can be treated as 0 or 1, whichever gives bigger rectangles.

Key Points:

• A map has one cell per truth table row; rows and columns of a 4-row or 4-column map are ordered 00, 01, 11, 10.
• Rectangles must hold only ones, have a size that is a power of two (1, 2, 4, 8 or 16), and may wrap around the edges.
• Every rectangle should be as large as possible, every 1 must be covered, and each rectangle needs at least one cell no other rectangle covers.
• Doubling a rectangle drops one variable: 2 cells drop one input, 4 cells drop two, 8 cells drop three.
• Inputs that stay constant across a rectangle form the product: 1 means the variable, 0 means its inverse.
• A don’t care is treated as 1 only when it makes a rectangle larger; otherwise treat it as 0.

Memory Tip: Picture the map as a doughnut: the left edge touches the right edge and the top touches the bottom, so groups can wrap around.

Common Mistake: Labelling the rows or columns 00, 01, 10, 11. Going from 01 to 10 changes two inputs at once, so neighbouring cells stop being logically adjacent.

Important Questions:

• Why do Karnaugh maps use the order 00, 01, 11, 10? Neighbouring cells must differ in exactly one input so the differing input can drop out. Normal binary order changes two inputs between 01 and 10.
• How many inputs does a rectangle of 4 cells remove? Two. Each doubling of the rectangle drops one variable from the product.

Chapter 8: Combinational Logic Applications

Stage 2: Applying the fundamentals · Difficulty: Medium · Key topics: half adder, full adder, carry look-ahead, seven-segment display, active-low signals, decoder, multiplexer, demultiplexer, integrated circuits

The book now moves from theory to real circuits, and each application follows the same path: problem definition, truth table, Boolean expression, logic diagram. The half adder produces a sum and a carry, the full adder adds a carry-in, and a 16-bit adder chains one half adder with fifteen full adders, which creates carry delay that look-ahead adders reduce. A seven-segment display driver is worked out with a Karnaugh map. The chapter then covers active-low enables, decoders, multiplexers and demultiplexers, and finishes with how to wire a 7400 NAND chip on a protoboard with an LED and a pull-up resistor.

Key Points:

• Half adder: Sum = A XOR B and Carryout = A AND B; it can only handle the rightmost column.
• Full adder adds A, B and Carryin; its Carryout is B·Cin + A·B + A·Cin.
• A seven-segment driver takes a 4-bit input and drives seven outputs from a 16-row truth table.
• Active-low means a device is enabled by logic 0; it is shown with a bar over the name or a small circle on the pin.
• A decoder with n inputs has 2^n outputs and exactly one is active at a time.
• A multiplexer uses n select lines to pass one of 2^n data inputs to a single output; a demultiplexer does the reverse.
• The 7400 chip holds four two-input NAND gates; an LED always needs a series resistor.

Memory Tip: Multiplexer is the TV channel selector (many channels in, one picture out). Demultiplexer is the computer choosing which printer gets the job (one source in, many destinations out).

Common Mistake: Forgetting that active-low means 0 is the “on” value. An enable of 0 selects the device and 1 switches it off.

Important Questions:

• What is the difference between a half adder and a full adder? A half adder adds two bits and has no carry-in; a full adder adds two bits plus a carry-in, so it can be chained to add multi-bit numbers.
• What does a multiplexer do? It uses select lines to connect one of its 2^n data inputs to the output, so three select lines choose one of eight inputs.

Chapter 9: Binary Operation Applications

Stage 2: Applying the fundamentals · Difficulty: Hard · Key topics: bitwise AND, OR, XOR, masks, parity, checksum, cyclic redundancy check, Hamming code, error correction

This chapter turns logic into software tools, mostly for catching and fixing errors. Bitwise operators in C clear bits with AND, set them with OR and toggle them with XOR, with examples such as an odd-even test, an IPv4 subnet check, auditorium lights and turn indicators. Comparing two streams with XOR and adding a parity bit detect errors, while a checksum adds up the data and can use one’s or two’s complement forms. A cyclic redundancy check divides the data using XOR subtraction and sends the remainder, and a Hamming code uses overlapping parity groups to find and correct a single flipped bit.

Key Points:

• AND with a mask clears bits, OR sets bits and XOR toggles them; in C the operators are &, |, ^ and ~.
• Testing the LSB with a mask of 00000001 is much faster than dividing and multiplying to check odd or even.
• A parity bit detects an odd number of bit errors but misses two flipped bits.
• With a one’s complement checksum, datasum plus checksum gives all ones; with a two’s complement checksum it gives all zeros.
• CRC: append n-1 zeros, divide with XOR subtraction, append the remainder; the receiver divides again and a zero remainder means no error.
• Standard CRC divisors include the 17-bit CRC-CCITT (0x11021) and the 33-bit IEEE 802.3 Ethernet value (0x104C11DB7).
• Hamming code needs p parity bits for n data bits where p + n is at most 2^p – 1; an extra overall parity bit gives single-error correction and double-error detection.

Memory Tip: Think of XOR as a programmable inverter. Where the mask bit is 0 the data passes through unchanged, and where it is 1 the data bit flips.

Common Mistake: Believing parity or a simple checksum catches every error. Two flipped bits leave parity unchanged, and errors that cancel out can leave a checksum unchanged.

Important Questions:

• How can you quickly tell whether an integer is odd? AND it with 00000001. A result of 1 means the least significant bit is set, so the number is odd.
• Why is a CRC stronger than a simple checksum? A simple sum can miss errors that cancel out or ignore data order, while a CRC uses the remainder of a division, so a small change in the data changes the remainder.

Chapter 10: Memory Cells

Stage 2: Applying the fundamentals · Difficulty: Medium · Key topics: rising and falling edges, Q and Q0, undefined states, S-R latch, D latch, edge-triggered and transparent latches, divide-by-two, counter

Processors need to remember values such as a running total, so this chapter builds a one-bit memory cell. It first adds new truth table symbols: arrows for rising and falling edges, Q for a stored value, Q0 for the previously stored value and U for an undefined or avoided condition. An S-R latch is built from two cross-connected NAND gates with feedback, giving set, reset and hold behaviour plus one illegal input. A D latch adds a data input and a clock, in edge-triggered and transparent forms. The chapter applies latches to a divide-by-two circuit, a binary counter and an eight-bit parallel data output with a write line.

Key Points:

• S-R latch (NAND version): S=0, R=1 sets Q to 1; S=1, R=0 resets Q to 0; S=1, R=1 holds the old value Q0; S=0, R=0 is illegal.
• Q0 means the previously stored value and U marks a condition that is undefined or must be avoided.
• A D latch has a data input D and a clock input that decides when D is stored.
• An edge-triggered latch copies D to Q only at a clock transition; a transparent latch passes D to Q the whole time the clock is at its passing level.
• Feeding the inverted Q back to D makes Q toggle on each clock edge, which divides the frequency by two; n stages divide by 2^n.
• Cascaded divide-by-two stages count pulses in binary, which makes a counter.

Memory Tip: Think of the clock as a camera shutter. An edge-triggered latch takes its picture at the click; a transparent latch is like keeping the shutter open while the clock is at its passing level.

Common Mistake: Mixing up edge-triggered and transparent latches. A transparent latch follows D for as long as the clock is at its passing level; only the edge-triggered one samples at a single instant.

Important Questions:

• Why is S=0 and R=0 illegal for the NAND S-R latch? Both outputs go to 1, and when the inputs return to 1 the final state is unpredictable.
• How does a latch divide a clock frequency by two? The inverted output Q is fed back to D, so Q flips on every rising clock edge and completes one cycle for every two input cycles.

Chapter 11: State Machines

Stage 2: Applying the fundamentals · Difficulty: Hard · Key topics: states, state diagrams, next-state logic, latches, design process, pattern detection, Moore and Mealy machines

A state machine produces outputs that depend on its inputs and also on what it has remembered, such as a traffic light or an elevator that must know its current floor. The chapter defines states and draws state diagrams with circles for states, arrows for transitions and a reset arrow for the initial state, using an up-down 3-bit counter as the example. It lists errors to check, such as unreachable states and missing transitions, and shows the three-block circuit: next-state logic, state latches and output logic. A push-button light and a serial pattern detector are designed step by step, and the chapter ends by comparing Moore and Mealy machines.

Key Points:

• A state machine circuit has three blocks: next-state logic, latches that hold the current state, and output logic.
• n latches can hold up to 2^n states; ten states need four latches.
• With n inputs, every state needs exactly 2^n outgoing transitions; a state with no incoming transition is unreachable and must be removed.
• The initial state is marked by an arrow labelled reset.
• Moore machine: output depends only on the current state. Mealy machine: output depends on the state and the input, and transitions are labelled input/output.
• How you number the states changes the logic: renumbering two states in the push-button light turned the output equation into a plain wire.

Memory Tip: In a Moore machine the output sits inside the circle (it belongs to the state). In a Mealy machine the output rides on the arrow (it depends on the input too).

Common Mistake: Leaving out transitions. A state diagram is incomplete unless every state defines what happens for every possible input combination.

Important Questions:

• How many latches does a 28-state machine need? Five. Four latches give only 16 states and five give 32.
• What is the difference between a Moore and a Mealy machine? Moore outputs depend only on the current state; Mealy outputs depend on the current state and the present input.

Chapter 12: Memory Organization

Stage 3: The computer as a whole · Difficulty: Medium · Key topics: memory array, address decoder, chip select, buses, tristate outputs, memory map, memory-mapped I/O, SRAM, DRAM, SDRAM, DDR

After a short look at magnetic core memory, the chapter shows how modern memory keeps the same grid: rows are locations and columns are bits, which is where the notation 1K x 8 comes from. The processor sends an address, a decoder activates one row, and chip select, read and write signals control the transfer. The interfacing section covers data, address and control buses, tristate outputs to avoid contention, memory maps, splitting an address into enable bits and device bits, and designing an active-low chip select. The same idea is applied to IP subnets. The last part covers memory-mapped I/O and compares RAM, ROM, SRAM, DRAM, FPM, EDO, SDRAM and DDR.

Key Points:

• A processor with m address lines has a memory space of 2^m locations; 20 lines give 1 Meg.
• The size of an address range is the high address minus the low address plus one.
• An address splits into enable bits (most significant) that select the device and device address bits (least significant) that select a location inside it.
• A chip select is active-low and goes low only when the enable bits match the device’s address pattern.
• Tristate outputs enter a high-impedance state so several devices can share one bus without contention.
• SRAM stores bits in latches (fast, costly); DRAM stores them in capacitors (dense, cheap) and needs refresh circuitry.
• DRAM sends the row and column halves of the address in two steps (RAS and CAS); DDR SDRAM transfers data on both clock edges.

Memory Tip: To test whether a range belongs to one device, look at its top bits. They must stay constant while the lower bits sweep from all zeros to all ones.

Common Mistake: Assuming any address range can be one device. A range such as B000 to CFFF in hex cannot be selected by one chip select, because no split gives constant upper bits with the lower bits running fully from zero to one.

Important Questions:

• How many address lines are needed for a 1 Meg memory space? Twenty, because 2^20 = 1,048,576 locations.
• What is the difference between SRAM and DRAM? SRAM uses latches, is very fast and suits caches; DRAM uses one capacitor per bit, is denser and cheaper, but needs periodic refresh and is slower.

Chapter 13: Memory Hierarchy

Stage 3: The computer as a whole · Difficulty: Hard · Key topics: memory hierarchy, hard drive, FM, MFM, RLL, access time, tracks, sectors, cylinders, formatting, cache, direct mapping, set associative mapping, write-back

This chapter lines up the storage levels from registers to cache, main memory and hard drive. The hard drive section covers platters, the flying Winchester head, FM, MFM and RLL encoding, the four parts of access time with a full worked calculation, SMART monitoring and the way data is organised into tracks, sectors and cylinders, followed by low-level formatting, partitioning and file system formatting. The cache section explains locality, blocks and tags, hits and misses, direct, fully associative and set associative mapping with address-splitting examples, replacement algorithms and the write-through and write-back policies. Registers close the chapter.

Key Points:

• The hierarchy runs from fastest and smallest to slowest and largest: registers, cache, main memory, hard drive.
• Hard drive access time = queuing time + seek time + rotational latency + transfer time; at 7200 RPM average rotational latency is about 4.2 ms.
• Capacity = bytes per sector x sectors per track x cylinders x sides x platters; zoned bit recording packs more sectors on outer tracks than constant sectors per track.
• Caches work because of the principle of locality, both temporal (reuse) and spatial (nearby data).
• Direct mapping splits an address into tag, line and word; fully associative mapping uses tag and word; set associative mapping uses tag, set and word.
• Replacement algorithms include LRU, FIFO, LFU and random; random performs only slightly worse.
• Write-through updates memory on every write; write-back updates memory only when a modified line is replaced.

Memory Tip: Memorise the three address splits as a ladder: direct is tag | line | word, set associative is tag | set | word, fully associative is tag | word. Each step down gives the block more freedom about where it may sit.

Common Mistake: Counting the word bits as part of the tag or line number. The low-order word bits select a word inside a block, and a cache miss always fetches the whole block.

Important Questions:

• What problem does associative mapping solve compared with direct mapping? Thrashing, where two active blocks keep replacing each other because they map to the same single line.
• What is the difference between write-through and write-back? Write-through updates main memory on every write, creating heavy bus traffic; write-back updates memory only when a modified line is replaced, but it causes coherency problems with shared memory.

Chapter 14: Serial Protocol Basics

Stage 3: The computer as a whole · Difficulty: Medium · Key topics: OSI model, serial vs parallel, frame, packet, Ethernet 802.3, IPv4, TCP, ports, checksums

The chapter explains why long-distance links use serial rather than parallel transfer: fewer wires, connectors and failures, at the cost of speed and the need to carry addressing inside the same bit stream. It introduces the OSI seven-layer model and the anatomy of a frame, which has a preamble, a packet with a header and data, and a trailer with a CRC. One protocol is studied per layer: IEEE 802.3 Ethernet, the Internet Protocol and the Transmission Control Protocol. The chapter ends by dissecting a captured frame field by field and verifying the IP and TCP checksums.

Key Points:

• OSI layers from the bottom: physical, datalink, network, transport, session, presentation, application.
• An Ethernet frame starts with a 7-byte preamble and a start delimiter of 10101011, then 6-byte destination and source MAC addresses.
• Ethernet data is 46 to 1500 bytes (short data is padded), the minimum frame is 64 bytes, and the trailer is a 4-byte CRC-32.
• IPv4 addresses are 4 bytes; the time-to-live field drops by one at every hop, so the header checksum is recalculated at each router.
• TCP uses 16-bit port numbers: well-known 0 to 1023 (HTTP is 80), registered 1024 to 49151, dynamic 49152 to 65535.
• TCP control bits are URG, ACK, PSH, RST, SYN and FIN; its checksum covers the header, the data and a pseudo header.

Memory Tip: Picture Russian nesting dolls: TCP data sits inside an IP packet, which sits inside an Ethernet frame, and each layer adds its own header around what it carries.

Common Mistake: Mixing up the three addresses. The MAC address (6 bytes) identifies a device on the local link, the IP address (4 bytes) a host on the network and the TCP port (2 bytes) an application.

Important Questions:

• What is the purpose of the Ethernet preamble? It is seven bytes of alternating ones and zeros that act as a clock so the receiver can synchronise before the real frame begins.
• What is the valid size of the Ethernet data field? 46 to 1500 bytes; shorter data is padded, and the length field counts only the real bytes.

Chapter 15: Introduction to Processor Architecture

Stage 3: The computer as a whole · Difficulty: Medium · Key topics: organization vs architecture, registers, flags, stack, ALU, control unit, assembly and machine language, endianness, pipelining, polling, interrupts, DMA

This chapter opens the processor. Organization is the list of components; architecture is how they are put together. The components covered are buses, the four register types, the sign, overflow, carry and zero flags, buffers, the stack and I/O ports. Inside the CPU sit the control unit, ALU, instruction decoder and registers, and a for-loop that sums and searches an array is traced step by step. A mock 8-bit processor shows that assembly maps one-to-one onto machine code. The chapter ends with big and little-endian storage, pipelining, and the four ways to move data to peripherals: memory-mapped I/O with polling, interrupts, DMA and I/O channels.

Key Points:

• There are four register types: data, address, instruction and flag registers.
• A virtual subtract sets the flags and discards the result; zero means equal, no borrow means greater than, and a borrow (carry set) means less than.
• The stack is last-in-first-out: push stores a register on top, pull or pop removes the top item.
• Big-endian stores the most significant byte first; little-endian stores the least significant byte first.
• Pipelining overlaps fetch, decode and execute: non-pipelined cycles = 3 x instructions, pipelined cycles = 2 + instructions.
• An interrupt makes the processor push its registers, instruction pointer and flags, run an interrupt service routine and restore its state.
• Polling wastes time by checking device status repeatedly; a DMA controller moves data between device and memory without the processor.

Memory Tip: Big-endian puts the “big end” (the most significant byte) at the lowest address. Little-endian puts the “little end” first.

Common Mistake: Expecting pipelining to make one instruction faster. It raises throughput by overlapping instructions, and a wrongly predicted conditional jump flushes the pipeline and costs extra cycles.

Important Questions:

• What is the difference between polling and interrupts? In polling the processor keeps reading a device’s status register; with interrupts the device signals the processor only when it needs attention, so the processor can do other work in between.
• How is the 32-bit value 1A2B3C4D stored in 8-bit memory? Big-endian stores 1A, 2B, 3C, 4D in order; little-endian stores 4D, 3C, 2B, 1A.

Chapter 16: Intel 80×86 Base Architecture

Stage 3: The computer as a whole · Difficulty: Medium · Key topics: 80186, execution unit, general purpose registers, flags, bus interface unit, segment addressing, instruction queue, I/O ports

To avoid a toy processor that is too simple and a modern one that is too complex, the book studies the 16-bit 80186, the root of the 80×86 family, with 16 data lines and 20 address lines. The execution unit holds the ALU, the general registers AX, BX, CX and DX (each split into high and low bytes), the pointer and index registers, and the control and status flags. The bus interface unit forms physical addresses from segment and offset registers, and keeps an instruction queue full so fetch overlaps execution. The chapter closes with the separate memory and I/O control lines and the IN and OUT instructions.

Key Points:

• AH and AL combine to form AX; with AH = B0 and AL = 5F, AX = B05F in hex. AX is the accumulator, BX the base, CX the counter and DX the data register.
• SP points to the last item on the stack, BP to function parameters, IP to the next instruction, and SI and DI are the source and destination index registers.
• Control flags are TF, DF and IF; status flags are OF, SF, ZF, AF, PF and CF.
• Physical address = segment value shifted left four bits + 16-bit offset; for example 3241:A34E gives 3C75E.
• Segment pairings: CS with IP, DS with SI, SS with SP or BP, ES with DI; a segment spans 64K.
• Four control lines (MRDC, MWTC, IORC, IOWC) separate memory transfers from I/O transfers, and the I/O space is always 64K ports.
• MOV cannot reach an I/O port; use IN or INS to read and OUT or OUTS to write.

Memory Tip: Segment arithmetic is “add a zero hex digit, then add the offset”: 3241 becomes 32410, and 32410 + A34E = 3C75E.

Common Mistake: Adding the segment and offset directly. The segment must be shifted left by four bits (one hex digit) before the offset is added.

Important Questions:

• How does the 80186 form a 20-bit physical address from 16-bit registers? It shifts the 16-bit segment register left four bits and adds the 16-bit offset, giving a 20-bit address.
• What are the benefits of segmented addressing? Sixteen-bit registers can reach 20 address lines, and the operating system can place each application’s 64K segment anywhere in memory, which lets several applications run together.

Chapter 17: Intel 80×86 Assembly Language

Stage 3: The computer as a whole · Difficulty: Hard · Key topics: assembler vs compiler, directives, DB and DW, EQU, opcodes, conditional jumps, addressing modes, sample program

The last chapter teaches how to write real 80×86 assembly. An assembler turns each line into one machine instruction, and a line has four fields: label, opcode, operands and comment. Directives such as SEGMENT, .MODEL, .STACK, .DATA, .CODE, PROC, END, the data definition directives and EQU instruct the assembler and generate no code. The opcodes are grouped into data transfer, data manipulation, program control and special operations, followed by register, immediate and pointer addressing. A skeleton program and a worked calculation, (A / 8) + B – C using an arithmetic shift, bring everything together, and a closing review points to further study.

Key Points:

• A line of assembly has a label, opcode, operands and a comment that starts with a semicolon.
• Directives instruct the assembler and produce no object code; DB, DW, DD and DQ define byte, word, double word and quad word data, and DUP repeats a value.
• EQU works like C’s #define: it substitutes a value at assembly time and allocates no storage.
• CMP subtracts without storing the result so the flags can drive a conditional jump; LOOP decrements CX and jumps while CX is not zero.
• SAR is an arithmetic right shift that preserves the sign, while SHR does not; SAL and SHL are identical.
• An immediate operand can only be the source; brackets mean pointer addressing, as in [BX+4], and DS is the default segment.
• A program skeleton uses .MODEL SMALL, .STACK 100H, .DATA, .CODE and a MAIN procedure, and ends with a DOS call (INT 21H).

Practice Tip: Enter the book’s RESULT = (A / 8) + B – C program in a free 8086 emulator and single-step it. Watch AX change after SAR AX,3 to see a shift do a division by eight.

Common Mistake: Writing a hex constant that starts with a letter, such as FFH, without a leading zero. The assembler reads it as a label, so write 0FFH.

Important Questions:

• What is the difference between an assembler and a compiler? An assembler turns each assembly line into exactly one machine instruction, while a compiler translates high-level statements into many instructions and decides the steps itself.
• What does the LOOP instruction do? It decrements CX and jumps back to the label as long as CX is not zero, which makes a counted loop.

How to Study This Book

The preface says the material comes in three stages, and your course probably follows the same split. Chapters 1 to 7 are the mathematical foundation and design tools, Chapters 8 to 11 apply them to real circuits, and Chapters 12 to 17 give the top-level view of the computer. A Digital Logic Design course usually uses Chapters 1 to 11; a Computer Organization and Assembly Language (COAL) course usually uses Chapters 12 to 17, plus Chapters 2 and 3 again.

Do not skip Chapters 2 and 3 even if you know binary. Two’s complement, hexadecimal and overflow are used in nearly every later chapter, and exam questions on signed ranges and overflow are easy marks. Chapter 1 is short; the part worth your time is the pulse train section on period, frequency and duty cycle, because it produces calculation questions.

Chapters 4 to 7 are the exam core of digital logic. Practise the chain in order: truth table by columns (Chapter 4), then Boolean simplification (Chapter 5), then SOP and POS (Chapter 6), then Karnaugh maps (Chapter 7). Draw at least ten maps by hand, including ones with don’t cares and wrap-around rectangles.

In the second stage, Chapter 8 (adders, decoders, multiplexers) is built entirely from Chapters 4 to 7. Chapter 11 on state machines needs the latches of Chapter 10 and Karnaugh maps for the next-state logic, so read 10 before 11. Chapter 9 can be read on its own; its CRC and Hamming code material is useful for a networking course as well.

Memory is where the numerical questions move to. Learn to split an address into enable bits and device bits for chip selects (Chapter 12), and to split an address into tag, line or set, and word for cache questions (Chapter 13). Hard drive access-time calculations in Chapter 13 are long but follow one pattern: seek, rotational latency, transfer.

Chapter 14 is a networking primer. Read it if your course covers Ethernet, IP and TCP, and skip it if it does not. Chapter 15 is the concept chapter for processors, and Chapters 16 and 17 are the 80×86 specifics, so you need an assembler or emulator for Chapter 17.

Know what the book does not cover: Verilog or VHDL, solid-state drives, virtual memory, and 32-bit or 64-bit x86 programming. Chapter 13 describes mechanical hard drives only, Chapter 12 stops at DDR3, and Chapters 16 and 17 use the 16-bit 80186 with DOS-style assembly. These are good teaching models, but add the newer material from your lecture notes.

The chapters end with problems but we found no printed solutions; the back matter is only an index. Check your answers with a classmate, a simulator or your instructor.

Used In These Programs

This book is part of the Digital Logic Design and Computer Organization courses in: BS Computer Science · BS Information Technology. Browse all Digital Logic books or all Computer Science books.

Who Should Read This

This book is written for undergraduates taking their first Digital Logic Design or Computer Organization and Assembly Language course in BSCS or BSIT, and for anyone who wants to know how a computer works from the transistor upward. It assumes only simple arithmetic; a little programming experience helps for the C examples in Chapters 9 and 13 and for the assembly in Chapter 17. It is a good fit for self-study because every chapter ends with a What’s Next? section and problems. It is not the right choice if your course is built on Verilog or VHDL, or on 64-bit x86 or ARM assembly. Students who want a fuller networking text after Chapter 14 should read Computer Networking: Principles, Protocols and Practice, and those who want the software side of memory and processes after Chapter 15 will find Think OS a natural next step. It also helps for interview and entry-test questions on number systems, logic gates and memory.

Applicable Universities

This book is useful for students at Pakistani universities offering BSCS and BSIT including Punjab University, Virtual University, COMSATS, FAST, UET, NUST, and other HEC-recognized institutions.

Official Copy of Computer Organization and Design Fundamentals

The author makes this book free from his page at East Tennessee State University, as separate chapter PDFs and as one complete download. Click below to open the official page.

FAQs

Related Books

• Computer Networking: Principles, Protocols and Practice – Bonaventure (3rd Edition)
• Computer Science First Year Book (Class 11) – ICS Punjab Board
• Think OS – Allen B. Downey (Version 0.7.4)
• Operating Systems and Networks – IT Series BSCS (5th Edition)

Computer Organization and Design Fundamentals gives you a single free path from a binary signal to a working processor, written in plain language and finished with problems for every chapter. Browse more Computer Science books for the rest of your semester.

Computer Organization and Design Fundamentals: Examining Computer Hardware from the Bottom to the Top by David L. Tarnoff, East Tennessee State University. Copyright 2005-2007 David L. Tarnoff, all rights reserved; the author makes the PDF free to download. Official source: https://faculty.etsu.edu/tarnoff/138292/