Microsoft PowerPoint – L2 2021
Outline
• Discussion on first week’s lab
• Encoding, numbers, floating‐point (details)
• Lab walk through
• Memory (unlikely time – probably just back‐up slides)
Let’s talk about labs
• My point of view:
• Lots of groups interacted well
• Cameras on
• Active chat
• Discord worked well for those who used it
• Progress was slower than in‐person labs
• Codeshare really helps demonstrators to interact with students
• Work‐through (answers) later in lecture
An ideal setup
Let’s talk about labs
• My point of view:
• T12 until R09 ran about the same. Groups
are set‐up, should be smoother next week
• Issues exist – we’re trying to learn about
them so we can try to address them
Let’s talk about labs
• Over to you:
• https://padlet.com/davidboland/nxrrkb9f0la9cmd3
Encoding Information
Why do computers need to encode
information?
Why do computers need to encode
information?
• Because they can only deal with 0’s and 1’s
What do we mean by encoding information
for computers?
What do we mean by encoding information
for computers?
• Numbers
• (binary)
What do we mean by encoding information
for computers?
• Numbers
• (binary)
• Colours
• Red/green/blue
• Machine Code
What do we mean by encoding information
for computers?
• Anything that you possibly want to do with a computer
What do we mean by encoding information
for computers?
• Literally everything…
Start with numbers…
• Why?
• Computers very good at arithmetic
• Computers do a lot of arithmetic
Start with natural numbers
• What are they?
How do we count numbers in base 10?
How do we count numbers in binary?
• Same way, but max of 2
What do numbers in base 10 mean
• Consider the number 429
• How do we break it down?
What does a binary number mean
• Consider the number 111010 mean
• How do we break it down?
How do we convert numbers between bases
• Convert 82710 to binary?
Why Octal/Hexadecimal
• How do you think this monitor is encoded?
Why Octal/Hexadecimal
• Make binary more human readable
• Conversion (from binary) is easy
First exercise from worksheet
First exercise from worksheet
• 110 110 101 001 =6651
• 1101 1010 1001 = DA9
• A = 1010
• B = 1110
• C = 1210
• D = 1310
• E = 1410
• F = 1510
Useful properties of base 10
• Is 1345 a multiple of 10? Is it a multiple of 100?
• Is 13450 a multiple of 10? Is it a multiple of 100?
• Is 10400 a multiple of 10? Is it a multiple of 100?
• Is this hard?
Useful properties of base 10
• How do you multiply 1274 by 10?
• How do you multiply 1830 by 100?
• Is this hard?
Useful properties of base 10
• How do you divide 10400 by 10?
• How do you divide 10400 by 100?
• Is this hard?
Useful properties of base 10
• Is 1345 a multiple of 7? Is it a multiple of 77?
• Is 13450 a multiple of 70? Is it a multiple of 777?
• Is 10400 a multiple of 70? Is it a multiple of 777?
• How do you multiply 1274 by 7?
• How do you multiply 1830 by 77?
• How do you divide 10400 by 77?
• How do you divide 10400 by 777?
• Is this hard?
Useful properties of base 2
• Is 101100 a multiple of 2? Is it a multiple of 4?
• How do you multiply 1010010 by 2?
• How do you multiply 1011110 by 4?
• How do you divide 10101010 by 2?
• How do you divide 10111100 by 4?
• Is this hard?
Useful properties of base 8, base 16
• Worksheet exercise 2
Couple of bonus questions
• What is 10016 ‐1 ?
How many different numbers can you
represent?
• 10 digits?
• 10 octal values?
• 10 hex values?
• 10 bits?
Encoding integers
• What is the difference between the set of integers and set of natural
numbers?
Encoding integers
• What is the difference between the set of integers and set of natural
numbers?
• Sign‐magnitude: the easiest way to represent negative numbers
• Add a sign bit
Encoding integers
• What is the difference between the set of integers and set of natural
numbers?
• Sign‐magnitude: the easiest way to represent negative numbers
• Add a sign bit
• Is this a good representation?
• 0011 1101 1101
• 1*2^0
• 0*2^1
• 1*2^2
• 1*2^3
• 1*2^4
• 0*2^5
• 1*2^6
• 1*2^7
• 1*2^8
How do we add sign‐magnitude numbers
How do we add positive numbers
• How do we add 1503+1729?
How do we add positive binary numbers
• How do we add 1001+1011?
How do we add sign‐magnitude numbers
• Suppose we have two binary numbers in sign‐magnitude
representation:
• A+B (A+ve, B+ve)
• A+B (A+ve, B‐ve)
• A+B (A‐ve, B‐ve)
One’s complement
• Invert all bits
• Simpler addition
Two’s complement
• Easy to compute
• Invert all bits and add 1
• Has a direct understanding
• Simpler addition still
Worksheet Q2
28
26
Why Floating‐point?
Encoding Real Numbers
• Do we need floating‐point to encode real numbers?
Why Floating‐point?
• Can we represent natural numbers with fixed point?
• Can we represent integer numbers with fixed point?
Why Floating‐point?
• You have 8 bits. How do you represent numbers between 0 and 63?
Why Floating‐point?
• You have 8 bits. How do you represent numbers between 0 and 63?
• You have 8 bits. How do you numbers between 0 and 126?
Why Floating‐point?
• You have 8 bits. How do you represent numbers between 0 and 63?
• You have 8 bits. How do you numbers between 0 and 126?
• Is 8‐bits sufficient to represent numbers between 0 and 63?
How many different values can you
represent?
• 10 digits?
• 10 octal values?
• 10 hex values?
• 10 bits?
Why Floating‐point?
• You want to represent a wide range with a fixed number of bits?
Fixed Point
• What numbers does 8‐bit fixed‐point represent?
Fixed Point
• Suppose I represent an 8‐bit number that lies in the range [‐2, 2] in
fixed‐point. What does that mean?
Why Floating‐point?
• You want to represent a wide range with a fixed number of bits?
• Reason for floating‐point: You want to represent a variable range with
a fixed number of bits
Why Floating‐point?
• You want to represent a wide range with a fixed number of bits?
• Reason for floating‐point: You want to represent a variable range with a
fixed number of bits
• Your memory can store 16 bits.
• Your algorithm involves some calculations with many variables
• Variables include numbers as large as 30000.
• Your algorithm has an exit condition var1‐var2>1e‐6
• You need more fixed‐point bits than you can handle
Bisection algorithm
Fixed vs Float
Overflow
5 bit fixed point, 2 bits integer, 3 bits fractional
Roundoff
Number system must not overflow (error unbounded)
Accumulation of round‐off errors must lie below tolerable region
5 bit floating point, 2 bits exponent, 3 bits mantissa
m
e bbbx ….02 21 }1,0{, ib
Fixed vs floating point
• Fixed point:
• Number system must not overflow (error unbounded)
• Accumulation of round‐off errors must lie below tolerable region
• Floating‐point similarities:
• Number system must not overflow
• Accumulation of round‐off errors must lie below tolerable region
• Differences:
• Bigger dynamic range
• Underflow
• Size of roundoff errors vary relative to the representable value
• Floating point is not associative
Is floating‐point good?
Notes vs IEEE 754 Standard Floating Point
• Single precision:
• Double precision
Notes vs IEEE 754 Standard Floating Point
• Single precision:
• Half precision
Notes vs IEEE 754 Standard Floating Point
• IEEE standard
• Implicit leading 1
• Special codes:
• NaN (0/0, sqrt(‐10))
• Infinity (100/0, ‐100/0)
• Exponent subtract a bias (127 for single gives range ‐126 to +127)
Important to remember
• Floating point needs its representation defined
Why should I learn custom floating‐point?
Floating‐point practice
• Worksheet Q3
Floating‐point
range/precision/underflow/overflow
• How do you increase range?
• How do you increase precision?
• What is overflow?
• What is underflow?
• Worksheet Q4
Floating‐point games
Floating point is not associative
Which answer is correct?
71
1
e
i
i
Floating point is not associative
How do you add numbers in FP
• Compute 3+0.625
• 3 is 22×0.110
• 0.625 is 20×0.101
• Align exponents
• 3 is 22×0.110
• 0.625 is 22×0.00101
• Perform addition
• 22×0.11101
• Re‐normalise to 5 bits
• 22×0.111 = 3.5
• Roundoff error of 0.125
• Compute 3.5+0.875.
• 3.5is 22×0.111
• 0.875 is 20×0.111
• Align exponents
• 3.5 is 22×0.111
• 0.875 is 22×0.00111
• Perform addition
• 22×1.00011
• Re‐normalise to 5 bits
• 23×0.100 = 4
• Roundoff error of 0.375
m
e bbbx ….02 21
Evaluate 3+0.625+0.875, with 3 bit mantissa
How do you add numbers in FP
• Compute 0.625+0.875
• 0.625 is 20×0.101
• 0.875 is 20×0.111
• Align exponents
• 0.625 is 20×0.101
• 0.875 is 20×0.111
• Perform addition
• 20×1.100
• Re‐normalise to 5 bits
• 21×0.110 = 1.5
• No roundoff error
• Compute 1.5+3
• Result is 21×0.110
• 3 is 22×0.110
• Align exponents
• 3 is 22×0.110
• 0.875 is 22×0.0110
• Perform addition
• 22×1.001
• Re‐normalise to 5 bits
• 23×0.101 = 5
• Roundoff error of 0.5
m
e bbbx ….02 21
Evaluate 0.625+0.875+3, with 3 bit mantissa
Not just round‐off errors can go wrong
12
252
1
25
i
Floating point games
12
252
1
25
i
Encoding symbols
• Why?
• Computers cannot only work with numbers
• How do you encode any set of symbols?
• Need to make a link between binary and a symbol
• First define set
• Work out minimum number of bits
Why ASCII
• 8‐bits
• Came up with 100 characters. Leave some room for redundancy.
Why ASCII
• 8‐bits
• Came up with 100 characters. Leave some room for redundancy.
• Good thing: increase to approx. 200 (foreign characters)
• Problems?
Why ASCII
• 8‐bits
• Came up with 100 characters. Leave some room for redundancy.
• Good thing: increase to approx. 200 (foreign characters)
• Problems?
• What happens when add Chinese characters
• Refine set of symbols, number of bits
• Close to 36000
• Different encodings
• Unicode
ASCII vs Unicode
• Which is better?
Activity 1
• Benefits of RGB coding
• What is 1110 0010 1101 0100 0000 0101?
• Note: Order matter
Activity 2
Activity 2
• How many combinations can we encode?
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need:
• 360*100*100 = 3.6 million
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need:
• 360*100*100 = 3.6 million
• Could we just use 22 bits?
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need:
• 360*100*100 = 3.6 million
• Could we just use 22 bits?
• Hard look‐up table
• Fast encoding/decoding
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need: 360*100*100 = 3.6 million
• Could we just use 22 bits?
Activity 2
• How many combinations can we encode?
• 23 bits ‐> how many: 8million
• How many do we need: 360*100*100 = 3.6 million
• Could we just use 22 bits?
• Why would we not?
• Hard look‐up table
• Simple rules vs efficient rules
• Fast encoding/decoding
Encoding/decoding
• Advantage of RGB is that it can be easily used
• Digital designers make these decisions to maximise efficiency.
Memory
• Every computer has memory
• What operations does a memory perform
What does a memory conceptually look like
• Cells/number of cells
Memory notation
• What is a Byte?
General notation
• How many grams in a kilogram?
General notation
• How many grams in a kilogram?
• How many metres in a kilometre?
General notation
• How many grams in a kilogram?
• How many metres in a kilometre?
• How many bytes in a kilobyte?
Memory notation
• KB: 2^10 Bytes,
• MB: 2^20 Bytes,
• GB: 2^30 Bytes,
Memory visualisation
• How many cells in a 2GB memory, where each cell is 1 Byte.
Memory visualisation
• How many cells in a 2GB memory, where each cell is 1 Byte.
• 2^30 *2 = 2^31
Memory visualisation
• How many cells in a 2GB memory, where each cell is 2 Bytes.
Memory visualisation
• How many cells in a 2GB memory, where each cell is 2 Bytes.
• 2^30
Memory Read/Write
• Write 4 bits into 8‐bit cell. What happens?
• What if you don’t pad the 4‐bits.
• Overwrite 4, keep other
• Remaining 4 unchanged
• Doesn’t write at all
Address
• Every cell in memory must have an address
• What type of number/encoding for address?
• Base‐2 natural numbers
• How many bits for address?
• How many bytes does a memory with addresses 10 bits, 1 byte cells
have?
• 4GB memory, 2 byte cells. How many cells?
• 2^31
• 10 bit address, 16 bit cell. How many cells?
Address Questions
• How many bytes does a memory with addresses 10 bits, 1 byte cells
have?
Address Questions
• 4GB memory, 2 byte cells. How many cells?
• 2^31
• 10 bit address, 16 bit cell. How many cells?
Address Questions
• 10 bit address, 16 bit cell. How many cells?
Memory Read/Write
• If write cell it stays
• If read it, you get it back
Memory Read/Write
• If I write to a cell which already has a value, what happens to that
value
Memory Read/Write
• If I write to a cell which already has a value, what happens to that
value
• Write means overwrite
Memory Read/Write
• Write 4 bits into 8‐bit cell. What happens?
Activity 2
How does a memory work
• Address goes to all cells.
• Decoder chooses one cell
How do we store things in memory
• What if I want to store a big thing in memory
How do we store things in memory
• What if I want to store a big thing in memory
• Use cells in consecutive locations (bytes)
• Which order?
How do we store things in memory
• What if I want to store a big thing
• Use cells in consecutive locations (bytes)
• Which order?
• Can a big endian architecture share memory with a little endian
memory
Activity 3
How to store arrays
• What is an array?
How to store arrays
• Suppose it is an array of integers
• A[] = {10, 267, 39, 40}
• How many bits?
• Suppose you have a memory with 1 byte cells. What does it look like?
How to store arrays
• Memory has no notion of size
• It does not know how many bits are the integers
• It does not know they are storing integers
• How to know size of array if stored in memory?
How to store arrays
• Memory has no notion of size
• It does not know how many bits are the integers
• It does not know they are storing integers
• How to know size of array if stored in memory?
• Create a symbol to say end of array
• Typically used for strings (null character)
• Not great for integers (already have a 0)
• Store the size
• First put a number
• Do nothing…
• c
How to find elements in memory
• Address base
• + bytes encoding size
• +3* size of element
• E.g. look up A[5]
• What if look up A[7] in a array declared of size 6.
• First check it legal
• Error message arrayindexoutofbounds
• Does this happen at run‐time or compile time?
How to find elements in memory
• Address base
• + bytes encoding size
• +3* size of element
• E.g. look up A[5]
• What if look up A[7] in a array declared of size 6.
• First check it legal
• Error message arrayindexoutofbounds
• Does this happen at run‐time or compile time?
Activity 4
• Store in little endian
• Assume not storing size
Indirection
• Read data in address 10.
• Go to memory, read address 10. Done
• Is it here where I do this
• No, go somewhere else.
• Give a way to get there
• Treasure hunt
• Find an address of what you want
• Memory same.
• Use memory to store address
• How do you find something you want
• Read address
• Look up new address
• Can have multiple indirection
Why indirection?
• Multiple indirection. Why?