৪৯তম বিসিএস ⎯ তথ্য ও যোগাযোগ প্রযুক্তি [২৮১]

or an 8-bit signed integer, one bit is used for the sign (positive or negative) and the remaining 7 bits are used to represent the magnitude of the number.

• The most significant bit (MSB) is used as the sign bit:
-> 0 indicates a positive number.
-> 1 indicates a negative number.

• For positive numbers (when the MSB is 0), the remaining 7 bits can represent values from 0 to 127 (which is 2⁷−1).

• For negative numbers (when the MSB is 1), the values are represented in two's complement. In two's complement, the most negative value is −2⁷, or -128, and the most positive value is +127.

The range for an 8-bit signed integer is from -128 to +127.

Source:  Digital Logic & Computer Design By M. Morris Mano

Step 1: Understand the Relationship Between Binary and Hexadecimal

• Binary (Base-2) uses digits 0 and 1.
• Hexadecimal (Base-16) uses digits 0-9 and letters A-F.
• 1 hex digit = 4 binary digits (bits).

So, every group of 4 bits in binary can be directly converted into one hex digit.

Step 2: Group Binary Digits into 4-Bit Blocks

• The given binary number is 101101011001
• Count the digits: 12 bits.
• Since hex groups are 4 bits, we can split this 12-bit number into 3 groups of 4 bits each.
• Start grouping from the right (least significant bit): 1011 0101 1001
• 1011 is Leftmost group, 0101 is Middle group, 1001 is Rightmost group

Step 3: Convert Each 4-Bit Group to Hexadecimal
We use this conversion table:

Now convert each group:
1011 is B
0101 is 5
1001 is 9

Step 4: Combine the Hex Digits
Combine the hex digits in the same order (left to right):
Binary 101101011001 is Hexadecimal B59

The answer is B59

Source:  Digital Logic & Computer Design By M. Morris Mano

Computer performance can be evaluated using multiple metrics:
Clock speed: Measures how many cycles per second the CPU executes.
Instruction execution time: Measures the time taken to execute a program or instruction.
CPU utilization: Percentage of time the CPU is actively executing instructions.

All these factors together help determine overall system performance.

Example:
A CPU with a higher clock speed and lower instruction execution time will generally perform better.

Source:  Digital Logic & Computer Design By M. Morris Mano

Processor clock rate: It does not affect instruction count.
Clock rate (e.g., 2 GHz vs 3 GHz) only affects how fast instructions are executed, not how many instructions are required.

Instruction Count (IC) depends on:
Algorithm: Different algorithms perform different numbers of operations.
Example:
Searching in a list → Linear Search vs Binary Search.
Binary Search = fewer instructions.

Compiler efficiency: Different compilers may generate more or fewer instructions for the same high-level code.
Example:
Optimizing compiler removes redundant operations → fewer instructions.

CPU Architecture / Instruction Set: The ISA determines how high-level code translates into machine instructions.
Example:
A single C statement may compile into 2 instructions in CISC but 5 in RISC.

Source:  Digital Logic & Computer Design By M. Morris Mano

Given that,
Clock frequency = 2GHz = 2×10⁹ Hz
Clock Cycle Time = ?

Now,
The Clock Cycle Time is the reciprocal of clock frequency,
∴ Clock Cycle Time = 1/ Clock frequency
= 1/ 2×10⁹ 
= 0.5 × 10^-9
so, Clock Cycle Time = 0.5 × 10^-9 s
∴ Clock Cycle Time = 0.5 ns  [1ns =10^-9 s]
The answer is 0.5 ns

Source:  Digital Logic & Computer Design By M. Morris Mano.

Performance is defined as the inverse of execution time,
Performance = 1/ Execution Time

For two machines A and B running the same program,

Performance Ratio = Performance(A)/ Performance(B)
= { 1/Execution Time(A) } / { 1/Execution Time(B) }

