✅ 1. CACHE MAPPING NUMERICAL (Direct Mapping) NUMERICALS

 

✅ 1. CACHE MAPPING NUMERICAL (Direct Mapping)

Q1.

A computer has:

• Main memory = 4K words

• Cache = 128 words

• Block size = 4 words

Find:

1. No. of blocks in main memory

2. No. of lines in cache

3. Mapping of memory block 205 to cache line.

---

Solution

1) Blocks in main memory

Main memory size = 4K = 4096 words
Block size = 4 words

$$\text{No. of blocks} = \frac{4096}{4} = 1024$$

---

2) Cache lines

Cache size = 128 words
Block size = 4 words

$$\text{Cache lines} = \frac{128}{4} = 32$$

---

3) Mapping of block 205

Direct mapping:

$$\text{Cache line} = \text{Block number} \mod \text{No. of lines}$$ $$205 \mod 32 = 13$$

✔ Answer:

Block 205 maps to cache line 13.

---

✅ 2. SET-ASSOCIATIVE CACHE NUMERICAL

Q2.

8 KB cache, block size = 64 bytes, 4-way set associative.
Find number of sets.

---

Solution

Cache size = 8 KB = 8192 bytes
Block size = 64 bytes

1 set has 4 blocks (because 4-way).

Total blocks =

$$\frac{8192}{64} = 128$$

No. of sets =

$$\frac{128}{4} = 32$$

✔ Answer:

32 sets

---

✅ 3. MEMORY INTERLEAVING

Q3.

A system has 4 memory banks using lower-order interleaving.
Words are stored starting from address 0.
Find the bank number for address: 37.

---

Solution

Lower-order interleaving:

$$\text{Bank} = \text{Address} \mod \text{No. of banks}$$

Here:
37 mod 4 = 1

✔ Answer:

Address 37 is in Bank 1.

---

✅ 4. EFFECTIVE ACCESS TIME (EAT)

Q4.

Hit ratio = 90%
Cache access time = 10 ns
Main memory access = 100 ns

Find EAT.

---

Solution

$$EAT = (Hit\ Ratio \times Cache\ Time) + (Miss\ Ratio \times Memory\ Time)$$

Hit ratio = 0.9
Miss ratio = 1 – 0.9 = 0.1

$$EAT = (0.9 \times 10) + (0.1 \times 100)$$ $$= 9 + 10 = 19\ \text{ns}$$

✔ Answer:

19 ns

---

✅ 5. PIPELINE THROUGHPUT

Q5.

A pipeline has 5 stages, each taking 20 ns.
Calculate time to execute 10 instructions.

---

Solution

Pipeline time =

$$kT + (n - 1)T$$

k = stages = 5
T = 20 ns
n = instructions = 10

$$= 5(20) + 9(20)$$ $$= 100 + 180 = 280\ \text{ns}$$

✔ Answer:

280 ns

---

✅ 6. BINARY → EXCESS-3 NUMERICAL

Q6.

Convert 75 (decimal) into Excess-3 code.

---

Solution

Digits: 7 and 5

Step 1 → Convert to BCD:
7 → 0111
5 → 0101

Step 2 → Add 3 (0011) to each:

0111 + 0011 = 1010
0101 + 0011 = 1000

✔ Answer:

75 = 1010 1000 (Excess-3)

---

✅ 7. BINARY MULTIPLICATION (Booth’s Algorithm)

Q7.

Multiply: (+7) × (−3) using Booth’s algorithm.
(Short exam-style solution.)

---

Solution Summary

7 = 0111
−3 = 1101 (2’s complement)

Perform Booth steps → final answer:

✔ Answer:

(+7) × (−3) = −21
Binary result: 1010 1011

---

✅ 8. ADDRESSING MODE NUMERICAL

Q8.

Effective address = ?
Instruction: MOV A, M
HL register pair = 2050H

---

Solution

Indirect addressing:
Address = content of HL.

✔ Answer:

EA = 2050H

---

✅ 9. MEMORY SIZE CALCULATION

Q9.

How many bytes in a memory with 16-bit address bus?

---

Solution

No. of addressable locations =

$$2^{16} = 65536$$

Each location stores 1 byte.

✔ Answer:

64 KB

---

✅ 10. CACHE TAG CALCULATION

Q10.

Find tag, set, and block offset for:

• Cache = 4 KB

• Block size = 32 bytes

• 2-way associative

• 16-bit address

---

Solution Steps

1. Cache size = 4096 bytes
   Block size = 32 →
   Blocks = 4096 / 32 = 128 blocks

2. 2-way set associative →
   Sets = 128 / 2 = 64 sets

3. Set bits = log₂(64) = 6 bits

