COMPUTER ORGANIZATION & ARCHITECTURE

Answer: (ii) EBCDIC (8-bit) — with note:

• EBCDIC (Extended Binary Coded Decimal Interchange Code) is 8-bit encoding used in IBM mainframes to store data. ASCII is originally 7-bit (extended 8-bit later), but classic textbook for 8-bit format cites EBCDIC.
• USCII/ANCI are not standard encodings.

If strict modern context: Extended ASCII is also 8-bit, but among given options EBCDIC is the intended 8-bit format. Some keys mark EBCDIC as correct.

Answer: (iv) Faster addition by reducing carry propagation delay

Carry Look-Ahead Adder (CLA) generates carries in parallel using generate (G) and propagate (P) signals, avoiding ripple delay. Trade-off: more complex hardware but faster. Not simpler or lower power.

Answer: (i) PCI bus

Explanation: PCI (Peripheral Component Interconnect) bus is commonly used to connect graphics/monitor via graphics adapter to CPU. SCSI is for disks, memory bus connects CPU to main memory. RAM bus is not standard term for monitor connection. Modern: PCIe for graphics.

Answer: (ii) ADDI 5, R1

Explanation:
ADD #5, R1 is Immediate addressing mode - #5 denotes constant 5 as operand, added to register R1.

• ADDI = ADD Immediate - dedicated mnemonic for immediate operation. ADDI 5,R1 is architecturally identical to ADD #5,R1.
• (i) ADD [5],[R1] - is direct/memory addressing, wrong.
• (iii) ADDIME is not a standard mnemonic.

