Data Representation Notes

Seminar Contents

• Learning objectives
• Computer data
• Representing binary integers
• Converting from binary to decimal
• Powers in different bases
• Integer word sizes
• Converting from decimal to binary
• Hexadecimal and octal representations
• Binary addition
• Representing negative numbers
• One’s complement and Two’s complement
• Representing character data, images, and audio

Learning Objectives

• Gained an understanding of the nature of computer data
• Learnt how to represent binary integers
• Learnt how to convert from binary to decimal
• Learnt how to represent powers in different bases
• Gained an understanding of Integer word sizes
• Learnt how to convert from decimal to binary
• Gained an understanding of hexadecimal and octal number representations
• Learnt how to perform binary addition
• Learnt how to represent negative numbers in binary
• Learnt how to apply One’s complement and Two’s complement
• Gained an understanding of how character data, images, and audio are represented digitally

Computer Data (Section 1.5)

• Data is any type of information that can be stored in a computer memory and processed.
• All kinds of information can be stored, as long as it can somehow be represented using 1’s and 0’s (bits).
• Examples of different data types:
  • Audio and Images, etc.
    • 11111111 = White Pixel
    • 00000000 = Black Pixel
  • Texts / characters
    • 01000001 = letter “A”
    • 01000010 = letter “B”
  • Different types of numbers
    • 00000100 = Number 4
    • 00000101 = Number 5
  • Data Processing Instructions
    • 00011001 = Instruction “Add”
• Since each of these is stored as bits, how those bits are determined depends on what type of data the computer expects or thinks they are.

Integer Representation (Section 1.6)

• An integer is a whole number (not a real number).

• Integers can be represented in binary form by writing them in base 2 instead of our common base 10 notation.

• In base 10 you count digits 0..9, then powers of 10, e.g. 10, 100.

• In base 2 you count digits 0..1, then powers of 2, e.g. 10(=2), 100(=4).

• Any number can be evaluated using this formula:
  \sum{i=0}^{n} di \times b^i

  • d_i is the i-th digit.
  • b^i is the base (or radix) raised to the i-th power.
  • The number is the sum of terms from i = 0 to i = n.
  • n is the number of digits in the number -1.

• Example:

  • 123 = 1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0 = 100 + 20 + 3

Binary Integers

• The place of a digit in a binary number gives the power of 2 that the value of that digit represents.
• The value of a binary number can be read as follows:
  • Number = 1 \times 2^7 + 1 \times 2^6 + 0 \times 2^5 + 0 \times 2^4 + 0 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 1 \times 128 + 1 \times 64 + 0 \times 32 + 0 \times 16 + 0 \times 8 + 1 \times 4 + 0 \times 2 + 1 \times 1 = 197
• Examples: Binary to Decimal Conversion
  • 00000011_2 = 2 + 1 = 3
  • 00010010_2 = 16 + 2 = 18
  • 10000101_2 = 128 + 4 + 1 = 133
  • 11110000_2 = 128 + 64 + 32 + 16 = 240

Powers in Different Bases

• Decimal:
  • 10^0 = 1
  • 10^1 = 10
  • 10^2 = 100
  • 10^3 = 1,000
  • 10^4 = 10,000
  • 10^5 = 100,000
  • 10^6 = 1,000,000
  • 10^7 = 10,000,000
  • 10^8 = 100,000,000
  • 10^9 = 1,000,000,000
  • 10^{10} = 10,000,000,000
• Binary:
  • 2^0 = 1
  • 2^1 = 2
  • 2^2 = 4
  • 2^3 = 8
  • 2^4 = 16
  • 2^5 = 32
  • 2^6 = 64
  • 2^7 = 128
  • 2^8 = 256
  • 2^9 = 512
  • 2^{10} = 1024
• Hexadecimal:
  • 16^0 = 1
  • 16^1 = 16
  • 16^2 = 256
  • 16^3 = 4096
  • 16^4 = 65,536
• Octal:
  • 8^0 = 1
  • 8^1 = 8
  • 8^2 = 64
  • 8^3 = 512
  • 8^4 = 4096
• Octal example:
  • 21_8 = 2 \times 8^1 + 1 \times 8^0 = 2 \times 8 + 1 \times 1 = 17

Bits and Values

• If we have N bits, we can represent 2^N different values with those N bits. Note that we start counting values from 0.

Decimal to Binary Conversion (Section 1.6)

To convert any number N, base 10, to binary:

1. (a) Find the largest power of 2 <= N, say 2^X
   (b) then subtract 2^X from N.
2. Substitute N- 2^X for N then repeat step 1b until (N- 2^X) becomes 0.
3. Assemble the binary number with 1s in the bit positions corresponding to powers of 2 used in the decomposition of N, and 0s elsewhere.

