Unit IV: Computer Arithmetic - Computer Architecture - BCA Notes (Pokhara University)

Breaking

Friday, April 17, 2020

Unit IV: Computer Arithmetic - Computer Architecture

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

Data Representation:

The data representation may be decimal, binary, octal, qunery, hexadecimal, etc. The data representation should have:

Provision for Decimal Position:

Fix Point Representation: The decimal position is either at the beginning or at the end of a number. For example: 3.2 = 0.32*10

Floating Point Representation: Here, the second register is used to determine the position of decimal.

Provision For Sign Representation:

Signed Magnitude Representation:

This method uses the far left-hand bit which is often referred to as the sign bit. The general rule is that a positive number starts with 0 and a negative number starts with a 1.

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

One’s Complement Representation:

It is the opposite of something. Because the computer does not prefer to subtract, this method finds the complement of a positive number and then the addition can take place.

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

Example:
Find the one’s complement of +100
1. Convert +100 to binary.
2. Swap all the bits.
3. Check the answer by adding 127 to the result.

Example:
$+100 = 01100100_{2}$
$01100100_{2} = 10011011_{2}$ (bit interchange)
$10011011_{2} = -27_{10}$
$127_{10} + -27_{10} = 100_{10}$

Two’s Complement Representation:

The only difference between the two processes is that the leftmost bit is $-128_{10}$ rather than $-127_{10}$. The process for two’s complement is exactly the same as one’s complement, however, we required to add 1 to the results.

Example:
Find the two’s complement of $+15_{10}$ 
1. Convert $+15_{10}$ to binary.
2. Swap all the bits.
3. Add 1 to the result.

Example:
$+15 = 00001111_{2}$ 
$00001111_{2} = 11110000_{2}$ (Interchange)
$11110000_{2} + 1_{2} = 11110001_{2}$ 
$-128 + 64 + 32 + 16 + 1 = -15_{10}$

Integer Arithmetic:

Negation:

In sign-magnitude (1’s Complement) representation, the rule for forming the negation of an integer is simple, just invert the sign bit. In 2’s Complement notation, the negation of an integer can be formed with the following rules:
a. Take the Boolean complement of each bit of the integer (including the sign bit). That is, set each 1 to 0 and each 0 to 1.
b. Treating the result as an unsigned binary integer, add 1.

Among these two representation 2’s Complement representation is the most widely used method.

Addition/Subtraction:

Algorithm:

Step 1: Convert all the given numbers in binary form.
Step 2: If any number is negative then find its 2’s Complement.
Step 3: Perform addition, if carry occurs then discard the carry.
Step 4: If the sign bit of the result is 1, then the result is negative. To find its magnitude re-complement the number.

Overflow:

‘N’ bit operation produces more than N bits. This condition is called an overflow condition.

Consider:

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

The central element is a binary adder in which two numbers are presented for addition. The addition produces a sum and overflow condition. Two numbers are presented form two registers A and B. and finally, the result is stored in the accumulator. The overflow flag indicates, the overflow of data.

In the above-shown diagram, if the number is negative then it is passed to adder after 2’s Complement.

Unsigned Binary Multiplication Algorithm:

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

Perform Unsigned Multiplication of $(13)_{10} * (11)_{10}$ 
Solution:
$(13)_{10} = (1101)_{2}$ 
$(11)_{10} = (1011)_{2}$ 
C
A
Q
M
Count
Comment
0
0000
1101
1011
4
Initialize
0
1011
1101
1011
4
A ß A+M
0
0101
1110
1011
3
Right Shift C, A, Q
0
0010
1111
1011
2
Right Shift C, A, Q
0
1101
1111
1011
2
A ß A+M
0
0110
1111
1011
1
Right Shift C, A, Q
1
0001
1111
1011
1
A ß A+M
0
1000
1111
1011
0
Right Shift C, A, Q

