UNIT I

Basic Structure of Computers: Basic organization of computers, historical perspective, bus

structures.
Data representation: Data types, complements, fixed point representation, floating point
representation, other binary codes, and error detection codes.

Computer Arithmetic: Addition, subtraction, multiplication and division algorithms.

Definition of Computer Organization: It describes the hardware components, their inter connection
and their working to make up a computer system.

BASIC STRUCTURE OF COMPUTERS:

COMPUTER TYPES: A digital computer or simply a computer is a fast electronic calculating machine
that accepts digitized information as input, processed according to the stored instructions, produces
result as the output. The list of instructions is called a computer program and the internal storage is
called the computer memory. Computers can be classified into different times based on their size,
cost and computational power.

Following are various types of computers.

1. Personal computers(desktops)

2. Notebook computers

3. Workstations

4. Mainframes(Enterprise systems)

5. Super computers

The most common type of computer is the personal computer. This is commonly found in homes,
schools and offices. This type of computers are also called as desktop computers. These are having a
keyboard, mouse as input device. Monitor, printer, audio as output units. It also contains storage
and processing units. The desktops use storage medium like CD ROMS, DVDs, hard disks, diskettes.

Portable notepad computers are a compact version of personal computer with all these components
are packed into a single unit. It has size of thin briefcase.

Workstations have high resolution input/output capability. These computers have more
computational power than the PCs. Workstations are used in engineering applications, especially for
interactive design work.

Mainframes or Enterprise systems are used for business data processing in medium or large scale
organizations. Mainframes require much more storage capacity servers and require more computing
power than the workstations. These mainframe severs are accessed by the education, business,
personal user communities.
Super computers are used for large scale numerical calculations. These are used in applications such
as weather forecasting, aircraft design and simulation, scientific calculations. The super computers
have multiple functional units and multiple processors.

GENERATION OF COMPUTERS

Development of technologies used to fabricate the processors, memories and I/O units of the
computers has been divided into various generations as given below:

 First generation

 Second generation

 Third generation

 Fourth generation

 Beyond the fourth generation 3

First generation: 1946 to 1955:

Computers of this generation used Vacuum Tubes. The computes were built using stored program
concept. Ex: ENIAC, EDSAC, IBM 701. Computers of this age typically used about ten thousand
vacuum tubes. They were bulky in size had slow operating speed, short life time and limited
programming facilities.

Second generation: 1955 to 1965:

Computers of this generation used the germanium transistors as the active switching electronic
device. Ex: IBM 7000, B5000, IBM 1401. Comparatively smaller in size About ten times faster
operating speed as compared to first generation vacuum tube based computers. Consumed less
power, had fairly good reliability. Availability of large memory was an added advantage.

Third generation: 1965 to 1975:

The computers of this generation used the Integrated Circuits as the active electronic components.
Ex: IBM system 360, PDP minicomputer etc. They were still smaller in size. They had powerful CPUs
with the capacity of executing 1 million instructions per second (MIPS). Used to consume very less
power consumption.

Fourth generation: 1976 to 1990:

The computers of this generation used the LSI chips like microprocessor as their active electronic
element. HCL horizen III, and WIPRO’S Uniplus+ HCL’s Busybee PC etc. They used high speed
microprocessor as CPU. They were more user friendly and highly reliable systems. They had large
storage capacity disk memories.

Beyond Fourth Generation: 1990 onwards: Specialized and dedicated VLSI chips are used to control
specific functions of these computers. Modern Desktop PC’s, Laptops or Notebook Computers.
Functional Unit:
A computer in its simplest form comprises five functional units namely input unit, output unit
memory unit, arithmetic & logic unit and control unit. Figure 2 depicts the functional units of
a computer system.

Figure 2: Basic functional units of a computer

Let us discuss about each of them in brief:

1. Input Unit: Computer accepts encoded information through input unit.

The standard input device is a keyboard. Whenever a key is pressed,
keyboard controller sends the code to CPU/Memory.

Examples include Mouse, Joystick, Tracker ball, Light pen, Digitizer, Scanner etc.

2. Memory Unit: Memory unit stores the program instructions

(Code), dataand results of computations etc. Memory unit is
classified as:

 Primary /Main Memory

 Secondary /Auxiliary Memory