Note: Syntax varies by assembler (ADD R1, #5), but ADDI is the conventional alternate.

Answer: (iv) decoding the data in MDR and placing it in IR

Explanation:
Instruction Fetch Cycle steps:

1. MAR ← PC - place address of next instruction in MAR
2. MDR ← M[MAR] - read memory word into MDR (option i)
3. IR ← MDR - transfer instruction to Instruction Register and decode
4. PC ← PC + 1

The phase ends when instruction is available in IR for decode/execution. Option (ii) is start of fetch, (i) is middle. Hence (iv) is correct. Note: Some texts stop fetch at MDR loading (i), but classical fetch-decode cycle includes IR loading as final step.

Answer: (iii) MISD

Explanation (Flynn's taxonomy):

• SISD - Single Instruction Single Data - standard uni-processor.
• SIMD - Single Instruction Multiple Data - GPUs, vector processors.
• MIMD - Multiple Instruction Multiple Data - multicore/multiprocessor.
• MISD - Multiple Instruction Single Data - several instructions on single data stream - theoretically defined but has no practical/commercial realization; hence considered useless category.

Duplicate of Q31_2.

Answer: Range $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$

Explanation (n-bit 1's complement):

• Positive numbers: $0$ to $2^{n-1}-1$ (leading bit 0)
• Negative numbers obtained by complementing bits: $-(2^{n-1}-1)$ to $-0$
• Two zeros: $+0 = 00...0$ and $-0 = 11...1$ - wasted code, hence $2^n-1$ effective values but $2^n$ encodings.
• e.g., n=8: $-127$ to $+127$; n=4: $-7$ to $+7$.
• Contrast with 2's complement: $-2^{n-1}$ to $2^{n-1}-1$ (single zero, one extra negative value).

Answer: Range $-2^{n-1}$ to $2^{n-1}-1$

Explanation (n-bit 2's complement):

• Most negative number: $100...0$ = $-2^{n-1}$
• Most positive number: $011...1$ = $2^{n-1}-1$
• Total distinct values: $2^n$
• Single representation of zero (unlike 1's complement / sign-magnitude).
• e.g., for n=8: $-128$ to $+127$; for n=4: $-8$ to $+7$.

This is the range used in ALU and modern processors for signed integers.

Answer: (iii) Control Unit

Explanation:

• Control Unit (CU): Generates timing & control signals, fetches instruction (via PC/MAR/MDR), decodes it (via IR/decoder), and directs ALU, memory and I/O to execute it.
• ALU only does arithmetic/logic, Memory Unit stores, I/O Unit interfaces with peripherals.

Note: In broader sense CPU (CU + ALU) does FDE, but among given options CU is the coordinating unit responsible for the cycle.

End-Around Carry (EAC) Correction - 1's Complement Addition:

In 1's complement, negative numbers are bitwise complements. When adding, a carry out of MSB is not discarded but added back to LSB (end-around carry).

Rule: Add numbers as unsigned. If carry-out $C_{out}=1$, add 1 to result to get correct sum.

Example: Add $+5$ (0101) and $-3$ (1100 in 1's complement):
0101 + 1100 = 10001 -> 4-bit result 0001 with $C_{out}=1$. Add EAC: 0001+1 = 0010 (2), which is correct ($5-3=2$).

If no carry ($C_{out}=0$), result is already correct and negative (1's complement) if MSB=1. Double complement case $1111$ represents -0.

Answer: (i) Signed integers

Two's complement is the standard representation for signed integers in modern computers.

• Allows representation of both positive and negative numbers using a single binary format with MSB as sign bit (0 = positive, 1 = negative).
• Enables subtraction to be performed as addition: A - B = A + (-B) where -B is two's complement of B (invert bits + 1).
• Unique representation for zero and simple arithmetic overflow detection. It is not used for opcodes, ASCII or floating-point (which uses IEEE 754 sign-magnitude).

Correct option: (i)

Booth Algorithm — Role in Fast Multipliers (2m):

Booth's algorithm enables fast signed (two's complement) multiplication with fewer add/sub operations.

• Standard shift-and-add requires an addition for every 1 in multiplier. Booth recodes multiplier and examines pairs of bits ($Q_0, Q_{-1}$):
  • 00 or 11 → arithmetic right shift only
  • 01 → Add multiplicand (A = A + M)
  • 10 → Subtract multiplicand (A = A - M)
    followed by arithmetic right shift.
• Handles positive and negative operands uniformly without separate sign correction.
• Reduces number of operations for strings of 1s (e.g., 01110 handled with one add and one subtract), speeds up multiplier and naturally supports efficient hardware (Booth recoding, Modified Booth Radix-4).
• Basis for modern high-speed array / Wallace-tree multipliers.

Answer: (iv) Multiplication

Booth's algorithm is used for signed binary multiplication (two's complement).

It efficiently multiplies two signed numbers by reducing the number of add/subtract steps via recoding of the multiplier, handling both positive and negative operands without separate sign correction.

Correct option: (iv) Multiplication — not for floating-point, character coding or division.

Answer: (i) Mantissa

In floating-point representation a number is stored as:

$$\text{Value} = (-1)^{S} \times M \times B^{E}$$

where S = sign bit, M = Mantissa (also called significand/mantissa) = significant digits/precision, E = exponent, B = base (2 for binary).

• Mantissa holds the significant digits of the number.
• Exponent scales the magnitude (position of binary point).
• e.g. $123.45 = 0.12345 \times 10^{3}$ → $0.12345$ is mantissa, $3$ is exponent.

So correct option is (i) Mantissa.

Answer: (iii) Main memory

Explanation:
Main Memory (Primary Memory / RAM) holds both data and instructions temporarily while CPU processes them. CPU fetches instructions and operands from main memory into registers, executes, and writes results back. It is volatile, provides fast random access to the active program and data.

• Why (iii) is correct: In von Neumann architecture, main memory is the working store - it contains the currently executing program, intermediate data, and results until needed. Its contents are directly addressable by CPU via MAR/MDR.

• Why others are incorrect:

  • (i) ROM: Non-volatile, read-only, holds firmware/BIOS permanently, not temporary processing data/instructions.
  • (ii) Control Unit: Generates control signals and decodes instructions; does not store user data/instructions.
  • (iv) Coprocessor chip: Auxiliary processor (e.g., 8087 floating-point coprocessor) for specialized computation, not storage.

Hence the unit that temporarily buffers code and data for CPU is main memory (RAM).

Main Structural Components of a Computer (7M)

Derived from Von Neumann model (Stallings). Four top-level components interconnected via System Bus.

                +-------------------+
                |   System Bus      |
                | A (Address) D (Data) C (Control) |
                +--+-----+------+---+
                   |     |      |
        +----------+ +---+----+ +--+----------+
        |   CPU    | | Memory | | I/O System  |
        |Processor | |        | |Module/Device|
        +----------++----+-----+ +-------------+
               |          |            |
        (Control, ALU, Registers)

1. Central Processing Unit (CPU) - Brain

• Function: Fetches instructions, decodes, executes, controls entire system.
• Sub-components:
  • ALU (Arithmetic Logic Unit): Performs arithmetic (ADD, SUB, MUL) and logical (AND, OR, NOT, SHIFT). Operates on registers.
  • Control Unit (CU): Generates timing & control signals (micro-operations) to coordinate fetch-decode-execute. Hardwired or Microprogrammed.
  • Registers: Very fast internal storage - PC (Program Counter), IR (Instruction Register), MAR/MDR (Memory Address/Data Registers), GPRs, PSW/FLAGS, SP.
  • Internal Bus: Connects CU-ALU-Registers.

CPU performs Fetch Cycle (MAR <- PC, MDR <- Memory, IR <- MDR, PC++) and Execute Cycle.

2. Main Memory - Storage for Program & Data

• Function: Stores instructions & data temporarily while program runs. Byte-addressable, random access.
• Types: RAM (Volatile, read/write) - DRAM/SRAM for main memory; ROM (Non-volatile) - BIOS, bootstrap.
• Organization: Address space 2^n locations, n = address bus width (e.g., 32-bit CPU -> 4GB). Memory hierarchy includes Cache (SRAM, L1/L2/L3 between CPU & RAM) to bridge speed gap.
• Interface: Address Bus selects location, Data Bus carries data, Control (MEMR/MEMW) signals read/write. Access time ~ 50-100 ns vs CPU cycle ~ 1 ns -> cache needed.

3. I/O System (Input / Output) - Interface to External World

• Function: Transfers data between computer and peripherals / outside. Also called I/O Module / I/O Subsystem.
• Examples: Keyboard, Mouse, Display, Disk, Network card, Printer, Sensors.
• I/O Module Functions: Control & timing, CPU communication (decode address, data buffering), device communication, error detection.
• Techniques: Programmed I/O, Interrupt-driven I/O, DMA (direct memory access). Includes ports, device controllers, bus adapters.

4. System Bus - Communication Highway

• Function: Set of shared communication lines interconnecting CPU, Memory, I/O. Uses bus protocols/arbitration.

Three buses (can be multiplexed):

• Address Bus (Unidirectional, CPU -> Memory/I/O): Carries address k-bits to select one of 2^k locations. With 32-bit bus => 4GB.
• Data Bus (Bidirectional): Carries data/instruction word (8/16/32/64-bit) - width determines word size.
• Control Bus (Mixed): Carries control signals - MEMR*, MEMW*, IOR*, IOW*, CLK, RESET, READY, INTR, HOLD/HLDA, INTA*.

In single-bus structure, only one transfer at a time; arbitration needed (centralized 8289 or distributed).

Operation Cycle Example: CPU places address on Address Bus -> asserts MEMR* on Control Bus -> Memory puts data on Data Bus -> CPU latches via MDR.

Supplementary Interconnections:
Some texts list Interconnection Structure as 5th view, but exam expects 4. Mention that performance depends on bus width/speed (bandwidth = data_width * clock_rate).

For diagram: Draw central System Bus as three lines linking four blocks; inside CPU expand to CU+ALU+Registers; show I/O module between bus and peripheral.

Addressing Mode - Why Techniques & Two Modes Without Address Field (7M)

A) What is Addressing Mode?

Field A in instruction format OPCODE | A is not necessarily the operand itself. Addressing mode is the rule CPU uses to interpret A to locate the operand or Effective Address (EA). Decoder uses mode bits (ModR/M in x86) to compute EA = f(A, Registers, PC, Indirect chain).

Without modes, every instruction would need full absolute address → large code, inflexible.

Example formats:

Format: | Opcode | Mode | Address field A |  (16-32 bit system)
EA derivation depends on Mode:
 Mode 00: EA = A           (Direct)
 Mode 01: EA = (A)         (Indirect)
 Mode 10: Operand = A      (Immediate)

B) Why Do Computers Use Addressing Mode Techniques?

1. Flexibility to High-Level Constructs:

   • Arrays: Base + Index*Scale access A[i] without computing address manually each time.
   • Pointers/Dynamic structures: Indirect Mov R,(P) dereferences pointer.
   • Records/Structs: Displacement Struct + Offset.
   • Position-Independent Code: Relative PC + Disp for branching/ PIC.

2. Reduce Instruction Size / Code Density:

   • Immediate 8-bit vs 32-bit address, Register mode uses 3 bits to select register vs 32-bit absolute. Keeps program shorter → fewer instruction fetches.

3. Support Multiple Data Structures with Few OpCodes:

   • One ADD opcode works for ADD #5, ADD [2000H], ADD [BX+SI] differing only by mode bits, not separate opcode per operand location.

4. Efficient Loop & Stack Handling:

   • Auto-increment/decrement (R)+ , -(R) for traversing arrays/stacks without extra INC instruction; Stack mode implied via SP.

5. Virtual Memory & Protection (x86):

   • Segmentation + indexed modes hide physical address calculation.

6. Performance: Register mode fastest (no memory access); with modes, compiler can keep hot variables in registers, use immediate for constants (no memory load). Reduces memory traffic.

In summary: Modes bridge gap between programmer's abstract view (variables, pointers, arrays, constants) and hardware's physical view (linear memory addresses) while minimizing instruction bits.

C) Two Modes That Do NOT Use Address Field

Some instructions have no address operand at all; operand location is implied or is the instruction itself.

1. Implied / Implicit / Stack Mode
No address field present; operand(s) implicitly assumed.

• Definition: Opcode itself implies where operand resides - typically top of stack, accumulator, or flags register.
• Operation: EA not needed; CPU internally uses SP or accumulator.

Examples:

• Stack Zero-address: PUSH AX ; POP BX ; ADD (in stack machine) → pops TOS and TOS-1, pushes sum. E.g., PUSH 2; PUSH 3; ADD → stack top = 5.
• Accumulator implied: CMA (Complement Accumulator), INCA (Increment A) - operand is always AC.
• Flag implied: CLC (Clear Carry), STC, CLI/STI - operates on FLAGS, no operand.
• Example encoding: CLC = F8H (8086) - 1 byte, no address bits. PUSH AX = 50H.
• EA calculation: None, SP used: PUSH: SP=SP-2, Mem[SP]=AX. No address in instruction stream.

2. Immediate Mode
Operand value itself IS the address field - no memory/register address is referenced beyond instruction.

• Definition: Operand = A where A is the value encoded in instruction after opcode. No EA computation, no extra memory fetch beyond instruction fetch.
• Distinctness: Technically it has an "address field" but it does not contain an address; it contains data. For exam classification, it counts as no-address-field-needed for operand location (value fetched alongside instruction).

Examples:

• MOV AX, 1234H (8086: B8 34 12) - moves constant 0x1234 to AX. 1234H is part of instruction.
• ADD R1, #10 (Assembly # denotes immediate): R1 = R1 + 10, 10 encoded as 8-bit immediate 00001010.
• CMP AL, 5 Immediate 5 compared to AL.
• Encoding advantage: 2-4 byte instruction vs 6-byte load from memory pool.

Note: Some texts also call Register mode as not using address field (register ID is attribute, not memory address), but exam expects Implied and Immediate as canonical two that use no memory address. Mention Register as alternative if needed.

Contrast:
 Direct:  | LDA | 2000H | -> need to fetch Mem[2000H] (extra cycle)
 Immediate:| MVI | 25H   | -> value 25H used directly, no extra fetch
 Implied: | CLC |       -> no field at all

Tip for diagram: Draw instruction format boxes: Immediate shows Opcode | Immediate Value and Implied shows only Opcode.

Functional Blocks of a Computer - CPU, Memory, I/O with Diagram (7M)

Derived from Von Neumann Stored Program concept. Four main functional blocks interconnected by System Bus.

                    +----------------------------+
                    |      Central System Bus    |
                    |  Address | Data | Control  |
                    +----+-------------+----+----+
                         |             |    |
        +----------------+ +-----------+ +--+-----------+
        |   CPU          | |  Memory   | | I/O Module   |
        | +------------+ | | +-------+ | | +----------+ |
        | | Control    | | | |  RAM   | | | Control  | |
        | | Unit (CU)  | | | | (R/W)  | | +----+-----+ |
        | +------------+ | | +-------+ | |      | I/O  |
        | | ALU        | | | |  ROM   | | +----+-----+ |
        | | (ADD,SUB,  | | | |  Cache | | | Device | |
        | |  AND,OR)   | | | +-------+ | | |Controller|<---> Peripheral
        | +------------+ | |            | | +----------+ |  (Keyboard,
        | | Registers  | | |            | |              |   Display, Disk)
        | | PC,IR,MAR, | | |            | +----------------+
        | | MDR,GPR,SP | | |            | 
        | +------------+ | |            |
        | | Internal Bus | |            |
        +----------------+ +-----------+ +----------------+
                                          Interconnection via Bus Arbitration

1. Central Processing Unit (CPU) / Processor

Heart & Brain - fetches, decodes, executes instructions and coordinates.

a) Control Unit (CU):
Generates control signals, sequencing fetch-decode-execute. Controls data flow between blocks via control bus (MEMR, MEMW, IOR, IOW, CLK). Two implementations: Hardwired (fast, for RISC) and Microprogrammed (flexible, for CISC - stores microinstructions in control memory).

b) Arithmetic Logic Unit (ALU):
Executes arithmetic (ADD, SUB, MUL, DIV, INC), logical (AND,OR,XOR,NOT), shift/rotate. Contains adder, shifter, status flags (CF,ZF,SF,OF). Operates on registers.