4. Offset bits = log₂(32) = 5 bits

5. Tag bits = 16 – (6 + 5) = 5 bits

---

✔ Final Answer:

• Tag = 5 bits

• Set = 6 bits

• Offset = 5 bits

✅ UNIT 5 — MEMORY & I/O ORGANIZATION

 

This unit explains how data is stored, accessed, and transferred inside a computer — essential for understanding how modern CPUs achieve high speed.

---

⭐ 5.1 Memory Hierarchy

Memory is organized in layers based on speed, cost, and capacity.

From Fastest → Slowest

1. Registers

2. Cache Memory

3. Main Memory (RAM)

4. Secondary Memory (HDD/SSD)

5. Tertiary (CD/DVD)

Key Idea:

• Higher levels → faster, expensive, smaller

• Lower levels → slower, cheap, larger

CPU always tries to read from the fastest possible level.

---

⭐ 5.2 Cache Memory

Cache = small, very fast memory between CPU & RAM.

Why cache is needed?

Because CPU is extremely fast but RAM is slower → cache avoids waiting.

---

Types of Cache

1. L1 Cache

Fastest, smallest, inside CPU core.

2. L2 Cache

Bigger, slower.

3. L3 Cache

Shared between multiple cores.

---

Cache Mapping Techniques

1️⃣ Direct Mapping

Each block of main memory maps to exactly one cache line.

Advantages: Simple
Disadvantages: Conflict misses

2️⃣ Associative Mapping

Any memory block → any cache line.

Advantages: Flexible
Disadvantages: Expensive hardware

3️⃣ Set-Associative Mapping

Memory block → a small set of cache lines.
Most commonly used.

---

⭐ 5.3 Main Memory (RAM + ROM)

RAM Types

• SRAM → used in cache

• DRAM → used in main memory

ROM Types

• PROM

• EPROM

• EEPROM

---

⭐ 5.4 Memory Interleaving

Memory speed can be increased by storing data across multiple banks.

Types:

1️⃣ Lower-Order Interleaving

Low-order bits choose memory bank.

2️⃣ Higher-Order Interleaving

High-order bits choose memory bank.

Goal: Increase reading speed by accessing multiple banks simultaneously.

---

⭐ 5.5 Associative Memory (Content Addressable Memory)

Data is accessed by content, not by address.

Used in:

• Cache tag matching

• TLB (Translation Lookaside Buffer)

---

⭐ 5.6 I/O Organization

Two main categories:

1️⃣ Programmed I/O

CPU controls I/O directly.
Simple but slow.

2️⃣ Interrupt-Driven I/O

I/O device interrupts CPU when ready.
Faster than programmed I/O.

3️⃣ Direct Memory Access (DMA)

Fastest I/O method.

DMA Features:

• Transfers data directly between memory & I/O

• CPU is freed during transfer

• Very efficient for large data (disk, graphics)

---

⭐ 5.7 Memory-Mapped vs I/O-Mapped I/O

Feature	Memory-Mapped I/O	I/O-Mapped I/O
Address Space	Uses normal memory addresses	Separate I/O address space
Instructions	Normal memory instructions	Special I/O instructions (IN, OUT)
Speed	Faster	Moderate
Example	Modern CPUs	8085 (IN/OUT)

---

⭐ 5.8 Secondary Storage Concepts

HDD

• Mechanical

• Slower

• Large capacity

SSD

• No moving parts

• Much faster

• Expensive

CD/DVD

• Optical storage

• Used for distribution & backup

✅ UNIT 4 — Microprocessor Basics, Instruction Cycle, Pipelining & Hazards

 This unit connects digital electronics to how a CPU actually works internally.

⭐ 4.1 What is a Microprocessor?

A microprocessor is the brain of the computer, an IC that performs:

• Arithmetic operations (ALU)

• Logical operations

• Control (via CU)

• Data transfer

Examples:

• 8085 (8-bit, classic for exams)

• 8086 (16-bit)

• i3, i5, i7 (modern CPUs)

---

⭐ 4.2 Basic Microprocessor Architecture

Major Components:

1️⃣ ALU (Arithmetic Logic Unit)

Performs:

• Add, Subtract

• AND, OR, NOT

• Compare

2️⃣ Control Unit (CU)

• Controls timing

• Fetch, Decode, Execute instructions

• Sends control signals to memory and I/O

3️⃣ Registers

High-speed small storage inside CPU:

• Accumulator (A)

• General registers (B, C, D, E, H, L)

• Program Counter (PC)

• Stack Pointer (SP)

• Flag Register (Z, S, CY, P, AC flags)

---

⭐ 4.3 Instruction Cycle