Perform Unsigned Multiplication Of $(8)_{10} * (3)_{10}$ 
Solution:
$(8)_{10} = (1000)_{2}$ 
$(3)_{10} = (0011)_{2}$ 
C
A
Q
M
Count
Comment
0
0000
1000
0011
4
Initialize
0
0000
0100
0011
3
Right Shift C, A, Q
0
0000
0010
0011
2
Right Shift C, A, Q
0
0000
0001
0011
1
Right Shift C, A, Q
0
0011
0001
0011
1
A ß A+M
0
0001
1000
0011
0
Right Shift C, A, Q

Signed Binary Multiplication (Booth’s) Algorithms:

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

Perform Multiplication of $(7)_{10} * (-3)_{10}$ 
Solution:
$(7)_{10} = (0111)_{2}$ 
$(-3)_{10} = (1101)_{2}$ 
A
Q
Q-1
M
Count
Comment
0000
0111
0
1101
4
Initialize
0011
0111
0
1101
4
A ß A-M
0001
1011
1
1101
3
Right Shift A, Q, Q-1
0000
1101
1
1101
2
Right Shift A, Q, Q-1
0000
0110
1
1101
1
Right Shift A, Q, Q-1
1101
0110
1
1101
1
A ß A+M
1110
1011
0
1101
0
Right Shift A, Q, Q-1

Perform Signed Multiplication of $(6)_{10} * (-4)_{10}$ 
Solution:
$(6)_{10} = (0110)_{2}$ 
$(-4)_{10} = (1100)_{2}$ 
A
Q
Q-1
M
Count
Comment
0000
0110
0
1100
4
Initialize
0000
0011
0
1100
3
Right Shift A, Q, Q-1
0100
0011
0
1100
3
A ß A-M
0010
0001
1
1100
2
Right Shift A, Q, Q-1
0001
0000
1
1100
1
Right Shift A, Q, Q-1
1101
0000
1
1100
1
A ß A+M
1110
1000
0
1100
0
Right Shift A, Q, Q-1

Unsigned Binary Division Algorithm:

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

Perform Unsigned Division of $(7)_{10} / (3)_{10}$ 
Solution:
$(7)_{10} = (0111)_{2}$ 
$(3)_{10} = (0011)_{2}$ 
A
Q
M
Count
Comment
0000
0111
0011
4
Initialize
0000
1110
0011
4
Left Shift A, Q
1101
1110
0011
4
A ß A-M
0000
1110
0011
3
Q0 ß 0, A ß A+M
0001
1100
0011
3
Left Shift A, Q
1110
1100
0011
3
A ß A-M
0001
1100
0011
2
Q0 ß 0, A ß A+M
0011
1000
0011
2
Left Shift A, Q
0000
1000
0011
2
A ß A-M
0000
1001
0011
1
Q0 ß 1
0001
0010
0011
1
Left Shift A, Q
1110
0010
0011
1
A ß A-M
0001
0010
0011
0
Q0 ß 0, A ß A+M

Perform Unsigned Division of $(8)_{10} / (4)_{10}$ 
Solution:
$(8)_{10} = (1000)_{2}$ 
$(4)_{10} = (0100)_{2}$ 
A
Q
M
Count
Comment
0000
1000
0100
4
Initialize
0001
0000
0100
4
Left Shift A, Q
1101
0000
0100
4
A ß A-M
0001
0000
0100
3
Q0 ß 0, A ß A+M
0010
0000
0100
3
Left Shift A, Q
1110
0000
0100
3
A ß A-M
0010
0000
0100
2
Q0 ß 0, A ß A+M
0100
0000
0100
2
Left Shift A, Q
0000
0000
0100
2
A ß A-M
0000
0001
0100
1
Q0 ß 1
0000
0010
0100
1
Left Shift A, Q
1100
0010
0100
1
A ß A-M
0000
0010
0100
0
Q0 ß 0, A ß A+M

Representation of Fractions:

Fractional numbers are numbers between 0 and 1. They are called real numbers in computing terms. Real numbers contain both an integer and fractional part. Example: 23.714 OR 01101.1001. Computers use two main methods to represent real numbers:

Fixed Point Representation:

