Module 2 COA

National Institute of Science & Technology
NIST University
Institute Park, Pallur Hills, Berhampur, Odisha
CSE and ECE
1
NIST University www.nist.edu
Computer Organization and Architecture

[Professional Elective 2]
B Tech 4th Semester CSE/IT students of 2022 Batch
//MODULE-2//
By
Nibedita P Mohapatra
Assistant Professor
Department of Computer Science and Engineering
NIST Confidential
Outline
Signed number representation
Fixed & floating point representations

Character representation
Computer Arithmetic
 Ripple carry adder
Carry look-ahead adder
Multiplication
Booth multiplier
Carry save multiplier
 Division restoring & non restoring techniques
Floating point arithmetic
NIST Confidential 3
Signed number representation
Signed integers can represent zero, positive integers, as well as negative

integers. Three representation schemes are available for signed integers:
Sign-Magnitude representation
1's Complement representation
2's Complement representation
In all the above three schemes, the most-significant bit (msb) is called the
sign bit. The sign bit is used to represent the sign of the integer - with 0 for
positive integers and 1 for negative integers. The magnitude of the integer,
however, is interpreted differently in different schemes.
NIST Confidential
n-bit Sign Integers in Sign-Magnitude
Representation:
In sign-magnitude representation:
The most-significant bit (msb) is the sign bit, with value of 0

representing positive integer and 1 representing negative integer.
The remaining n-1 bits represents the magnitude (absolute value) of the
integer. The absolute value of the integer is interpreted as "the magnitude
of the (n-1)-bit binary pattern".
NIST Confidential
Example 1: Suppose that n=8 and the binary representation is 0 100
0001B.
Sign bit is 0 ⇒ positive
Absolute value is 100 0001B = 65D
Hence, the integer is +65D
Example 2: Suppose that n=8 and the binary representation is 1 000

0001B.
Sign bit is 1 ⇒ negative
Hence, the integer is -1D
NIST Confidential
NIST Confidential
n-bit Sign Integers in 1's Complement
Representation
In 1's complement representation:
Again, the most significant bit (msb) is the sign bit, with value of 0
representing positive integers and 1 representing negative integers. The
remaining n-1 bits represents the magnitude of the integer, as follows:
 For positive integers, the absolute value of the integer is equal to "the
magnitude of the (n-1)-bit binary pattern".
 For negative integers, the absolute value of the integer is equal to "the
magnitude of the complement (inverse) of the (n-1)-bit binary
pattern" (hence called 1's complement).
NIST Confidential
Example 1: Suppose that n=8 and the binary representation

0 100 0001B.
Example 2: Suppose that n=8 and the binary representation

1 000 0001B.
Absolute value is the complement of 000 0001B, i.e., 111
1110B = 126D
NIST Confidential
NIST Confidential
n-bit Sign Integers in 2's Complement
Representation
In 2's complement representation:

