Important Questions and Answers on Computer Architecture – Part 2
Half Adder vs Full Adder in Digital Electronics – Truth Tables, Circuits, and Logical Expression
What is Adder?
An adder is a fundamental combinational digital circuit that performs the arithmetic operation of addition on binary numbers.
There are two basic types of adder: 1) Half Adder 2) Full Adder
Half adder:
A combinational logic circuit that adds two single-bit binary numbers, producing a sum bit and a carry-out bit.
Truth table:
Logical expression:
S = A⊕ B; C = AB
Logic circuit:
Full adder:
a combinational logic circuit that adds three one-bit binary numbers, producing a sum and a carry output
Truth table:
Logical expression:
S = A'B'Cᵢ + A'BCᵢ' + AB'Cᵢ' + ABCᵢ
= A'(B'Cᵢ + BCᵢ') + A(B'Cᵢ' + BCᵢ)
= A’(B⊕Cᵢ) + A(𝐵⊕𝑐𝑖
)'
= A’X + AX’ [X = B⊕Cᵢ]
= A⊕B⊕Cᵢ
C0 = A’BCᵢ + AB’Cᵢ + ABCᵢ' + ABCᵢ
= Cᵢ(A’B + AB’) + AB(Cᵢ’ + Ci’)
= Cᵢ(A⊕B) +AB
Logic circuit:
How to make a full adder using half adder.click here
Explicit & implicit normalizaion:
Cache mapping:
Definition of Cache Mapping:
Cache mapping is the process by which data from the main memory is placed into the cache
memory. It determines where and how a particular block of data from main memory will be
stored in the cache. The goal of cache mapping is to maximize efficiency and reduce access time
by ensuring that frequently accessed data is quickly available to the processor.
There are three main types of cache mapping techniques:
1.Direct Mapping: Each block of main memory maps to only one possible cache line.
2.Associative Mapping: Any block of main memory can be placed in any line of the cache.
3.Set-Associative Mapping: A compromise between direct and associative mapping, where the
cache is divided into sets and a block can be placed in any line of a specific set.
Math Example:
Ex,
Main Memory Size: 64 words: and the block size: 4 words
Number of Blocks in Main memory: 64/4 = 16 (which we can
write 0,1,2,3,….,15)
Block replacement
▪ During a Cache miss, how to choose which entry to replace from the cache?
Cache Replacement Policies:
✓ Random Replacement
✓ FIFO & LIFO
✓ Recency-Based Policies
✓ Frequency-Based Policies
✓ Optimal Replacement / Belady’s Algorithm
1. Random Replacement
▪ Remove any block from cache at random
▪ Access to information is not needed
▪ Not implemented now. (Used to be implemented in ARM(Advanced RISC (Reduced Instruction
Set Computer) Machine Architecture) architectures.
2. FIFO
▪ Removes blocks from cache in their order of arrival
▪ Cache behaves as a First-In-First-Out queue.
2. LIFO
▪ Removes the most recently added block (ex., Last-In-First-Out)
▪ Cache behaves as a Stack
3. Optimal Replacement / Belady’s Algorithm
Fixed Auxiliary Storage
The time taken by the disk’s read/write head to move to the track where the required data is stored is called, Seek Time: TS
The time it takes for the right part of the disk to spin under the read/write head after it has moved to the correct track is called rotational delay.: TR ( Half of the Rotation Time)
Average Access Time (Tavg): TS + TR + TDataTransfer
Ex. Consider a HDD with the following specifications,
1) 4 Surfaces
2) 512 tracks per surface
3) 1024 sectors per track
4) Size of each sector: 512 Bytes
a. Find out the capacity of the HDD.
b. If format overhead is 8 Bytes per sector, then find out the formatted capacity of the HDD.
c. Find the number of bits required to address each sector.
a. Find out the capacity of the HDD.
Capacity = No. of surfaces * No. of tracks per surface * No. sectors per track * sector size
= 4 * 512 * 1024 * 512
= 2^30 Bytes = 1 GB
b. If format overhead is 8 Bytes per sector, then find out the formatted capacity of the HDD.
Total no. of sectors = No. surfaces * No. tracks per sector * No. sectors per track
= 2^2 * 2^9 * 2^10
= 2 ^21
Formatting overhead = No. of sector * overhead per sector
= 2^21 * 8 Bytes
= 2^21 * 2^3
= 2^24 Bytes = 16 MB
Formatted capacity = (1024 – 16) MB = 1008 MB
c. Find the number of bits required to address each sector.
Total no. of sectors = 2^21
No. of bits required to address each sector = log2 2 ^21 = 21
No comments