∴ Performance(A)/ Performance(B) = Execution Time(B) / Execution Time(A)

Source:  Digital Logic & Computer Design By M. Morris Mano.

A computer instruction is a binary-encoded command that tells the CPU which operation to perform and what operands (data) to use. Instructions form the machine language of a computer.

Example:
The 8086 assembly instruction ADD AX, BX is translated into binary that the CPU understands, specifying an addition operation and the registers involved.

Source:  Digital Logic & Computer Design By M. Morris Mano

Basic hardware operations include:
Data Transfer: Moving data between memory, registers, or I/O devices
Arithmetic Operations: Addition, subtraction, multiplication, division
Logical Operations: AND, OR, NOT, XOR
Control Operations: Branch, jump, call, return

Program compilation is a software process, not a hardware operation.

Example:
The CPU ALU performs arithmetic and logic operations, while data moves between registers and memory during program execution.

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

An operand is the data (immediate value, register, or memory address) that the CPU operates on using the instruction. Instructions can have zero, one, or multiple operands depending on the operation.

Example:
In the instruction MOV AX, 5, 5 is the operand.
In ADD AX, BX, AX and BX are operands.

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

In direct addressing mode, the address field of the instruction specifies the memory location of the operand directly.

Example:
MOV AX, [1234h]: The data from memory address 1234h is moved into register AX.

Other modes:
Register addressing (MOV AX, BX)
Register indirect (MOV AX, [BX+SI])
Immediate (MOV AX, 5)

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

The method of accessing data depends on the storage device and the type of operation required, as stated in the table below,

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

The instruction cycle is the sequence of steps the CPU performs to execute an instruction.

Fetch: Retrieve the instruction from memory
Decode: Determine the operation and operands
Execute: Perform the operation
Store/Write back: Save the result back to memory or register

Example:
ADD AX, BX → Fetch instruction → Decode opcode → Add contents → Store result in AX

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

A computer instruction typically consists of the following,
Opcode: Specifies the operation to be performed (e.g., ADD, MOV).
Operand(s): Specifies data or memory/register locations to be used.
Addressing mode: Specifies how to interpret the operand(s) (immediate, direct, indirect, etc.).

Example:
MOV AX, [2000h]

Opcode: MOV
Operand: AX, [2000h]
Addressing mode: Direct addressing

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

The instruction length depends on several factors.
• More operands require more bits.
• Larger opcode requires more bits.
• Addressing modes (immediate, direct, indirect) may need additional bits for addresses.

Example:
A RISC CPU may have fixed-length instructions (e.g., 32 bits), whereas a CISC CPU may have variable-length instructions depending on operands and addressing mode.

Source:  Digital Logic & Computer Design By M. Morris Mano.

In relative addressing mode, the operand’s address is determined by adding an offset to the current program counter (PC). This is commonly used for branch and jump instructions.

Example:
JMP 05h → Jump to PC + 05h.

Source:  Digital Logic & Computer Design By M. Morris Mano

BX → Base register
SI → Index register
05h → Displacement
Effective Address = BX + SI + 05h, which is a classic indexed addressing mode with displacement.

Example:
Used to access array elements with a base address in BX, index in SI, and fixed offset for specific element.

Source:  Digital Logic & Computer Design By M. Morris Mano

ADD AX, 5
• Here, operand 5 is a constant value given in the instruction.
• This is Immediate Addressing Mode (the operand is specified directly in the instruction).
• Operand AX is a register, but the important addressing mode for the literal value is immediate.

JMP LABEL
• This transfers control to a LABEL, usually represented as an offset relative to the Program Counter (PC).
• This is Relative Addressing Mode (effective address = PC + displacement).

Now,
• First instruction uses Immediate addressing.
• Second instruction uses Relative addressing.

Source:  Digital Logic & Computer Design By M. Morris Mano

Register addressing: Operand comes from a register. Example: ADD AX, BX.
Memory addressing: Operand comes from memory (direct or indirect). Example: MOV AX, [2000h].
Immediate addressing: Operand is a constant value in the instruction. Example: ADD AX, 5.

