Digital Logic and Computer Organisation Exhaustive Study Guide

Number Systems, Radix Complements, and Boolean Foundations

Number Systems and Base Conversions

• Decimal to Binary Conversion:

  • To convert a decimal integer to binary, repeatedly divide the number by 2 and record the remainder until the quotient becomes 0. The binary equivalent is formed by reading the remainders from bottom to top (Most Significant Bit to Least Significant Bit).

  • Example Calculation (Decimal 141):

    • $141 \div 2 = 70$ remainder $1$

    • $70 \div 2 = 35$ remainder $0$

    • $35 \div 2 = 17$ remainder $1$

    • $17 \div 2 = 8$ remainder $1$

    • $8 \div 2 = 4$ remainder $0$

    • $4 \div 2 = 2$ remainder $0$

    • $2 \div 2 = 1$ remainder $0$

    • $1 \div 2 = 0$ remainder $1$

  • Reading remainders from MSB to LSB gives: $141_{10} = 10001101_2$

• Octal to Hexadecimal Conversion (Without Decimal Intermediate):

  • To convert an octal number directly to hexadecimal, convert each octal digit into its 3-bit binary equivalent, group the resulting binary bits into 4-bit clusters starting from the least significant bit, and translate each 4-bit group into its corresponding hexadecimal digit.

  • Example Calculation (Octal $2345_8$):

    • Convert each octal digit to 3-bit binary: $2_8 = 010_2$, $3_8 = 011_2$, $4_8 = 100_2$, $5_8 = 101_2$

    • Combine binary streams: $010011100101_2$

    • Group into 4-bit clusters: $0100 \quad 1110 \quad 0101$

    • Convert clusters to hexadecimal: $0100_2 = 4_{16}$, $1110_2 = E_{16}$, $0101_2 = 5_{16}$

    • Result: $(2345)_8 = (4E5)_{16}$

• Hexadecimal to Octal Conversion via Binary:

  • Example Calculation (Hexadecimal $64CD_{16}$):

    • Convert each hex digit to 4-bit binary: $6_{16} = 0110_2$, $4_{16} = 0100_2$, $C_{16} = 1100_2$, $D_{16} = 1101_2$

    • Combined binary representation: $0110010011001101_2$

    • Group into 3-bit clusters from LSB: $000 \quad 011 \quad 001 \quad 001 \quad 100 \quad 110 \quad 101$

    • Convert 3-bit clusters to octal: $000_2 = 0_8$, $011_2 = 3_8$, $001_2 = 1_8$, $001_2 = 1_8$, $100_2 = 4_8$, $110_2 = 6_8$, $101_2 = 5_8$

    • Result: $(64CD)_{16} = (0311465)_8 = (311465)_8$

• Fractional Base Conversions to Decimal:

  • Conversion of $(16.5)_{16}$ to Decimal:

    • $(16.5)_{16} = 1 \times 16^1 + 6 \times 16^0 + 5 \times 16^{-1}$

    • $= 16 + 6 + \frac{5}{16} = 22 + 0.3125 = (22.3125)_{10}$

  • Conversion of $(26.24)_8$ to Decimal:

    • $(26.24)_8 = 2 \times 8^1 + 6 \times 8^0 + 2 \times 8^{-1} + 4 \times 8^{-2}$

    • $= 16 + 6 + \frac{2}{8} + \frac{4}{64} = 22 + 0.25 + 0.0625 = (22.3125)_{10}$

• Gray Code Conversion:

  • Gray code is an unweighted binary code where two consecutive values differ by only one bit.

  • To convert binary to Gray code: keep the MSB same, and XOR each binary bit with the adjacent bit on its left.

  • Conversion for Decimal 12: $12_{10} = 1100_2$

    • Gray MSB $G_3 = B_3 = 1$

    • $G_2 = B_3 \oplus B_2 = 1 \oplus 1 = 0$

    • $G_1 = B_2 \oplus B_1 = 1 \oplus 0 = 1$

    • $G_0 = B_1 \oplus B_0 = 0 \oplus 0 = 0$

    • Result: Decimal 12 in Gray code is $1010$