• Example: Convert 770 to binary:
  1. a) The largest power of 2 <= 770, is 2^9 or 512.
  2. b) Subtract 512 from 770 which gives you 258.
  3. The largest power of 2 <= 258, is 2^8 or 256.
  4. b) Subtract 256 from 258 which gives you 2.
  5. The largest power of 2 <= 2, is 2^1 or 2.
  6. b) Subtract 2 from 2 which gives you 0.
  7. We have reached 0, stop finding powers of 2 and go to step 3.
  8. Powers of 2 used to decompose 770 are: 9, 8, and 1. Set those bit positions to 1
     1100000010_2

Hexadecimal (Section 2.6)

• Hexadecimal (Hex) and binary numbers are closely related since 16 is a power of 2 (2^4).
• Conversion between hexadecimal and binary is also straightforward.
• Hexadecimal has 16 digits: from 0 to F.
• Each hexadecimal digit only requires 4 binary bits to represent it.
• To convert between binary and hexadecimal grouping four binary digits together to make one hexadecimal digit.
• Hexadecimal numbers often have a “0x” in front to identify them. E.g. 0xF1
• Hexadecimal numbers can use capitals or lowercase for letters

Why use hexadecimal?

To simplify the binary numbering system

• Computers use binary while humans can use hexadecimal to shorten binary and make it easier to understand
• Uses
  • To define locations in memory. Every byte is two hexadecimal digits compared to eight digits when using binary. E.g. F3 instead of 11110011
  • To define colours on web pages. Each primary colour – red, green and blue is characterised by two hexadecimal digits. The format being used is #RRGGBB. RR stands for red, GG stands for green, and BB stands for blue. E.g. FF0000 = FULL red
  • To represent Media Access Control (MAC) addresses. MAC addresses consist of 12-digit hexadecimal numbers and are used to uniquely identify each network adapter.
  • To display error messages. Hexadecimals are used to define the memory location of the error. This is useful for programmers in finding and fixing errors.

Octal

• Octal numbers are similar to hexadecimal but only have 8 digits from 0 to 7
• Octal digits are made up from groups of 3 bits

Why use octal?

The main advantage of using Octal numbers is that it uses less digits than decimal and Hexadecimal number systems

• It has fewer computations and therefore less computational errors
• It uses only 3 bits to represent any digit in binary and it is easy to convert from octal to binary and vice-versa
• Uses
  • Octal is best used when the number of bits in one word is a multiple of 3
  • For example, it has been used:
    • As a shorthand for representing file permissions on UNIX systems
      • 777 = 111\ 111\ 111 world / group / individual
    • Representation of UTF8 numbers, etc.

Binary Addition

• How do we add up binary numbers?
• We add up each binary place and take any carry over into the next column.
• Example: Single Bit Addition

• Example: Multiple Bit Addition

Negative Integers (Section 4.2)

• So far, we have only dealt with positive integers
• We need some way of representing the signs (+ or -)
• We could try making the most significant bit (left-most bit) in a word 0 for positive numbers and 1 for negative numbers
  • E.g.
    • +2 = 00000010
    • +127 = 01111111
    • -2 = 10000010
    • -127 = 11111111
  • This method uses a Sign Bit and the remaining bits represent the Magnitude of the integer.
    • 0 = positive integer
    • 1 = negative integer

Negative Integers

Negative Integers

• A problem with this approach, there are two zeroes: +0 and -0

Negative Integers

• You can view subtraction in terms of addition
  • B – C is equivalent to B + (-C)
• Let’s try to add +7 to –5 with binary addition and using the most significant bit as the sign bit.
• This does not work. We need some other way of representing negative numbers so addition works correctly
  • +7 0 0000111
  • -5 1 0000101
  • +2 1 0001100 = -12 !

One’s Complement

• Using a sign bit plus binary magnitude does not work.
• Let’s try using a sign bit plus the bitwise complement of the magnitude.
• The One’s complement of a binary value is defined as follows:
  • We can apply One’s Complement a binary number by complementing each of its bits (change all the 1s to 0s and all the 0s to 1s)

| Bit | One’s Complement |
| :-: | :----------------: |
| 0 | 1 |
| 1 | 0 |

• Binary Value: 1000111
• One’s Complement: 0111000

One’s Complement

• Using a sign bit plus binary magnitude does not work.

• Let’s try using a sign bit plus the bitwise complement of the magnitude.

• Now let’s try to add some numbers like before

• Still wrong but closer – we are only out by 1

• The clue to what is wrong is due to having 2 zeros

  • +2 = 0 0 0 0 0 0 1 0
  • +127 = 0 1 1 1 1 1 1 1
  • +0 = 0 0 0 0 0 0 0 0
  • -2 = 1 1 1 1 1 1 0 1
  • -127 = 1 0 0 0 0 0 0 0
  • -0 = 1 1 1 1 1 1 1 1