ADD [BX+SI+04h], 10
• [BX+SI+04h] = Memory operand (indexed with registers BX + SI + displacement).
• 10 = Immediate constant.
• This uses memory + immediate.
• The memory part itself already involves registers (BX, SI).
• Combines register (BX, SI), memory, and immediate

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

The LOOP instruction in x86 does:
• Decrement CX (or ECX in 32-bit mode) → implicit use of a register.
• If CX ≠ 0, jump to LABEL.
i. The LABEL is encoded as a displacement relative to the Program Counter (PC).
ii. This is relative addressing.

Addressing modes involved:
• CX: used implicitly → Implicit Register Addressing.
• LABEL: encoded as an offset from PC → Relative Addressing.

So, the combined addressing modes are Relative (for jump) + Implicit register (CX)

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

Claude Shannon gave a formula for the maximum data rate (channel capacity) of a communication channel with bandwidth B Hz and signal-to-noise ratio (S/N).

C=Blog2(1+S/N)

Where:
C = channel capacity in bits/sec
B = channel bandwidth (Hz)
S/N = signal-to-noise ratio (power ratio, not dB)

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

ALU sets status flags based on the result of operations:
Zero (Z): Result is zero
Carry (C): An arithmetic carry/borrow occurred
Overflow (O): Signed arithmetic overflow occurred

Example:
ADD AX, BX resulting in 0 → Zero flag set
ADD AL, 0xFF → Carry flag set

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

ASK: Carrier amplitude varies with digital data
FSK: Carrier frequency varies
PSK: Carrier phase varies

Example:
Modems use PSK or FSK for transmitting binary data

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

Floating-point numbers use a mantissa (significant) and exponent to represent numbers in scientific notation, which allows a wide dynamic range of values.

Example:
• 6.022 × 10 × 23 → Mantissa = 6.022, Exponent = 23
• In IEEE 754 single precision, this is stored in 32 bits (1 sign bit, 8 exponent bits, 23 mantissa bits).

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss.

Before adding floating-point numbers, their exponents must match. The smaller exponent is adjusted by shifting the mantissa. After alignment, mantissas are added, followed by normalization and rounding.

Example:
Add 1.23 × 10³ + 4.56 × 10²
• Align exponents: 1.23 × 10³ + 0.456 × 10³ = 1.686 × 10³
• Normalize and round as needed.

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss.

When two nearly equal numbers are subtracted, most leading digits cancel, leaving only a few significant digits. This can lead to loss of precision, called cancellation error.

Example:
12345.67 – 12345.66 = 0.01 → only two digits of precision remain, potential accuracy loss in computation.

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

IEEE 754 specifies round to nearest even as the default to reduce bias in repeated rounding. If exactly halfway, round to the nearest even mantissa.

Example:
• 2.5 rounds to 2 (even)
• 3.5 rounds to 4 (even)

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

Floating-point operations can trigger exceptions:
Overflow: Result too large to represent
Underflow: Result too small to represent
Invalid operation: e.g., 0/0, (-1), results in NaN

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

Frequency Modulation (FM):
s(t)=A_c ​cos [ 2π f_{c ​}t + k_f​ ∫m(t) dt ]

Where,

A_c = carrier amplitude (constant in FM).
f_c = carrier frequency.
m(t) = message signal.
k_f = frequency sensitivity.

In FM, message signal amplitude affects the frequency deviation (Δf):

Δf=k_f⋅∣m(t)∣_max
 ​

• FM varies carrier frequency proportionally to message amplitude
• Peak deviation = k × message amplitude

Example:
Audio signal with higher amplitude → wider frequency swing of FM carrier


Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

In a single-cycle processor, the clock period is long enough to accommodate the slowest instruction. Every instruction, regardless of complexity, completes in one clock cycle.