Again, the most significant bit (msb) is the sign bit, with value of 0
representing positive integers and 1 representing negative integers.
The remaining n-1 bits represents the magnitude of the integer, as follows:
For positive integers, the absolute value of the integer is equal to "the
magnitude of the (n-1)-bit binary pattern".
For negative integers, the absolute value of the integer is equal to "the
magnitude of the complement of the (n-1)-bit binary pattern plus one"
(hence called 2's complement).
NIST Confidential
Example 1: Suppose that n=8 and the binary representation 0 100

0001B.
Example 2: Suppose that n=8 and the binary representation 1 000

0001B.
Absolute value is the complement of 000 0001B plus 1, i.e., 111 1110B
+ 1B = 127D
NIST Confidential
NIST Confidential
NIST Confidential
National Institute of Science & Technology Fixed & floating point representations
Because of the fixed precision (i.e., fixed number of bits), an n-bit 2's
complement signed integer has a certain range. For example, for n=8, the
range of 2's complement signed integers is -128 to +127. During addition
(and subtraction), it is important to check whether the result exceeds this
range, in other words, whether overflow or underflow has occurred.
Example 3: Overflow: Suppose that n=8, 127D + 2D = 129D (overflow -

beyond the range)
127D → 0111 1111B 2D → 0000 0010B(+ 1000 0001B → -127D (wrong)
Example 4: Underflow: Suppose that n=8, -125D - 5D = -130D
(underflow - below the range)
-125D → 1000 0011B -5D → 1111 1011B(+ 0111 1110B → +126D (wrong)
NIST Confidential
NIST Confidential
National Institute of Science & Technology Floating Point Number Representation
A floating-point number (or real number) can represent a very large
(1.23×10^88) or a very small (1.23×10^-88) value. It could also represent
very large negative number (-1.23×10^88) and very small negative number
(-1.23×10^88), as well as zero, as illustrated:
NIST Confidential
A floating-point number is typically expressed in the scientific notation,

with a fraction (F), and an exponent (E) of a certain radix (r), in the form of
F×rÊ. Decimal numbers use radix of 10 (F×10Ê); while binary numbers
use radix of 2 (F×2Ê).
Representation of floating point number is not unique. For example, the

number 55.66 can be represented as 5.566×10^1, 0.5566×10^2,
0.05566×10^3, and so on. The fractional part can be normalized. In the
normalized form, there is only a single non-zero digit before the radix point.
For example, decimal number 123.4567 can be normalized as
1.234567×10^2; binary number 1010.1011B can be normalized as
1.0101011B×2^3.
NIST Confidential
National Institute of Science & Technology Character representation
In computer memory, character are "encoded" (or "represented") using a
chosen "character encoding schemes" (aka "character set", "charset",
"character map", or "code page").
For example, in ASCII (as well as Latin1, Unicode, and many other
character sets):
code numbers 65D (41H) to 90D (5AH) represents 'A' to 'Z', respectively.
code numbers 97D (61H) to 122D (7AH) represents 'a' to 'z', respectively.
code numbers 48D (30H) to 57D (39H) represents '0' to '9', respectively.
NIST Confidential
It is important to note that the representation scheme must be known

before a binary pattern can be interpreted. E.g., the 8-bit pattern "0100
0010B" could represent anything under the sun known only to the person
encoded it.
The most commonly-used character encoding schemes are: 7-bit ASCII
(ISO/IEC 646) and 8-bit Latin-x (ISO/IEC 8859-x) for western European
characters, and Unicode (ISO/IEC 10646) for internationalization (i18n).
A 7-bit encoding scheme (such as ASCII) can represent 128 characters
and symbols. An 8-bit character encoding scheme (such as Latin-x) can
represent 256 characters and symbols; whereas a 16-bit encoding scheme
(such as Unicode UCS-2) can represents 65,536 characters and symbols.
NIST Confidential
Computer Arithmetic
We have discussed three representations for signed integers: signed-
magnitude, 1's complement and 2's complement. Computers use 2's
complement in representing signed integers. This is because:
There is only one representation for the number zero in 2's complement,
instead of two representations in sign-magnitude and 1's complement.
Positive and negative integers can be treated together in addition and

subtraction. Subtraction can be carried out using the "addition logic".
NIST Confidential
Example 1: Addition of Two Positive Integers: Suppose that n=8, 65D +

5D = 70D
65D → 0100 0001B 5D → 0000 0101B(+ 0100 0110B → 70D (OK)
Example 2: Subtraction is treated as Addition of a Positive and a Negative

Integers: Suppose that n=8, 5D - 5D = 65D + (-5D) = 60D
65D → 0100 0001B -5D → 1111 1011B(+ 0011 1100B → 60D (discard
carry - OK)
Example 3: Addition of Two Negative Integers: Suppose that n=8, -65D -

5D = (-65D) + (-5D) = -70D
-65D → 1011 1111B -5D → 1111 1011B(+ 1011 1010B → -70D (discard
carry - OK)
NIST Confidential
National Institute of Science & Technology Ripple Carry Adder
Ripple Carry Adder is a combinational logic circuit.
It is used for the purpose of adding two n-bit binary numbers.
It requires n full adders in its circuit for adding two n-bit binary
numbers.
It is also known as n-bit parallel adder.
4-bit ripple carry adder is used for the purpose of adding two 4-bit
binary numbers.
NIST Confidential
In Mathematics, any two 4-bit binary numbers A 3A2A1A0 and
B3B2B1B0 are added as shown below-
NIST Confidential
Using ripple carry adder, this addition is carried out as shown by the
following logic diagram-
NIST Confidential
Ripple Carry Adder works in different stages.
Each full adder takes the carry-in as input and produces carry-out and
sum bit as output.
The carry-out produced by a full adder serves as carry-in for its
adjacent most significant full adder.
When carry-in becomes available to the full adder, it activates the full
adder.
After full adder becomes activated, it comes into operation.
The carry out produced by each full adder serves as carry-in for its
adjacent most significant full adder.
Each carry bit ripples or waves into the next stage.
That’s why, it is called as “Ripple Carry Adder”.
NIST Confidential
Disadvantages
Ripple Carry Adder does not allow to use all the full adders
simultaneously.
Each full adder has to necessarily wait until the carry bit becomes
available from its adjacent full adder.
This increases the propagation time.
Due to this reason, ripple carry adder becomes extremely slow.
This is considered to be the biggest disadvantage of using ripple carry
adder.
NIST Confidential
National Institute of Science & Technology Carry Look Ahead Adder-
 Carry Look Ahead Adder is an improved version of the ripple carry

adder.
It generates the carry-in of each full adder simultaneously without
causing any delay.
The time complexity of carry look ahead adder = Θ (logn).
The working of carry look ahead adder is based on the principle-
The carry-in of any stage full adder is independent of the carry bits
generated during intermediate stages.
NIST Confidential
NIST Confidential
The carry-in of any stage full adder depends only on the following two
parameters-
Bits being added in the previous stages
Carry-in provided in the beginning
Now,
The above two parameters are always known from the beginning.
So, the carry-in of any stage full adder can be evaluated at any instant
of time.
Thus, any full adder need not wait until its carry-in is generated by its
previous stage full adder.
NIST Confidential
National Institute of Science & Technology 4-Bit Carry Look Ahead Adder-
Consider two 4-bit binary numbers A3A2A1A0 and B3B2B1B0 are to be
added. Mathematically, the two numbers will be added as-
NIST Confidential
From here, we have-

C1 = C0 (A0 ⊕ B0) + A0B0
C2 = C1 (A1 ⊕ B1) + A1B1
C3 = C2 (A2 ⊕ B2) + A2B2
C4 = C3 (A3 ⊕ B3) + A3B3
For simplicity, Let-

G
. i = AiBi where G is called carry generator
Pi = Ai ⊕ Bi where P is called carry propagator
NIST Confidential
Then, re-writing the above equations, we have-

C1 = C0P0 + G0 ………….. (1)
C2 = C1P1 + G1 ………….. (2)
C3 = C2P2 + G2 ………….. (3)
C4 = C3P3 + G3 ………….. (4)
Now,
Clearly, C1, C2 and C3 are intermediate carry bits.
So, let’s remove C1, C2 and C3 from RHS of every equation.
Substituting (1) in (2), we get C2 in terms of C0.
Then, substituting (2) in (3), we get C3 in terms of C0 and so on.
NIST Confidential
Finally, we have the following equations-

C1 = C0P0 + G0
C2 = C0P0P1 + G0P1 + G1
C3 = C0P0P1P2 + G0P1P2 + G1P2 + G2
C4 =C0P0P1P2P3 + G0P1P2P3 + G1P2P3 + G2P3 + G3
These equations show that the carry-in of any stage full adder depends
only on-
Bits being added in the previous stages
Carry bit which was provided in the beginning
NIST Confidential
NIST Confidential
Multiplication
Multiplication
Repeated Addition
Unsigned Integers
Generating partial products, shifting, and adding
Just like longhand multiplication
Two’s Complement Multiplication
 Straightforward multiplication will not work if either the multiplier or
multiplicand are negative
multiplicand would have to be padded with sign bit into a 2n-bit partial
product, so that the signs would line up.
In a negative multiplier, the 1’s and 0’s would no longer correspond to
add-shift’s and shift-only.
NIST Confidential
National Institute of Science & Technology Booth multiplier
Booth algorithm gives a procedure for multiplying binary integers in
signed 2’s complement representation in efficient way, i.e., less number of
additions/subtractions required. It operates on the fact that strings of 0’s in
the multiplier require no addition but just shifting and a string of 1’s in the
multiplier from bit weight 2^k to weight 2^m can be treated as 2^(k+1 ) to
2^m.
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 following rules:
The multiplicand is subtracted from the partial product upon encountering

the first least significant 1 in a string of 1’s in the multiplier
NIST Confidential
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.
The partial product does not change when the multiplier bit is identical to
the previous multiplier bit.
We name the register as A, B and Q, AC, BR and QR respectively. Qn

designates the least significant bit of multiplier in the register QR. An extra
flip-flop Qn+1is appended to QR to facilitate a double inspection of the
multiplier.
NIST Confidential
NIST Confidential
Booth Multiplication Flow chart
NIST Confidential
Carry save multiplier
The carry-save array multiplier (CSA) uses an array of carry-save adders

for the accumulation of partial product. This reduces the critical path delay
of the multiplier as the carry-save adders propagate the carry to the next
level of adders rather than to the adjacent ones.
NIST Confidential
National Institute of Science & Technology Division restoring and non restoring techniques
A division algorithm provides a quotient and a remainder when we divide

two numbers. They are generally of two type slow algorithm and fast
algorithm. Slow division algorithm are restoring, non-restoring, non-
performing restoring, SRT algorithm and under fast comes Newton–
Raphson and Goldschmidt.
NIST Confidential
Restoring Division Algorithm For Unsigned Integer :
Step-1: First the registers are initialized with corresponding values (Q =

Dividend, M = Divisor, A = 0, n = number of bits in dividend)
Step-2: Then the content of register A and Q is shifted left as if they are a
single unit
Step-3: Then content of register M is subtracted from A and result is stored
in A
Step-4: Then the most significant bit of the A is checked if it is 0 the least
significant bit of Q is set to 1 otherwise if it is 1 the least significant bit of Q
is set to 0 and value of register A is restored i.e. the value of A before the
subtraction with M .
Step-5: The value of counter n is decremented.

NIST Confidential
Step-6: If the value of n becomes zero we get of the loop otherwise we

repeat from step 2 .
Step-7: Finally, the register Q contain the quotient and A contain
remainder.
NIST Confidential
Non-Restoring Division For Unsigned Integer
Now, here perform Non-Restoring division, it is less complex than the

restoring one because simpler operation are involved i.e. addition and
subtraction, also now restoring step is performed. In the method, rely on the
sign bit of the register which initially contain zero named as A.
Step-1: First the registers are initialized with corresponding values (Q =
Dividend, M = Divisor, A = 0, n = number of bits in dividend) .
Step-2: Check the sign bit of register A .
Step-3: If it is 1 shift left content of AQ and perform A = A+M, otherwise

shift left AQ and perform A = A-M (means add 2’s complement of M to A
and store it to A) .
NIST Confidential
Step-4: Again the sign bit of register A
Step-5: If sign bit is 1 Q[0] become 0 otherwise Q[0] become 1 (Q[0]

means least significant bit of register Q) .
Step-6: Decrements value of N by 1 .
Step-7: If N is not equal to zero go to Step 2 otherwise go to next step.
Step-8: If sign bit of A is 1 then perform A = A+M .
Step-9: Register Q contain quotient and A contain remainder.
NIST Confidential
Floating Point Arithmetic
The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical

standard for floating-point computation which was established in 1985 by
the Institute of Electrical and Electronics Engineers (IEEE).
There are several ways to represent floating point number but IEEE 754 is
the most efficient in most cases. IEEE 754 has 3 basic components:
The Sign of Mantissa –
This is as simple as the name. 0 represents a positive number while 1

represents a negative number.
NIST Confidential
The Biased exponent –
The exponent field needs to represent both positive and negative exponents.
A bias is added to the actual exponent in order to get the stored exponent.
The Normalized Mantissa –
The mantissa is part of a number in scientific notation or a floating-point

number, consisting of its significant digits. Here we have only 2 digits, i.e.
O and 1. So a normalized mantissa is one with only one 1 to the left of the
decimal.
NIST Confidential
IEEE 754 numbers are divided into two based on the above three
components: single precision and double precision.
49
50
1. 85.125 85 = 1010101 0.125 = 001 85.125 = 1010101.001 =1.010101001

x 2^6 sign = 0 1.
Single precision: biased exponent 127+6=133 133 = 10000101

Normalized mantisa = 010101001 we will add 0's to complete the 23 bits
The IEEE 754 Single precision is:

= 0 10000101 01010100100000000000000
This can be written in hexadecimal form 42AA4000
51
2.Double precision:
biased exponent 1023+6=1029
1029 = 10000000101
Normalized mantisa = 010101001
we will add 0's to complete the 52 bits
The IEEE 754 Double precision is:

= 0 10000000101
0101010010000000000000000000000000000000000000000000
This can be written in hexadecimal form 4055480000000000
52
NIST Confidential
THANK YOU

Module 2 COA

Uploaded by

Copyright:

Available Formats

Module 2 COA

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Module 2 COA

Uploaded by

Copyright:

Available Formats

National Institute of Science & Technology

Computer Organization and Architecture

Fixed & floating point representations

Signed integers can represent zero, positive integers, as well as negative

The most-significant bit (msb) is the sign bit, with value of 0

Example 2: Suppose that n=8 and the binary representation is 1 000

Example 1: Suppose that n=8 and the binary representation

Example 2: Suppose that n=8 and the binary representation

In 2's complement representation:

Example 1: Suppose that n=8 and the binary representation 0 100

Example 2: Suppose that n=8 and the binary representation 1 000

Example 3: Overflow: Suppose that n=8, 127D + 2D = 129D (overflow -

A floating-point number is typically expressed in the scientific notation,

Representation of floating point number is not unique. For example, the

It is important to note that the representation scheme must be known

Positive and negative integers can be treated together in addition and

Example 1: Addition of Two Positive Integers: Suppose that n=8, 65D +

Example 2: Subtraction is treated as Addition of a Positive and a Negative

Example 3: Addition of Two Negative Integers: Suppose that n=8, -65D -

It is also known as n-bit parallel adder.

 Carry Look Ahead Adder is an improved version of the ripple carry

From here, we have-

For simplicity, Let-

Then, re-writing the above equations, we have-

Finally, we have the following equations-

The multiplicand is subtracted from the partial product upon encountering

We name the register as A, B and Q, AC, BR and QR respectively. Qn

The carry-save array multiplier (CSA) uses an array of carry-save adders

A division algorithm provides a quotient and a remainder when we divide

Step-1: First the registers are initialized with corresponding values (Q =

Step-5: The value of counter n is decremented.

Step-6: If the value of n becomes zero we get of the loop otherwise we

Now, here perform Non-Restoring division, it is less complex than the

Step-2: Check the sign bit of register A .

Step-3: If it is 1 shift left content of AQ and perform A = A+M, otherwise

Step-5: If sign bit is 1 Q[0] become 0 otherwise Q[0] become 1 (Q[0]

Step-6: Decrements value of N by 1 .

Step-7: If N is not equal to zero go to Step 2 otherwise go to next step.

Step-8: If sign bit of A is 1 then perform A = A+M .

Step-9: Register Q contain quotient and A contain remainder.

The IEEE Standard for Floating-Point Arithmetic (IEEE 754) is a technical

This is as simple as the name. 0 represents a positive number while 1

The Biased exponent –

The Normalized Mantissa –

The mantissa is part of a number in scientific notation or a floating-point

1. 85.125 85 = 1010101 0.125 = 001 85.125 = 1010101.001 =1.010101001

Single precision: biased exponent 127+6=133 133 = 10000101

The IEEE 754 Single precision is:

The IEEE 754 Double precision is:

You might also like