Every instruction executes in three steps:

1️⃣ Fetch Cycle

• PC → Address Bus

• Memory → Instruction → CPU

• PC = PC + 1

2️⃣ Decode Cycle

• Instruction decoded by Control Unit

• Identifies required operation

3️⃣ Execute Cycle

• ALU performs operation

• Result stored in Register/Memory

• Flags updated

---

⭐ 4.4 Machine Cycle & T-States

Machine Cycle:

A part of instruction cycle (memory read, memory write, I/O read, etc.)

T-States:

Each machine cycle is divided into clock cycles.

Example (8085):

• Memory Read Cycle = 3 T-states

• Memory Write Cycle = 3 T-states

• Opcode Fetch Cycle = 4 T-states

---

⭐ 4.5 Addressing Modes

Defines how data is accessed.

Mode	Example	Meaning
Immediate	MVI A, 05H	Data is inside instruction
Direct	LDA 2050H	Access memory address directly
Register	MOV A, B	Data is in register
Indirect	LDAX B	Address is held in register pair
Implicit	CMA	Operand is fixed

---

⭐ 4.6 Instruction Format

8085 uses:

• 1-byte instructions

• 2-byte instructions

• 3-byte instructions

Example:
MOV A, B → 1 byte
MVI A, 32H → 2 bytes
LDA 2050H → 3 bytes

---

⭐ 4.7 Interrupts

Interrupt = CPU’s attention signal.

Types:

1. Hardware – RST 7.5, RST 6.5, RST 5.5, INTR

2. Software – RST instruction

3. Maskable / Non-maskable

4. Vectored / Non-vectored

Example:

• TRAP → Non-maskable, vectored

• RST 7.5 → Maskable, vectored

---

⭐ 4.8 Pipelining

Modern CPUs use pipelines to speed up execution.

Typical stages (RISC pipeline):

1. IF – Instruction Fetch

2. ID – Instruction Decode

3. EX – Execute

4. MEM – Memory Access

5. WB – Write Back

Why pipelining is fast?

Because multiple instructions execute in parallel.

---

⭐ 4.9 Types of Pipelines

• Superpipelining
  (More pipeline stages)

• Superscalar Pipeline
  (More than one instruction issued per cycle)

---

⭐ 4.10 Pipeline Hazards

These are problems that slow down pipelined execution.

---

1️⃣ Data Hazard

Occurs when one instruction depends on the result of the previous one.

Example:

I1: ADD R1, R2, R3  
I2: SUB R4, R1, R5   ← depends on R1  

---

2️⃣ Control Hazard

Occurs in branching.

Example:

BEQ LABEL

Branch decision unknown → pipeline stalls.

---

3️⃣ Structural Hazard

Two instructions need the same hardware resource at the same time.

---

Solutions to hazards

• Forwarding / Bypassing

• Pipeline Stalling

• Branch Prediction

• Separate instruction & data memory

✅ UNIT 3 — Combinational & Sequential Circuits

 ⭐ 3.1 ADDERS

1️⃣ Half Adder

Adds two single-bit numbers (A and B).

Outputs:

• Sum = A ⊕ B

• Carry = A • B

---

2️⃣ Full Adder

Adds three bits (A, B, Cin).

Outputs:

• Sum = A ⊕ B ⊕ Cin

• Cout = AB + BCin + ACin

---

3️⃣ 4-bit & 8-bit Parallel Adder

Uses four full adders connected so that carry passes from one stage to next (ripple carry).

---

⭐ 3.2 SUBTRACTORS

Half Subtractor

Inputs: A, B
Outputs:

• Difference = A ⊕ B

• Borrow = A' • B

Full Subtractor

Inputs: A, B, Bin
Outputs:

• Difference = A ⊕ B ⊕ Bin

• Borrow = A'B + B Bin + A' Bin

---

⭐ 3.3 ADDER–SUBTRACTOR COMBINED CIRCUIT

A single circuit performs both add & subtract using XOR-based control.

Control input M:

• M = 0 → Add

• M = 1 → Subtract

---

⭐ 3.4 MAGNITUDE COMPARATOR

Compares two numbers A and B and generates:

• A > B

• A = B

• A < B

Used in CPU for decision-making (conditional branches).

---

⭐ 3.5 MULTIPLEXER (MUX) & DEMULTIPLEXER (DEMUX)

Multiplexer (MUX)

Selects one input from many and sends to output.

Example: 4-to-1 MUX

Select lines: S1, S0
Output:
Y = S1'S0'I0 + S1'S0I1 + S1S0'I2 + S1S0I3

---

Demultiplexer (DEMUX)

Opposite of MUX — one input → many outputs.