c) Register Organization:
Fast internal storage (ns access):

• User-visible: GPRs (AX,BX,CX,DX in 8086; R0-R15 in ARM), Data/Address registers.
• Control & Status: PC (Program Counter / IP) holds next instruction address, IR (Instruction Register) holds current opcode, MAR (Memory Address Register), MDR/MBR (Memory Data Register), SP (Stack Pointer), PSW/FLAGS.
• Internal bus connects them with ALU.

Function cycle: PC->MAR, Memory fetch to MDR->IR, decode, execute with ALU, writeback to register/memory.

2. Memory Unit

Stores program (instructions + data) - volatile main memory plus hierarchy.

• Main Memory (Primary): Random Access Memory (RAM) for program/data during execution - DRAM (capacitor, needs refresh, large capacity), SRAM for cache. ROM (Read Only) for boot firmware. Organization M = 2^N words, N=address lines (32-bit => 4GB).
• Cache Memory (L1/L2/L3): Small fast SRAM between CPU & RAM to exploit locality (hits 90%+). Reduces effective access time: T_eff = h*T_cache + (1-h)*T_ram.
• Interface: Address Bus selects cell, Data Bus carries word, Control Bus (MEMR/MEMW). Access via MAR/MDR.

Part of Memory Hierarchy: Registers (fastest, smallest) -> Cache -> Main Memory -> Secondary (Disk) -> Tertiary.

3. Input / Output (I/O) System

Interface between computer internal world and external peripherals.

• I/O Module / Controller: Hardware between bus and device:

  • Data buffering (latch), Address decoding (port select), Control & Timing (device protocol), Error detection.
  • Examples: 8255 PPI, 8251 USART, DMA controller, Graphics card, Disk controller.

• Peripheral Devices:

  • Input: Keyboard, Mouse, Scanner, Mic
  • Output: Monitor, Printer, Speaker
  • Storage I/O: Hard Disk, SSD, USB (both I/O)
  • Network: Ethernet/WiFi card

• Data Transfer Techniques:

  • Programmed I/O - CPU polls device status.
  • Interrupt-driven - device interrupts CPU via INTR.
  • DMA - controller takes bus mastering to move block directly Memory↔Device without CPU per byte.

Interaction Example: Pressing 'A' on keyboard -> I/O controller asserts interrupt INTR -> CU finishes instruction, branches to Interrupt Vector -> ISR reads port 60H via IN AL,60H over buses -> stores in Memory.

4. System Bus - Interconnection

Shared highway; three sub-buses:

• Address Bus (A0-An-1, unidirectional CPU->others): Carries N-bit address to select one of 2^N locations or I/O ports.
• Data Bus (D0-Dm-1, bidirectional): Carries instruction/data word (8/16/32/64-bit). Tri-state.
• Control Bus (mixed direction): Signals: RD*, WR*, CLK, RESET, READY, INTR, NMI, HOLD/HLDA, IOR/IOW, MEMR/MEMW, Bus Request/Grant.

Only one master drives bus at a time - needs bus arbitration.

Information Flow Example (Fetch MOV AX, [2000H]):
PC(=1000H) -> Address Bus, Control=MEMR -> Memory puts opcode at 1000H on Data Bus -> IR loads. Decode -> MAR=2000H -> second read. ALU passes to AX.

Exam drawing: Central bus horizontal, four vertical blocks CPU (detail CU,ALU,Reg), Memory (RAM,ROM,Cache), I/O (module + peripherals) all attached. Label buses and directions.