This method assumes the decimal point is in a fixed position. Relies on using a fixed number of bits for both the integer and fractional parts i.e. 5 and 3. Example: 10011101 = 10011.101
Integer
Fractional
16
8
4
2
1
0.5
0.25
0.125
1
0
0
1
1
1
0
1

Therefore,
16 + 2 + 1 = 19 (Integer)
0.5 + 0.125 = 0.625 (Fraction)
So 10011.101 = 19.625

Problems Are:         
We fix the numbers that we can represent i.e. we are limited to the amount of numbers that we can actually represent.

Floating Point Representation:

This is the preferred method because we can represent large numbers. This uses exponential notation which highlights two specific parts of a decimal number:
Mantissa: Fractional part.
Exponent: Is the power by 10 in which the mantissa is multiplied.

The aim of floating-point representation is to show how many numbers before or after the decimal point. The general representation of large floating-point representation is, $±S*B^{±E}$ 

Where,
S is significant
B is base
E is exponent

A computer will represent a binary number into THREE parts:
Sign Bit
Mantissa
Exponent

Example:
$-241.65 = -0.24165 * 10_{3}$ 
$0.0028 = 0.28 * 10_{-2}$ 
$110.11= 0.11011 * 2_{3}$ 

Floating-Point Arithmetic:

The overflow and underflow condition may occur insignificant and exponent.

Addition and Subtraction:

Algorithm:

1. Check for zero. If anyone operand is zero then the result will be another non-zero operand.
2. Align the significant. The decimal position can change so that the exponent value of both operands will be equal.
3. Add or subtract the significant.
4. Normalize the result.

The floating-point numbers and their arithmetic calculation can be illustrated as:

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

BCD Arithmetic Unit:

Binary coded decimal (BCD) is a system of writing numerals that assigns a four-digit binary code to each digit 0 through 9 in a decimal (base-10) numeral. The four-bit BCD code for any particular single base-10 digit is its representation in binary notation, as follows:
0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
9 = 1001

Numbers larger than 9, having two or more digits in the decimal system, are expressed digit by digit. For example, the BCD rendition of the base-10 number 1895 is 0001 1000 1001 0101. The binary equivalents of 1, 8, 9, and 5, always in a four-digit format, go from left to right.

The BCD representation of a number is not the same, in general, as its simple binary representation. In binary form, for example, the decimal quantity 1895 appears as 11101100111

Other bit patterns are sometimes used in BCD format to represent special characters relevant to a particular system, such as sign (positive or negative), error condition, or overflow condition.

The BCD system offers relative ease of conversion between machine-readable and human-readable numerals. As compared to the simple binary system, however, BCD increases the circuit complexity. The BCD system is not as widely used today as it was a few decades ago, although some systems still employ BCD in financial applications.

BCD Adder:

BCD stands for binary coded decimal. Suppose, we have two 4-bit numbers A and B. The value of A and B can vary from 0(0000 in binary) to 9(1001 in binary) because we are considering decimal numbers.

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

The output will vary from 0 to 18 if we are not considering the carry from the previous sum. But if we are considering the carry, then the maximum value of output will be 19 (i.e. 9+9+1 = 19).

When we are simply adding A and B, then we get the binary sum. Here, to get the output in BCD form, we will use BCD Adder.

Example 1:
Input:
A = 0111  B = 1000
Output:
Y = 1 0101
Explanation:
We are adding A (=7) and B (=8).
The value of a binary sum will be 1111(=15).
But, the BCD sum will be 1 0101, where 1 is 0001 in binary and 5 is 0101 in binary.

Example 2:
Input:
A = 0101 B = 1001
Output:
Y = 1 0100
Explanation:
We are adding A(=5) and B(=9).
The value of a binary sum will be 1110(=14).
But, the BCD sum will be 1 0100, where 1 is 0001 in binary and 4 is 0100 in binary.

Note – If the sum of two number is less than or equal to 9, then the value of BCD sum and the binary sum will be same otherwise they will differ by 6(0110 in binary).