Primary memory is a semiconductor memory that provides access at high
speed. Run time program instructions and operands are stored in the main
memory. Main memory is classified again as ROM and RAM. ROM holds
system programs and firmware routines such as BIOS, POST, I/O Drivers that
are essential to manage the hardware of a computer. RAM is termed as
Read/Write memory or user memory that holds run time program instruction
and data. While primary storage is essential, it is volatile in nature and
expensive. Additional requirement of memory could be suppliedas auxiliary
memory at cheaper cost. Secondary memories are non volatile in nature.

3. Arithmetic and logic unit: ALU consist of necessary logic circuits like adder,
comparator etc., to perform operations of addition, multiplication, comparison
of two numbers etc.

4. Output Unit: Computer after computation returns the computed results,

error messages, etc. via output unit. The standard output device is a video
monitor, LCD/TFT monitor. Other output devices are printers, plotters etc.

5. Control Unit: Control unit co-ordinates activities of all units by issuing control
signals. Control signals issued by control unit govern the data transfers and
then appropriate operations take place. Control unit interprets or decides the
operation/action to be performed.

BASIC OPERATIONAL CONCEPTS:

The operations of a computer can be summarized as follows:

1.A set of instructions called a program reside in the main memory of computer.

2. The CPU fetches those instructions sequentially one-by-one from the main
memory, decodes them and performs the specified operation on associated
data operands in ALU.

3. Processed data and results will be displayed on an output unit.

4. All activities pertaining to processing and data movement inside the

computer machine are governed by control unit.

The internal operation of the computer can be as depicted in the figure below:
 Instructions and data are stored in the memory. To perform a given task, the instructions and
data are brought from the memory to the processor. Consider the following instruction:

ADD LOCA, R0

This instruction adds the operand at the memory location LOCA to the operand in a register
of a processor R0, and places the sum into register R0.

The above ADD instruction combines a memory access operation with an ALU operation.

The above operation can be done with the following two-instruction sequence.

LOAD LOCA,R1

ADD R1,R0

Fig 1.2 shows how the memory and processor can be connected.

In addition to the ALU and the control circuit, the processor contains number of registers
used for several different purposes.
The fig shows how memory & the processor can be connected. In addition to the ALU & the
control circuitry, the processor contains a number of registers used for several different
purposes.

The instruction register (IR):- Holds the instructions that is currently being executed. Its
output is available for the control circuits which generates the timing signals that control the
various processing elements in one execution of instruction.

The program counter PC:- This is another specialized register that keeps track of execution of
a program. It contains the memory address of the next instruction to be fetched and executed.

Besides IR and PC, there are n-general purpose registers R0 through Rn-1.

The other two registers which facilitate communication with memory are: -

1. MAR – (Memory Address Register):- It holds the address of the location to be accessed.

2. MDR – (Memory Data Register):- It contains the data to be written into or read out of
the address location.
Operating steps are:

1. Programs reside in the memory & usually get these through the I/P unit.

2. Execution of the program starts when the PC is set to point at the first instruction of
the program.

3. Contents of PC are transferred to MAR and a Read Control Signal is sent to the memory.

4. After the time required to access the memory elapses, the address word is read out of
the memory and loaded into the MDR.

5. Now contents of MDR are transferred to the IR & now the instruction is ready to
be decoded and executed.

6. If the instruction involves an operation by the ALU, it is necessary to obtain the

required operands.

7. An operand in the memory is fetched by sending its address to MAR & Initiating a
read cycle.

8. When the operand has been read from the memory to the MDR, it is transferred from
MDR to the ALU.

9. After one or two such repeated cycles, the ALU can perform the desired operation.

10. If the result of this operation is to be stored in the memory, the result is sent to MDR.

11. Address of location where the result is stored is sent to MAR & a write cycle is initiated.

12. The contents of PC are incremented so that PC points to the next instruction that is to
be executed.

Figure : Interaction between the memory and the ALU

BUS STRUCTURES:
To form an operational system, the functional units of the computer are connected by using bus. A
bus is contains a group of lines that serves as a connecting path for several devices.

There are different types of buses:

• Address bus

• Data bus

