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

## 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. #### 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. Example:
Find the one’s complement of +100
1. Convert +100 to binary.
2. Swap all the bits.

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.

#### 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 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:

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:

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:

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:

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.

#### 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:

### 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 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.

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.

## 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.

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}\$

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.

Note: Registers Are Placed After Each Sub-operation To Store The Intermediate Results.