Non-Restoring Division Algorithm and Restoring Division Example

1. Non-Restoring Division Algorithm

In restoring division, after subtracting the divisor, if the partial remainder becomes negative, the divisor is added back (restored). This wastes an operation.

In non-restoring division, we do NOT restore. Instead, we keep the negative remainder and adjust in the next step:

• If A is positive (or zero): shift left, then subtract B.
• If A is negative: shift left, then add B.

The quotient bit is set based on the sign of A after the operation.

Algorithm Steps

Let A = accumulator (initially 0), Q = dividend, B = divisor, SC = n.

1. Initialize A = 0, load Q with dividend, B with divisor, SC = n.
2. If sign of A = 0: Shift left AQ, then A = A - B. If sign of A = 1: Shift left AQ, then A = A + B.
3. If sign of A = 0: set Q[0] = 1. Else set Q[0] = 0.
4. Decrement SC. If SC ≠ 0, go to step 2.
5. At end, if A is negative, restore once: A = A + B.
6. Quotient in Q, Remainder in A.

2. Flowchart

                 START
                   |
        A=0, load Q=Dividend,
        B=Divisor, SC=n
                   |
        +------> Shift left AQ
        |          |
        |    sign of A = 0 ?
        |      /          \
        |    YES           NO
        |     |             |
        |  A = A - B     A = A + B
        |     \           /
        |      sign of A = 0 ?
        |      /          \
        |    YES           NO
        |  Q[0]=1        Q[0]=0
        |      \          /
        |     SC = SC - 1
        |          |
        |      SC = 0 ?
        |      /      \
        +----NO       YES
                       |
                 sign of A = 1 ?
                  /        \
                YES         NO
             A = A + B       |
                  \         /
              Quotient=Q, Remainder=A
                       |
                     STOP

3. Hardware Implementation Diagram

        +-----------+   +-----------+
        |  B Register|   | Complementer/
        |  (Divisor) |-->| Adder      |
        +-----------+   +------+-----+
                               |
              +----------------+
              v
        +-----------+-----------+     shift left
        |   A (acc) |   Q (Qtnt)|  <-------------
        +-----+-----+-----------+
              |
        sign bit (MSB of A)
              |
              v
        +-----------------+     +-------------+
        | Control Logic   |<--->| Sequence    |
        | (Add / Subtract)|     | Counter SC  |
        +-----------------+     +-------------+

Components: A register (n+1 bits, partial remainder), Q register (holds dividend then quotient), B register (divisor), parallel adder/subtractor with complementer, sign flip-flop, sequence counter SC, and control logic that selects add or subtract based on the sign of A.

4. Divide 10 / 3 using Restoring Division

Given data:

• Dividend = 10
• Divisor = 3

Binary representation (4 bits):

• Dividend $Q = 1010$ (10)
• Divisor $B = 0011$ (3)
• $n = 4$
• $A = 00000$ (initially 0, using 5-bit A to hold sign)
• $-B = 11101$ (2's complement of 00011)

The restoring method: shift left AQ, subtract B. If A < 0, set Q[0]=0 and restore (add B back); else set Q[0]=1.

After 4 iterations:

• Quotient $Q = 0011 = 3$
• Remainder $A = 00001 = 1$

Verification: $10 = 3 \times 3 + 1$ ✓

Final Result

$$\boxed{\text{Quotient} = 3, \quad \text{Remainder} = 1}$$

Instruction Format

Definition

An instruction format defines the layout or structure of a binary instruction stored in memory. It specifies how the bits of an instruction are divided into different fields, each carrying specific information needed by the CPU to execute that instruction.

The simplest way to organize a computer is to have a single processor register called the accumulator, and an instruction format with two parts:

• First part (Opcode field): Specifies the operation to be performed (e.g., ADD, SUB, LOAD, STORE).
• Second part (Address field): Specifies the memory address where the operand is located, i.e., tells the control unit where to find the operand in memory.

General Structure of an Instruction Format

+------------------+----------------------+
|   Opcode (bits)  |   Address (bits)     |
+------------------+----------------------+

Example: Basic Computer Instruction Format (16-bit)

In a basic computer, each instruction is 16 bits long, organized as follows:

Bit position:  15      14  13  12      11  10  9  ...  0
               +-------+---+---+-------+---+---+-------+
               |   I   | Opcode (3)    |  Address (12) |
               +-------+---+---+-------+---+---+-------+

How It Works During Fetch and Decode

According to the fetch-decode cycle:

• T0: AR <- PC (Address Register gets the Program Counter value)
• T1: IR <- M[AR], PC <- PC + 1 (Instruction is fetched from memory into Instruction Register)
• T2: Decode IR(12-14), AR <- IR(0-11), I <- IR(15) (Opcode bits 12-14 are decoded; address bits 0-11 are loaded into AR; indirect bit is noted)

Example Instruction

Suppose a 16-bit instruction is:

0  001  000000000101
^   ^        ^
I  Opcode   Address (5)

• I = 0 → Direct addressing
• Opcode = 001 → Could represent an ADD operation
• Address = 5 → Operand is located at memory address 5

This means: "Add the value stored at memory location 5 to the accumulator directly."

Summary

Instruction format is essential because it tells the CPU what to do (opcode) and where to find the data (address). The design of the instruction format directly affects the number of operations supported and the size of addressable memory.

Differences Between Input-Output Processor (IOP) and Direct Memory Access (DMA)

Brief Introduction

DMA (Direct Memory Access) is a data transfer mechanism between memory and I/O devices controlled by an external DMA controller circuit, without CPU involvement during the actual transfer.

IOP (Input-Output Processor) is a more advanced processor with direct memory access capability that can execute its own channel programs stored in main memory, communicating independently with I/O devices.

Major Differences

Summary

DMA is a hardware controller that temporarily takes over the system bus to transfer data directly between memory and I/O without CPU processing. IOP is a dedicated processor that goes further by executing its own channel programs stored in memory, managing I/O operations fully independently after a single initiation command from the CPU. IOP is therefore a superset of DMA functionality.