• Control bus

1. Address Bus:
1. Address bus carry the memory address while reading from writing into memory.
2. Address bus carry I/O post address or device address from I/O port.
3. In uni-directional address bus only the CPU could send address and other units could
not address the microprocessor.
4. Now a days computers are having bi-directional address bus.
2. Data Bus:
1. Data bus carry the data.
2. Data bus is a bidirectional bus.
3. Data bus fetch the instructions from memory.
4. Data bus used to store the result of an instruction into memory.
5. Data bus carry commands to an I/O device controller or port.
6. Data bus carry data from a device controller or port.
7. Data bus issue data to a device controller or port.

3. Control Bus:
Different types of control signals are used in a bus:
1. Memory Read: This signal, is issued by the CPU or DMA controller when performing a read
operation with the memory.
2. Memory Write: This signal is issued by the CPU or DMA controller when performing a write
operation with the memory.
3. I/O Read: This signal is issued by the CPU when it is reading from an input port.
4. I/O Write: This signal is issued by the CPU when writing into an output port.
5. Ready: The ready is an input signal to the CPU generated in order to synchronize the show
memory or I/O ports with the fast CPU.

A data bus carries the data words between the devices. The Address bus and control bus carries
address and control information.
The simplest way to interconnect functional units is to use a single bus, as shown in the following fig:

Figure : Single bus structure

All units are connected to one bus. In single bus structure only two units can actively use the
bus at a given time. The advantage of the single bus structure is low cost and the flexibility
for attaching the peripheral devices.
The system that contains multiple buses allows the two or more transfers to be carried out at
the same time. It leads to better performance but at an increased cost.
The devices connected to the bus vary widely in the speed of their operation. The keyboards,
Printers are relatively slow where as the disks are considerably faster. Memory and
processor units are fastest parts of computer that operate at electronic speeds.
A common approach is used to eliminate the timing differences between various devices and
facilitate the smooth communication is using the buffer registers with the devices. This
approach prevents the high speed processor from being locked to a slow I/O device during a
sequence of data transfers.
Data
Representation

Data Types:

 Registers contain either data or control information

 Control information is a bit or group of bits used to specify the sequence
of command signals needed for data manipulation
 Data are numbers and other binary-coded information that are operated on
 Possible data types in registers:
o Numbers used in computations
o Letters of the alphabet used in data processing
o Other discrete symbols used for specific purposes
 All types of data, except binary numbers, are represented in binary-coded form

 A number system of base, or radix, r is a system that uses distinct symbols for r
digits
 Numbers are represented by a string of digit symbols
 The string of digits 724.5 represents the

quantity 7 x 102 + 2 x 101 + 4 x 100 + 5

x 10-1

 The string of digits 101101 in the binary number system represents the

quantity 1 x 25 + 0 x 24 + 1 x 23 + 1 x 22 + 0 x 21 + 1 x 20 = 45

 (101101)2 = (45)10
 We will also use the octal (radix 8) and hexidecimal (radix 16) number

systems (736.4)8 = 7 x 82 + 3 x 81 + 6 x 80 + 4 x 8-1 = (478.5)10

(F3)16 = F x 161 + 3 x 160 = (243)10

 Conversion from decimal to radix r system is carried out by separating the

number into its integer and fraction parts and converting each part
separately
 Divide the integer successively by r and accumulate the remainders
 Multiply the fraction successively by r until the fraction becomes zero
 Each octal digit corresponds to three binary digits
 Each hexadecimal digit corresponds to four binary digits
 Rather than specifying numbers in binary form, refer to them in octal
or hexadecimal and reduce the number of digits by 1/3 or ¼,
respectively
 A binary code is a group of n bits that assume up to 2n distinct combinations
 A four bit code is necessary to represent the ten decimal digits – 6 are unused
 The most popular decimal code is called binary-coded decimal (BCD)
 BCD is different from converting a decimal number to binary
 For example 99, when converted to binary, is 1100011
 99 when represented in BCD is 1001 1001

 The standard alphanumeric binary code is ASCII

 This uses seven bits to code 128 characters
 Binary codes are required since registers can hold binary information only.
Complements
 Complements are used in digital computers for simplifying subtraction and