Example:
ADD and MUL instructions both execute in one cycle; therefore, the clock must be long enough for multiplication to complete.

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

In a multi-cycle processor, instructions are broken into stages (fetch, decode, execute, memory access, write-back), each taking one cycle. Different instructions may require different numbers of cycles.

Example:
ADD may take 4 cycles, MUL may take 6 cycles. Clock period is shorter than single-cycle processor.

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

Recall single-cycle processor:
• In a single-cycle processor, each instruction executes in exactly one clock cycle.
• The clock cycle must be long enough for the slowest instruction.
• Control is simpler (but that’s not efficiency).

Result: inefficient hardware usage because simpler instructions waste time waiting for the clock to finish.

Recall multi-cycle processor:
• In a multi-cycle processor, instructions are divided into multiple steps (fetch, decode, execute, memory access, write-back).
• Each step is executed in one clock cycle.
• The clock period is determined by the longest step, not the longest instruction.
• Complex instructions take more cycles, simple instructions take fewer cycles.

Result: shorter clock period → faster execution on average.

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

Hardwired CU: Uses combinational logic circuits to generate control signals.
Microprogrammed CU: Uses a control memory storing microinstructions to generate control signals.

Example:
• Hardwired CU → Faster, less flexible
• Microprogrammed CU → Easier to modify for new instruction sets

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

A microinstruction is a low-level instruction that defines the control signals in a microprogrammed control unit of the CPU.
It typically contains fields to:
• Generate control signals for datapath elements (ALU, memory, I/O, registers).
• Specify next microinstruction (next-address field).
• Optional condition field for branching (e.g., check Zero flag, carry, etc.).

Example:
Microinstruction sequence:
Step 1: Activate ALU for addition
Step 2: Store result → jump to next microinstruction

Source: Data Structures and Algorithm Analysis in C by Mark Allen Weiss

• CISC instruction sets have complex instructions.
• CISC has a large number of instructions, some of which are complex and may take multiple cycles to execute.
• Instructions can perform multiple low-level operations (like memory access, arithmetic, branching) in a single instruction.
• Microprogrammed CU simplifies implementation because each instruction can be represented as a sequence of microinstructions.

Source:  Digital Logic & Computer Design By M. Morris Mano

Data hazard: Occurs when an instruction depends on the result of a previous instruction that has not yet completed.
Control hazard: Occurs due to branch or jump instructions affecting instruction fetch.
Structural hazard: Occurs when hardware resources are insufficient for all concurrent instructions.

Example:
Data hazard: ADD R1, R2, R3 followed by SUB R4, R1, R5
Control hazard: Conditional branch instruction
Structural hazard: Only one memory port but multiple instructions need access simultaneously

Source:  Digital Logic & Computer Design By M. Morris Mano

RAW hazard (true dependency): Instruction needs to read a value before it is updated by a previous instruction.
WAR hazard (anti-dependency): Instruction writes to a location before it is read by an earlier instruction
WAW hazard (output dependency): Instruction writes to a location before it is updated by a previous instruction

Example:
ADD R1, R2, R3
SUB R4, R1, R5  [ <- RAW hazard on R1 ]

Source:  Digital Logic & Computer Design By M. Morris Mano

Branch prediction guesses the outcome of a branch instruction to keep the pipeline filled.
Correct predictions avoid pipeline stalls caused by control hazards.

Example:
CPU predicts BEQ R1, R2 as not taken → continues fetching instructions
If prediction fails → flush pipeline and fetch correct instructions

Source:  Digital Logic & Computer Design By M. Morris Mano

Exceptions can arise due to hardware or software events, including:
• Arithmetic overflow: Result too large for CPU representation
• Divide-by-zero: Illegal arithmetic operation
• Invalid opcode: Attempt to execute a non-existent instruction

Example:
Instruction DIV R1, 0 → Divide-by-zero exception
Instruction ADD R1, 0xFFFF, 0xFFFF → Arithmetic overflow