• Examples:

  • -4 1 1 1 1 1 0 1 1

  • +6 0 0 0 0 0 1 1 0

  • +2 1 0 0 0 0 0 0 1 = +1

  • -3 1 1 1 1 1 1 0 0

  • -2 1 1 1 1 1 1 0 1

  • -5 1 1 1 1 1 1 0 0 1 = -6

Two’s Complement (Approach 1)

• Let’s try One’s complement +1 for negative numbers: This is called Two’s complement

• Now let’s try to add some numbers like before

  • +7 0 0 0 0 0 1 1 1
  • -5 1 1 1 1 1 0 1 1
  • +2 1 0 0 0 0 0 0 1 0 = +2

• Examples:

  • +7 = 0 0000111
  • +4 = 0 0000100
  • +1 = 0 0000001
  • -2 = 1 1111110
  • -5 = 1 1111011
  • +6 = 0 0000110
  • +3 = 0 0000011
  • 0 = 0 0000000
  • -3 = 1 1111101
  • +5 = 0 0000101
  • +2 = 0 0000010
  • -1 = 1 1111111
  • -4 = 1 1111100

• This works!

  • +3 0 0 0 0 0 0 1 1
  • -5 1 1 1 1 1 0 1 1
  • -2 1 1 1 1 1 1 1 0 = -2
  • -3 1 1 1 1 1 1 0 1
  • -2 1 1 1 1 1 1 1 0
  • -5 1 1 1 1 1 1 0 1 1 = -5

Two’s Complement (Approach 2)

• There is an alternative (simpler) method to obtain the Two’s complement for a number
• The approach is as follows
  1. Start from the right-hand side of the binary number
  2. For all bits to the left of the first 1
     3. 1 Change all 1s to 0s and all 0s to 1s
• Eg:
  • +36 0 0 1 0 0 1 0 0
  • -36 1 1 0 1 1 1 0 0
  • First 1 from the right hand-side

Number Representations

• Numbers are stored as a word sized set of bits.
• It is possible to use both smaller and larger words sizes to represent numbers of different ranges.
• Some programming languages (like C) might use the following unsigned and signed data types on a 32-bit word size architecture:

I/O Data Types and Encoding

• I/O devices need to represent a wide range of different data types
  • Keyboard presses
  • On-screen text display
  • Bitmapped Images and Graphics
  • Audio, Video
• A processor needs to be able to process all of these different types
• Hence, each of these data types has its own internal binary representation

Character Data (Section 4.4)

• Keyboard input consists of a series of individual characters
• Onscreen text display also consists of characters
• Each character is represented using an 8-bit code that is defined by the ASCII standard. There are other standards (Unicode, EBCDIC) not covered in this course.
• We can represent a string of characters using a string of hexadecimal words:
  • “Computer1” = 43 6F 6D 70 75 74 65 72 49

| Dec | Hex | Char |
| :-: | :-: | :--: |
| 65 | 41 | A |
| 66 | 42 | B |
| 67 | 43 | C |
| 68 | 44 | D |
| 69 | 45 | E |
| 70 | 46 | F |
| 71 | 47 | G |
| 72 | 48 | H |
| 73 | 49 | I |
| 74 | 4A | J |

| Dec | Hex | Char |
| :-: | :-: | :--: |
| 97 | 61 | a |
| 98 | 62 | b |
| 99 | 63 | c |
| 100 | 64 | d |
| 101 | 65 | e |
| 102 | 66 | f |
| 103 | 67 | g |
| 104 | 68 | h |
| 105 | 69 | i |
| 106 | 6A | j |

| Dec | Hex | Char |
| :-: | :-: | :--: |
| 48 | 30 | 0 |
| 49 | 31 | 1 |
| 50 | 32 | 2 |
| 51 | 33 | 3 |
| 52 | 34 | 4 |
| 53 | 35 | 5 |
| 54 | 36 | 6 |
| 55 | 37 | 7 |
| 56 | 38 | 8 |
| 57 | 39 | 9 |

• The tables show some parts of the ASCII character set.
• Some characters and their decimal and hexadecimal values are shown

ASCII Table

• Hex Binary:
  • A 41 0100 0001
  • a 61 0110 0001
  • B 42 0100 0010
  • b 62 0110 0010

Bitmap Images

• A bitmap image is a 2D array of unsigned numbers where each element specifies the colour at that location.
• Each individual element in the array is called a pixel
• A computer display is basically just a large bitmap
• The number of bits used to represent each pixel defines the number of colour shades that the bitmap can contain
• Example 1 bit Image 12 x 10 pixels

Image

• 0 = black
• 1 = white
• Example 4-bit Image 12 x 10 pixels