logical manipulation
 Two types of complements for each base r system: r’s complement and (r – 1)’s
complement
 Given a number N in base r having n digits, the (r – 1)’s complement of N
is defined as (rn – 1) – N

 For decimal, the 9’s complement of N is (10n – 1) – N

 The 9’s complement of 546700 is 999999 – 546700 = 453299
 The 9’s complement of 453299 is 999999 – 453299 = 546700
 For binary, the 1’s complement of N is (2n – 1) – N
 The 1’s complement of 1011001 is 1111111 – 1011001 = 0100110
 The 1’s complement is the true complement of the number – just toggle all bits

 The r’s complement of an n-digit number N in base r is defined as rn – N

 This is the same as adding 1 to the (r – 1)’s complement
 The 10’s complement of 2389 is 7610 + 1 = 7611
 The 2’s complement of 101100 is 010011 + 1 = 010100
 Subtraction of unsigned n-digit numbers: M – N
o Add M to the r’s complement of N – this results in
M + (rn – N) = M – N + rn
o If M  N, the sum will produce an end carry rn which is discarded
o If M < N, the sum does not produce an end carry and is equal to
rn – (N – M), which is the r’s complement of (N – M). To obtain the
answer in a familiar form, take the r’s complement of the sum and place a
negative sign in front.

Example: 72532 – 13250 = 59282. The 10’s complement of 13250 is 86750.

M = 72352
10’s comp. of N = +86750
Sum = 159282
Discard end carry = -100000
Answer = 59282

Example for M < N: 13250 – 72532 = -59282

M = 13250
10’s comp. of N = +27468
Sum = 40718
No end carry
Answer = -59282 (10’s comp. of 40718)
 Example for X = 1010100 and Y = 1000011

X = 1010100
2’s comp. of Y = +0111101
Sum = 10010001
Discard end carry = -10000000
Answer X – Y = 0010001

Y = 1000011
2’s comp. of X = +0101100
Sum = 1101111

No end carry
Answer = -0010001 (2’s comp. of 1101111)

Fixed-Point Representation:
 Positive integers and zero can be represented by unsigned numbers
 Negative numbers must be represented by signed numbers since + and – signs
are not available, only 1’s and 0’s are
 Signed numbers have msb as 0 for positive and 1 for negative – msb is the sign bit
 Two ways to designate binary point position in a register
o Fixed point position
o Floating-point representation
 Fixed point position usually uses one of the two following positions
o A binary point in the extreme left of the register to make it a fraction
o A binary point in the extreme right of the register to make it an integer
o In both cases, a binary point is not actually present
 The floating-point representations uses a second register to designate the
position of the binary point in the first register

 When an integer is positive, the msb, or sign bit, is 0 and the remaining
bits represent the magnitude
 When an integer is negative, the msb, or sign bit, is 1, but the rest of the
number can be represented in one of three ways
o Signed-magnitude representation
o Signed-1’s complement representation
o Signed-2’s complement representation

 Consider an 8-bit register and the number +14

o The only way to represent it is 00001110
 Consider an 8-bit register and the number –14
o Signed magnitude: 1 0001110
o Signed 1’s complement: 1 1110001
o Signed 2’s complement: 1 1110010
 Typically use signed 2’s complement

 Addition of two signed-magnitude numbers follow the normal rules

 o If same signs, add the two magnitudes and use the common sign
o Differing signs, subtract the smaller from the larger and use the sign of
the larger magnitude
o Must compare the signs and magnitudes and then either add or subtract
 Addition of two signed 2’s complement numbers does not require a comparison
or subtraction – only addition and complementation
o Add the two numbers, including their sign bits
o Discard any carry out of the sign bit position
o All negative numbers must be in the 2’s complement form
o If the sum obtained is negative, then it is in 2’s complement form

+6 00000110 -6 11111010
+13 00001101 +13 00001101
+19 00010011 +7 00000111

+6 00000110 -6 11111010
-13 11110011 -13 11110011
-7 11111001 -19 11101101

 Subtraction of two signed 2’s complement numbers is as follows

o Take the 2’s complement form of the subtrahend (including sign bit)
o Add it to the minuend (including the sign bit)
o A carry out of the sign bit position is discarded

 An overflow occurs when two numbers of n digits each are added and the sum
