# Unit 1: Fundamentals of Processors and Data Representation --- ## 1. Bus Architecture and Bus Arbitration ### Bus Architecture * **Bus**: A set of wires or lines used to transfer data, addresses, and control signals between different components of a computer system. * **Types of Buses**: * **Data Bus**: Transfers data between CPU, memory, and I/O devices. Bidirectional. * **Address Bus**: Specifies the memory location or I/O device the CPU wants to access. Unidirectional (CPU to memory/I/O). * **Control Bus**: Carries control and timing signals (e.g., read/write, interrupt requests, clock). Bidirectional. * **Bus Width**: Number of data lines, affects data transfer rate. ### Bus Arbitration * **Purpose**: To manage access to the bus when multiple devices request it simultaneously. * **Arbiter**: Hardware logic that decides which device gets bus control. * **Methods**: * **Centralized Arbitration**: A single bus controller manages bus access. * **Serial Arbitration**: Daisy-chaining, priority based on physical connection. Simple but slow for many devices. * **Parallel Arbitration**: Each device has a dedicated line to the arbiter. Faster but requires more wires. * **Distributed Arbitration**: Each device has its own arbitration logic. No central controller. More complex but robust. --- ## 2. Register Transfer, Bus and Memory Transfer ### Register Transfer Language (RTL) * A symbolic notation used to describe the micro-operations and data transfers between registers. * **Notation**: `Destination Register <- Source Register, Control Signal` * Example: `R1 <- R2` (Transfer content of R2 to R1) * Example: `R3 <- R3 + R4, Enable_Add` (Add R4 to R3 and store in R3 if `Enable_Add` is active) ### Bus Transfer * Data transfer between registers using a common bus. * A bus controller enables specific registers for reading and writing. * **Example**: Transfer from R1 to R2 via bus: * `R1_out -> Bus, R2_in <- Bus` (controlled by a common selection signal) ### Memory Transfer * Involves **Memory Address Register (MAR)** and **Memory Data Register (MDR)**. * **Read Operation**: 1. CPU places address in MAR. 2. CPU asserts Read control signal. 3. Memory retrieves data from the specified address. 4. Data is placed in MDR. 5. CPU reads data from MDR. * **Write Operation**: 1. CPU places address in MAR. 2. CPU places data in MDR. 3. CPU asserts Write control signal. 4. Memory writes data from MDR to the specified address. * **RTL Representation**: * Read: `MDR <- M[MAR]` * Write: `M[MAR] <- MDR` --- ## 3. Arithmetic, Logic & Shift Microoperations * **Microoperation**: An elementary operation performed on the data stored in registers. * **Arithmetic Microoperations**: * **Increment**: `R1 <- R1 + 1` * **Decrement**: `R2 <- R2 - 1` * **Add**: `R3 <- R1 + R2` * **Subtract**: `R4 <- R5 - R6` * **Arithmetic Shift**: Signed shifts, preserve sign bit. * **Logic Microoperations**: * **AND**: `R1 <- R1 & R2` * **OR**: `R2 <- R2 | R3` * **XOR**: `R3 <- R3 ^ R4` * **Complement (NOT)**: `R4 <- ~R5` * **Shift Left (Logical)**: `R5 <- R5 << 1` (Zero fills the rightmost bit) * **Shift Right (Logical)**: `R6 <- R6 >> 1` (Zero fills the leftmost bit) * **Shift Microoperations**: * **Logical Shift Left (LSL)**: `R <- R << 1` * **Logical Shift Right (LSR)**: `R <- R >> 1` * **Arithmetic Shift Left (ASL)**: Same as LSL, but can cause overflow. * **Arithmetic Shift Right (ASR)**: Preserves sign bit (leftmost bit). * **Circular Shift (Rotate)**: Bits shifted out are inserted back into the other end. * **Rotate Left (ROL)**: `R <- R << 1 | R[msb]` * **Rotate Right (ROR)**: `R <- R >> 1 | R[lsb]` --- ## 4. Fixed & IEEE 754 Floating Point Representation ### Fixed Point Representation * The **binary point** is fixed at a specific position. * **Integers**: * **Unsigned**: All bits represent magnitude. Range $0$ to $2^n-1$ for $n$ bits. * **Signed**: One bit for sign, rest for magnitude. * **Signed Magnitude**: MSB is sign bit (0=+, 1=-). * **1's Complement**: Negative numbers are bitwise complement of positive. * **2's Complement**: Most common. Negative numbers are $2^n$ + magnitude. Simplifies arithmetic. * **Fractions**: Binary point is usually assumed to be to the left of the MSB. ### IEEE 754 Floating Point Representation * A standard for representing real numbers in binary. * **Format**: `Sign (S) | Exponent (E) | Mantissa (M)` * **Components**: * **Sign (S)**: 1 bit (0 for positive, 1 for negative). * **Exponent (E)**: Biased representation. `Actual Exponent = E - Bias`. * Single Precision (float): 8 bits, Bias = 127. * Double Precision (double): 11 bits, Bias = 1023. * **Mantissa (M)**: Represents the fractional part. An **implicit leading '1'** is assumed for normalized numbers (for single and double precision, excluding subnormals). * **Value Calculation**: * Normalized: $(-1)^S \times (1.M) \times 2^{(E - Bias)}$ * De-normalized (Subnormal): $(-1)^S \times (0.M) \times 2^{(E - Bias)}$ * **Special Values**: * **Zero**: E=0, M=0. * **Infinity**: E=all 1s, M=0. * **NaN (Not a Number)**: E=all 1s, M != 0. --- ## 5. Error Detection Codes * **Purpose**: To detect errors introduced during data transmission or storage. * **Parity Bit**: * An extra bit added to a binary message to make the total number of 1s either even or odd. * **Even Parity**: Total number of 1s (including parity bit) is even. * **Odd Parity**: Total number of 1s (including parity bit) is odd. * **Detection Capability**: Detects single-bit errors. Cannot detect double-bit errors. * **Hamming Codes**: * More powerful than parity. Can detect up to 2-bit errors and correct 1-bit errors. * Uses multiple parity bits positioned at powers of 2 (1, 2, 4, 8, ...). * Each parity bit checks a specific subset of data bits. --- ## 6. Signed Number Representation * **Unsigned**: All bits represent magnitude. Range $0$ to $2^n-1$. * **Signed Magnitude**: * MSB is the sign bit (0 for +, 1 for -). * Remaining bits are the magnitude. * **Issue**: Two representations for zero (+0 and -0), complex arithmetic. * **1's Complement**: * Positive numbers: Same as unsigned. * Negative numbers: Bitwise complement of the positive equivalent. * **Issue**: Two representations for zero (+0 and -0). * **2's Complement**: * Most widely used representation for signed integers. * Positive numbers: Same as unsigned. * Negative numbers: To find $-X$ from $X$, invert all bits of $X$ and add 1. Or, $-X = 2^n - X$. * **Advantages**: * Unique representation for zero. * Addition and subtraction logic is the same for signed and unsigned numbers. * **Range for n bits**: $-(2^{n-1})$ to $+(2^{n-1} - 1)$. --- ## 7. Addition and Subtraction ### Addition * Performed using **full adders** (or ripple-carry adders). * For $n$-bit numbers, $n$ full adders are connected in series. * **Algorithm**: 1. Align numbers by the binary point. 2. Add corresponding bits from right to left, propagating carry. 3. Handle overflow if necessary. * **2's Complement Addition**: * To compute $A+B$, simply add $A$ and $B$ using binary addition. * The carry-out of the MSB is ignored (for addition without subtraction). * **Overflow**: Occurs if the sign of the result is incorrect. * Adding two positives results in a negative. * Adding two negatives results in a positive. ### Subtraction * Typically implemented by adding the 2's complement of the subtrahend. * To compute $A-B$: Compute $A + (-B)$. * $-B$ is the 2's complement of $B$. * **Algorithm for $A-B$ (using 2's complement)**: 1. Find the 2's complement of $B$. 2. Add $A$ to the 2's complement of $B$. 3. The result is $A + (-B)$. * **Overflow Detection in Subtraction**: * When adding $A + (-B)$, overflow occurs if: * $A$ is positive, $-B$ is negative, and the result is negative. * $A$ is negative, $-B$ is positive, and the result is positive. --- ## 8. Booth’s Algorithm * An algorithm for **fast multiplication** of signed binary numbers (using 2's complement). * It reduces the number of additions/subtractions required compared to the standard multiplication algorithm. * **Principle**: Examines pairs of bits in the multiplier. * `00` or `11`: No operation (shift only). * `01`: Add multiplicand (M) to the partial product. * `10`: Subtract multiplicand (M) from the partial product. * **Steps**: 1. Initialize: Multiplier (Q), Multiplicand (M), Accumulator (A) to 0, and a trailing 0 for Q (Q0). 2. Iterate $n$ times (where $n$ is the number of bits in the multiplier). 3. In each iteration, examine the last two bits of Q ($Q_1Q_0$). 4. Perform the appropriate operation (shift, add M, subtract M) based on $Q_1Q_0$. 5. Perform an arithmetic right shift on A, Q, and Q0. * **Advantage**: Can be significantly faster when the multiplier has long strings of 0s or 1s. --- ## 9. Restoring and Non-Restoring Division Algorithms ### Restoring Division * Algorithm for dividing unsigned binary numbers. * **Principle**: 1. Initialize: Dividend (V), Divisor (D). 2. Repeatedly subtract the divisor from the remainder. 3. If the result is negative, **restore** the remainder (add the divisor back) and set the quotient bit to 0. 4. If the result is non-negative, the quotient bit is 1. * **Steps (for n-bit quotient)**: 1. Start with the dividend in the accumulator (A). 2. For $i = 1$ to $n$: * Perform an arithmetic left shift on A. * Subtract the divisor D from A. * If $A < 0$: * Add D back to A (restore). * Set the $i$-th quotient bit to 0. * Else ($A \ge 0$): * Set the $i$-th quotient bit to 1. * **Drawback**: The restoring step can be computationally expensive. ### Non-Restoring Division * An optimization of the restoring division algorithm. * **Principle**: Avoids the explicit restoring step by using different operations based on the sign of the previous remainder. * **Steps (for n-bit quotient)**: 1. Initialize: Dividend in A, Divisor in D. Handle the first step separately. 2. For $i = 1$ to $n$: * If $A \ge 0$: * Arithmetic left shift A. * Subtract D from A. * Else ($A < 0$): * Arithmetic left shift A. * Add D to A. * If $A \ge 0$: * Set $i$-th quotient bit to 1. * Else ($A < 0$): * Set $i$-th quotient bit to 0. 3. **Final Correction**: If the final remainder in A is negative, add the divisor D to A and set the most significant quotient bit to 0. Otherwise, the remainder is positive. * **Advantage**: Generally faster than restoring division.