Radix and Diminished Radix Complements

• Definitions of Complements with Respect to Base $r$:

  • For a given base $r$ and an $n$-digit number $N$:

    • Radix Complement ($r$'s complement): Defined mathematically as $r^n - N$ for non-zero numbers, and $0$ if $N = 0$.

    • Diminished Radix Complement ($(r-1)$'s complement): Defined mathematically as $(r^n - 1) - N$.

  • For binary numbers ($r = 2$):

    • $2$'s complement is the Radix complement ($2^n - N$ or 1's complement + 1).

    • $1$'s complement is the Diminished Radix complement ($(2^n - 1) - N$ or bitwise NOT).

• Subtraction Using 2's Complement:

  • Given two 4-bit numbers $A = 1100_2$ (Decimal 12) and $B = 1001_2$ (Decimal 9):

  • Operation $A - B$ ($1100_2 - 1001_2$):

    • Take 2's complement of $B$: 1's complement of $1001_2$ is $0110_2$; add 1 to get $0111_2$

    • Add $A + \text{2's complement of } B$:             \begin{array}{r@{\quad}l} 1100 \\ + 0111 \\ \hline 10011 \end{array}

    • An end carry of $1$ occurs, indicating the result is positive. Discard the end carry.

    • Result: $0011_2$ (Decimal 3).

  • Operation $B - A$ ($1001_2 - 1100_2$):

    • Take 2's complement of $A$: 1's complement of $1100_2$ is $0011_2$; add 1 to get $0100_2$

    • Add $B + \text{2's complement of } A$:             \begin{array}{r@{\quad}l} 1001 \\ + 0100 \\ \hline 1101 \end{array}

    • No end carry occurs, indicating the result is negative and in 2's complement form.

    • Take 2's complement of $1101_2$ to get magnitude: 1's complement is $0010_2$; add 1 to get $0011_2$ (Decimal 3).

    • Result: $-0011_2$ (Decimal -3).

Universal Logic Gates and Logic Implementation

• Implementation of AND and OR Gates Using NAND Gates:

  • AND Gate using NAND Gates: Requires 2 NAND gates.

    • Gate 1 performs NAND on inputs $A$ and $B$: $Y_1 = (AB)'$

    • Gate 2 acts as an inverter by feeding $Y_1$ to both inputs: $Y = ((AB)')' = AB$

  • OR Gate using NAND Gates: Requires 3 NAND gates.

    • Gate 1 inverts input $A$: $A'$

    • Gate 2 inverts input $B$: $B'$

    • Gate 3 combines $A'$ and $B'$ with NAND: $Y = (A' \cdot B')' = A'' + B'' = A + B$

• Implementation of Logic Functions Using NOR Gates:

  • AND Gate using NOR Gates: $Y = (A' + B')' = A'' \cdot B'' = AB$

  • OR Gate using NOR Gates: $Y = ((A + B)')' = A + B$

  • NAND Gate using NOR Gates: $Y = (((A + B)')')' = (A + B)'$

Canonical Boolean Forms, Logic Gates, and Gate Minimization

Boolean Laws and Complement Proofs

• Fundamental Laws of Boolean Algebra:

  • Associative Law: The grouping of variables does not affect the operation result.

    • AND Operation: $A(BC) = (AB)C$

    • OR Operation: $A + (B + C) = (A + B) + C$

  • Distributive Law: Multiplication distributes over addition, and addition distributes over multiplication.

    • AND over OR: $A(B + C) = AB + AC$

    • OR over AND: $A + BC = (A + B)(A + C)$

• Proof of Distributive Law $A + BC = (A + B)(A + C)$ using Truth Table:

• Proof of DeMorgan's Laws for Three Variables:

  • Law 1: $(A + B + C)' = A'B'C'$

  • Law 2: $(ABC)' = A' + B' + C'$

• Truth Table for Truth Table Function $F = BC + A'C'$:

• Complements of Functions:

  • For $F = wx + yz$:         $F' = (wx + yz)' = (wx)' \cdot (yz)' = (w' + x')(y' + z')$

  • For $F = (X + Y'Z)(X'Y + XZ')$: Apply DeMorgan's laws systematically.         $F' = [(X + Y'Z)(X'Y + XZ')]' = (X + Y'Z)' + (X'Y + XZ')'$         $(X + Y'Z)' = X' \cdot (Y'Z)' = X'(Y + Z')$         $(X'Y + XZ')' = (X'Y)' \cdot (XZ')' = (X + Y')(X' + Z)$         $F' = X'(Y + Z') + (X + Y')(X' + Z)$

• Theorem: The logical sum of all minterms of a Boolean function of $n$ variables is identically equal to 1.

  • Proof for 3 variables: The sum of all minterms is $\sum(m_0, m_1, m_2, m_3, m_4, m_5, m_6, m_7)$.         $\sum m = A'B'C' + A'B'C + A'BC' + A'BC + AB'C' + AB'C + ABC' + ABC$         $= A'B'(C' + C) + A'B(C' + C) + AB'(C' + C) + AB(C' + C)$         $= A'B'(1) + A'B(1) + AB'(1) + AB(1) = A'B' + A'B + AB' + AB$         $= A'(B' + B) + A(B' + B) = A'(1) + A(1) = A' + A = 1$

Karnaugh Map (K-Map) Optimization

• Purpose of K-Map: A Karnaugh Map is a graphical representation technique used to minimize Boolean functions systematically without requiring complex algebraic manipulations. It arranges minterms in a grid where adjacent cells differ by only one binary variable (Gray code sequence).

• Structure of a Three-Variable K-Map: Contains $2^3 = 8$ cells representing minterms $m_0$ through $m_7$, arranged in 2 rows (for variable $A$) and 4 columns (for variables $B, C$ labeled $00, 01, 11, 10$).

• Don't Care Condition ($d$ or $X$): Conditions in logic design where certain input combinations are guaranteed never to occur or where the output value does not matter. In K-Maps, don't cares can be assigned as either 0 or 1 to form the largest possible adjacent groups.

• POS Expressions and Conversion:

  • To convert POS expression $(X + Y')(X' + Z)$ to SOP form:         $(X + Y')(X' + Z) = XX' + XZ + X'Y' + Y'Z = 0 + XZ + X'Y' + Y'Z = XZ + X'Y' + Y'Z$

• K-Map Simplification Examples:

  • Problem 1: Simplify $F(A,B,C,D) = \prod(0,2,5,7,8,10,13,15)$ into equivalent POS form.

    • The maxterms given are $0, 2, 5, 7, 8, 10, 13, 15$.

    • Plotting zeros at these positions in a 4-variable K-map:

      • Corners $(0, 2, 8, 10)$ form a quad yielding $(B + D)$.

      • Middle quad $(5, 7, 13, 15)$ forms a quad yielding $(B' + D')$.

    • Simplified POS Expression: $F = (B + D)(B' + D')$

  • Problem 2: Simplify $A'B'C'D' + AC'D' + B'CD' + A'BCD + BC'D$ using 4-variable map.

    • Convert terms to minterms:

      • $A'B'C'D' = m_0$

      • $AC'D' = m_8 + m_{12}$

      • $B'CD' = m_2 + m_{10}$

      • $A'BCD = m_7$

      • $BC'D = m_5 + m_{13}$

    • Combined minterms: $\sum(0, 2, 5, 7, 8, 10, 12, 13)$

    • Groupings:

      • Quad $(0, 2, 8, 10) \rightarrow B'D'$

      • Quad $(5, 7, 13, 15)$ (with added $m_{15}$ if simplified) or Quad $(5, 13, 8, 12 \dots)$ yielding simplified SOP: $B'D' + BC' + A'BD$

  • Problem 3: Simplify $F(A,B,C,D) = \sum(0, 6, 8, 13, 14)$ with don't cares $d(A,B,C,D) = \sum(2, 4, 10)$.

    • Minterms + Don't cares: $0, 2, 4, 6, 8, 10, 13, 14$

    • Quad $(0, 2, 8, 10) \rightarrow B'D'$

    • Quad $(2, 6, 10, 14) \rightarrow CD'$

    • Quad $(0, 2, 4, 6) \rightarrow A'D'$

    • Single term $m_{13} (1101) \rightarrow A B C' D$

    • Simplified Sum-of-Minterms Form: $F = B'D' + CD' + A'D' + ABC'D$

  • Problem 4: Simplify $F(x,y,z) = \prod(0, 1, 4, 5, 6)$ with don't cares $d(x,y,z) = \prod(2,3,7)$.

    • Since all maxterms and don't care maxterms cover all cells from 0 to 7, the function simplifies to a constant $F = 0$

Multi-Level Gate Circuits

• Multi-Level NOR Implementation:

  • To implement $CD(B + C)A + (BC' + DE')$ using NOR gates:

    • Convert all AND/OR operations using double complement and DeMorgan's rule to format the logic trees as multi-stage inverted ORs.

• Multi-Level NAND Implementation:

  • To implement $W(x + y + z) + xyz$ using NAND gates:

    • Convert the expression into an inverted AND-OR configuration where intermediate gates are all configured as NAND logic.

Combinational Logic Design, Arithmetic Circuits, and Multiplexers

Combinational Circuit Design

• Definition: A combinational circuit consists of logic gates whose outputs at any given time are determined directly from the present combination of inputs, without relying on past storage elements or feedback paths.

• Design Example 1: Three inputs ($A, B, C$), output $Y = 1$ when binary value $< 3$.

  • Binary values less than 3 correspond to input combinations $000 (0), 001 (1), 010 (2)$.

  • Truth Table:

*   K-Map simplification gives output equation: $Y = A'B' + A'C'$

• Design Example 2: Three inputs ($A, B, C$), output $Y = 1$ when binary value is even.

  • Even binary numbers end in $0$ for the LSB ($C = 0$), covering binary values $0, 2, 4, 6$

  • Output equation simplified directly: $Y = C'$

Arithmetic Circuits

• Half Adder:

  • Adds two single binary bits ($A$ and $B$).

  • Truth Table:

*   Equations:
    *   $\text{Sum } S = A \oplus B = A'B + AB'$
    *   $\text{Carry } C = AB$

• Full Adder Construction Using Two Half Adders:

  • Full Adder adds three bits: $A$, $B$, and Carry-in $C_{in}$.

  • Half Adder 1: Takes $A$ and $B$, produces $S_1 = A \oplus B$ and $C_1 = AB$

  • Half Adder 2: Takes $S_1$ and $C_{in}$, produces final Sum $S = S_1 \oplus C_{in} = A \oplus B \oplus C_{in}$ and carry $C_2 = S_1 \cdot C_{in}$

  • Final Carry Generation: Combine intermediate carries with an OR gate: $C_{out} = C_1 + C_2 = AB + (A \oplus B)C_{in}$

• Ripple Carry Adder:

  • A cascade of $n$ Full Adders connected in series where the carry output of each full adder is connected as the carry input to the next higher-order full adder.

  • Limitation: Propagation delay increases linearly with the number of bits $n$ because high-order bits must wait for the carry to ripple through all lower stages.

• Carry-Save Addition Technique:

  • An addition method used in high-speed multipliers where three or more numbers are added together simultaneously. Instead of propagating carries immediately, a Carry-Save Adder (CSA) produces two outputs for each stage: a Sum vector and a Carry vector. The carries are propagated only in the final addition step using a conventional ripple-carry or carry-lookahead adder, reducing total execution time.

• Booth's Multiplication Algorithm:

  • An efficient algorithm for multiplying signed binary numbers in 2's complement notation.

  • Operates by scanning multiplier bits $Q_0$ and an extra adjacent bit $Q_{-1}$ (initially set to 0):

    • If $Q_0 Q_{-1} = 10$: Subtract multiplicand $M$ from accumulator $A$ ($A \leftarrow A - M$), then arithmetic shift right $(A, Q, Q_{-1})$.

    • If $Q_0 Q_{-1} = 01$: Add multiplicand $M$ to accumulator $A$ ($A \leftarrow A + M$), then arithmetic shift right $(A, Q, Q_{-1})$.

    • If $Q_0 Q_{-1} = 00$ or $11$: Arithmetic shift right $(A, Q, Q_{-1})$ directly.

  • Repeat process for $n$ clock cycles where $n$ is the bit length.

• Floating-Point Arithmetic Operations:

  • Represented as $N = M \times r^E$, where $M$ is the mantissa, $r$ is the radix, and $E$ is the exponent.

  • Addition/Subtraction: Requires exponent alignment (shifting the mantissa of the smaller exponent right until exponents match), followed by mantissa addition/subtraction, and finally normalizing the result.

  • Multiplication: Multiply mantissas, add exponents, and normalize.

  • Division: Divide mantissas, subtract exponents, and normalize.

Decoders, Multiplexers, and Logic Implementation

• Decoder and Enable Input Significance:

  • A decoder converts an $n$-bit binary input code into up to $2^n$ unique output lines.

  • Significance of Enable Input ($E$): Acts as a master switch. When disabled ($E=0$), all outputs remain inactive regardless of input selections. Enable lines allow expansion of decoders into larger matrices.

  • Implementation of 3x8 Decoder using 2x4 Decoders: Uses two 2x4 decoders and an inverter connected to the most significant input bit ($A$). When $A=0$, the inverted signal enables the first 2x4 decoder (outputs $Y_0$ to $Y_3$); when $A=1$, it enables the second 2x4 decoder (outputs $Y_4$ to $Y_7$).

• Multiplexer (MUX) Selection Lines:

  • A Multiplexer routes one of $n$ data inputs to a single output.

  • The required number of selection lines $m$ is determined by the formula:         $2^m = n \implies m = \log_2(n)$

• Multiplexer Implementations of Functions:

  • Implementation of $F(A,B,C,D) = \sum(0,2,5,8,10,14)$ using 8x1 MUX:

    • Select lines connected to $A, B, C$. Input lines $I_0$ to $I_7$ are configured based on variable $D$:

      • $I_0 (000) \rightarrow D'$ (minterms 0, 2)

      • $I_1 (001) \rightarrow 0$

      • $I_2 (010) \rightarrow D$ (minterm 5)

      • $I_3 (011) \rightarrow 0$

      • $I_4 (100) \rightarrow D'$ (minterm 8, 10)

      • $I_5 (101) \rightarrow 0$

      • $I_6 (110) \rightarrow D'$ (minterm 14)

      • $I_7 (111) \rightarrow 0$

  • Implementation of 8x1 MUX using 2x1 MUXes: Arranged in a tree structure using four 2x1 MUXes at the first level, two 2x1 MUXes at the second level, and one 2x1 MUX at the final level.

• Magnitude Comparators:

  • A magnitude comparator compares two binary numbers $A$ and $B$ and determines whether $A > B$, $A = B$, or $A < B$.

  • 2-Bit Magnitude Comparator: Takes inputs $A_1 A_0$ and $B_1 B_0$. Output functions:

    • $A = B$ equation: $(A_1 \odot B_1)(A_0 \odot B_0)$

    • $A > B$ equation: $A_1 B_1' + (A_1 \odot B_1) A_0 B_0'$

    • $A < B$ equation: $A_1' B_1 + (A_1 \odot B_1) A_0' B_0$

Basic Computer Organization, Bus Architecture, and Instruction Cycles

Basic Computer Hardware Organization

• Functional Units of a Computer:

  • Input Unit: Accepts data and instructions from external peripheral sources.

  • Memory Unit: Stores instructions, raw input data, and intermediate results (Primary RAM/ROM and Secondary Storage).

  • Arithmetic Logic Unit (ALU): Performs all arithmetic computations (addition, subtraction) and logical evaluations (AND, OR).

  • Control Unit (CU): Fetches instructions from memory, decodes them, and generates control timing signals to coordinate all system operations.

  • Output Unit: Transforms binary processed data back into human-readable or external actionable signals.

• Computer Register Organization:

• Significance of Program Counter (PC): Keeps track of execution flow by holding the memory address of the next instruction. It automatically increments after each instruction fetch, unless a branch/jump directive occurs.

Bus Architecture and Memory Reference Instructions

• Common Bus System:

  • A shared collection of signal wires configured to transfer data, address, and control signals among multiple internal computer registers efficiently without interconnecting every register pair directly.

  • Construction of Common Bus System for 4 Registers of 4 Bits Each: Uses four 4x1 Multiplexers. Bit $i$ from each of the four registers ($A, B, C, D$) is connected to the four data inputs of Multiplexer $i$. Two select lines $S_1, S_0$ choose which register drives the 4-bit bus lines simultaneously.

• Instruction Cycle Flowchart and Operation:

  1. Fetch: Load instruction at memory address $[PC]$ into Instruction Register ($IR \leftarrow M[PC]$), then increment $PC \leftarrow PC + 1$.

  2. Decode: Decode opcode bits inside $IR$; load effective address bits into Address Register ($AR$).

  3. Read Effective Address: If the instruction specifies an indirect address, fetch the ultimate operand address from memory ($AR \leftarrow M[AR]$).

  4. Execute: Perform the control operation dictated by opcode.

• Effective Address: The precise physical memory address that contains the actual operand required for an instruction execution.

• Addressing Modes:

  • Immediate Mode: Operand is explicitly specified within the instruction word itself.

  • Direct Addressing Mode: Address field directly specifies memory location of the operand.

  • Indirect Addressing Mode: Address field points to a memory location containing the effective address of operand.

  • Register Mode: Operand resides inside a designated internal register.

  • Register Indirect Mode: Register holds the memory address of the operand.

  • Displacement / Relative Mode: Effective Address = Base Register / PC value + offset value.

CPU Architecture, Stack Organization, and Computer Generations

• CPU Instruction Formats:

  • Three-Address Instructions: Specify two source operands and one destination operand (e.g., $ADD \, R_1, A, B$).

  • Two-Address Instructions: Destination register doubles as one of the source operands (e.g., $ADD \, R_1, A$).

  • One-Address Instructions: Uses implicit Accumulator ($AC$) register for one operand and destination (e.g., $ADD \, M$).

  • Zero-Address Instructions: Uses an implicit Last-In-First-Out (LIFO) Pushdown Stack for processing (e.g., $ADD$).

• Stack Organization:

  • Register Stack: Fixed array of internal registers governed by a Stack Pointer ($SP$) register.

    • PUSH Operation: $SP \leftarrow SP + 1; \quad M[SP] \leftarrow DR$

    • POP Operation: $DR \leftarrow M[SP]; \quad SP \leftarrow SP - 1$

  • Memory Stack: Dedicated logical segment of main RAM designated as stack space.

• Computer Generations Summary:

• Multicomputer vs. Multiprocessor:

  • Multiprocessor: Tightly coupled architecture where multiple CPUs share a common memory space and unified clock.

  • Multicomputer: Loosely coupled architecture consisting of autonomous processing nodes, each with its own local memory, communicating via message-passing networks.

• Von Neumann Architecture Principles: Characterized by stored-program concept where instructions and data reside in a shared single memory unit, executed sequentially by a single processing unit containing ALU and CU registers.

Memory Systems, Cache Organization, Virtual Memory, and Secondary Storage

Memory Hierarchy and DRAM Technology

• Memory Hierarchy Structure: Arranged in descending speed and ascending capacity/cost parameters:

  1. Processor Registers (Fastest access, smallest capacity, highest cost)

  2. Cache Memory (L1, L2, L3 SRAM)

  3. Main Memory (DRAM)

  4. Secondary Storage (SSD, Hard Disk Drives)

  5. Auxiliary / Off-line Storage (Magnetic Tapes, Optical Disks)

• Synchronous vs. Asynchronous DRAM:

  • Asynchronous DRAM: Operates independently of the system bus clock. Memory access is controlled via asynchronous handshaking control signals ($RAS$, $CAS$).

  • Synchronous DRAM (SDRAM): Synchronizes access directly with the system bus clock signal, allowing pipelined execution and faster burst mode data access.

ROM Variants and Internal Memory Organization

• ROM Variants:

  • ROM (Read-Only Memory): Mask-programmed during manufacturing; contents cannot be modified.

  • PROM (Programmable ROM): Blank OTP (one-time programmable) memory written using electrical programmer devices.

  • EPROM (Erasable PROM): Data erased by exposing chip to high-intensity Ultraviolet light through quartz window.

  • EEPROM (Electrically Erasable PROM): Byte-level erasing/rewriting performed electrically.

  • Flash Memory: Advanced variant of EEPROM providing block-level electrical erasing and rapid writing.

• Internal Chip Organization: Memory cells are arranged in a 2D matrix array. A Row Decoder activates a specific word line based on higher address bits, while Column Decoders select specific bit lines to read/write target data words onto data lines.

Cache Memory Concepts and Mapping

• Cache Efficiency Metrics:

  • Hit Ratio ($H$): The fraction of memory references found inside cache memory.         $H = \frac{\text{Cache Hits}}{\text{Cache Hits} + \text{Cache Misses}}$

  • Average Access Time ($T_{avg}$):         $T_{avg} = H \cdot T_c + (1 - H) \cdot T_m$         Where $T_c$ is cache access time and $T_m$ is main memory access time.

• Direct Mapping Cache Numerical Example:

  • System Specifications: Main Memory size = 1 MB ($2^{20}$ bytes), Cache Memory size = 4 KB ($2^{12}$ bytes).

  • Address Bit Fields Calculation: Total Address Bits = 20 bits.

    • Cache Index / Block Field = 12 bits (determines line inside 4KB cache)

    • Tag Field = Total Address Bits - Cache Index Bits = $20 - 12 = 8$ bits.

Virtual Memory, Address Mapping, and Page Replacement

• Virtual Memory Principles: An operational memory management technique that gives software the illusion of a large continuous main memory by combining dynamic RAM hardware with secondary block storage.

• Address Space vs. Memory Space:

  • Address Space (Virtual Address): Logical set of addresses generated by the CPU.

  • Memory Space (Physical Address): Actual set of physical memory addresses existing in primary RAM.

• Virtual Memory Numerical Problem:

  • System Parameters: Virtual Address Space = 16 bits ($2^{16} = 64\text{ KB}$), Physical Memory Space = 13 bits ($2^{13} = 8\text{ KB}$), Page / Block Size = 1 KB ($1024\text{ bytes} = 2^{10}$ bytes).

  • Number of Pages Calculation:$\text{Number of Pages} = \frac{\text{Virtual Address Space}}{\text{Page Size}} = \frac{2^{16}}{2^{10}} = 2^6 = 64\text{ pages}$

  • Number of Blocks (Frames) Calculation:$\text{Number of Blocks} = \frac{\text{Memory Space}}{\text{Block Size}} = \frac{2^{13}}{2^{10}} = 2^3 = 8\text{ blocks}$

• Page Faults and FIFO Page Replacement:

  • A Page Fault occurs when a referenced virtual page is not currently present in physical main memory (RAM).

  • FIFO (First-In-First-Out) Page Replacement Algorithm: Replaces the oldest page that has resided in physical memory frame longest when a new page fault occurs.

Content Addressable Memory (CAM) and Secondary Storage

• Content Addressable Memory (CAM) / Associative Memory:

  • A memory device where content is accessed directly by matching input data patterns rather than specifying binary address locations. All memory words compare input search keys simultaneously in parallel.

  • Argument Register: Contains the specific multi-bit data pattern being searched across all CAM memory cells.

  • Key/Mask Register: Mask register that specifies which specific bit positions within the Argument Register are actively evaluated during the simultaneous match operation.

• Secondary Storage Devices and Memory Interleaving:

  • Secondary Devices: Magnetic Hard Disk Drives (HDD), Solid State Drives (SSD using Flash NAND technology), Optical Media (CD/DVD/Blu-Ray), and Magnetic Tapes.

  • Memory Interleaving: A technique that splits main RAM into multiple independent memory modules operating in parallel. By spreading sequential memory block addresses across different modules (Low-Order Interleaving), read/write access bottlenecks are reduced and overall system throughput increases.