Chapter 2

Data Representation
in Computer Systems
2
3
4
5
6
7
8
9
10
11
12
 SIGNED INTEGER REPRESENTATION

13
 Signed Integer Representation
• The conversions we have so far presented have involved only
positive numbers.
• To represent negative values, computer systems allocate the high-
order bit to indicate the sign of a value.
– The high-order bit is the leftmost bit in a byte.
– It is also called the MSB.
• The remaining bits contain the value of the number.
• When an integer variable is declared in a program, many
programming languages automatically allocate a storage area that
includes a sign as the first bit of the storage location.
• Three ways in which signed binary numbers may be expressed
» Signed magnitude
» One’s complement
» Two’s complemen

14
 Signed Magnitude Representation
• In an 8-bit word, signed magnitude representation
places the absolute value of the number in the 7 bits to
the right of the sign bit
• In 8-bit signed magnitude
– Positive 3 is 00000011
– Negative 3 is 10000011
• Computers perform arithmetic operations on signed
magnitude numbers in much the same way as
humans carry out pencil and paper arithmetic.
– Ignoring the signs of the operands while performing a calculation,
applying the appropriate sign after the calculation is complete

15
 Example one
Using signed magnitude binary arithmetic, find the sum of
75 and 46.
Solution
convert 75 and 46 to binary, and arrange as a sum, but
separate the (positive) sign bits from the magnitude bits.

We were careful to pick two values

whose sum would fit into 7 bits. If
that is not the case, we have a
problem

16
 Example Two

Using signed magnitude binary arithmetic, find the sum

of 107 and 46.

We see that the carry from the seventh bit overflows and
is discarded, giving us the erroneous result
107 + 46 = 25

17
 Example Three

Using signed magnitude binary arithmetic, find the

sum of - 46 and - 25.

• Because the signs are the same, all we do is add

the numbers and supply the negative sign when
we are done
18
 Example Four

Using signed magnitude binary arithmetic, find the sum of 46

and - 25.

 Mixed sign addition (or subtraction) is done the same way

 The sign of the result gets the sign of the number that is larger.
– Note the “borrows” from the second and sixth bits.

19
 Signed Magnitude Representation

• Advantage
– easy for people to understand.
• Disadvantage
– It allows two different representations for zero: positive
zero and negative zero.
– It requires complicated computer hardware
• For these reasons (among others) computers
systems employ Complement systems for
numeric value representation.

20
 One’s Complement

• With one’s complement addition, the carry bit is “carried

around” and added to the sum.
• In 8-bit one’s complement
• positive 3 is: 00000011
• Negative 3 is: 11111100
• In one’s complement, as with signed magnitude, negative
values are indicated by a 1 in the high order bit.
• Complement systems are useful because they eliminate the
need for subtraction.
• The difference of two values is found by adding the minuend
to the complement of the subtrahend.

21
 One’s Complement
Example One
Using one’s complement binary arithmetic, find the sum
of 48 and - 19
We note that
48 in one’s complement 00110000
19 in one’s complement 00010011
-19 in one’s complement is 11101100

22
 One’s Complement

• Although the “end carry around” adds some

complexity, one’s complement is simpler to implement
than signed magnitude
• Disadvantage
– two different representations for zero
• Two’s complement solves this problem.

23
 Two’s Complement
• To express a value in two’s complement:
– If the number is positive, just convert it to binary and
you’re done.
– If the number is negative, find the one’s complement of
the number and then add 1.
• With two’s complement arithmetic, all we do is add our two binary
numbers. Just discard any carries emitting from the high order bit.

24
 Two’s Complement
Example One
Using Two’s complement binary arithmetic, find the sum of 48
and - 19.
– 48 in two’s complement is 0011 0000
– 19 in one’s complement is 0001 0011
– -19 in one’s complement is 1110 1100
– -19 in two’s complement is 1110 1101

25
 Overflow