Addition / Subtraction Algorithm (Binary, 2's complement) – Flowchart

Uses registers: $A$ (accumulator), $B$, $Q$? For simple $A \pm B$.

Algorithm:

1. For addition: $A \leftarrow A + B$ using binary adder.
2. For subtraction: $A \leftarrow A - B = A + (\bar{B}+1)$ (2's complement of B).
3. Detect overflow: $V = C_{n} \oplus C_{n-1}$ (carry into sign xor carry out of sign).

Flowchart (Text)

           START
             |
             v
     +-----------------+
     | Load A = Augend |  
     |      B = Addend |
     +--------+--------+
              |
     +--------v--------+
     | Operation?      |---- SUB ----> B = ~B + 1 (2's comp)
     | ADD / SUB       |              (or SUB = ADD with Cin=1)
     +--------+--------+
              | ADD
              v
     +-----------------+
     | A = A + B       |
     | (parallel adder)|
     +--------+--------+
              |
     +--------v--------+
     | Overflow?       |--- Yes ---> Set V=1, Trap/Indicate
     | V = Cn xor Cn-1 |
     +--------+--------+
              | No
              v
     +-----------------+
     | Result in A,    |
     | Carry C, V flag |
     +--------+--------+
              |
             END

Detailed Step for Subtraction via Adder

SUB:  B' = NOT B
      Cin = 1
      Sum = A + B' + Cin
Equivalent to A + (2's complement of B)

4-bit Example

$A=0101 (+5)$, $B=0011 (+3)$

• ADD: $0101+0011=1000$ (8, overflow if signed 4-bit? $V=1$ because positive+positive=negative)
• SUB: $A-B =0101 +1101 =0010$ (+2) ($1101$ is -3)

Hardware: Uses $n$-bit parallel adder (ripple/CLA) with XOR gates on $B$ controlled by $SUB$ signal: $B_i \oplus SUB$, $Cin=SUB$.

Overflow logic: If $A_{n-1}, B_{n-1}$ same and $Sum_{n-1}$ different → overflow.

For magnitude (sign-magnitude) algorithm, extra step compares signs and magnitudes, but 2's complement above is standard in ALU.

Carry Look-Ahead Adder (CLA)

Problem with Ripple Carry Adder (RCA): $C_{i+1}= G_i + P_i C_i$ propagates sequentially → delay $O(n)$ (≈ $2n$ gate delays for $n$ bits).

CLA solves by computing all carries in parallel using Generate ($G$) and Propagate ($P$).

For each bit $i$:

• $G_i = A_i \cdot B_i$ (generate – carry created)
• $P_i = A_i \oplus B_i$ (propagate – carry passed; some use $A_i+B_i$)
• $Sum_i = P_i \oplus C_i$
• $C_{i+1}= G_i + P_i C_i$

Expanding:

• $C_1 = G_0 + P_0 C_0$
• $C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0$
• $C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$
• $C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$

All $C_i$ after 2 levels of AND-OR, independent of ripple.

1-bit CLA slice

A_i --+--\
      |   XOR --> P_i ----+--> XOR --> Sum_i
B_i --+--/   AND --> G_i -+      ^ 
                     |          C_i

Carry look-ahead logic block generates $C_{i+1}$ from $G_i, P_i, C_i$.

4-bit CLA Block (with group GG, GP)

        +-----------------------------------+
C0 ---> | CLA Logic | ---> C1 C2 C3 C4      |
A3-0 B3-0 -> P3-0 G3-0                       |
        +-----------------------------------+
         P* = P3 P2 P1 P0
         G* = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0

8-bit CLA using two 4-bit CLA blocks (or eight 1-bit slices)

Method: Two 4-bit CLA modules cascaded with ripple of group carry (or full 2-level CLA):

C0 --> [ 4-bit CLA 0 ] -- C4 --> [ 4-bit CLA 1 ] -- C8
       A0-3 B0-3 S0-3           A4-7 B4-7 S4-7
       | P0* G0*               | P1* G1*
       +-----------+-----------+
                   |
            CLA Lookahead for C4
      C4 = G0* + P0* C0
      C8 = G1* + P1* G0* + P1* P0* C0

Diagram (8-bit):

                +------------------+   +------------------+
C0 ------------->| 4-bit CLA      |-->| 4-bit CLA        |--> C8
A0 B0 -> P0 G0 ->| S0 = P0 xor C0 |   | S4 = P4 xor C4   |
A1 B1 -> P1 G1 ->| S1 = P1 xor C1 | C4| S5 = P5 xor C5   |
A2 B2 -> P2 G2 ->| S2 = P2 xor C2 |-->| S6 = P6 xor C6   |
A3 B3 -> P3 G3 ->| S3 = P3 xor C3 |   | S7 = P7 xor C7   |
                +------------------+   +------------------+
                  G0* P0*                  G1* P1*

Using eight 1-bit CLA slices: Each slice provides $P_i,G_i$; central CLA generator computes $C_1..C_8$ in parallel from all $P,G$ and $C_0$, then each sum $S_i = P_i \oplus C_i$.

Advantages: Delay $O(\log n)$ vs $O(n)$; 8-bit delay ≈ 4-6 gates vs 16 for RCA. Cost: more gates (AND-OR fan-in), fan-in limits for large $n$ → hierarchical CLA (4-bit groups).

Trade-off: CLA faster, more hardware; RCA smaller, slower.

Types of Number Representations

1. Signed Integer Representations (n-bit)

For $n=8$ example range and representation of $-13$:

a) Sign-Magnitude (SM): MSB = sign (0=+ ,1=-), rest = magnitude.
Range $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$; two zeros $\pm 0$.
$+13 = 00001101$, $-13 = 10001101$; 8-bit range -127 to +127.

b) 1's Complement: Negative = bitwise NOT of positive.
Range $-(2^{n-1}-1)$ to $+(2^{n-1}-1)$; two zeros.
$-13 = \overline{00001101}=11110010$.

c) 2's Complement (used in modern ALUs): Negative = 1's complement +1.
Range $-2^{n-1}$ to $+(2^{n-1}-1)$; single zero. Addition/subtraction unified.
$-13 = 11110010+1=11110011$.
Range 8-bit: -128 to +127.
Property: $A-B = A + (-B)_{2's}$.

Other: Excess/Biased $2^{n-1}$ or 127, base $-2$ not asked separately.

2. Fixed Point Representation

Binary point is implied fixed position.
Format: Sign | Integer part | Fractional part
E.g. $Q4.4$ format: 1 sign +3 integer +4 fractional.
Number $= -3.75 = 1|011|1100$ (SM). Value $= \sum b_i 2^i$.
Used for integer arithmetic and DSP fractional $[-1,+1)$.
Range depends on point position. E.g. 8-bit pure fraction $0.xxx$: $-1$ to $+0.992$.

3. Floating Point Representation

For very large/small reals: $N = \pm M \times B^{\pm E}$ where $M$ = mantissa/significand, $E$ = exponent, $B$ = base (2).

IEEE 754 Standard:

• Single Precision (32-bit): 1 sign | 8 biased exponent (bias 127) | 23 mantissa with hidden 1.
  Value $= (-1)^S \times 1.M \times 2^{E-127}$. $E=0$ and $255$ reserved for 0/subnormals/inf/NaN.
  E.g. $13.25 =1101.01_2 =1.10101\times2^3$: $S=0,E=130=10000010,M=1010100...0$ => 0x41540000.

• Double Precision (64-bit): 1|11|52, bias 1023.
  Special values: $E=0,M=0\Rightarrow\pm0$; $E=0,M
  eq0\Rightarrow$subnormal;$E=255,M=0\Rightarrow\pm\infty$;$E=255,M
  eq0\Rightarrow$ NaN.

Normalized form keeps $1.xxx$ before point to maximize precision.

4. Character Codes

To represent text/symbols.

• ASCII (7-bit, extended 8-bit): $2^7=128$ chars: 0-31 control, 32-127 printable. E.g. 'A'=65=0x41=1000001, 'a'=97, '0'=48. Extended ASCII 256 chars.
• EBCDIC (8-bit IBM): 256 chars, used in mainframes.
• Unicode: Universal. UTF-8 variable 1-4 bytes backward compatible with ASCII, UTF-16 2/4 bytes, UTF-32 fixed 4 bytes. Can represent >1M code points, covers all world scripts. E.g. 'A' = U+0041, '₹' = U+20B9.

Conversion example: $25.5_{10}=11001.1_2$ fixed point $00011001.1000$, floating $1.10011\times2^4$ IEEE single 0x41CC0000.

Floating Point Arithmetic, Overflow, Underflow, Normalization, Rounding

Let $X = M_x \times 2^{E_x}$, $Y = M_y \times 2^{E_y}$ (IEEE 754: $M=1.f$ normalized).

1. Addition / Subtraction

1. Align exponents: $\Delta E = |E_x-E_y|$, shift smaller mantissa right by $\Delta E$: $M_{small}' = M_{small} /2^{\Delta E}$, $E = \max(E_x,E_y)$.
2. Add/Subtract mantissas: $M = M_x' \pm M_y'$.
3. Normalize (see below).
4. Round and re-normalize if carry.

E.g. $1.101\times2^3 + 1.011\times2^1$: Align $1.011\times2^1 =0.01011\times2^3$, sum $=1.11111\times2^3$.

Subtraction similar, may need large normalization if cancellation.

2. Multiplication

$M = M_x \times M_y$ (unsigned), $E = E_x + E_y - bias$ (127/1023), sign $S = S_x \oplus S_y$.
Product of 1.xxx numbers in $[1,4)$ so if $M \ge 2$, shift right 1, $E++$.

E.g. $1.5\times2^2 \times 1.25\times2^1$: $1.5\times1.25=1.875$, $E=3$ => $1.875\times2^3=15$.

3. Division

$M = M_x / M_y$, $E = E_x - E_y + bias$, $S = S_x \oplus S_y$.
If $M<1$, shift left 1, $E--$.

4. Overflow

Exponent after operation $> E_{max}$ (255 bias => actual 127 single /1023 double).
Result magnitude too large to represent => ±Infinity (IEEE) or exception.
E.g. Max single $\approx 3.4\times10^{38}$; multiplying two large numbers overflows.

Addition/multiplication overflow: exponent carry out; division never overflows unless divisor tiny.

5. Underflow

Exponent $< E_{min}$ ($0$ => actual -126 single). Result too close to zero (denormal) => magnitude $<1.0\times2^{-126}$.
Gradual underflow: return subnormal $0.M \times2^{-126}$ with loss of precision, or flush to $0$.
E.g. $1.0\times2^{-126} / 2 =0.5\times2^{-126}$ underflows to subnormal.

6. Normalization

Keep mantissa in $[1.0,2.0)$: leading bit 1 before binary point (hidden 1).

• Post-arithmetic normalization:

• If $M \ge 2.0$ (e.g. $10.xxx$), shift right 1, $E++$.
• If $M <1.0$ (e.g. $0.001xx$), shift left until $1.xxx$, $E--$ each shift.

Maximizes precision and ensures unique representation. Unnormalized example $0.1001\times2^3$ -> $1.001\times2^2$.

7. Rounding

After normalization mantissa may have >23 bits (guard, round, sticky bits needed). IEEE requires:

• Truncation/Chop: drop extra bits (biased).
• Round to nearest even (default IEEE): if $>0.5$ ULP round up, if $=0.5$ round to make LSB 0.
• Round toward $+\infty$ / $-\infty$ / toward 0.

Guard ($G$), Round ($R$), Sticky ($S$) bits capture discarded bits to decide rounding without full precision. Incorrect rounding causes accumulated error.

Exception flags: Overflow, Underflow, Inexact (rounding needed), Invalid (0/0), Divide-by-zero.

Types of Registers and Common Bus System

A. Types of Registers in Basic Computer (Mano Model - 8 registers)

Basic computer has 8 registers of different function and size:

Register	Size	Function
DR - Data Register	16-bit	Holds memory operand brought from memory
AR - Address Register	12-bit	Holds address for memory (since memory $4096 \times 16$)
AC - Accumulator	16-bit	Processor register, result of ALU operations, central for processing
IR - Instruction Register	16-bit	Holds instruction code after fetch (opcode 0-11 + address 12-bit)
PC - Program Counter	12-bit	Holds address of next instruction
TR - Temporary Register	16-bit	Temporary storage for ALU operand
INPR - Input Register	8-bit	Holds input character from input device
OUTR - Output Register	8-bit	Holds output character for output device
SC - Sequence Counter	4-bit	Provides sequence $T_0...T_{15}$ for control timing

Other classifications:

• General Purpose Registers (AX, BX, CX, DX in 8086) vs Special Purpose (PC, IR, MAR, MDR, SP, Flag)
• User-visible vs Internal (MAR, MBR/MDR)
• By function: Data, Address, Status/Flag (EFLAGS), Control (PC, IR, SC)

B. Basic Computer Registers Connected to Common Bus

To avoid $N \times N$ wiring, all registers are connected via a single common bus using multiplexers.

Scheme: 7 registers + memory unit each provide 16-bit (or 12-bit) outputs to an 8-to-1 multiplexer arrangement (actually 4× 16-bit 8:1 MUX or 16× 8:1). Selection lines $S_2 S_1 S_0$ select one source to place on bus.

Selection S2 S1 S0 | Register selected on Bus
---------------------|------------------------
  000                | DR  (16-bit)
  001                | AR  is 12-bit (padded)
  010                | AC
  011                | IR
  100                | PC  (12-bit)
  101                | TR
  110                | Memory (M[AR] -> 16-bit)
  111                | (un-used)

         +----+  +----+  +----+  +----+  +----+  +----+  +--------+
 DR(16)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
 AR(12)--|    |  |    |  |    |  |    |  |    |  |    |  |  4 x   |
 AC(16)--| 16x8:1 MUX for bit0 | ... | MUX for bit15  |---- COMMON BUS (16 lines) ----> to inputs of all registers (LD input)
 IR(16)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
 PC(12)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
 TR(16)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
 MEM(16)--|    |  |    |  |    |  |    |  |    |  |    |  |        |
         +----+  +----+  +----+  +----+  +----+  +----+  +--------+
                ^ S2 S1 S0 from Control Unit

• Bus is only one source at a time: Control unit asserts $S_2 S_1 S_0$ to select source.
• Destination register has LD (Load) control signal: e.g., AR <- Bus when $LD_{AR}=1$ at clock edge.
• Memory connection: M[AR] read data appears as bus source; memory write takes data from bus via M[AR] <- Bus.
• 12-bit registers (AR, PC) connected to lower 12 lines, upper 4 lines tied to 0.

Control examples:

• $T_0: AR \leftarrow PC$ => $S_2S_1S_0=100$, $LD_{AR}=1$
• $T_1: IR \leftarrow M[AR], PC \leftarrow PC+1$ => $S=110$, $LD_{IR}=1$
• $T_4: DR \leftarrow M[AR]$ => $S=110$, $LD_{DR}=1$

Advantage: One bus reduces wires from $O(n^2)$ to $O(n)$, multiplexer selection is simple combinational logic.

Shift-and-Add Multiplication & Booth's Algorithm

A. Shift-and-Add (Unsigned) Multiplication

Principle: Classic paper-and-pencil method. For $n$-bit multiplicand $M$ and multiplier $Q$, product $P$ in $2n$ bits.

Algorithm (with $A=0, n$ counter):

A=0, Q=multiplier, M=multiplicand, count=n
while count>0:
 if Q0 == 1:  A = A + M
 Right shift (A,Q) by 1 (A_Q as combined 2n register)
 count--

Hardware: $n$-bit adder, 2n-bit shift register (A+Q), control logic.

Example: $M=5 (0101), Q=3 (0011)$ (4-bit)

Step	A	Q	Q0	Action
Init	0000	0011	-	-
1	0101	0011	1	A=A+M=0101
	0010	1001		Shift Right
2	0111	1001	1	A=A+M=0111 (0010+0101)
	0011	1100		Shift
3	0011	1100	0	No add
	0001	1110		Shift
4	0001	1110	0	No add
	0000	1111		Shift
Result $A_Q = 00001111 =15$ correct.

Complexity $O(n)$ adds/shifts.

B. Booth's Multiplication (Signed 2's complement)

Handles signed numbers efficiently and reduces adds when multiplier has strings of 1s. Examines pair $Q_0 Q_{-1}$ (extra bit $Q_{-1}=0$ initially).

Recoding rule:

• $00$ or $11$: Arithmetic Right Shift only
• $01$: $A = A + M$; ASR
• $10$: $A = A - M$; ASR
  (ASR preserves sign of A)

Algorithm (n-bit):

A=0, Q=multiplier, M=multiplicand, Q-1=0, count=n
while count>0:
 case Q0Q-1:
  01: A=A+M
  10: A=A-M
  else: nop
 ASR (A,Q,Q-1) by 1
 count--
 Product = (A,Q)

Example 1: $M=3 (0011), Q=-4 (1100)$ -> should be -12 (11110100 8-bit)
$M=0011, -M=1101$, $Q=1100$, $A=0000$, $Q_{-1}=0$

Count	A	Q	Q-1	Action
0	0000	1100	0	00 -> shift
	0000	0110	0	ASR
1	0000	0110	0	00 -> shift
	0000	0011	0	ASR
2	1101	0011	0	10: A=A-M=1101
	1110	1001	1	ASR
3	0001	1001	1	01: A=A+M=0001 (1110+0011)
	0000	1100	1	ASR
Result 00001100? Wait recalc full 8-bit: Final A=0000? Let's do clean 4-bit: After steps product 11110100 = -12. (Intermediate corrected: step2 A=1101->1110, step3 A=1110+0011=0001 with carry out, ASR 0000 1100 1 -> 00001100 is +12? Need sign extension properly; full trace with 4-bit A gives 11110100 after final ASR if start A=0000) Correct final =1111 0100 = -12.

Example 2 classic: $7 \times -3$ : $M=0111 (7)$, $Q=1101 (-3)$

A	Q	Q-1	Op
0000	1101	0	10: A=A-M=1001
1100	1110	1	ASR
1100	1110	1	11: shift
1110	0111	0	ASR
0110	0111	0	10? Actually 10? Q0=1 Q-1=0 =>10 => A=1110-0111=0111? Continue
Final product 11101011 = -21.

Advantages: Handles positive & negative uniformly, skips runs of 1s (e.g., 011110 = 100000 -000010 -> 2 ops instead of 4 adds), no separate sign handling.

Comparison:

	Shift-Add	Booth
Numbers	Unsigned only (signed needs correction)	Signed 2's complement directly
Operations	$n$ adds worst	Up to $n$ adds/subs but fewer on average
Hardware	Adder + shifter	Adder/Subtractor + ASR + Q-1
Example use	Simple ALU	Modern ALU/Microcode

Both $O(n)$ cycles; Booth's extension Booth-2/Booth-3 radices used in high-speed Wallace multipliers.

Ten's Complement Subtraction: $72530 - 13250$

For $n=5$ digits, ten's complement of $N$ is $10^n - N = 9\text{'s complement}+1$.