occupies n + 1 digits
 Overflows are problems since the width of a register is finite
 Therefore, a flag is set if this occurs and can be checked by the user
 Detection of an overflow depends on if the numbers are signed or unsigned
 For unsigned numbers, an overflow is detected from the end carry out of the msb
 For addition of signed numbers, an overflow cannot occur if one is positive
and one is negative – both have to have the same sign
 An overflow can be detected if the carry into the sign bit position and the
carry out of the sign bit position are not equal

+70 0 1000110 -70 1 0111010

+80 0 1010000 -80 1 0110000
+150 1 0010110 -150 0 1101010

 The representation of decimal numbers in registers is a function of the

binary code used to represent a decimal digit
 A 4-bit decimal code requires four flip-flops for each decimal digit
 This takes much more space than the equivalent binary representation and
the circuits required to perform decimal arithmetic are more complex
 Representation of signed decimal numbers in BCD is similar to the
representation of signed numbers in binary
 Either signed magnitude or signed complement systems
 The sign of a number is represented with four bits
 o 0000 for +
o 1001 for –
 To obtain the 10’s complement of a BCD number, first take the 9’s
complement and then add one to the least significant digit

 Example: (+375) + (-240) = +135

0 375 (0000 0011 0111 1010)BCD

+9 760 (1001 0111 0110 0000)BCD
0 135 (0000 0001 0011 0101)BCD

Floating-Point Representation
 The floating-point representation of a number has two parts
 The first part represents a signed, fixed-point number – the mantissa
 The second part designates the position of the binary point – the exponent
 The mantissa may be a fraction or an integer
 Example: the decimal number +6132.789 is
o Fraction: +0.6123789
o Exponent: +04
o Equivalent to +0.6132789 x 10+4
 A floating-point number is always interpreted to represent m x re
 Example: the binary number +1001.11 (with 8-bit fraction and 6-bit exponent)
o Fraction: 01001110
o Exponent: 000100
o Equivalent to +(.1001110)2 x 2+4
 A floating-point number is said to be normalized if the most significant digit
of the mantissa is nonzero
 The decimal number 350 is normalized, 00350 is not
 The 8-bit number 00011010 is not normalized
 Normalize it by fraction = 11010000 and exponent = -3
 Normalized numbers provide the maximum possible precision for the
floating- point number

Section 3.5 – Other Binary Codes

 Digital systems can process data in discrete form only
 Continuous, or analog, information is converted into digital form by means of an
analog-to-digital converter
 The reflected binary or Gray code, is sometimes used for the converted
digital data
 The Gray code changes by only one bit as it sequences from one number to
the next
 Gray code counters are sometimes used to provide the timing sequences
that control the operations in a digital system
  Binary codes for decimal digits require a minimum of four bits
 Other codes besides BCD exist to represent decimal digits

 The 2421 code and the excess-3 code are both self-complementing
 The 9’s complement of each digit is obtained by complementing each bit in thecode
 The 2421 code is a weighted code
 The bits are multiplied by indicated weights and the sum gives the decimal digit
 The excess-3 code is obtained from the corresponding BCD code added to 3

Error Detection Codes

 Transmitted binary information is subject to noise that could change bits 1 to 0and
vice versa
 An error detection code is a binary code that detects digital errors
during transmission
 The detected errors cannot be corrected, but can prompt the data to
be retransmitted
 The most common error detection code used is the parity bit
 A parity bit is an extra bit included with a binary message to make the total
number of 1’s either odd or even
 The P(odd) bit is chosen to make the sum of 1’s in all four bits odd
 The even-parity scheme has the disadvantage of having a bit combination of all0’s
 Procedure during transmission:
o At the sending end, the message is applied to a parity generator
o The message, including the parity bit, is transmitted
o At the receiving end, all the incoming bits are applied to a parity checker
o Any odd number of errors are detected

 Parity generators and checkers are constructed with XOR gates (odd function)
 An odd function generates 1 iff an odd number if input variables are 1

Addition and Subtraction

 There are three ways of representing negative fixed-point binary numbers:
