Restoring Division Algorithm (Fixed Point Binary Division)

Algorithm

Registers: A (accumulator/partial remainder), Q (holds dividend, then quotient), M (divisor), Count = number of bits.

1. Initialize: A = 0, Q = dividend, M = divisor, Count = n.
2. Repeat n times:
   • Shift the combined register (A, Q) left by 1 bit.
   • A = A − M (add 2's complement of M).
   • If A ≥ 0 (MSB = 0): set Q[0] = 1.
   • Else (A < 0, MSB = 1): set Q[0] = 0 and restore A = A + M.
   • Decrement Count.
3. End: Q = quotient, A = remainder.

STEP 1: Given Data

• Dividend = 448 = 0111000000 (10 bits)
• Divisor = 17 = 10001 (5 bits) → M = 10001
• 5-bit registers → n = 5 iterations
• 2's complement of M = 01111

Important note on register sizing

To hold both A and Q for a 10-bit dividend divided by a 5-bit divisor, and to detect the sign of a subtraction of two 5-bit numbers, the accumulator generally needs one extra (sign) bit. Working strictly with 5-bit registers as required, I use A as a 5-bit register and detect "A ≥ 0" via the carry-out of the addition of the 2's complement (carry = 1 means result ≥ 0, no borrow), which is the standard hardware convention.

Loading: A = 00000, Q = 0111000000? Q is only 5 bits. Since the dividend is 10 bits but registers are 5 bits, the standard approach splits the dividend into A and Q:

• A = high 5 bits = 01110
• Q = low 5 bits = 00000

STEP 2: Solve

M = 10001, 2's complement of M = 01111

Initial: A = 01110, Q = 00000

Iteration 1

• Shift left: A = 11100, Q = 00000
• A + comp(M): 11100 + 01111 = 101011 → A = 01011, carry = 1 ⇒ ≥ 0 ⇒ Q[0] = 1
• A = 01011, Q = 00001

Iteration 2

• Shift left: A = 10110, Q = 00010
• 10110 + 01111 = 100101 → A = 00101, carry = 1 ⇒ ≥ 0 ⇒ Q[0] = 1
• A = 00101, Q = 00011

Iteration 3

• Shift left: A = 01010, Q = 00110
• 01010 + 01111 = 011001 → A = 11001, carry = 0 ⇒ < 0 ⇒ Q[0] = 0, restore
• Restore: 11001 + 10001 = 101010 → A = 01010
• A = 01010, Q = 00110

Iteration 4

• Shift left: A = 10100, Q = 01100
• 10100 + 01111 = 100011 → A = 00011, carry = 1 ⇒ ≥ 0 ⇒ Q[0] = 1
• A = 00011, Q = 01101

Iteration 5 (the final required step)

• Shift left: A,Q = 00011 01101 → A = 00110, Q = 11010
• 00110 + 01111 = 010101 → A = 10101, carry = 0 ⇒ < 0 ⇒ Q[0] = 0, restore
• Restore: 10101 + 10001 = 100110 → A = 00110
• A = 00110, Q = 11010

Result

• Quotient Q = 11010 = 26
• Remainder A = 00110 = 6

Verification

$$17 \times 26 + 6 = 442 + 6 = 448 \checkmark$$

Summary Table

Quotient = 26, Remainder = 6.

Instruction Format of Basic Computer Architecture

Definition

An instruction format specifies the layout of bits within an instruction word. It defines how the total bits of the word are partitioned into fields, typically:

• Mode field (I): indicates the addressing mode (direct or indirect).
• Operation code (opcode): specifies the operation to be performed.
• Address field: specifies the memory address of the operand.

In the basic computer (Mano's model), each instruction occupies one memory word, and the format is determined by the memory word size and the number of addressable locations.

Given Data

• Memory size = 256K words
• Word size = 32 bits (so each instruction is 32 bits)

Step 1: Number of Bits for the Address Field

The address field must be large enough to address every word in memory.

$$256K = 256 \times 1024 = 2^8 \times 2^{10} = 2^{18}$$

$$\text{Address bits} = \log_2(2^{18}) = 18 \text{ bits}$$

So 18 bits are required for the address field.

Step 2: Allocate the Remaining Bits

Total word size = 32 bits. Reserve 1 bit for the addressing mode (I), the rest goes to the opcode.

$$\text{Opcode bits} = 32 - 1 - 18 = 13 \text{ bits}$$

Check:

$$1 + 13 + 18 = 32 \text{ bits} \checkmark$$

Instruction Word Format (32 bits)

  31    30           18 17                        0
 +----+----------------+--------------------------+
 | I  |    Opcode      |         Address          |
 |1bit|    13 bits     |         18 bits          |
 +----+----------------+--------------------------+

Explanation of Each Field

Key Points

• Address field size ($18$ bits) is fixed by the memory size ($256K = 2^{18}$).
• One bit is used as the mode bit to select direct/indirect addressing.
• The remaining $13$ bits form the opcode.

Final answer: Mode = 1 bit, Opcode = 13 bits, Address = 18 bits, totaling 32 bits.