Source:  Digital Logic & Computer Design By M. Morris Mano

CPU saves the program counter and processor state, then jumps to an exception handler (service routine) to resolve the exception.
After handling, control may return to the interrupted instruction or the next instruction.

Example:
Divide-by-zero → CPU jumps to routine that prints error message and stops program safely.

Source:  Digital Logic & Computer Design By M. Morris Mano

Multiple instructions per cycle increase throughput.
Superscalar processors do not eliminate hazards; hardware or dynamic scheduling handles them.
Control complexity increases, not decreases.

Example:
A 4-way superscalar CPU can ideally execute 4 instructions per clock cycle, depending on instruction independence.

Source:  Digital Logic & Computer Design By M. Morris Mano

Scoreboarding: Tracks instruction status and functional unit availability to resolve hazards.
Tomasulo Algorithm: Uses register renaming and reservation stations to execute instructions out-of-order dynamically.

Example:
Instruction ADD R1, R2, R3 may wait if R2 is not ready; scoreboarding keeps track of availability.

Source:  Digital Logic & Computer Design By M. Morris Mano

In a pipelined processor, hazards (like data hazards, structural hazards) may stall the pipeline.
Out-of-order execution (dynamic scheduling using Tomasulo’s algorithm or reservation stations) allows the CPU to:
• Execute instructions as soon as operands are ready, even if earlier instructions are waiting.
• Independent instructions can “overtake” stalled ones.
• This improves instruction throughput and keeps pipeline units busy.
At the end, results are committed in program order (to maintain correctness).

Dynamic scheduling allows independent instructions to be executed out-of-order while waiting for operands of stalled instructions.
This minimizes pipeline stalls and increases overall performance.

Source:  Digital Logic & Computer Design By M. Morris Mano.

Cache memory is a small, fast memory placed between CPU and main memory.
It stores frequently accessed instructions and data to reduce latency and improve performance.
Cache is much faster than main memory but smaller in size.

Example:
CPU frequently accesses variable X → X is kept in cache → next access is faster.

Source:  Digital Logic & Computer Design By M. Morris Mano.

A cache hit occurs in a computer system when the CPU requests data and that data is found in the cache memory.
Cache Memory:
Cache is a small, high-speed memory located close to the CPU.
It stores frequently accessed instructions or data from the main memory (RAM) to reduce access time.

CPU Data Request:
When the CPU needs data, it first checks the cache memory.
If the requested data is present in the cache, it can be accessed much faster than fetching it from main memory.

Source:  Digital Logic & Computer Design By M. Morris Mano

Write-through: Data is written to both cache and main memory simultaneously.
Write-back: Data is written to cache only; main memory updated later when cache block is replaced.

Each policy has trade-offs in speed and memory consistency.

Example:
MOV [X], R1 → in write-through, memory updated immediately; in write-back, updated later.

Source:  Digital Logic & Computer Design By M. Morris Mano

L1: Closest to CPU, small (16–64 KB), fastest
L2: Larger (256 KB–1 MB), slightly slower
L3: Shared, largest (2–32 MB), slowest among caches but faster than main memory

Example:
CPU frequently accesses L1 → immediate execution
L3 serves as backup if L1/L2 miss

Source:  Digital Logic & Computer Design By M. Morris Mano

LRU: Evict block that has not been used for the longest time
FIFO: Evict block that came in first
Random: Evict a random block
Policies help decide which block to replace on a cache miss

Example:
LRU → Frequently accessed data remains in cache
Random → Simplest hardware implementation

Source:  Digital Logic & Computer Design By M. Morris Mano

Virtual memory allows programs to use a logical address space that may be larger than physical memory.
The operating system maps virtual addresses to physical memory and secondary storage (disk) as needed.

Example:
A 32-bit program can address 4 GB of memory, even if physical RAM is only 1 GB.

Source: Structured Computer Organization by Andrew S. Tanenbaum