• When we use any finite number of bits to represent
a number, we always run the risk of the result of our
calculations becoming too large to be stored in the
computer.
• While we can’t always prevent overflow, we can
always detect overflow.
• In complement arithmetic, an overflow condition is
easy to detect.

26
 Two’s Complement
Example Two
Using two’s complement binary arithmetic, find the
sum of 107 and 46.
• We see that the nonzero carry from the seventh bit
overflows into the sign bit, giving us the erroneous result:
107 + 46 = -103

• Rule for detecting signed two’s complement overflow

• When the “carry in” and the “carry out” of the sign bit differ, overflow has
27 occurred.
 Do we need unsigned numbers?

• Signed and unsigned numbers are both useful

– e.g, memory addresses are always unsigned
• Using the same number of bits, unsigned
integers can express twice as many values as
signed numbers.

28
 ‫المحاضرة السابعة‬

FLOATING-POINT REPRESENTATION

29
 2.5 Floating-Point Representation

• The signed magnitude, one’s complement,

and two’s complement representation that
we have just presented deal with integer
values only.
• Without modification, these formats are
not useful in scientific or business
applications that deal with real number
values.
• Floating-point representation solves this
problem.
30
 2.5 Floating-Point Representation
• Floating-point numbers allow an arbitrary number of decimal
places to the right of the decimal point.
– For example: 0.5  0.25 = 0.125
• They are often expressed in scientific notation.
– For example:
0.125 = 1.25  10-1
5,000,000 = 5.0  106
• Computers use a form of scientific notation for floating-
point representation
• Numbers written in scientific notation have three
components

31
 2.5 Floating-Point Representation
• Computer representation of a floating-point number
consists of three fixed-size fields

• The one-bit sign field is the sign of the stored value

• The size of the exponent field, determines the range of values
that can be represented
• The size of the significand determines the precision of the
representation.
• The significand of a floating-point number is always preceded by an
implied binary point.
• Thus, the significand always contains a fractional binary value.
• The exponent indicates the power of 2 to which the significand is
raised
32
 Example
• Express 3210 in the simplified 14-bit floating-point model.
– We know that 32 is 25.
– So in (binary) scientific notation 32 = 1.0 x 25 = 0.1 x 26.
– Using this information, we put 110 (= 610) in the exponent
field and 1 in the significand as shown.

33
 2.5 Floating-Point Representation

• Another problem with our system is that we have made no

allowances for negative exponents. We have no way to
express 0.5 (=2 -1)! (Notice that there is no sign in the
exponent field!)

All of these problems can be fixed with no

changes to our basic model.

34
 2.5 Floating-Point Representation

• To provide for negative exponents, we will use a biased

exponent.
• A bias is a number that is approximately midway in the
range of values expressible by the exponent. We subtract
the bias from the value in the exponent to determine its
true value.
– In our case, we have a 5-bit exponent. We will use 16 for our
bias. This is called excess-16 representation.
• In our model, exponent values less than 16 are negative,
representing fractional numbers.

35
 2.5 Floating-Point Representation

• Example:
– Express 3210 in the revised 14-bit floating-point model.
• We know that 32 = 1.0 x 25 = 0.1 x 26.
• To use our excess 16 biased exponent, we add 16 to 6,
giving 2210 (=101102).
• Graphically:

36
 2.5 Floating-Point Representation

• Example:
– Express 0.062510 in the revised 14-bit
floating-point model.
• We know that 0.0625 is 2-4. So in (binary) scientific notation 0.0625 = 1.0 x 2-4 =
0.1 x 2 -3.
• To use our excess 16 biased exponent, we add 16 to -3, giving 1310 (=011012).

37
 Example

• Express -26.62510 in the revised 14-bit

floating-point model.
– We find 26.62510 = 11010.1012. Normalizing, we
have: 26.62510 = 0.11010101 x 2 5.
– To use our excess 16 biased exponent, we add 16
to 5, giving 2110 (=101012). We also need a 1 in
the sign bit.