1. signed-magnitude
2. Signed-l's complement
3. Signed-2's complement
 Addition and Subtraction with Signed-Magnitude Data
 The algorithms for addition and subtraction stated as follows (the words inside
parentheses should be used for the subtraction algorithm):
 Addition (subtraction) algorithm.
1. when the signs of A and B are identical (different), add the two magnitudes and attach
the sign of A to the result.
2. When the signs of A and B are different (identical), compare the magnitudes and
subtract the smaller number from the larger. Choose the sign of the result to be the same as
A if A
> B or the complement of the sign of A if A < B. If the two magnitudes areequal,
subtract B from A and make the sign of the result positive.
Table 1: Addition and Subtraction of Signed Magnitude Numbers

Hardware Implementation for Addition and Subtraction with Signed-Magnitude Data

 To implement the two arithmetic operations with hardware, it is first necessary that the
two numbers be stored in registers.
 Let A and B be two registers that hold the magnitudes of the numbers, and As, and Bs be
two flip-flops that hold the corresponding signs.
 Here parallel-adder is needed to perform the microoperation A + B. (Consists of Full
adder).
 The complementer for generating the 2’s Complement while performing subtraction
operation. (Consists of X-OR gate).
 Where M is Mode of operation. When M = 0, the output of B is transferred to the adder,
the input carry is 0, and the adder is equal to the sum A + B.
 When M =1, the l's complement of B is applied to the adder, the input carry is 1, and
output is = A + + 1. This is equal to A plus the 2's complement of B, which is

equivalent to the A – B.
 Figure 1: Hardware for signed-magnitude addition and subtraction
Hardware Algorithm for Signed-magnitude addition and subtraction
 The magnitudes are added with a microoperation EAA + B. where EA is a register that
combines E and A.
 The value of E is transferred into the Add-overflow flip-flop AVF, if E is 1.
 The magnitudes are subtracted by adding A to the 2's complement of B.
 No overflow can occur if the numbers are subtracted so AVF is cleared to 0.
 1 in E indicates that A≥ B and the number in A is the correct result. If this number i.s zero, the
sign A, must be made positive to avoid a negative zero.
 0 in E indicates that A < B. For this case it is necessary to take the 2's complement of the value in
A. This operation can be done with one mlcrooperation A + 1.
 Figure 2: Flowchart for add and subtract operations
Addition and Subtraction with Signed-2's Complement Data:
 The addition of two numbers in signed-2's complement form consists of adding the numbers with
the sign bits treated the same as the other bits of the number. A carry-out of the sign-bit positionis
discarded.
 The subtraction consists of first taking the 2's complement of the subtrahend and then adding it to
the minuend.
 The register configuration for the hardware implementation is shown in Figure 3.
 Figure 3: Hardware for signed2's complement addition and subtraction
 The algorithm for adding and subtracting two binary numbers in signed2's complement
representation is shown in the flowchart of Figure 4.

Figure 4: Algorithm for adding and subtracting numbers in signed 2's complement
representation
 The sum is obtained by adding the contents of AC and BR (including their sign bits). The overflow
bit V is set to 1 if the exclusive-OR of the last two carries is 1, and it is cleared to 0 otherwise.
 The subtraction operation is accomplished by adding the content of AC to the 2's complement of
BR. Taking the 2's complement of BR has the effect of changing a positive number to negative, and
vice versa. An overflow must be checked during this operation because the two numbers added
could have the same sign.
 The programmer must realize that if an overflow occurs, there will be an erroneous result in the
AC register.
Multiplication Algorithms
 Multiplication of two fixed-point binary numbers in signed-magnitude representation is done
with process of successive shift and adds operations. This process is best illustrated with a
numerical example as follows:
Hardware Implementation for Signed-Magnitude Data Multiplication

 The hardware for multiplication consists of the equipment shown in Figure 5.

Figure 5: Hardware for multiply operation

 Initially, the multiplicand is in register B and the multiplier in Q.

 Initially A is set to 0 as number of bits in the multiplicand.
 The sequence counter SC is initially set to a number equal to the number of bits in the multiplier.
 The sum of A and B forms a partial product which is transferred to the EA register. Both partial
