←
Computer Science and Electronics for Digital Assistant · Chapter 4

Computer Organization and Arithmetic

What to remember

  • A computer has an input unit, a CPU (ALU, control unit, registers), memory and an output unit, joined by buses. Instructions run in a fetch-decode-execute cycle.
  • Memory forms a hierarchy: registers, cache, main memory, secondary storage. Faster means smaller and costlier.
  • Binary arithmetic uses two's complement for negative numbers; know addition rules, overflow, and the IEEE 754 floating-point format.

1. Basic structure and Von Neumann model

In the Von Neumann (stored-program) model, instructions and data are kept in the same memory and the CPU fetches them one by one. The Harvard architecture uses separate memories for instructions and data. The main parts are:

  • Input and output units, such as keyboard, mouse, monitor, printer.
  • CPU (processor): the ALU (Arithmetic and Logic Unit) does arithmetic and logic; the Control Unit (CU) directs all operations; registers are tiny, very fast stores inside the CPU.
  • Memory: primary (RAM, ROM) and secondary.

Important registers: Program Counter (PC) holds the address of the next instruction; Instruction Register (IR) holds the current instruction; Memory Address Register (MAR) holds the address to be accessed; Memory Data (Buffer) Register (MDR/MBR) holds the data moving to or from memory; Accumulator (AC) holds results of the ALU; Status/Flag register holds flags such as carry, zero, sign and overflow.

2. Buses and the instruction cycle

A bus is a set of wires that carries signals.

BusCarriesDirection
Address busMemory or I/O addressOne way, from CPU
Data busDataTwo way
Control busControl signals (read, write, clock)Mostly from CPU

The width of the address bus decides the memory size: an n-bit address bus can address 2ⁿ locations. Example: a 16-bit address bus gives 2¹⁶ = 65,536 = 64 K locations.

Instruction cycle: (1) Fetch the instruction from the address in the PC and increase the PC; (2) Decode it in the control unit; (3) Execute it; (4) store the result if needed. An interrupt is a signal that makes the CPU pause the present program and run a service routine. Clock speed is measured in hertz (MHz, GHz). Pipelining overlaps the stages of several instructions to raise throughput.

3. Instructions and addressing

An instruction has an opcode (the operation) and operands (the data or addresses). The instruction set is the full list of instructions a CPU supports. Types of architecture: CISC has many complex instructions of varying length; RISC has fewer simple, fixed-length instructions, usually one per cycle.

Addressing modes: immediate (the operand is in the instruction), direct (the address is given), indirect (the address of the address is given), register, indexed, and relative. Instruction formats by the number of addresses: zero-address (stack), one-address (uses accumulator), two-address and three-address.

4. Memory hierarchy

LevelSpeedSizeCost per bit
RegistersFastestSmallestHighest
CacheVery fastSmallHigh
Main memory (RAM)FastMediumMedium
Secondary (HDD, SSD)SlowLargeLow
  • RAM is volatile and read-write. SRAM (static) is faster, uses flip-flops and is used for cache; DRAM (dynamic) is cheaper, uses capacitors and needs refreshing; it is used for main memory.
  • ROM is non-volatile. Types: PROM (programmable once), EPROM (erased by UV light), EEPROM (erased electrically), and flash memory.
  • Cache memory holds frequently used data between CPU and RAM. A hit means the data is found in cache; a miss means it is not. Hit ratio = hits ÷ total accesses. Mapping methods: direct, associative and set-associative.
  • Virtual memory uses disk to extend RAM. Locality of reference (programs reuse nearby data) is why cache works.
  • Access time is the time to read or write; cycle time is the minimum time between two accesses.

Units: 1 byte = 8 bits; 1 KB = 1,024 bytes; 1 MB = 1,024 KB; 1 GB = 1,024 MB; 1 TB = 1,024 GB.

5. Input-output organization