38
 2.5 Floating-Point Representation

• The IEEE-754 single precision floating

point standard uses bias of 127 over its 8-
bit exponent.
• The double precision standard has a bias
of 1023 over its 11-bit exponent.

39
 2.5 Floating-Point Representation
• To resolve the problem of synonymous forms, we will
establish a rule that the first digit of the significand
must be 1.
– This results in a unique pattern for each floating-point number.

• In the IEEE-754 standard, this 1 is implied meaning

that a 1 is assumed after the binary point.
– By using an implied 1, we increase the precision of the
representation by a power of two.

40
 2.5 Floating-Point Representation
• Both the 14-bit model that we have presented
and the IEEE-754 floating point standard allow
two representations for zero.
– Zero is indicated by all zeros in the exponent and the
significand, but the sign bit can be either 0 or 1.
• This is why programmers should avoid testing a
floating-point value for equality to zero.
– Negative zero does not equal positive zero.

41
 ‫المحاضرة الثامنة‬

1- CHARACTER CODES
2- ERROR DETECTION

42
 2.6 Character Codes

• We know that numbers can be

represented in binary
• What about non-numbers such as text,
images and sound?

43
 2.6 Character Codes

• In order to store letters in memory they must

be encoded somehow as binary numbers.
• Since we know how to store numbers in
binary, if we can assign each letter a unique
number
• Then we can then convert that number to
binary.

44
 Encoding Text
• For example, if letter "K" has number 75, then we convert
75 to unsigned binary 01001011, which will be the binary
code for "K".
• This is the method used to store letters in binary - by using a
code that associates each letter of the text character set with
a unique number.
• Numerous codes have been developed such as
– Binary-coded decimal
– Binary-Coded Decimal Interchange Code (EBCDIC).
– American Standard Code for Information Interchange
– Unicode
45
46
 Computer coding systems
• Larger computer memories and storage devices permit richer
character codes
• The earliest computer coding systems used 6 bits.
• BCD was one of these early codes. It was used by IBM
mainframes in the 1950s and 1960s.
• In 1964, BCD was extended to an 8-bit code, Extended
Binary-Coded Decimal Interchange Code (EBCDIC).
• EBCDIC supported upper and lowercase alphabetic
characters, in addition to special characters, such as
punctuation and control characters.
• EBCDIC and BCD are still in use by IBM mainframes today.

47
 Computer coding systems
• Other computer manufacturers chose the 7-bit ASCII as a
replacement for 6-bit codes.
• Until recently, ASCII was the dominant character code
outside the IBM mainframe world.
• Many of today’s systems embrace Unicode, a 16-bit system
that can encode the characters of every language in the
world.
– The Java programming language, and some operating systems now
use Unicode as their default character code.
• The Unicode code space is divided into six parts. The first
part is for Western alphabet codes, including English, Greek,
and Russian.
48
 Computer coding systems

• The Unicode codes- pace

allocation is shown at the
right.
• The lowest-numbered
Unicode characters
comprise the ASCII code.
• The highest provide for
user-defined codes.

49
 ERROR DETECTION

50
 Error Detection and Correction

• It is physically impossible for any data recording or

transmission medium to be 100% perfect 100% of the
time over its entire expected useful life.
• As more bits are packed onto a square centimeter of
disk storage, as communications transmission speeds
increase, the likelihood of error increases.
• Thus, error detection and correction is critical to
accurate data transmission, storage and retrieval.

51
 Error Detection and Correction
• Check digits, appended to the end of a long number
can provide some protection against data input
errors.
– The last character of the Universal Product Code (UPC)
Barcodes and International Standard Book Number (ISBN)s are
check digits.
• Longer data streams require more economical and
sophisticated error detection mechanisms.
• Cyclic redundancy checking (CRC) codes provide
error detection for large blocks of data.

52
 Error Detection and Correction

• Checksums and CRCs are examples of systematic error