product and multiplier are shifted to the right. This shift will be denoted by the statement shr
EAQ to designate the right shift depicted in Figure 5.
 The least significant bit of A is shifted into the most significant position of Q, the bit from E
is shifted into the most significant position of A, and 0 is shifted into E.

 After the shift, one bit of the partial product is shifted into Q, pushing the multiplier bits one
position to the right. In this manner, the rightmost flip-flop in register Q, designated by Q n, will
hold the bit of the multiplier, which must be inspected next.
 The counter is decremented by 1 after forming each partial product. When the content of the
counter reaches zero, the product is formed and the process stops.

Hardware Algorithm for Signed-Magnitude Data Multiplication

 The following figure 6 is a flowchart of the hardware multiply algorithm.

Figure 6: Flowchart multiply operation on sign magnitude representation numbers

 Initially, the multiplicand is in B and the multiplier in Q. Their corresponding signs are in Bs and
Qs, respectively.
 The signs are compared, and both signs of A and Q are set to correspond to the sign of the
product since a double-length product will be stored in registers A and Q.
 Registers A and E are cleared and the sequence counter SC is set to a number equal to the number
of bits of the multiplier.
 After the initialization, the low-order bit of the multiplier in Q, is tested. If it is a 1, the multiplicand
in B is added to the present partial product in A. If it is a 0, nothing is done.
 Register EAQ is then shifted once to the right to form the new partial product. The sequence
counter is decremented by 1 and its new value checked. If it is not equal to zero, the process is
repeated and a new partial product is formed. The process stops when SC = 0.
 Note that the partial product formed in A is shifted into Q one bit at a time and eventually replaces
the multiplier. The final product is available in both A and Q, with A holding the most significant
bits and Q holding the least significant bits.
 The following table describes multiplication of binary numbers 10111(+23) and 10011(+19) which
are represented using Sign Magnitude Representation.
 Table 2: Numerical Example for Binary Multiplier

Now Result is available in Registers A and Q. i.e. 0110110101 => 437 and sign bit of A is 0. So
result is
+437.
 The following table 3 describes multiplication of binary numbers 10011(+19) and 00110(+6)
which are represented using Sign Magnitude Representation.
 Here Multiplicand is positive value, so Bs = 0. Here Multiplier is positive value, so Qs = 0.
 Now As = BsQs , i.e As = 0  0 => 0.

Table 3: Numerical Example for Binary Multiplier

Multiplicand B=10011 E A Q SC

Initially 0 00000 00110 5

Qn = 0. So shr EAQ 0 00000 00011 4

00000
Qn = 1. So add B to A 10011
10011
Now shr EAQ 0 01001 10001 3

01001
Qn = 1. So add B to A 10011
11100
Now shr EAQ 0 01110 01000 2

Qn = 0. So shr EAQ 0 00111 00100 1

Qn = 0. So shr EAQ 0 00011 10010 0

Now Result is available in Registers A and Q. i.e. 0001110010 => 114 and sign bit of A is 0. So
result is
+114.

 The following table 4 describes multiplication of binary numbers 10010(-18) and 00110(+5)
 which are represented using Sign Magnitude Representation.
 Here Multiplicand is negative value, so Bs = 1. Here Multiplier is positive value, so Qs = 0.

 Now As = BsQs ,i.e As = 1  0 => 1.

Table 4: Numerical Example for Binary

Multiplier

Multiplicand B=10010 E A Q SC

Initially 0 00000 00101 5

00000
Qn = 1. So add B to A 10010
10010
Now shr EAQ 0 01001 00010 4

Qn = 0. So shr EAQ 0 00100 10001 3

00100
Qn = 1. So add B to A 10010
10110

Now shr EAQ 0 01011 01000 2

Qn = 0. So shr EAQ 0 00101 10100 1

Qn = 0. So shr EAQ 0 00010 11010 0

Now Result is available in Registers A and Q. i.e. 0001011010 => 90 and sign bit
of A is 1. So result is -90.
Booth Multiplication Algorithm (for signed-2’s complement numbers)
 Booth algorithm gives a procedure for multiplying binary integers in signed-2's complement
representation.
 As in all multiplication schemes, Booth algorithm requires examination of the multiplier bits and