Example: 1-to-4 DEMUX.

---

⭐ 3.6 DECODER & ENCODER

Decoder

Converts n inputs → 2ⁿ outputs.

Example:
2-to-4 decoder
3-to-8 decoder

Used in memory address decoding.

Encoder

Converts 2ⁿ inputs → n outputs.

Example:
8-to-3 encoder
Priority encoder (ignores lower priority inputs)

---

⭐ 3.7 LATCHES & FLIP-FLOPS

1️⃣ LATCH (Level Triggered)

SR Latch

Basic memory element.

S	R	Q(next)
0	0	Q (no change)
0	1	0
1	0	1
1	1	Invalid

2️⃣ Flip-Flop (Edge Triggered)

D Flip-Flop

Stores 1-bit of data.

Q(next) = D

JK Flip-Flop

J	K	Qnext
0	0	Q
0	1	0
1	0	1
1	1	Toggle

T Flip-Flop

T = 1 → Toggle
T = 0 → Hold

---

⭐ 3.8 COUNTERS

1️⃣ Ripple Counter (Asynchronous)

Every flip-flop triggers the next one.

Example: 4-bit ripple counter (counts 0–15).

2️⃣ Ring Counter

A single 1 rotates through flip-flops.

3️⃣ Johnson Counter

Complement of last flip-flop output is fed to first.

---

⭐ 3.9 SEQUENTIAL CIRCUITS

A sequential circuit =
combinational circuit + memory (flip-flops).

Used in:

• Registers

• Counters

• Finite State Machines

• Control units of CPUs

✅ UNIT 2 — Logic Gates, Boolean Algebra, K-Maps, Codes

🌟 2.1 LOGIC GATES

Logic gates are electronic circuits that perform logical operations on binary inputs (0 or 1).

1️⃣ Basic Gates

AND Gate

A	B	Output = A • B
0	0	0
0	1	0
1	0	0
1	1	1

OR Gate

A	B	A + B
0	0	0
0	1	1
1	0	1
1	1	1

NOT Gate

A	A'
0	1
1	0

---

2️⃣ Universal Gates (NAND, NOR)

Any circuit can be built using only NAND or only NOR.

NAND Gate

Output = (A • B)’
Truth Table → Only 1 when both inputs are NOT 1.

NOR Gate

Output = (A + B)’
Truth Table → Only 1 when both inputs are 0.

---

3️⃣ Exclusive Gates

XOR Gate

Output = 1 when inputs are different.
Equation: A ⊕ B = A’B + AB’

XNOR Gate

Output = 1 when inputs are same.

---

🌟 2.2 BOOLEAN ALGEBRA

Important Laws

1. Identity Laws

A + 0 = A
A • 1 = A

2. Null Laws

A + 1 = 1
A • 0 = 0

3. Idempotent Laws

A + A = A
A • A = A

4. Complement Laws

A + A’ = 1
A • A’ = 0

5. De Morgan’s Laws

(AB)’ = A’ + B’
(A + B)’ = A’B’

---

🌟 2.3 Minterms & Maxterms

Minterm (SOP Form)

Each minterm = product term (AND)
Example for 2 variables:
m0 = A’B’
m1 = A’B
m2 = AB’
m3 = AB

Sum of Minterms = SOP

Maxterm (POS Form)

Each maxterm = sum term (OR)
M0 = A + B
M1 = A + B’ etc.

---

🌟 2.4 Simplification Using Karnaugh Map (K-MAP)

Example:

Simplify F(A, B, C) = Σ(1, 3, 5, 7)

K-MAP:

Fill 1’s in cells 1,3,5,7.

Groups formed:

• Group of four (1,3,5,7)

Final simplified function:
👉 F = B

K-map makes long Boolean expressions very small.

---

🌟 2.5 NUMBER CODES

✔ 1. Weighted Codes

Each digit has a weight.
Examples:

• 8421 (BCD)

• 2421

• 5211

✔ 2. Non-Weighted Codes

Weights do NOT apply.
Examples:

• Gray Code

• Excess-3

• ASCII

---

Gray Code

Only one bit changes between consecutive numbers (used in error-free encoding).

Binary to Gray:

G1 = B1
G2 = B1 ⊕ B2
G3 = B2 ⊕ B3

Example:
Binary 101 → Gray = 111

---

Excess-3 Code

Add 3 to each BCD digit.

Example:
BCD 0101 (5)
Excess-3 = 0101 + 0011 = 1000

---

Code Conversions Covered

✔ Binary ↔ Gray
✔ Binary ↔ BCD
✔ BCD ↔ Excess-3
✔ Hex ↔ Binary
✔ Decimal ↔ Binary