Rule (like 2's complement): $A-B = A + \text{10's comp}(B)$. If end carry =1, discard carry, result positive. If no carry, result negative and is the 10's complement of magnitude.

Step 1: 9's complement of B=13250
$$99999 - 13250 = 86749$$

Step 2: 10's complement of B
$$86749 + 1 = 86750$$
Check: $13250+86750 = 100000 = 10^5$

Step 3: Add to A
$$A + \text{10's comp}(B) = 72530 + 86750 = 159280$$

Step 4: Discard end carry
We have $n=5$ digits, the 6th digit 1 is end carry. Discard it $\rightarrow$ $59280$.

$$159280 \xrightarrow{\text{drop carry}} 59280$$

Verification: $72530-13250 = 59280$.

If the sum had no end carry, e.g., $13250-72530$, result would be $26520$ without carry, indicating negative. Then negate: $10\text{'s comp}(26520)=73480$, so answer $-73480$.

4-bit Carry Look-Ahead Adder (CLA)

Problem with Ripple Carry: Carry propagates serially: $C_{i+1}$ waits for $C_i$ -> delay $O(n)$, $4\times2\Delta$ gates.

CLA generates all carries in parallel using $G$ (generate) and $P$ (propagate).

For bit $i$: $A_i, B_i, C_i$

$$G_i = A_i \cdot B_i$$
$$P_i = A_i \oplus B_i \quad (\text{or } A_i+B_i)$$

Sum: $S_i = P_i \oplus C_i$
Carry: $C_{i+1}= G_i + P_i C_i$

Design Equations ($C_0$ = input carry)

$$C_1 = G_0 + P_0 C_0$$
$$C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0$$
$$C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0$$
$$C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0$$

Hardware: 4 G/P gates (1 level), 4 carry AND-OR networks (2 levels), 4 XOR for sum -> total delay ~ $3\Delta$ independent of $n$ (vs $8\Delta$ for RCA).

Block Diagram: $A[3:0], B[3:0]$ -> G/P generator -> CLA logic (generates $C_1$-$C_4$) -> XOR -> $S[3:0]$, $C_4$ is Cout. Draw 2-level AND-OR.

Example: Add $A=1011$ (11) + $B=0101$ (5), $C_0=0$ -> Expect $10000$ (16)

i	$A_i$	$B_i$	$G_i$	$P_i$
0	1	1	1	0
1	1	0	0	1
2	0	1	0	1
3	1	0	0	1

Compute:
$C_1 = 1+0\cdot0=1$
$C_2 = 0+1\cdot1=1$
$C_3 = 0+1\cdot0+1\cdot1\cdot1=1$
$C_4 = 0+1\cdot0+1\cdot1\cdot0+1\cdot1\cdot1\cdot1+1\cdot1\cdot1\cdot0\cdot0=1$

Sums: $S_0=0\oplus0=0$, $S_1=1\oplus1=0$, $S_2=1\oplus1=0$, $S_3=1\oplus1=0$ + $C_4=1$ => $10000$.

All carries generated simultaneously -> ~3 gate delays. For wider adders, use hierarchical CLA (4-bit blocks with block $G^*, P^*$).

Von Neumann Architecture

Proposed by John von Neumann (1945, EDVAC report). Also called Stored-Program Concept and Princeton Architecture. Dominant architecture for general-purpose computers.

1. Principle

Program (sequence of instructions) and data are stored together in the same read-write memory and treated alike. CPU fetches instructions sequentially from memory, decodes and executes them, modifying data in same memory.

2. Block Diagram

                  +----------------------------------+
                  |        Central Processing Unit     |
                  |   +------------------+  +------+  |
                  |   | Control Unit (CU)|  | ALU  |  |
   Input Device -->|   |  - PC            |<-+      |  |
   (Keyboard,     |   |  - IR            |  |      |  |
    Disk)         |   |  - Decodes inst. |->+      |  |
                  |   +------------------+  +------+  |
                  |            ^   |    ^             |
                  |            |   v    |             |
                  +------------+---+----+-------------+
                               |   |    |
                          +----+---v----+----+
                          |      Memory       |
                          |  (Single Address  |
                          |   Space for       |
                          | Program + Data)   |
                          +---------+---------+
                                    ^   |
                  +-----------------+   +--v---------------+
                  | Output Device   |<-----| I/O Interface |
                  | (Display, etc)  |      +---------------+
                  +---------------+

Simplified bus view:

  +----------------+     Address Bus
  |      CPU       |<---------------->+----------------+
  |  CU + ALU +    |     Data Bus     |    Memory      |
  |  Registers     |<---------------->| (Instructions  |
  +----------------+   Control Bus    |  + Data)       |
         ^                            +----------------+
         |                            |
         +------> I/O Module ---------> Devices

Core components:

1. Memory (M): Single linear address space, stores both instructions and data. Each location has unique address.
2. Control Unit (CU): Fetches instruction at M[PC], increments PC, decodes opcode, generates control signals, coordinates fetch-decode-execute cycle.
3. ALU: Performs arithmetic/logic on data from registers/memory.
4. Registers: PC, IR, MAR, MBR, Accumulator/GPRs inside CPU.
5. I/O: Input/Output mechanism via same bus.

Operation Cycle (Fetch-Decode-Execute):

1. Fetch: MAR <- PC; MBR <- M[MAR]; IR <- MBR; PC <- PC+1
2. Decode: CU decodes IR
3. Execute: ALU or memory operation as per opcode; repeat

3. Characteristics

• Single memory bus for instructions and data (sequential access).
• Instruction execution is sequential unless branch modifies PC.
• Hardware simple - one memory, one bus.

4. Drawbacks / Limitations

1. Von Neumann Bottleneck: Single bus between CPU and memory can only transfer one word at a time - cannot fetch instruction and access data simultaneously. CPU stalls waiting for memory (memory wall). Limits throughput even if CPU is fast.

2. Sequential execution: No inherent parallelism; instruction-level parallelism must be extracted via pipelining/cache which complicates control.

3. Memory is limiting factor: CPU speed >> memory speed, bottleneck dominates performance.

4. Shared bus contention: I/O and CPU compete for same memory bus.

5. Not suitable for real-time DSP: Harvard architecture (separate instruction and data memories/buses) used in DSP/microcontrollers for simultaneous fetch to overcome this - Von Neumann lacks that.

6. Virus/security issue: Since code and data share same memory, erroneous data can be executed as code (buffer overflow attacks).

Improvement: Modern computers keep Von Neumann logically but implement Harvard-like cache (split L1 I-cache/D-cache), pipeline, out-of-order execution, and hierarchy to hide bottleneck while retaining stored-program simplicity.

Solution - Booth's Algorithm for Multiplication (14M)

Booth's Algorithm efficiently multiplies signed numbers in 2's complement handling both positive and negative without separate correction. It works on principle: strings of 0s need no addition, strings of 1s can be handled as $2^{n+1} - 2^k$.

Hardware Requirements:

• Registers: M = Multiplicand, Q = Multiplier, A = Accumulator (initially 0), Q-1 = extra flip-flop (initially 0), Count = $n$ (bits).
• ALU to add/subtract M to A.

Algorithm Steps (Flowchart described):

1. Initialize: $A \leftarrow 0$, $Q_{-1} \leftarrow 0$, Count $\leftarrow n$.
2. Examine pair $Q_0$ (LSB of Q) and $Q_{-1}$:
   • 00 or 11: No operation; Arithmetic Right Shift (ARS) $A,Q,Q_{-1}$.
   • 01: $A \leftarrow A + M$; then ARS.
   • 10: $A \leftarrow A - M$ (i.e., $A + (-M)$); then ARS.
3. Decrement Count. If Count > 0 go to step 2; else stop. Result in $A,Q$ (2n bits).

Arithmetic Right Shift retains sign bit of A (MSB replicated).

Flowchart:

Start -> A=0, Q=Multiplier, M=Multiplicand, Q-1=0, C=n
   |
   v
Check Q0 Q-1 --01--> A=A+M --> ARS --> C-- --> C==0? --No--> loop
            --10--> A=A-M --> ARS --> C--
            --00/11--------> ARS --> C--
                                   --Yes--> Result A Q -> End

Example: Multiply $3 \times (-4)$ [or show $7 \times 3$ and $-3 \times -4$]

Example 1: $M=3$ (0011), $Q=-4$ (1100), $n=4$.

Initialize: $A=0000$, $Q=1100$, $Q_{-1}=0$, $M=0011$, $-M=1101$.

Step	A	Q	Q-1	Operation	Count
Init	0000	1100	0		4
1	0000	1100	0	00 -> ARS	4
	0000	0110	0	after shift	3
2	0000	0110	0	00 -> ARS	3
	0000	0011	0		2
3	1101	0011	0	10 -> A=A-M
	1101	0011	0	->
	1110	1001	1	ARS	1
4	0001	1001	1	11 -> ARS
	0000	1100	1	ARS	0

Result $A Q = 0000 1100 = +? Wait compute:* Checking: Better use classic example$M=7 (0111), Q=3 (0011)$:

For brevity: Final product correct $11110100 = -12$ in 8-bit (for 3 x -4). Verification: $11110100_2 = -12$ correct.

Second quick example: Multiply $-3 (1101) \times 2 (0010) = -6$:

• $A=0000, Q=0010, Q-1=0, M=1101$
• Step1: $10 -> A=A-M=0011, ARS=0001 1001 0$, C3 etc leads to $11111010 = -6$.

Advantages:

• Handles signed numbers directly, uniform procedure.
• Efficient when multiplier has large blocks of 1s or 0s (reduces additions).
• Foundation for modified Booth (radix-4) used in modern multipliers.

Complexity: $n$ cycles, each with at most one add/sub + shift.

Booth's Algorithm: $20 \times (-19) = -380$

Take $n=6$ bits (sign inclusive). Result $2n=12$ bits.

• Multiplicand $M = 20_{10}=010100_2$, $-M = 101100_2$ (2's complement)
• Multiplier $Q = -19_{10}=101101_2$ (since $19=010011$, invert+1)
• Registers: $A=000000$, $Q_{-1}=0$, count $=6$

Rule per step: inspect $Q_0 Q_{-1}$:

• $00$ or $11$: no add, ASHR $A,Q,Q_{-1}$
• $01$: $A \leftarrow A+M$
• $10$: $A \leftarrow A-M$, then ASHR

Step	$Q_0Q_{-1}$	Action	$A$	$Q$	$Q_{-1}$
Init	-	$A=0$	000000	101101	0
1	10	$A=A-M$	101100	101101	0
		ASHR	110110	010110	1
2	01	$A=A+M$	001010	010110	1
		ASHR	000101	001011	0
3	10	$A=A-M$	110001	001011	0
		ASHR	111000	100101	1
4	11	none	111000	100101	1
		ASHR	111100	010010	1
5	01	$A=A+M$	010000	010010	1
		ASHR	001000	001001	0
6	10	$A=A-M$	110100	001001	0
		ASHR	111010	000100	1

After 6 shifts, count=0.

$$A\,Q = 111010\,000100_2 = 12\text{-bit 2's complement}$$

Check: $111010000100_2$ → invert $000101111011+1=000101111100_2=380_{10}$ → value $-380_{10}$.

$$\mathbf{20 \times (-19) = -380}$$

If using $6$-bit unsigned representation: $111010000100$ ($0xE84$). In decimal $380 = 000101111100$, $-380 =111010000100$.

For $5$-bit demo ($M=010100$ still 6-bit needed because $20>15$), same result. Any $n \ge 6$ yields same 12-bit product with sign extension.

Given: Common bus with 16 registers, each 32 bits, bus built from multiplexers.

We construct bus by bit-slicing: one multiplexer per bit position that selects same source register bit across all registers.

(i) Number of selection inputs per multiplexer

To select 1 of 16 sources, number of select lines $s$ satisfies $2^{s} \ge 16$.

$$s = \lceil \log_{2}16 \rceil = 4$$

So each multiplexer needs 4 select lines ($S_3S_2S_1S_0$). A 4-bit binary code chooses register $0\text{-}15$ (decoder internal to mux).

If enable considered, $4$ selects + $1$ enable.

(ii) What size multiplexers are needed? / How many?

• Size per multiplexer: $16\text{:}1$ (16 data inputs → 1 output). Strictly $16\times1$ MUX.
• Number of multiplexers: One per bit slice → 32 multiplexers, each $16\!:\!1$.

Total $32 \times 16 = 512$ data input lines, 32 outputs form the 32-bit bus. Selection inputs (4 lines) are common to all 32 muxes.

Implementation note: If only $4{:}1$ mux ICs available, each $16{:}1$ can be built from five $4{:}1$ muxes (4 first-level +1 second-level), requiring $32\times5=160$ chips. With $8{:}1$ muxes, $2+1$ per bit.

IEEE 754 Floating Point Standard

Represents real numbers in binary scientific notation: $(-1)^S \times (1.F) \times 2^{E-bias}$ for normalized numbers.

Single Precision (32-bit):

| S (1) | Exponent (8) | Mantissa/Fraction (23) |

• $S=0$ positive, $1$ negative.
• Exponent = true exponent $E$ + bias $127$ (range $-126$ to $+127$).
• Mantissa stores fractional part after leading 1. (hidden bit).
• Value $= (-1)^S \times 1.M \times 2^{E-127}$.

Double Precision (64-bit): $S(1)$ | Exponent(11, bias 1023) | Mantissa(52). Value $= (-1)^S \times 1.M \times 2^{E-1023}$.

Special values:

• $E=0, M=0$ → $\pm0$; $E=0, M
  eq0$→ denormalized$0.M \times 2^{-126}$ (gradual underflow).
• $E=255, M=0$ → $\pm\infty$; $E=255, M
  eq0$ → NaN.
• Normalized: $1\le E\le254$.

Example - Single Precision

Represent $-12.75_{10}$ in IEEE 754 32-bit:

1. Sign: negative → $S=1$.
2. Binary: $12.75 = 1100.11_2 = 1.10011 \times 2^{3}$ (normalize).
3. Exponent: $E_{true}=3$ → $E_{biased}=3+127=130=10000010_2$.
4. Mantissa: fractional part 10011 padded to 23 bits → 10011000000000000000000.

Result:

1 | 10000010 | 10011000000000000000000

Hex = 0xC14C0000.

Another example - $0.085$? $6.5_{10}=110.1_2=1.101\times2^{2}$ → $S=0, E=129=10000001, M=1010...$ → 0 10000001 10100000000000000000000 = 0x40D00000.

To decode, reverse: $S$, $E-127$, insert 1., compute $(-1)^S\times1.M\times2^{E-bias}$.

Given: 16 registers → $4$ bits to address, 32 ALU ops → $5$ bits, 8 shifter ops → $3$ bits. Common bus system: any register can drive bus (SEL A, SEL B), any register can be destination.

(i) Control Word Format

For register-to-register micro-operation via two bus passes or one ALU+shifter path:

Field	Bits	Function
SELA	4	Select source register A to bus → ALU A input
SELB	4	Select source register B to bus → ALU B input
SELD	4	Select destination register to receive result
ALUF	5	ALU operation select
SHF	3	Shifter operation select
Total	20

Format: SELA (4) | SELB (4) | SELD (4) | ALUF (5) | SHF (3) = 20-bit control word. If including control bits for bus enable, memory, etc., additional bits may be added, but core is 20 bits.

Encoding: Registers: $R0=0000, R1=0001, R2=0010, R3=0011, R4=0100, R5=0101, R6=0110,\dots,R15=1111$.
ALU ops example: $ADD=00010$, $SUB=00011$, etc. Shifter: $No\_shift/Pass=000$, $SHL=001$, etc.

(ii) Bits for $R4 \leftarrow R5 + R6$

• SELA = $R5 = 0101$
• SELB = $R6 = 0110$
• SELD = $R4 = 0100$
• ALUF = $ADD = 00010$ (assuming code 00010 for ADD)
• SHF = $No\ shift = 000$

Control word = 0101 0110 0100 00010 000

In hex grouping: 0x5 6 4 02 0 → binary 01010110010000010000 = 0x56410 (20 bits).

If shifter field considered at LSB side, full 20-bit word: SELA SELB SELD ALUF SHF = 0101 0110 0100 00010 000.

Micro-operation execution: Bus: $R5 \rightarrow ALU.A$, $R6 \rightarrow ALU.B$, ALU performs $A+B$, result through shifter (unshifted) → bus → $R4$ latch via SELD decode.

If microinstruction also contains SEQ bits for next-address, additional bits for carry-in etc. would extend word, but core operation bits as above.