BCD adder is a circuit that adds two BCD digits in parallel and produces a sum digit also in BCD. A decimal parallel adder that adds n decimal digits need n BCD adder stages with the output to carry from one stage connected to the input carry of the next higher order stage.
Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

Pipelining:

The term Pipelining refers to a technique of decomposing a sequential process into sub-operations, with each sub-operation being executed in a dedicated segment that operates concurrently with all other segments.

The most important characteristic of a pipeline technique is that several computations can be in progress in distinct segments at the same time. The overlapping of computation is made possible by associating a register with each segment in the pipeline. The registers provide isolation between each segment so that each can operate on distinct data simultaneously.

The structure of a pipeline organization can be represented simply by including an input register for each segment followed by a combinational circuit.

Let us consider an example of combined multiplication and addition operation to get a better understanding of the pipeline organization.

The combined multiplication and addition operation is done with a stream of numbers such as:
$A_{i}* B_{i} + C_{i}$ for i = 1, 2, 3, ......., 7

The operation to be performed on the numbers is decomposed into sub-operations with each sub-operation to be implemented in a segment within a pipeline.

The sub-operations performed in each segment of the pipeline is defined as:
$R1 ← A_{i}, R2 ← B_{i}-------Input A_{i}, and B_{i}$ 
$R3 ← R1 * R2, R4 ← C_{i}------Multiply, and Input C_{i}$ 
$R5 ← R3 + R4----------Add C_{i} to Product$ 

The following block diagram represents the combined as well as the sub-operations performed in each segment of the pipeline.

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining

Registers R1, R2, R3, and R4 hold the data and the combinational circuits operate in a particular segment.

The output generated by the combinational circuit in a given segment is applied as an input register of the next segment. For instance, from the block diagram, we can see that the register R3 is used as one of the input registers for the combinational adder circuit.

Arithmetic Pipelining:

Arithmetic Pipelines are mostly used in high-speed computers. They are used to implement floating-point operations, multiplication of fixed-point numbers, and similar computations encountered in scientific problems.

To understand the concepts of arithmetic pipeline in a more convenient way, let us consider an example of a pipeline unit for floating-point addition and subtraction.

The inputs to the floating-point adder pipeline are two normalized floating-point binary numbers defined as:
$X = A * 2^{a} = 0.9504 * 10^{3}$ 
$Y = B * 2^{b} = 0.8200 * 10^{2}$ 

Where A and B are two fractions that represent the mantissa and a and b are the exponents.

The combined operation of floating-point addition and subtraction is divided into four segments. Each segment contains the corresponding suboperation to be performed in the given pipeline. The suboperations that are shown in the four segments are:

1. Compare Exponents By Subtraction:

The exponents are compared by subtracting them to determine their difference. The larger exponent is chosen as the exponent of the result.
The difference of the exponents, i.e., 3 - 2 = 1 determines how many times the mantissa associated with the smaller exponent must be shifted to the right.

2. Align The Mantissas:

The mantissa associated with the smaller exponent is shifted according to the difference of exponents determined in segment one.
$X = 0.9504 * 10^{3}$ 
$Y = 0.08200 * 10^{3}$ 

3. Add Mantissas:

The two mantissa are added in segment three.
$Z = X + Y = 1.0324 * 10^{3}$ 

4. Normalize The Result:

After normalization, the result is written as:
$Z = 0.1324 * 10^{4}$ 

The following block diagram represents the suboperations performed in each segment of the pipeline.

Computer Arithmetic, Integer Representation, Integer Arithmetic, Unsigned Binary Addition and Subtraction, Unsigned Binary Multiplication Algorithm, Booth’s Algorithm, Unsigned Binary Division Algorithm, Representation of Fractions, Floating Point Representation, BCD Arithmetic Unit, BCD Adder, Pipelining, Arithmetic Pipelining
Note: Registers Are Placed After Each Sub-operation To Store The Intermediate Results.

No comments:

Post a Comment

If you have any doubt, then don't hesitate to drop comments.