shifting of the partial product. Prior to the shifting, the multiplicand may be added to the partial
product, subtracted from the partial product, or left unchanged according to the following rules:
1. The multiplicand is subtracted from the partial product upon encountering the first least
significant 1 in a string of 1's in the multiplier.
2. The multiplicand is added to the partial product upon encountering the first 0 (provided that
there was a previous 1) in a string of 0's in the multiplier.
3. The partial product does not change when the multiplier bit is identical to the previous
multiplier bit.

 The hardware implementation of Booth algorithm requires the register configuration shown in
 Figure 7.

 Qn designates the least significant bit of the multiplier in register QR. An extra flip-flop Qn+1is
appended to QR to facilitate a double bit inspection of the multiplier.

Figure 7: Hardware for Booth algorithm

 The flowchart for Booth algorithm is shown in Figure 8.

 AC and the appended bit Qn+1 are initially cleared to 0 and the sequence counter SC is set to a
number n equal to the number of bits in the multiplier.

 The two bits of the multiplier in Qn and Qn+1 are inspected.

 If the two bits are equal to 10, it means that the first 1 in a string of 1's has been encountered. This
requires a subtraction of the multiplicand from the partial product in AC.
 If the two bits are equal to 01, it means that the first 0 in a string of 0's has been encountered. This
requires the addition of the multiplicand to the partial product in AC.
 When the two bits are equal, the partial product does not change. An overflow cannot occur because
the addition and subtraction of the multiplicand follow each other.
 The next step is to shift right the partial product and the multiplier (including bit Q n+1). This is an
arithmetic shift right (ashr) operation which shifts AC and QR to the right and leaves the sign bit
in AC unchanged.
 The sequence counter is decremented and the computational loop is repeated n times.
Figure 8: Booth algorithm for multiplication of signed 2’s complements numbers.

 A numerical example of Booth algorithm is shown in Table 5. It shows the step-by-step

multiplication of (-9) x (-13) = + 117.
 Here the multiplier in QR is negative and that the multiplicand in BR is also negative. The 10-bit product appears
in AC and QR and is positive.
 Table 5: Example of Multiplication with Booth Algorithm

Now Result is available in Registers AR and QR. i.e. 0001110101 =>+117.

Division Algorithms

The Division of two fixed-point binary numbers in the signed-magnitude representation is done by the cycle of
successive compare, shift, and subtract operations.
The binary division is easier than the decimal division because the quotient digit is either 0 or 1. Also, there is no
need to estimate how many times the dividend or partial remainders adjust to the divisor.
 Hardware Implementation :

The hardware implementation in the division operation is identical to that required for
multiplication and consists of the following components –
 Here, Registers B is used to store divisor, and the double-length dividend is stored in registers A and Q
 The information for the relative magnitude is given in E.
 A sequence Counter register (SC) is used to store the number of bits in the dividend.

Flowchart of Division

 Initially, the dividend is in A & Q and the divisor is in B.

 The sign of the result is transferred into Q, to be part of the quotient. Then a constant is set into the SC to specify
the number of bits in the quotient.
 Since an operand must be saved with its sign, one bit of the word will be inhabited by the sign, and the magnitude
will be composed of n -1 bits.
 The condition of divide-overflow is checked by subtracting the divisor in B from the half of the bits of the dividend
stored in A. If A ≥ B, DVF is set and the operation is terminated before time. If A < B, no overflow condition occurs
and so the value of the dividend is reinstated by adding B to A.
 The division of the magnitudes starts with the dividend in AQ to left in the high-order bit shifted into E.
 (Note – If shifted a bit into E is equal to 1, and we know that EA > B as EA comprises a 1 followed by n -1 bits
whereas B comprises only n -1 bits). In this case, B must be subtracted from EA, and 1 should insert into Q,
for the quotient bit.
 If the shift-left operation (shl) inserts a 0 into E, the divisor is subtracted by adding its 2’s complement value
and the carry is moved into E. If E = 1, it means that A ≥ B; thus, Q, is set to 1. If E = 0, it means that A < B,
and the original number is reimposed by adding B into A.
 Now, this process is repeated with register A containing the partial remainder.
Example of a binary division using digital hardware:
Divisor B = 10001, Dividend A = 0111000000