I/O can be done by programmed I/O (CPU waits and checks the device), interrupt-driven I/O (the device interrupts when ready) and DMA (Direct Memory Access), where a DMA controller moves blocks between device and memory without the CPU, freeing it for other work. Ports connect devices; examples are USB, HDMI and serial/parallel ports. Interface chips and buffers handle speed differences.

6. Binary arithmetic

Binary addition: 0+0=0, 0+1=1, 1+0=1, 1+1=10 (sum 0, carry 1), 1+1+1=11 (sum 1, carry 1).

Example: 1011 + 0110 = 10001 (11 + 6 = 17).

Binary subtraction: 0−0=0, 1−0=1, 1−1=0, 0−1=1 with a borrow of 1. Example: 1010 − 0011 = 0111 (10 − 3 = 7).

Binary multiplication is shift-and-add: 101 × 11 = 101 + 1010 = 1111 (5 × 3 = 15). Division is repeated subtraction.

Complements: 1's complement is found by flipping every bit. 2's complement = 1's complement + 1. Subtraction by 2's complement: A − B = A + (2's complement of B), and a final carry out is discarded.

Example: 7 − 5 with 4 bits. 5 = 0101; 1's complement 1010; 2's complement 1011. 0111 + 1011 = 1 0010; discard the carry, result 0010 = 2.

Signed number representation (n bits):

MethodRange
Sign-magnitude−(2ⁿ⁻¹−1) to +(2ⁿ⁻¹−1)
1's complement−(2ⁿ⁻¹−1) to +(2ⁿ⁻¹−1)
2's complement−2ⁿ⁻¹ to +(2ⁿ⁻¹−1)

For 8 bits, 2's complement range is −128 to +127. In 2's complement there is only one zero. The most significant bit (MSB) is the sign bit (0 positive, 1 negative).

Overflow: in signed addition, overflow occurs when two numbers of the same sign give a result of the opposite sign. Adding a positive and a negative number never overflows. Example (8 bit): 100 + 50 = 150 exceeds 127, so overflow. For unsigned numbers, a carry out of the MSB shows overflow.

7. Floating-point and hardware adders

A floating-point number has a sign, an exponent and a mantissa (fraction). IEEE 754 single precision uses 32 bits: 1 sign bit, 8 exponent bits (bias 127) and 23 fraction bits. Double precision uses 64 bits: 1 sign, 11 exponent (bias 1023), 52 fraction. The value is (−1)^sign × 1.fraction × 2^(exponent − bias). Example: 1.0 has exponent 127 = 01111111 and fraction 0. Normalisation keeps the leading digit as 1.

Half adder adds two bits: Sum = A XOR B, Carry = A AND B. Full adder adds three bits (A, B, carry-in): Sum = A ⊕ B ⊕ Cin, Carry = AB + Cin(A ⊕ B). A full adder can be built from two half adders and an OR gate. A ripple-carry adder chains full adders; a carry-look-ahead adder is faster.

Worked examples

  • 1. Memory size: A 12-bit address bus addresses 2¹² = 4,096 locations = 4 K. If each location holds 1 byte, the memory is 4 KB.
  • 2. Hit ratio: 90 hits in 100 accesses give a hit ratio of 0.9. If cache time is 10 ns and main memory time is 100 ns, average access time = 0.9 × 10 + 0.1 × 100 = 19 ns (simple model).
  • 3. Subtraction by 2's complement (8 bit): 25 − 10. 10 = 00001010; 1's complement 11110101; 2's complement 11110110. 25 = 00011001. Sum = 1 00001111; discard the carry, result 00001111 = 15.
  • 4. Negative number: −5 in 8-bit 2's complement: 5 = 00000101; flip to 11111010; add 1 gives 11111011.
  • 5. Instruction time: A 2 GHz clock has a period of 0.5 ns. An instruction that needs 4 clock cycles takes 2 ns.
  • 6. Capacity: A memory of 64 K words with 16 bits per word stores 64 × 1,024 × 16 bits = 1,048,576 bits = 128 KB.

Exam traps

  • Fetch happens first; the PC points to the next, not the current, instruction.
  • SRAM is faster and costlier; DRAM needs refreshing.
  • 1 KB is 1,024 bytes in computer memory units.
  • 2's complement has one zero; sign-magnitude and 1's complement have two.
  • A carry out in 2's complement subtraction is discarded, not an error.
  • Address bus is one way; data bus is two way.
  • RISC has fewer, simpler instructions; CISC has many complex ones.
  • Cache is between CPU and RAM; virtual memory uses disk.

One-liners

  • 1. The ALU performs arithmetic and logic operations.
  • 2. The PC holds the address of the next instruction.
  • 3. The accumulator stores ALU results.
  • 4. An n-bit address bus can address 2ⁿ locations.
  • 5. SRAM is used for cache; DRAM for main memory.
  • 6. EEPROM is erased electrically.
  • 7. DMA moves data without CPU involvement.
  • 8. 2's complement = 1's complement + 1.
  • 9. 8-bit 2's complement range is −128 to +127.
  • 10. IEEE 754 single precision uses 32 bits.
  • 11. Half adder: Sum = A XOR B.
  • 12. 1 byte = 8 bits.

Practice questions

  1. In the Von Neumann model, instructions and data are stored

    1. in separate memories
    2. only in registers
    3. only on the hard disk
    4. in the same memory
    Answer

    D. in the same memory

    The stored-program concept uses one memory for both.

  2. Which unit of the CPU performs arithmetic and logical operations?

    1. MAR
    2. ALU
    3. Cache
    4. Control unit
    Answer

    B. ALU

    The Arithmetic and Logic Unit does the calculations.

  3. The register that holds the address of the next instruction to be fetched is the

    1. Program Counter
    2. Instruction Register
    3. Accumulator
    4. MDR
    Answer

    A. Program Counter

    The PC points to the next instruction.

  4. The register that holds the result of ALU operations is commonly called the

    1. Stack pointer
    2. MAR
    3. Accumulator
    4. Program Counter
    Answer

    C. Accumulator

    The accumulator keeps intermediate and final results.

  5. The correct order of the basic instruction cycle is

    1. fetch, execute, decode
    2. decode, fetch, execute
    3. execute, fetch, decode
    4. fetch, decode, execute
    Answer

    D. fetch, decode, execute

    The CPU fetches, decodes and then executes.

  6. Which bus is one-directional (from the CPU to memory)?

    1. Address bus
    2. Data bus
    3. Both address and data bus
    4. None of the buses
    Answer

    A. Address bus

    The address bus carries addresses from the CPU; the data bus is two-way.

  7. Which memory is the fastest in the hierarchy?

    1. Cache
    2. Registers
    3. RAM
    4. Hard disk
    Answer

    B. Registers

    Registers are the fastest and smallest.

  8. Which type of RAM is used for cache memory?

    1. DRAM
    2. EPROM
    3. SRAM
    4. Flash ROM only
    Answer

    C. SRAM

    SRAM is faster and costlier; DRAM is used for main memory.

  9. Which memory needs periodic refreshing?

    1. EEPROM
    2. DRAM
    3. SRAM
    4. ROM
    Answer

    B. DRAM

    DRAM stores bits in capacitors that leak charge.

  10. Which ROM can be erased electrically?

    1. Mask ROM
    2. PROM
    3. EPROM
    4. EEPROM
    Answer

    D. EEPROM

    EEPROM is electrically erasable; EPROM needs UV light.

  11. Direct Memory Access (DMA) is used to

    1. convert binary to decimal
    2. transfer data between I/O device and memory without the CPU
    3. increase the clock speed
    4. refresh DRAM
    Answer

    B. transfer data between I/O device and memory without the CPU

    A DMA controller moves blocks of data without CPU involvement.

  12. How many bits make one byte?

    1. 4
    2. 16
    3. 8
    4. 2
    Answer

    C. 8

    1 byte = 8 bits.

  13. An address bus of 16 lines can address how many memory locations?

    1. 65,536
    2. 16,384
    3. 1,048,576
    4. 32,768
    Answer

    A. 65,536

    2^16 = 65,536.

  14. A 12-bit address bus can address how many locations?

    1. 1,024
    2. 8,192
    3. 2,048
    4. 4,096
    Answer

    D. 4,096

    2^12 = 4,096 = 4 K.

  15. The 2's complement of the 4-bit number 0101 is

    1. 0101
    2. 1111
    3. 1011
    4. 1010
    Answer

    C. 1011

    Flip bits to 1010 and add 1 to get 1011.

  16. The 8-bit 2's complement representation of −5 is

    1. 11111010
    2. 10000101
    3. 00000101
    4. 11111011
    Answer

    D. 11111011

    5 = 00000101; flip to 11111010; add 1 gives 11111011.

  17. The range of an 8-bit 2's complement number is

    1. −256 to +255
    2. −128 to +127
    3. −127 to +127
    4. 0 to 255
    Answer

    B. −128 to +127

    Range is −2^7 to 2^7 − 1.

  18. Binary addition 1011 + 0110 gives

    1. 10001
    2. 10101
    3. 01111
    4. 10011
    Answer

    A. 10001

    11 + 6 = 17 = 10001.

  19. Binary multiplication 101 × 11 gives

    1. 1101
    2. 10001
    3. 1111
    4. 1011
    Answer

    C. 1111

    5 × 3 = 15 = 1111.

  20. In 4-bit 2's complement, 7 − 5 is done by adding 0111 and 1011. The result after discarding the carry is

    1. 1100
    2. 0010
    3. 0110
    4. 1010
    Answer

    B. 0010

    0111 + 1011 = 1 0010; discarding the carry gives 0010 = 2.

  21. Overflow in signed addition occurs when

    1. the carry out is always 1
    2. the result is zero
    3. a positive and a negative number are added
    4. two numbers of the same sign give a result of the opposite sign
    Answer

    D. two numbers of the same sign give a result of the opposite sign

    This is the standard overflow condition for signed numbers.

  22. In 8-bit 2's complement arithmetic, adding 100 and 50 produces

    1. an overflow
    2. an underflow of 50
    3. a correct result 150
    4. a result of zero
    Answer

    A. an overflow

    150 exceeds the maximum +127, so overflow occurs.

  23. In IEEE 754 single precision, the number of bits used for the exponent is

    1. 23
    2. 52
    3. 11
    4. 8
    Answer

    D. 8

    Single precision: 1 sign, 8 exponent, 23 fraction bits.

  24. In IEEE 754 double precision, the exponent bias is

    1. 1024
    2. 255
    3. 1023
    4. 127
    Answer

    C. 1023

    Double precision uses 11 exponent bits and bias 1023.

  25. Sum output of a half adder is given by

    1. A XOR B
    2. A OR B
    3. A AND B
    4. A NAND B
    Answer

    A. A XOR B

    Sum = A XOR B; Carry = A AND B.

  26. A full adder has how many inputs?

    1. 3
    2. 2
    3. 4
    4. 1
    Answer

    A. 3

    A, B and carry-in.

  27. The architecture that uses a small set of simple, fixed-length instructions is

    1. CISC
    2. RISC
    3. VLIW only
    4. Harvard only
    Answer

    B. RISC

    RISC = Reduced Instruction Set Computer.

  28. In an instruction, the part that specifies the operation to be done is the

    1. address bus
    2. flag
    3. operand
    4. opcode
    Answer

    D. opcode

    Opcode gives the operation; operand gives the data.

  29. The addressing mode in which the operand is given in the instruction itself is

    1. direct
    2. immediate
    3. indirect
    4. register indirect
    Answer

    B. immediate

    Immediate mode contains the data value.

  30. A cache gives 90 hits in 100 accesses. Cache time is 10 ns and main memory time 100 ns. The average access time by the simple model is

    1. 55 ns
    2. 28 ns
    3. 19 ns
    4. 10 ns
    Answer

    C. 19 ns

    0.9 × 10 + 0.1 × 100 = 19 ns.

  31. A 2 GHz clock has a clock period of

    1. 5 ns
    2. 0.5 ns
    3. 2 ns
    4. 0.2 ns
    Answer

    B. 0.5 ns

    Period = 1 / (2 × 10^9) s = 0.5 ns.

  32. A memory of 64 K words with 16 bits per word has a capacity of

    1. 64 KB
    2. 256 KB
    3. 1 MB
    4. 128 KB
    Answer

    D. 128 KB

    64 K × 2 bytes = 128 KB.

  33. Subtracting 10 from 25 in 8 bits by 2's complement gives

    1. 00001111
    2. 11110101
    3. 00010101
    4. 00001010
    Answer

    A. 00001111

    25 + (−10) = 15 after discarding the carry.

  34. Which is true of the sign bit in 2's complement numbers?

    1. 1 in the MSB means positive
    2. There is no sign bit
    3. 1 in the MSB means negative
    4. The LSB is the sign bit
    Answer

    C. 1 in the MSB means negative

    MSB 1 shows a negative number.

  35. Consider these statements. 1. The data bus is bidirectional. 2. The address bus is bidirectional. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    A. 1 only

    The address bus is one-way, so only 1 is correct.

  36. Consider these statements about memory. 1. SRAM is faster than DRAM. 2. DRAM needs refreshing. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both are correct.

  37. Consider these statements about number representation. 1. 2's complement has only one representation of zero. 2. Sign-magnitude has two representations of zero. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both statements are true.

  38. Consider these statements about the instruction cycle. 1. The PC is increased after the fetch. 2. The decode step is done by the control unit. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both are correct.

  39. Consider these statements about I/O. 1. In DMA the CPU transfers each byte itself. 2. Interrupt-driven I/O avoids the CPU waiting for the device. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    B. 2 only

    In DMA the controller moves the data; only 2 is correct.

  40. Match the memory with its feature. P. Cache Q. EPROM R. DRAM 1. UV erasable 2. Needs refresh 3. Between CPU and RAM

    1. P-3, Q-2, R-1
    2. P-2, Q-1, R-3
    3. P-1, Q-3, R-2
    4. P-3, Q-1, R-2
    Answer

    D. P-3, Q-1, R-2

    Cache sits between CPU and RAM, EPROM is UV erasable, DRAM is refreshed.

  41. Match the register with its role. P. PC Q. MAR R. IR 1. Holds the address to be accessed 2. Holds the current instruction 3. Holds the next instruction address

    1. P-3, Q-1, R-2
    2. P-1, Q-3, R-2
    3. P-3, Q-2, R-1
    4. P-2, Q-1, R-3
    Answer

    A. P-3, Q-1, R-2

    PC holds the next address, MAR the access address, IR the current instruction.

  42. Match the format with its size. P. Single precision Q. Double precision R. Byte 1. 8 bits 2. 32 bits 3. 64 bits

    1. P-3, Q-2, R-1
    2. P-2, Q-3, R-1
    3. P-2, Q-1, R-3
    4. P-1, Q-2, R-3
    Answer

    B. P-2, Q-3, R-1

    Single = 32 bits, double = 64 bits, byte = 8 bits.

  43. Consider these statements about cache memory. 1. It is placed between the CPU and main memory. 2. It works well because of locality of reference. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both statements are correct.

  44. Consider these statements about adders. 1. A half adder adds two bits. 2. A full adder can be built from two half adders and an OR gate. Which is/are correct?

    1. 1 only
    2. 2 only
    3. Both 1 and 2
    4. Neither 1 nor 2
    Answer

    C. Both 1 and 2

    Both are correct.

  45. The 1's complement of the binary number 10110 is

    1. 10111
    2. 01010
    3. 01110
    4. 01001
    Answer

    D. 01001

    Flip every bit of 10110 to get 01001.

Page 1 of 1
‹
›