detection.
• In systematic error detection a group of error control bits
is appended to the end of the block of transmitted data.
– This group of bits is called a syndrome.
• CRCs are polynomials over the modulo 2 arithmetic
field.

53
 Error Detection and Correction

• In modulo 2 arithmetic if we add / subtract 1 to 1, we

get 0. The addition rules couldn’t be simpler:(XOR)

0+0=0 0+1=1
1+0=1 1+1=0

54
Cyclic Redundancy Check
CRC
 Cyclic Redundancy Check
• Given a k-bit frame or message, the
transmitter generates an n-bit sequence,
known as a frame check sequence (FCS),
so that the resulting frame, consisting of
(k+n) bits, is exactly divisible by some
predetermined number.
• The receiver then divides the incoming
frame by the same number and, if there is
no remainder, assumes that there was no
error.
Binary Division
Polynomial
 Error Detection

• If no bits are lost or corrupted,

dividing the received
information string by the agreed
upon pattern will give a
remainder of zero.
• We see this is so in the
calculation at the right.
• Real applications use longer
polynomials to cover larger
information strings.
– Some of the standard polynomials
are listed in the text.

59
 Error Correction

• Data transmission errors are easy to fix once an

error is detected.
– Just ask the sender to transmit the data again.
• In computer memory and data storage, however, this
cannot be done.
– Too often the only copy of something important is in memory or
on disk.
• Thus, to provide data integrity over the long term,
error correcting codes are required.

60
 Error Correction codes
1) Hamming code
useful in correcting single bit errors.
1) Reed-Soloman codes
- useful in correcting burst errors that occur, when a series of
adjacent bits are damaged.
- Because CD-ROMs are easily scratched, they employ a
type of Reed-Soloman error correction.
• Because the mathematics of Hamming codes is much simpler
than Reed-Soloman, we discuss Hamming codes in detail.

61
 Error Correction
Hamming codes
• Hamming codes are code words formed by adding
redundant check bits, or parity bits, to a data word.
• It can be applied to data units of any length
• It is used to detect and correct single bit errors
• All bit positions that are power of 2 are marked as parity
bits (1, 2, 4, 8, 16, …..)

62
 How to determine the value of the parity bit

Rule
The value of parity bit is determined by the
sequence of bits that is alternatively checks
and skips.

P1: checks 1bit, skips 1bit (1, 3, 5, 7, 9,….)

P2: checks 2bits , skips 2bits (2, 3, 6, 7, 10, 11, ….)
P4: checks 4bits , skips 4bits (4, 5, 6, 7, 12, 13, 14, 15 ,….)

63
 Number of check bits that we need in our
code words.
• data words of length =m
• check bits = P
(m + P + 1)  2 P
• Suppose we have data word (1101) … length m = 4
• Then:
(4 + P + 1)  2 P
implies that P must be greater than or equal to 3
• This means to build a code with 4-bit data words that
will correct single-bit errors, we must add 3 check bits.

64
 Error Detection and Correction

• Using our code words of length 7, number each

bit position starting with 1 in the low-order bit.
• Each bit position corresponding to an even
power of 2 will be occupied by a check bit.
• These check bits contain the parity of each bit
position for which it participates in the sum.

65
 P4 P2 P1
0 0 0 m0
0 0 1 m1
0 1 0 m2
0 1 1 m3
1 0 0 m4
1 0 1 m5
1 1 0 m6
1 1 1 m7
P1= ∑(1, 3, 5, 7) = 0
P2= ∑ (2, 3, 6, 7) = 1
66
P4= ∑ (4, 5,6, 7) = 0
 Detecting error at the receiver

67
 Correcting errors at the receiver
• An error is located by forming a 3-bit number, out
of 3 parity checks
• We check parity bits
• If parity bit is odd, error exists and P=1
• If parity bit is even, no error exists and P=0
• After finding the error word, we find its decimal
value.
• Then we invert the incorrect bit to obtain the
correct word.

68
 Example
At the receiver side

69